[프로그래밍 언어론] 구문 분석 방법

* 이 포스트는 이전에 공부하면서 보고서로 작성한 것을 그대로 포스팅 한 것입니다.
* 참조 사이트 : http://wiki.fracktal.kr/doku.php?id=수업:컴파일러:구문_분석

구문분석(syntax analysis)은 파싱(parsing)이라고도 하며,
방법으로는 크게 top-down과 bottom-up의 두 종류로 나누어 볼 수 있습니다.

1) bottom-up
  주어진 표현식으로부터 시작 기호로 축약(reduce)해 나가는 방법으로, 문법에 제약이 없기 때문에 일반적으로 이용합니다.

- 축약(reduce) : S ⇒ abc 이고, A → b의 생성 규칙이 존재할 때, 문장 형태 abc에서 b를 A로 대치하는 것을 축약이라고 합니다.

예) 다음의 문법이 존재할 때, 문자열 abbcde를 분석하여 축약하는 과정

<문법>
S → aAcBe    ────── ➀
A → Ab        ────── ➁
  ｜ b          ────── ➂
B → d         ────── ➃

<축약 과정>
        abbcde ⇒ aAbcde        ─ ➂에 의해 b를 A로 대치
                  ⇒ aAcde         ─ ➂에 의해 Ab를 A로 대치
                  ⇒ aAcBe         ─ ➃에 의해 d를 B로 대치
                  ⇒ S               ─ ➀에 의해 aAcBe를 S로 대치

2) top-down
  시작 기호로부터 생성 규칙(rule)을 좌측 유도해 나가는 방법으로, 좌측 유도 과정에서 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 참조한 문자열을 재검토하기 위해 입력을 보내고, 다른 생성 규칙을 적용하여 유도를 시도합니다. 이와 같은 재검토 과정을 역행(backtracking)이라 부르며, 한 번 입력된 표현식을 여러 번 반복하여 다루기 때문에 시간이 매우 많이 걸린다는 단점이 있습니다.

top-down 구문 분석에서 정의된 문법이 어떤 조건을 만족하면, 주어진 스트링을 분석할 수 있게 되는데 이를 LL조건이라 하며, 이 조건을 만족하는 문법을 LL문법이라 합니다.

LL은 입력 문자열을 왼쪽에서 오른쪽으로 읽어 가며(left to right scanning) 좌 파스(left parse)를 생성하기 때문에 붙여진 이름입니다.

- left-recursion : 어떤 표현에 대해 A ⇒ A 와 같은 유도 과정이 있는 경우, 구문 분석 시에 같은 생성 규칙이 순환적으로 재귀되어 결국 무한루프에 빠지게 됩니다. 이 경우, 문법 변환을 통해 left-recursion 을 없애주어야 합니다.

- left-factoring : RHS에 공통된 기호를 가진 두 개 이상의 다른 정의가 존재할 경우(예: A → ab | ac ), top-down 구문 분석에선 어떤 규칙을 적용할지 알 수 없게 되므로 비단말 기호를 도입하여 인수분해 하는데, 이를 left-factoring 이라 합니다.