파서 직접 만들어보기
파서(Parser): 토큰과 토큰 사이의 관계를 분석하고, 의미를 포함하여 구조적으로 재조합 합니다. 재조합된 결과를 Abstract Syntax Tree라고 합니다.
예시코드를 다시 살펴보겠습니다.
키: 170
몸무게: 60
비만도: 키 / 몸무게 / 몸무게
"비만도는 " + 비만도 보여주기
이를 파싱하면 다음과 같은 AST가 만들어집니다.
[
SetVariable {
name: '키',
value: NumberValue { value: 170 },
},
SetVariable {
name: '몸무게',
value: NumberValue { value: 60 },
},
SetVariable {
name: '비만도',
value: BinaryCalculation {
operator: DivisionOperator { },
left: BinaryCalculation {
operator: DivisionOperator { },
left: Variable { name: '키' },
right: Variable { name: '몸무게' },
},
right: Variable { name: '몸무게' },
},
},
Print {
value: BinaryCalculation {
operator: AdditionOperator { },
left: StringValue { value: '비만도는 ' },
right: Variable { name: '비만도' },
},
},
]
동작 과정
파서를 직접 만들어보기 전에, 파서가 어떻게 동작하는지 간단히 살펴보겠습니다. 파싱을 하는 방법은 여러가지가 있지만, 이 튜토리얼에서는 Shift-Reduce 방식을 사용합니다.
Shift-Reduce는 다음과 같은 두가지 동작을 반복하는 방식입니다.
Shift: 코드에서 토큰을 하나 가져와서 스택에 넣습니다
Reduce: 스택에 있는 토큰을 규칙에 따라 합칩니다
Reduce는 더 이상 할 수 없을 때까지 반복합니다
규칙의 길이가 스택보다 짧다면, 스택의 윗 부분에서부터 규칙의 길이만큼의 토큰에만 규칙을 적용합니다
Shift-Reduce 방식으로 파싱을 진행하는 과정을 살펴보겠습니다.
준비
[
StringValue { value: "BMI는" },
Operator { value: "+" },
Variable { value: "BMI" },
Token { value: "보여주기" }
]
규칙
Evaluable,Operator,Evaluable은BinaryCalculation으로 합친다.Evaluable,Token { value: "보여주기" }는Print로 합친다.Variable,Keyword { value: ":" },Evaluable은SetVariable으로 합친다.
과정
스택:
[ StringValue { value: "BMI는" } ]적용 가능한 규칙: 없음
Shift
스택:
[ StringValue { value: "BMI는" }, Operator { value: "+" } ]적용 가능한 규칙: 없음
Shift
스택:
[ StringValue { value: "BMI는" }, Operator { value: "+" }, Variable { value: "BMI" } ]적용 가능한 규칙: 1번 규칙 (
Evaluable,Operator,Evaluable은BinaryCalculation으로 합친다)Reduce
스택:
[ BinaryCalculation { ... } ]적용 가능한 규칙: 없음
Shift
스택:
[ BinaryCalculation { ... }, Token { value: "보여주기" } ]적용 가능한 규칙: 2번 규칙(
Evaluable,Token { value: "보여주기" }는Print로 합친다)Reduce
이제 남은 토큰이 없으므로 파싱이 완료되었습니다. 스택에는 최종 결과인 Print가 남아있습니다.
Print {
value: BinaryCalculation {
operator: AdditionOperator { },
left: StringValue { value: 'BMI는 ' },
right: Variable { name: 'BMI' },
},
}
파서를 구현하는 방법을 알아보았으니, 만들어보겠습니다!
이번에도 직접 작성해보고, 제 코드(lets-build-interpreter/lib/parser.js)와 비교해보시는걸 추천드립니다.
다음 글: yaksok-ts-runtime