Context-free Grammar, Parse Tree, Ambiguous Grammar

Context-free Grammar

Context-free Grammar는 Chomsky hierarchy에서 생성 규칙의 왼쪽은 논터미널 기호 하나로 이루어져있고 오른쪽 부분은 문자열인 것을 말한다.

---

Parse Tree

Leftmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 왼쪽에 있는 nonterminal symbol를 replacement하는 경우

Rightmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 오른쪽에 있는 nonterminal symbol를 계속해서 replacement하는 경우

Left parse : leftmost derivation에 의해서 사용된 생성 규칙 순서

Right parse : rightmost derivation에 의해서 사용된 생성 규칙 순서의 역순

Syntax analysis의 종류 :

하향식(top-down) 구문분석 : left parse를 생성

상향식(bottom-up) 구문분석 : right parse를 생성

right parse는 left parse의 반대이다.

일단 이 예제에서는 left_most derivation이든 right_most deriavation이든 pasre tree는 같다.

---

Ambiguous Grammar

하나의 문장이 서로다른 두 개 이상의 parse tree를 갖는 문법 G.

left_most derivation과 right_most derivation으로 만들어진 parse tree가 다르다.

lm pase tree로 계산하면 3+(4*5)=23이 나오지만 rm pase tree로 계산하면 (3+4)*5=35가 나오게 된다.

 

이런 Ambiguous Grammar를 처리하는 방법은 두가지가 있다.

1. Ambiguous grammar를 unambiguous grammar으로 변환시킨 후 scanner를 만듦.

2. Ambiguous grammar로 scanner를 만든 다음에 충돌이 발생한 scanner에서 충돌을 없애는 방법

---

Ambiguous -> Unambiguous Grammar

일부 arithmetic expression의 경우에는 연산자 operator의 우선순위 precedence와 결합법칙 associativity을 이용하여 unambiguous grammar로 변환 가능하다.

하지만 위 방식은 모든 ambiguous grammar를 처리할 수 있는 것은 아니다.

연산자가 같다면 unambiguous grammar문제를 해결 할 수 없다.

따라서 우리는 Associative Property를 사용할 것이다.

Operator간의 precedence가 같은 경우에 어느 것을 먼저 계산하는지에 대해서 Associative Law결합 법칙이 사용된다.

Left associative : 가장 왼쪽의 연산자부터 오른쪽 연산자로 계산

Right associative: 오른쪽의 연산자부터 왼쪽 연산자로 계산

일반적으로 Left associative가 사용된다.

if else 문을 pasing하는 경우 위에서 처럼 else문이 첫 번째 if에 상응하는 else인지 두 번째 if에 상응하는 else인지 알 수 없다.

위와 같은 문법을 사용하면 문제를 해결 할 수 있다.