[프로그래밍언어론] 7. Parsing Problem

파서의 목표는 소스코드를 받아서 파싱을 한 뒤, Parse Tree 를 만드는 것이다.

만약 파싱하다가 실패했다면 소스코드에서 문법에 맞지 않는 부분이 있었다는 뜻이므로,

파서는 syntax error 가 발생했다는 걸 알려줘야 한다.

 

잘 동작하는 파서는 파싱할 때 토큰 1개를 더 앞서 볼 수 있다. (look ahead, LA)

그래야 알맞는 BNF 문법을 체크할 수 있다.

 

파서에는 2가지 카테고리가 있다.

첫번째는 탑-다운 / 두번째는 바텀-업 이다.

---

탑 - 다운 파서

탑-다운 파서는 root 부터 시작해서 아래로 내려가면서 파스 트리를 만든다.

탑-다운 파서는 왼쪽에서부터 파고들어 본다. (즉 pre-order 순으로 파싱트리를 만든다.)

xAα 라는 sentential form 이 주어졌을 때, 파서는 적합한 A 규칙을 골라 다음 sentential form 을 얻어야 한다.

저 문법은 왼쪽에 있는 x 라는 논터미널은 A라는 규칙에 의해 α로 extend 된다는 의미이다.

탑다운 파서는 왼쪽부터 시작해서 x를 내게 한 다음, A가 만들어지는지 확인하는 과정을 반복하며 파싱한다.

(구체적인 내용은 컴파일러 과목에서 다룬다.)

 

탑다운 파싱 알고리즘은 대표적으로 2가지가 있다.

- Recursive descent

- LL Parser

---

 

바텀 - 업 파서

바텁-업 파서는 leaf 노드인 터미널부터 시작해서 거꾸로 올라오며 파싱트리를 만든다.

바텀-업 파서도 왼쪽에서부터 올라오며 만든다.

즉, 오른쪽의 sentential form 인 α가 주어졌을 때, 어떤 규칙을 적용해야 α가 오른쪽에 올 수 있을지 찾는 과정을 거친다.

 

바텀업 파싱 알고리즘은 LR Parser 계열을 주로 사용한다.

---

파싱의 시간복잡도

모호하지 않은 문법에 대해 파서는 보통 O(n^3) 의 시간복잡도를 갖는다.

(n = input length)

그래서 컴파일러는 그래머 전체를 갖고 파싱하는게 아니라, 일부 그래머를 가지고 파싱하도록 해서 O(n) 의 시간복잡도로 최적화 한다.