구문 분석

 컴파일러의 전반부 구조를 3단계로 나눈다면,

1. 어휘(lexical) 분석

2. 구문(syntax) 분석

3. 의미(Semantic) 분석

으로 구분할 수 있다고 하였다.

 

오늘은 두 번째 단계인 구문 분석에 대해 알아보자.

어휘분석 단계에서는 정규표현식으로 기술하고, 상태전이도를 따라가며 판별하여 토큰을 구분하였다.

 

구문분석 단계에서는, 이 토큰들을 파스트리로 나타내고자 하는 것이 목표이다.

 

---

CFG(Context Free Grammar)

 

CFG는 언어의 문법을 정의하는 일반적인 방법으로, 표현된 문법으로 인식기를 손쉽게 구현할 수 있게된다.

CFG의 문법은 아래와 같이 네 종류의 집합으로 표현할 수 있다.

 

G(문법) = (N,T,P,S)

 

1. N  : non terminal 심벌 집합

중간과정 심벌이다.

• A, B, C와 같은 알파벳 시작 부분의 대문자로 나타내게 됨
• S는 보통 시작 심벌(start symbol)을 나타낸다.
• <stmt>와 같이 < >로 묶어서 나타내기도 함

 

2. T : terminal 심벌 집합

토큰과 비슷한 느낌이라 생각하면 되겠다.

• a, b, c와 같은 알파벳 시작 부분의 소문자와 숫자 0,1,2,…,9
• +, -와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자
• ‘if’ 또는 “then”과 같이 따옴표 사이에 표기된 문법 심벌

3. P : 생성 규칙 집합

• 예)

S → T + T

T → ‘0’

T → ‘1’

T → ‘2’

 

• A→a1 , A→a2 , …, A→ak와 같이 생성 규칙의 왼쪽이 모두 A인 경우에, A→a1 |a2 |…|ak로 간단히 표기

예) T → ‘0’| ‘1’| ‘2’

 

4. S : 시작 심벌

만약 아무런 언급이 없으면 첫번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌

---

그렇다면 input token stream이 주어졌을 때, 이 문장이 문법에 맞는지 어떻게 판단 할 수 있을까

유도

문법에서 언어를 생성하는 것이다.

생성 규칙을 연속적으로 적용하여 Non Terminal을 확장함으로써 얻을 수 있다.

 

예를 들어서,

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

라는 문법이 있다고 할 때,

(a+a) 라는 언어를 유도해내보자.

 E -> (E) -> (E+E) -> (a+E) -> (a+a)

위와 같은 방식으로 유도해낼 수 있고, 이를 트리 형식으로 나타내면 유도트리라고 부른다.

 

유도트리

 

유도를 할 때, 오른쪽 심벌을 먼저 대치할지, 왼쪽 심벌을 먼저 대치할지에 따라

좌측유도와 우측유도로 구분할 수 있다.

 

만약 문법G에 의해 생성되는 어떤 문장이, 두 개 이상의 유도트리를 갖는다면(좌측유도트리와 우측유도트리가 다르다면),

문법G는 모호한 문법이다.

 

 

 

위와 같은 문법에서, a + a * a 를 유도해볼 때,

좌측 유도와 우측 유도를 각각 해보면,

위와 같이 서로 다른 트리가 나온다.

직접 한번 해보아도 좋다.

즉, 위 문법은 모호하다고 할 수 있는 것이다.

 

그렇다면, 이런 모호성이 있는 문법을 어떻게 하면 해결할 수 있을까?

 

모호성 해결 1 - 연산자 우선순위 도입

 

연산자 우선순위를 도입한 동일한 문법을 만듬으로써 모호성을 해결 할 수 있다.

 

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

Recursion을 left나 right 둘 중 하나만 두고,

시작 심벌과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 두면 된다.

 

아래 예시를 보며 이해해보자.

위 문법은 아까 보았던, 서로 다른 유도트리가 생성되는 모호한 문법이다.

 

이 문법을,

이러한 형식으로 연산자 우선순위가 낮은 순서대로, 시작 심벌과 가까운 쪽에 놓는다면 모호성을 해결 할 수 있다.