이번 글에서는 ambuguity grammars (모호한 문법)에 대해서 알아볼 것이다. 지난 글의 말미에서 설명했듯이 syntax가 잘못된 경우에는 parse tree가 두 개 이상 만들어질 수 있다.
아래 그림은 잘못 작성된 BNF 이다.
const - const / const 에 대해서 두 가지 parse tree가 만들어 졌다. 연산자의 우선 순위에 의하여 오른쪽 parse tree가 맞지만, 잘못된 BNF로 인해 (const - const) / const 라는 sentence로도 해석될 수 있는 것이다.
따라서 우리는 이런 '모호함'을 제거해서 하나의 parse tree만 만들어질 수 있도록 해야한다. 모호함을 제거하는 방법은 간단하다.
우선 순위가 낮은 연산자부터 정의한 뒤, 우선 순위가 높은 연산자로 전개될 수 있도록 하는 것이다. 즉, 우선 순위가 높은 연산자의 depth를 더 깊게 만들어, 먼저 계산될 수 있도록 하는 것이다.
위의 그림과 같이 BNF를 정의하면, const - (const / const)라는 하나의 sentence만 나올 수 있다.
아래는 조금 더 복잡한 예제이다.
BNF 식만 봐도 이 문법은 모호한 것을 알 수 있다. 우선 순위가 낮은 연산자부터 정의해서 우선 순위가 높은 연산자로 전개한다는 것을 포인트로 스스로의 힘으로 먼저 풀어보길 바란다.
잘 모르겠다면 아래에 풀이를 같이 올릴테니 참고하면 될 것 같다.
