[프로그래밍 언어론] 구문법 - 파스 트리와 모호성

개요

 지난 프로그래밍 언어론 구문법 포스팅에서 다루지 않았던 것이 있다. 바로 파스 트리(Parse Tree)이며, 이것은 Derivation Tree 혹은 Syntax Tree로도 불린다.

 

Parse Tree(Derivation Tree)

수식 문법에서 3 + 4 * 5 유도하기

E -> E * E | E + E | (E) | N

N -> ND | D

D -> 0 | 1 | 2 | ... | 9

 

E => E + E => N + E => D + E => 3 + E => 3 + E * E => 3 + N * E => 3 + D * E => 3 + 4 * E => 3 + 4 * N => 3 + 4 * D => 3 + 4 * 5

위 수식 유도를 살펴보자. 파스 트리란 별 것 없이 위 유도 과정을 한 눈에 알아보기 쉽게 트리 형태로 그린 것이다. 

 위 수식 유도 과정을 간단하게 파스 트리로 그리면 위와 같다. 이렇게 유도 과정을 트리 형태로 그린 것이 파스 트리, 유도 트리이다. 

모호성

자, 위 3 + 4 * 5 수식 유도 과정을 유심히 살펴보자. 사실 위에서 살펴본 파스 트리가 아닌 아래와 같은 다른 파스 트리 형태로도 3 + 4 * 5 수식을 유도할 수 있다.

 이렇게 어떤 문자열에 대해 2개 이상의 좌측 유도를 가지는 문법을 모호한 문법이라고 한다. 즉, 어떤 스트링을 유도하는데 파스 트리를 2개 이상을 만들 수 있다면 해당 문법은 모호한 문법인 것이다. 이 모호성을 없애기 위한 두 방법을 알아보자.

 

1. 모호한 문법을 같은 언어를 정의하는 모호성 없는 문법으로 재작성

2. 모호성이 없도록 일부 수정

 

그래서 이런 모호성을 왜 없애야 할까? 문법에 모호성이 있다면 어떤 문자열에 대한 구문 구조를 2개 이상으로 해석할 수 있기 때문에 반드시 문법이 모호성을 가진다면 모호성을 없애주어야만 한다.

 

 위 수식 문법을 다음과 같이 수정한다면, 모호성을 없앨 수 있다. 모호성을 없앤 문법을 사용한 유도는 그리 어렵지 않으니직접 해보자. 

E -> E + T | T

T -> T * F | F

F -> N | (E)

 

모호성과 관련된 또 다른 예시를 살펴보자. 우리에게 익숙한 if - else 구문을 유도할 것이다. 다음 문법을 통해 문자열 'if e1 then if e2 then s1 else s2'를 유도해 보자.

 

S -> if E then S | if E then S else S

 위와 같이 2개의 파스 트리를 작성할 수 있으므로 이 문법도 모호성을 가진 문법이므로, 문법을 적절히 수정하여 모호성을 없애야 한다. 아래와 같이 이 문법을 수정해 보자.

 

S -> if E then S end | if E then S else S

이렇게 문법을 수정한다면, 위 사진의 첫 번째 파스 트리는 if e1 then if e2 then s1 else s2 end로 유도된다.

두 번째 파스 트리는 if e1 then if e2 then s1 end else e2와 같이 유도되어 모호성이 사라질 것이다.