구문 분석 및 파싱

구문 분석의 이유

1. 소스 코드가 구문(문법)적으로 올바른지 판단하기 위함

소스코드의 구문이 올바르지 못하다면 이를 복구합니다.

복구한다는 것은 구문 분석기가 정상적인 상태로 돌아가 계속 검사해나간다는 것을 말합니다.

복구가 중요한 이유는 오류가 하나 발견되더라도 이후 구문에 새로운 오류가 있을 수 있기때문에 이들 또한 한 번에 검사하기 위함입니다.

 

2. 구문적으로 올바른 코드의 완전한 파스 트리를 생성하거나 파스 트리 구조를 추적

파스트리는 이후 언어 번역을 위한 기반이 됩니다.

파스트리 생성 방식

하향식(Top-down) 파서

루트노드로부터 시작하여 하위 노드를 만들어나간다고 하여 하향식 파서입니다.

전위 순서(Preorder) 로 파스 트리를 생성하거나 추적하는 방식입니다.

전위 순서라고 함은 루트 노드로부터 트리를 추적할 때 왼쪽(전위) 자식이 모두 파싱이 된 상태에서 본인 노드를 파싱하고, 이후 오른쪽(후위) 자식을 파싱합니다. 이처럼 왼쪽 자식을 본인보다 먼저 탐색한다 하여 전위 순서라고 합니다.

 

재귀-하강(Recursive-descent) 파서, LL 파서 등이 있습니다.

상향식(Bottom-up) 파서

하향식과는 달리 잎(Leaf) 노드로부터 시작하여 루트노드 방향으로 파스 트리를 만들어나갑니다.

Rightmost derivation 의 역순으로 트리를 만들어나간다고 생각하시면 편합니다.

S -> aAc
A -> aA | b

이런 규칙이 있다고 하면 aabc 를 만들면 다음과 같이 만들 수 있습니다.

S -> aAc -> aaAc -> aabc

다음 포스팅에서는 재귀-하강 파싱에 대해 알아볼게요