목차
📁 모호성(Ambiguity)
문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖는다면 문법 G는 모호하다고 말한다.
즉, 좌측유도와 우측유도의 유도트리가 같으려면 문법이 모호하지 않은 문법이어야 한다.
예를 들어 "if b then if b then a else a"라는 문장을 아래 문법을 이용하여 유도해보자.
위 문장은 여러 유도과정이 나올 수 있고, 그에 따라 여러가지의 유도 트리가 나올 수 있다.
위 두 유도트리는 다르게 생겼지만, 둘 다 "if b then if b then a else a"라는 문장을 나타내고 있다.
또한 "a + a * a" 입력을 아래 문법을 이용하여 유도해보자.
이 예시 또한 두 개의 유도트리가 나올 수 있다.
이처럼 하나의 문장을 유도하는 과정이 여럿 나올 수 있는 문법은 "모호한 문법"이라고 말한다.
📁 모호성을 해결하는 방법
모호성은 같은 뜻을 가지는 동일한 문법을 만드는 방법으로 해결할 수 있다.
예를 들어 위 문법과 아래 문법은 다르게 생겼지만 같은 뜻을 가지는 문법이다.
1. 연산자 우선순위 도입
같은 뜻을 가지는 동일한 문법을 만들기 위해, 먼저 연산자 우선순위를 도입해볼 수 있다.
1) 연산자마다 새로운 Nonterminal을 도입한다.
2) recursion은 left나 right 둘 중 하나만 둔다.
3) 시작심벌과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 둔다.
예를 들어, 아래 문법에 연산자 우선순위를 도입해보자.
더하기 연산자에는 T, 곱하기 연산자에는 F라는 새 Nonterminal을 도입해보자.
일반적으로 연산자 우선순위는 괄호 -> 곱하기 -> 더하기 순이므로 더하기, 곱하기, 괄호 순으로 시작심벌과 가깝게 두면 다음과 같은 동일한 문법을 만들 수 있다.
본래 문법과 새 문법 모두 recursive하지만, E -> E+E와 같이 좌측과 우측 모두 재귀가 가능했던 본래 문법과 달리 새 문법은 E -> E+T, T -> T* F 처럼 좌측에서만 재귀가 가능하다.
새 문법으로 좌측 유도와 우측 유도를 해보면, 모호성이 사라져 트리 모양이 같음을 확인 할 수 있다.
2. 결합 법칙 도입
같은 뜻을 가지는 동일한 문법을 만들기 위해 결합법칙을 도입해볼 수 있다.
모든 연산자는 좌측 혹은 우측 결합을 하게 하거나, 결합이 성립되지 않도록 하는 방법이다.
위 a < b < c가 불가능한 이유는, 예를 들어 좌측 결합 방법으로 진행하면 a < b를 먼저 계산하여 boolean 값이 나오게 된다. 이후 boolean값과 c를 비교해야하는데 이는 불가능하므로 오류가 생긴다.
문법에서 recursion을 좌측 혹은 우측에 배치함으로써 결합법칙을 강제할 수 있다.
