[Compiler] Context Free Grammar (CFG)

지난 포스트를 통해서 Regular Expression을 NFA->DFA를 거쳐는 일종의 Lexical Analysis을 정리했다. 그러면 이제 수행해야 될 것이 Syntax Analysis가 될 것이다. 

 그런데 한가지 짚고 넘어가야 될 부분이 있다. 과연 지금까지 다룬 방법으로  사용자가 넣는 모든 입력들을 이 Syntax Analysis를 처리할 수 있냐는 것이다. 예를 들어서 brace {()} 가 있는 구문을 보자 이걸 Regular Expression으로 어떻게 표현할 수 있을까? 맨처음 RE로 표현할 수 있는 기본적인 수칙에 의하면 분명 (*)* 로 표현해야 될 것이다. 그다음 작업이 FA로 바꾸는 작업인데 State Transition Diagram으로 표현할 수 있겠는가? 만약 brace 안에 brace가 있는 형태, 즉 nested expression은 어떻게 표현할 수 있을까 에 대한 궁금증도 생길 듯 하다.

 우선 Regular Expression으로 특정 요소의 갯수를 파악하는 요소가 없다. 즉 위의 Regular Expression으로 뽑을 수 있는 경우의 수는 (() , (((((((((((((), ())))))))))), ... 등이 있을텐데 여러분들도 기본적으로 알다시피 brace가 정의되기 위해서는 open brace와 close brace의 갯수가 같아야 한다. 그래서 결론적으로 Regular Expression으로 표현할 수 있는 언어인 Regular Language는 위와 같은 nesting model을 표현하는게 어렵다고 할 수 있다. 결국 사람이 만들어내는 언어중에는 정규표현식으로 표현할 수 있는 구문도 나올 수 있고, 이를 찾기 위해서는 다른 방식의 grammar를  찾아야 한다.

 그럼 답을 찾아야 하는데 사실 Noam Chomsky 라는 사람이 이른바 Chomsky Hierarchy라는 것을 정의해놨다. Chomsky는  "Three models for the description of language"  라는 책을 통해서 세상의 언어를 표현하는 grammar를 네단계로 나눠서 설명했다.

여기서 맨 아래가 앞에 나왔던 Regular Expression이라는 것이고, 이것을 포괄하는 grammar가 바로 다음 단계인 Context-Free Grammar가 되겠다. 사실 이 grammar를 설명하려면 Terminal Symbol과 Nonterminal Symbol에 대한 설명이 필요할 것 같다. 

 Wiki에도 단일 페이지로 나와 있다시피 terminal Symbol이냐 Nonterminal Symbol이냐를 따지는 것은 사전에 정의된 grammar를 통해서 구분할 수 있다. 위키에 나온 예를 그대로 빌려오자면 다음과 같은 rule이 2개 정의된 grammar가 있다.

1. x can become ax

2. x can become xa

여기서 x의 경우는 사용자가 원하는대로 삽입을 할 수 있고, a는 x가 정의되어야만 어느쪽에 삽입하는지를 결정할 수 있다. 다시 말하면 x는 딱히 rule 1이나 rule 2에 상관없이 위치를 정할 수 있고, 바꿀 수 있는가하면 a는 x의 위치에 따라서 종속적으로 grammar에 소속된다. 바로 a와 같이 생성된 grammar에 종속되는 symbol을 Terminal이라고 하고, x와 같이 얼마든지 rule을 선택하고 위치를 바꿀 수 있는 요소가 Nonterminal Symbol이 되겠다. 이런 Compiler에서는 Terminal Symbol을 다른말로 Token이라고 한다. 그래서 어떤 input을 넣으면 그에 대한 Token을 찾아주는 프로세스 자체가 지금 하는 Syntax Analysis를 표현하는 것이라고 할 수 있다. 

 Context-Free Grammar(CFG)는 이런 Terminal과 Nonterminal의 상관관계를 표현한 문법 중 하나이다. 여기서 Context Free라는 것은 어떤 Nonterminal이 들어와도 해당 symbol에 대한 production Rule이 성립한다는 뜻에 나온 것이다. 그래서 앞에서 나온 nested expression과 같은 경우도 Regular Expression에서는 단순히 정해진 Expression 내에서만 표현하던 것과는 다르게 CFG는 Terminal과 Nonterminal의 관계로써 표현하는 방식이기 때문에 조금더 포괄적이라고 할 수 있다. 

 CFG에도 원론적인 rule이 존재하며 다음 요소들로 구성되어 있다.

Context Free Grammar G = < Terminal , Nonterminal , Production , Start Symbol >

여기서 원론적인 rule이란 Start Symbol은 Nonterminal로 시작해야 되고, 이 Nonterminal로부터 파생될 수 있는 Symbol은 Terminal과 Nonterminal, 그리고 Empty String등이 있다는 것이다. 이게 Production rule인 것이고 수식으로 표현하면 다음과 같다.

예를 한번 들어보자 다음과 같은 구문이 있다.

이걸  CFG에 맞춰서 분류해보면 다음과 같다. 우선 Nonterminal이 Start Symbol이므로 

Nonterminal N = {S}

가 될 것이고, 그러면 우측에 나와있는 요소인 (S)는 (,S,) 로 나눠질 수 있다. 이중 S가 Nonterminal이므로 그에 따라서 결정되는 ( , ) 는 Terminal이 될 것이다.

Terminal T = { ( , ) }

S는 최종적으로 ε  으로 가기 때문에 더이상 Nonterminal을 찾아낼 여지가 없다.

 Production을 구하자면 

Production P = { S->(S) , S-> ε } 

이 되겠다.

결론적으로 위의 예제를 통해서 우리가 생각해볼 수 있는 CFG의 과정은 지속적으로 Nonterminal Symbol이 있는지를 가린 후에 Nonterminal이 있으면 앞에서 말한 Rule에 따라서 왼쪽에 두고 계속 같은 과정을 수행하는 것이다. 그래서 nonTerminal이 없을 때까지 수행하다보면 우리가 Regular Expression으로 찾을 수 없었던, 앞에서 언급한 nested Model 같은 것도 도출할 수 있을 것이다. 그걸 한줄로 표현한 것이 다음 그림이다.

잘보면 Nonterminal로부터 Terminal로 Replace되는 과정이라는 것을 알 수 있고, 바로 이 Replace를 하는데 있어서 앞에서 찾았던 Production이 이용된다. 그럼 최종적으로 S->((())) 라는 것까지 뽑아낼 수 있겠다. 그럼 다른 예제를 하나더 본다.

그런데 막상 위와 같이 나열하면 어떤게 nonterminal이고 어떤게 terminal인지를 구분하기가 난감하다. 그래서 경우에 따라서는 요소에 따른 분류를 쉽게 하기 위해서 Notational Convention을 제공하기도 한다. 현재 예제에 적용하기 위한 notational Convention은 아래의 것만 있으면 될 듯 하다.

자 그럼 위의 convention을 적용해서 조금 축약해보면 다음과 같은 결과를 얻을 수 있다.

E -> E+T | E-T |  T

T -> T*F | T / F | F

F -> (E) | id

 지금 이 과정을 수행하는 이유는 사용자가 준 입력이 결국은 어떤 속성을 가지는 것인지를 분석하는 것이다. 이말을 앞에서 나왔던 이야기을 이용해서 풀어보자면 결국 nonterminal의 단어를 terminal 단어로 인식하게끔 하는 과정인 것이다.예를 들어 사용자가 apple이라는 단어를 집어넣었을 때 이걸 어떻게 분석할 건지에 대한 기준을 둔 것이다. 보는 관점에 따라서는 apple을 명사라고 생각할 수 있는 것이고, 다른 관점에서 보면 과일 중 하나라고도 볼수 있다. 또는 영어단어라고도 생각할 수 있는 것이다. 어떤 기준에 맞추든 다 맞는 말이며, 궁극적으로는 명사라고 정의되어 있는 것, 과일이라고 정의하는 것, 영어단어라고 정의하는 부분에 부합하는 것인지를 판단하는 과정이 지금 과정일 것이다. 위에서 잠깐 언급했던 Notational Convention이 명사, 과일, 영어단어를 언급한 기준이 될 것이다. 

 그런데 잘 보면 알다시피 원래 CFG의 기본적인 rule은 좌측항에 항상 Nonterminal이 들어와야 한다는 것인데, 우측항이 Terminal과 Nonterminal의 결합 형태로 들어올 수 있다. 앞에서 언급한 방식에 따르면 지금 이 과정의 최종 목적은 Nonterminal 남지 않을때까지 계속 production을 적용하는 것이다. 그렇게 하려면 사전에 정의된 Grammar를 이용해서 Replacement를 해야되는데 이와 같은 과정을 Derivation이라고 한다. 가령 다음과 같은 예가 있다고 하자.

그러면 E에 대한 Production Set은 E+E, E-E, -E, (E), id가 있을 것이다. 여기서 E->-(id)라는 새로운 Grammar가 성립하는지를 알고싶으면 바로 앞에서 설명했던 Derivation을 사용하면 된다.

맨 먼저 주어진 Grammar를 활용해서 계속 대체하다보면 다음과 같은 과정을 얻게 될 것이다.

이같은 과정을 -(id)에 대한 Derivation 이라고 하고 이를 통해서 -(id)가 grammar에 충족된다고 말할 수 있다. 이 때 사전에 정의된 grammar를 이용해서 derivation이 가능한 경우에는 보통 Derives in zero or more steps이라고 하고 표현으로는 A=>*a 라고 하고 위와 같이 replacement를 통해서 grammar를 찾은 경우는 Derives in one or more steps 라는 의미로 A=>+a 라고 사용한다. 즉, 위와 같은 E->-(id)의 과정은 Derivation으로 표현하면 적어도 한 step이상 Replacement를 거쳐 증명했으므로 E=>+ -(id) 라고 표현할 수 있을 것이다. 이로써 Nonterminal을 Terminal에 대한 CFG로 표현했다. 이런 과정을 하나의 Tree로도 표현해볼 수 있다.

 그런데 위에서는 간단한 Expression이었기 때문에 쉽게 Derivation을 할 수 있던 것이지 가령 E->id+id*id 라는 grammar를 적용해보면 어떻게 될까? 이때부터는 어떤 요소부터 Derivation을 수행하냐에 따라서 결과가 확 달라질 것이다. 우리야 사칙연산의 우선 순위에 따라서 *을 먼저 수행한다는 것을 알고 있지만 컴퓨터는 이를 사전에 정의하지 않은 이상 모른다. 이를 정의하지 않은 이상 왼쪽부터 순차적으로 연산을 수행할 것이고, 당연히 우리가 원하는 결과를 얻지 못할 것이다.이런 현상을 CFG의 Ambiguity라고 하고 이 때문에 이 derivation을 어떤 방향으로 수행할 것인지에 대한 규칙을 정해놓아야 한다. 보통 간단하게 생각해볼 수 있는 것이 left nonterminal을 우선적으로 terminal로 바꾸는 과정과 right Nonterminal을 먼저 terminal로 바꾸는 과정을 들 수 있을 것이다. 그래서 전자를 leftmost Derivation, 후자를 rightmost Derivation이라고 말한다. 앞에서 말한 예제에 Derivation의 방향을 정한 후 다시 Tree를 그려보면 다음과 같이 될 것이다.

앞에서 말했지만 컴퓨터는 이에 대한 규칙을 정해주기 전까지는 어떻게 맞는 건지를 알 수 없다. 다 기본적인 grammar를 충족하는 것이기 때문에 Syntax error를 보이지도 않고 사용자만 알수 있는 logical Error만 발생할 것이다. 이는 경우에 따라선 치명적인 문제로 작용할수 있다. 예를 들면 Dangling Else같은 문제를 들 수 있다.

Wiki에 나온 예제를 살펴보면 

if a then if b then s else s2

라는 조건문이 있으면 Ambiguity가 발생한다. 해석하는 사람에 따라서는 

if a then (if b then s) else s2

if a then (if b then s else s2)

라고 인식할 수 있기 때문이다. C에서는 brace라는 limitation을 줬지만 python과 같이 indentation으로 limit을 준 경우에는 Ambiguity가 클 수 밖에 없다. 

 사실 이문제는 자동적으로 해결할만한 solution이 없다. 사람이 이 문제가 잘못되었다는 것을 안다는 것은 사람의 직관에 의해서인 거지, 이것을 규칙으로 정의한다는 것 자체가 넌센스인 것이다. 물론 일일이 손으로 정의할 수도 있겠지만 그런 경우에는 grammar가 엄청 복잡해질 것이다. 그러면 우리가 Compiler를 만드는데 있어서 사용하려던 Automation의 개념도 의미가 없어질 것이기도 하다. 결국 할 수 있는 방법은 그냥 몇몇 케이스만 정의하고 그외의 치명적이지 않은 Ambiguity에 대해서는 허용할 수밖에 없다. 물론 그걸 해결하기 위해서는 추가적으로 정보가 더 필요하다. 가령 이전의 예제에서는 사칙연산에 대한 precedence와 Association에 대한 규칙이 필요할 것이다. 사실 Yacc나 Bison 같은 Parser Generator에는 이런 부분이 다음과 같이 정의되어 있다.

그러면 위의 규칙에 따라 앞의 Parse tree의 Ambiguity 도 다음과 같이 해결할 수 있다.

최종적으로 우리는 E->id+id*id 라는 grammar를 얻었다. 그 시작을 E라는 Nonterminal로부터 출발해서 위에서 아래로 분리하는 이른바 Top-Down Approach를 택하고 있는 것이다. 그리고 그 TopDown 과정을 취하는 동안 E=>E+E=>id+E=>id+E*E=>id+id*E=>id+id*id 을 수행했고, 잘 보면 왼쪽에서부터 자기자신이 하나하나씩 replacement가 수행되고 있는 것을 볼 수 있다. 이런 걸 보통 Left-Recursive Grammar라고 한다. 

 그런데 사실 이 Left-Recursive 방식은 앞에서 언급한 Top-Down Approach에서 문제를 야기할 수 있다. 만약 predefined 된 grammar의 요소에 자기 자신이 포함되어 있는 경우에는 계속 자기 자신을 대체하면서 Down으로 내려갈 것이다.이러면서 Recursion 수가 증가하면서 결국에는 끝도 없어진다는  것이다. 예를 들어 

1+2 를 분해하고 싶으면 Left Recursion에 의해서 E부터 하나씩 replacement를 수행할 것이다. 그런데 E->E+T로도 대체할 수 있으므로 계속 이걸 대체하다가는 시작점이 어디서부터인지를 가늠할 수 없게 된다, 가령 맞더라도 그 수행시간은 무척 길것이다. 그래서 최대한 분해를 할때는 이 Left recursive된 Production을 제거해줘야 한다. 이를 위해서 prime이라는 것을 쓰고 최대한 자기자신이 recursion되지 않게끔 다시 grammar를 rewrite해준다. 가령 이런것이다.  

원래의 grammar에는 자시자신이 포함된 형태가 포함되어 있으므로 이를 제거해주기 위해서 A`이라는 것을 삽입하고 이에 대한 Grammar를 따로 정의해준 것이다. 간단히 말하면 Grammar로 뽑을 수 있는 production인 β   βα   βαα    βααα    βαααα   .... 등을 표현하기 위한 과정이다. 그런데 어떤 사람은 보면 두번째 케이스도 A`이 들어가 있으므로 이것도 recursion이 아니냐고 물어볼 수 있는데 이같은 경우는 Right Recursion이라고 해서 loop 내에서 recursion이 무한하게 반복되는 left recursive와는 다르다. 

 그런데 이게 의미가 있는걸까? 그 의미가 크다. Left Recursion으로 terminal로 끝내고자 할때는 무조건 첫번째 string으로 β가 나와야 한다. 그런데 Left Recursion인 경우에는 첫번째 문자가 Aα이 될경우에는 β가 나올때까지 계속 Replacement가 일어날 것이다. 앞에서 전제하기론 CFG 자체가 Leftmost Derivation을 따르고 있는데 이처럼 앞에 무슨 string이 나올건지가 불확실한 상태에서는 해당 단어가 grammar속에 속하는지를 확신할 수 없을 것이다. 반면 오른쪽처럼 Right Recursive꼴로 바꾼 경우에는 명확하게 첫번째 string이 정의되어 있기 때문에 그 다음문자에 대한 예측을 할 수 있게 된다. 그냥 α 나 Empty String이 나오면 Terminal이 되기 때문이다. 이렇게 해주는 과정 자체를 Left Factoring이라고 한다.

 컴파일러 이론은 참 어려운 학문이다. 그래서 아직까지 더 공부해볼만한 가치가 있는 거 같다. 제대로 알고있는 건지는 확신이 안서긴 하지만...

Reference 

- Wikipedia : Chomsky Hierarchy (http://en.wikipedia.org/wiki/Chomsky_hierarchy)

- Wikipedia : Terminal and nonterminal (http://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols)

- CS5317 Lecture Note of University of Texas at Arlington : (http://lambda.uta.edu/cse5317/notes/node12.html)

- Wikipedia : Dangling Else ( http://en.wikipedia.org/wiki/Dangling_else)

 - Removing Left Recursive ( http://www.cs.virginia.edu/~cs415/reading/RemovingLeftRecursion.pdf)