파싱

1. 개요

2. 과정

• 어휘 분석(Lexing) 과정에서는 코드 문자열은 개별 토큰으로 분리되며, 각 토큰은 코드의 기본적인 의미 단위로써 자료형, 식별자, 리터럴, 연산자 및 기타 구문 기호를 나타낸다. 이러한 과정을 토큰화(tokenize)라고 한다.
• 구문 분석(parsing) 과정에서는 이러한 토큰들이 파스 트리(parse tree)로 재구성되어 소스 코드의 구조적 계층을 표현한다. 파스 트리의 각 노드는 코드의 구문적 관계를 나타낸다. 이러한 결과로 나온 파스 트리에서 불필요한 요소[1]를 제외하고 인터프리터를 위한 직접 실행할 요소나, 컴파일을 위해 필요한 구조만 가져와 AST(추상 구문 트리)를 형성한다.

2.1. 어휘 분석(lexing)

#!syntax cpp
int x = 2 + 3;
int y = x - 5;

2.2. 구문 분석(parsing)

2.2.1. 예시

#!syntax java
<expr> ::= <term> | <expr> '+' <term> // 시작 non-terminal
<term> ::= <factor> | <term> '*' <factor>
<factor> ::= <number>
<number> ::= <digit> | <digit> <number>
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

2.3. 파스 트리(parse tree)

3. 모호성(ambiguity)

#!syntax java
<expr> ::= <expr> '+' <expr> | <expr> '-' <expr> | <expr> '**' <expr> | <number> // 시작 non-terminal
<number> ::= <digit> | <digit> <number> // <number>는 예시 부분과 동일

좌측 유도	파스 트리
[math( \begin{array}{c|l} \textbf{expr} & \Rightarrow_D \textbf{expr} - \textbf{expr} \\ & \Rightarrow_D \textbf{number} - \textbf{expr} \\ & \Rightarrow_D3 - \textbf{expr} \\ & \Rightarrow_D 3 - \textbf{expr + expr}\\ & \Rightarrow_D 3 - \textbf{number} + \textbf{expr}\\ & \Rightarrow_D 3 - 2+\textbf{expr} \\ & \Rightarrow_D 3 - 2+\textbf{number} \\ & \Rightarrow_D 3 - 2+1 \\ \end{array})]

우측 유도

파스 트리

[math( \begin{array}{c|l} \textbf{expr} & \Rightarrow_D \textbf{expr} + \textbf{expr} \\ & \Rightarrow_D \textbf{expr} + \textbf{number} \\ & \Rightarrow_D \textbf{expr} + 1 \\ & \Rightarrow_D \textbf{expr} - \textbf{expr} + 1 \\ & \Rightarrow_D \textbf{expr} - \textbf{number} + 1 \\ & \Rightarrow_D \textbf{expr} - 2 + 1 \\ & \Rightarrow_D \textbf{number} - 2 + 1 \\ & \Rightarrow_D 3 - 2 + 1 \\ \end{array} )]

3.1. 모호성 해결 방법

• 문법 수정을 위해서 각 연산자마다 새로운 non-terminal을 만들고 시작 non-terminal부터 가장 낮은 우선순위를 가진 연산자를 적용한다.
• 결합 법칙 상으로는 좌측 결합이면 left recursion, 우측 결합이 되면 right recursion을 적용한다. 예를 들어 모호성 문단의 BNF는 +, - 연산자가 동일한 우선순위를 가지며 좌측 결합이고, **를 Python의 제곱 연산자라고 하면, +, -보다 높은 우선순위를 가지며 우측결합이다. 이를 기반으로 BNF를 다음과 같이 수정하면, 모호성이 해결된다.
  {{{#!syntax java
  <expr> ::= <expr> '+' <term> | <expr> '-' <term> | <term> // +, -은 좌측 결합이므로 left recursion 적용

4. 파싱 방식

Top-down

Bottom-up

4.1. 하향식 파서(Top-down Parser)

• Recursive Descent Parser
• Predictive Parser
• LL(1)
• LL(k)

4.2. 상향식 파서(Bottom-up Parser)

• Shift-Reduce Parser
• LR(0)
• SLR(1), Simple LR(1)
• CLR(1), Canonical LR(1)
• LALR(1), LookAhead LR(1)

5. 관련 문서

• 배커스-나우르 표기법
• 오토마타
• 유한 상태 기계
• 컴파일러
• 푸시다운 오토마타
• 프로그래밍 언어론