[컴개/CI] 모호성(Ambiguity)

모호성(Ambiguity)

모호성이란 문법 G에 의해 생성되는 어떤 문장이 두 개 이상의

유도트리를 갖는 경우 문법 G는 모호하다고 한다.

아래 예시는 입력으로 a + a * a가 들어 온 경우이다.

위의 두 개의 예시에서 모두 두 개 이상의 유도트리가 나왔으므로,

해당 문법들은 모호하다고 할 수 있다.

그렇다면 이러한 모호성은 어떻게 해결할 수 있을까?

 

모호성의 해결

같은 뜻을 가지는, 모호하지 않은 문법을 만들어보자.

이때, 같은 뜻을 가지는 여러 방법의 문법이 존재하는데,

S -> a 의 문법을 S -> A, A -> a로 바꿀 수 있다.

즉, 모호성을 해결하는 방법은 같은 언어를 생성하는 다른 문법을 사용하는 것이다.

 

모호성은 크게 두 가지 방법으로 해결할 수 있다.

1. 연산자 우선 순위 도입

2. 결합 법칙 도입

이제 각각의 방법에 대해 자세히 알아보도록 하자.

 

연산자 우선 순위 도입

연산자 우선 순위를 도입하여 동일한 문법을 만드는 방법이다.

연산자마다 새로운 Non-terminal을 도입하되,

recursion을 왼쪽이나 오른쪽 하나만 두고,

start symbol과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 둔다.

 

방금 예시로 들었던 E -> E+E | E*E | (E) | a 문법을 모호하지 않게 바꾸면 아래와 같다.

우선 순위가 높은 ()를 E와 가장 멀게 두고,

우선 순위가 낮은 +를 시작 심벌인 E에 두었다.

그렇다면 모호하지 않은 문법으로 좌측유도와 우측유도를 모두 하여 트리 모양이 같은지 비교해보자.

위 사진과 같이 두 트리의 모양이 동일함을 확인할 수 있다.

 

결합 법칙 도입

연산자 우선 순위를 도입하여 동일한 문법을 만들 수 있다.

모든 연산자는 좌측 또는 우측 결합이거나, 결합이 성립되지 않는다.

• Left: a + b + c = (a + b) + c
• Right: a ^ b ^ c = a ^ (b ^ c)
• None: a < b < c, 결합 불가 

Recursion을 잘 배치함으로써 문법에서 결합 법칙을 강제할 수 있다.

• Left Recursion: A -> A + a | a
• Right Recursion: A -> a ^ A | a