[프로그래밍 언어론] 구문분석의 모호성

* 이 포스트는 이전에 공부하면서 보고서로 작성한 것을 그대로 포스팅 한 것입니다.
* 참조교재 : 프로그래밍 언어론 (한빛미디어)

구문분석의 유도 과정에는 좌우선 유도(leftmost derivation)와 우우선 유도(rightmost derivation)가 있습니다.

주어진 문법을 유도 과정에 따라 파스트리로 작성하다 보면 같은 문장임에도 불구하고 두 개 이상의 서로 다른 파스 트리가 작성되는 경우가 있는데, 이러한 문법을 가리켜 모호하다(ambiguous)고 부릅니다.

예) 다른 파스트리를 만들어내는 문법
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> ＋ <expr>
           | <expr> － <expr>
           | <expr> × <expr>
           | (<expr>)
           | <number>
<number> → <number><digit>
               | <digit>
<digit> → 0 | 1 | 2 | … | 9

이 문법에 따라 A = 3 + 5 * 2 에 대한 파스 트리를 작성하게 될 경우,
연산자의 우선순위를 정하지 않았으므로 유도 방식에 따라 서로 다른 파스 트리가 작성되게 됩니다.

A = 3 - 5 - 2 에 대한 파스트리를 작성하게 될 경우에도 마찬가지로 다른 파스트리가 작성되게 되죠.

이렇게 모호성을 갖는 문법을 유용하게 하려면 문법을 모호함이 없도록 개정하거나, 어떤 구조가 의미 있는지를 결정 할 수 있도록 모호성 제거규칙(disambiguating rule)을 함께 첨부해 주어야 합니다.

예) 모호함이 없도록 개정한 문법
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> ＋ <term>
<expr> ｜ <expr> － <term>
          ｜ <term>
<term> → <term> × <factor>
          ｜ <factor>
<factor> → (<expr>)
           ｜ <number>
<number> → <number><digit>
              ｜ <digit>
<digit> → 0 | 1 | 2 | … | 9

유도 방식에 따라 다른 파스트리를 만들어 내었던 문법과는 다르게 어떤 과정으로 유도를 하든 같은 결과가 나타나게 됩니다.