모호한 문법

하나의 문장이 서로 다른 두 개 이상의 파스 트리를 가진다

-> 문법 G는 모호하다(ambiguous)

 

모호한 문법을 가지고 처리하기 위한 방법

1. 모호한 문법을 모호하지 않은 문법으로 변환시킨 후 모호하지 않은 문법을 가지고 구문 분석기를 만들어 처리하는 방법

2. 모호한 문법을 가지고 구문 분석기를 만든 다음에 충돌이 발생한 구문 분석기에서 충돌을 없애는 방법

 

모호한 문법을 모호하지 않은 동등한 문법으로 변환

- 모든 모호한 문법이 동등한 모호하지 않은 문법으로 변환되진 않음

- 산술식의 경우 연산자의 우선 순위(precedence)와 결합 법칙(associativity)을 이용하여 모호하지 않은 문법으로 변환

 

연산자의 우선순위 만으로 해결되지 않을 수 있음

이때는 결합 법칙을 사용

- 연산잔의 우선 순위가 같을 때 가장 왼쪽? 오른쪽? 부터 계산할 것인지에 대한 법칙

- 가장 왼쪽의 연산자로부터 계산하는 것을 좌측 결합(left assoicative), 오른쪽부터를 우측 결합(right associative)

- 대부분 프로그래밍 언어는 좌측 결합 방식을 취함

 

P: E -> E | E - E | E * E | E / E | (E) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

이런 모호한 문법은

 

P:

E -> E + T | E - T | T

T -> T * F | T / F | F

F -> (E) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

이런식으로 바뀔 수 있음

연산자 우선순위별로 계층을 도입하고,

연산자 우선 순위가 낮은게 항상 좌측에 등장하도록 하여 좌측 결합을 함

 

그래서 어떻게 모호한 문법을 모호하지 않은 문법으로 변환하느냐

1. 기초적인 피연산자를 생성 규칙 중 가장 아래에

2. 그 위로 연산자 순위가 높은 것부터 취함

- 연산자 우선순위가 높은 걸 좌측 결합 기준 좌측에 놓음

3. 같은 방식으로..

 

* 연산자마다 결합 법칙이 다를 수 있음

 

 

현수 else (dangling else)

- 중첩된 if 문에서 else가 어떤 if문에 걸리느냐

 

stat -> if expr then stat

           | if expr then stat else stat

           | other

일 때,

if E1 then if E2 then S1 else S2는 모호함

 

if E1 then ( if E2 then S1 else S2 ) ?

if E1 then ( if E2 then S1 ) else S2 ?

이래서 모호함

 

현수 else도 모호한 문법인데, 일반적인 프로그래밍 언어에선 else를 그 앞에 있는 가장 가까운 if와 연결

stat -> matched

           | unmatched

matched -> if expr then matched else matched

                   | other

unmatched -> if expr then

                       | i f expr then matched else unmatched 

 

matched : 정상적으로 if, else가 매핑된 상태

unmatched : else를 아직 기다리는 if문이 있는 상태

matched 는 정확히 완성된 if else만 포함

unmatched 는 else가 없음. 없는 채로 끝나던가 다시 unmatched 나오던가..