[Compiler] 연산자의 Associativity와 Recursion의 연관성
연산자의 Associativity와 CFG의 문법(Recursion)의 연관성
정의
연산자의 Associativity란?
(괄호가 없을 때) 같은 우선순위의 연산자들 중 무엇을 먼저 결합할지 결정해주는 속성을 말한다.
+ 연산자가 Left Asscociative하면 1+2+3은 (1+2)+3과 동일한 의미를 가지게 되고 Right Asscociative하면 1+2+3는 1+(2+3)과 동일한 의미를 가지게 된다.
Recursion이란?
CFG에서 non-terminal이 그 non-terminal을 포함한 sequence를 유도할 수 있으면 Recursive하다(순환한다)고 말한다. 우측에서 순환할 수도 있고 좌측에서 순환할 수도 있고 양쪽에서 순환할 수도 있다.
예시를 보면서 이해를 해보자.
Left Recursive한 Rule
A -> Aa | ɛ위와 같이 좌측에서 계속 유도할 수 있는 경우, 좌측에서 순환한다고 말한다.
Right Recursive한 Rule
A -> aA | ɛ위와 같이 우측에서 계속 유도할 수 있는 경우, 우측에서 순환한다고 말한다.
Left Recursive하면서 Right Recursive한 Rule
A -> A + A | ɛ위와 같이 우측에서도 계속 유도할 수 있고 좌측에서도 계속 유도할 수 있는 경우, 우측과 좌측에서 순환한다고 말한다.A + A의 경우, 자동화된 기계의 입장에서 보면 좌측 A에 유도할지 우측 A에 유도할지 충돌이 생긴다. 이와 같이 문법이 두 개 이상의 Parse Tree를 만들 수 있을 때 모호하다고 말한다. 컴파일러를 만들기 위해 CFG를 만들고 있다면 이러한 문법의 모호성은 제거해야만 한다. 안타깝게도 문법의 모호성을 제거해주는 자동화된 수단(알고리즘)은 존재하지 않는다. 그래서 머리를 써야만 한다. 다행히도 연산자의 우선순위나 Dangling Else와 같은 잘알려진 모호성 문제는 똑똑한 사람들이 고민해서 미리 해결하는 방법을 만들어 놨다. 내가 CFG를 작성하다가 잘알려지지 않은 방식의 모호한 문법을 작성했으면 별도의 자동화된 수단이 없으므로 자기 스스로 해결해야 한다. 이런점이 자동화된 수단(ex. Thompson Construction, Subset Construction, ...)이 넘쳐나는 Regular Expression과 많이 다르기 때문에 주의해야 한다.
연산자의 Associativity와 Recursion의 관계
- Left Associativity는 연산자가 좌측에서 우측으로 평가되기 때문에 Left Recursion을 사용해서 표현한다
ex)1+2+3=(1+2)+3 - Right Associativity는 연산자가 우측에서 좌측으로 평가되기 때문에 Right Recursion을 사용해서 표현한다
ex)1+2+3=1+(2+3)
- 연산자는 Left Associative하다. Left Recursion을 사용해서 Production Rule을 만들어보자
exp -> exp - number | number
number -> 0 | 1 | ... | 93 - 4 - 5가 주어졌을 때 위의 문법을 사용하면 3 - 4를 먼저 평가(Left Associative)하는지 확인해보자.
Bottom Up 방식으로 생각해보자. 우리의 최종 목표는 이 문법이 exp가 되는지 확인하는 것이다.
그러기 위해서는 다음과 같은 유도 과정을 거쳐야 한다.3 - 4 - 5 <= ... <= exp - number <= exp
문법이 좌측으로 recursive하기 때문에 3 - 4가 exp가 되고 5가 number가 되어야만 한다. 다른 경우는 없다.
그렇기 때문에 좌측이 먼저 평가가 되는 것을 확인할 수 있다.
Parse Tree를 작성해보면 더 명확하다.
Left Recursion의 문제 및 해결법
Lexical Analyzer는 Parser라고도 부른다
LR Parser는 괜찮지만 LL Parser와 같은 몇 개의 Top Down Parser는 Left Recursive한 문법 처리하지 못한다. 그런데 Left Associativity는 Left Recursion을 사용한다. 그럴 경우 그 문법의 Left Recursion을 없애면 된다.
여기서 알 수 있는 사실은 Lexical Analyzer는 어떤 형태의 Regular Expression인지 상관없이 모든 Regular Expression에서 잘 동작하지만 Syntax Analyzer(Parser)는 제한된 CFG로 동작한다는 것이다. 우리가 CFG를 만들어서 바로 넣으면 되는 것이 아니라 Left Recursion을 제거하거나 해서 필터링 한 문법을 넣어줘야 한다는 점을 주의하자.
Left Recursion은 LL Parser의 고질적인 문제기 때문에 그 해결법이 이미 인터넷에 많이 적혀 있어서 생략하겠다.
대신 그 방법을 약간 변형해서 내가 생각한 Right Recursion을 없애는 법을 적어보고자 한다. (틀릴 수도 있다 ㅎㅎ)
Right Recursion 없애기
Right Recurrsion을 제거하려면 Left Recurrsion을 사용해서 다시 적으면 된다.
- 새로운
non-terminal을 만들어서 반복되는 부분을 분리하기 위한 새로운 Production Rule을 정의한다. - 기존에 정의한 모호한 Rule을 버리고 새로 정의한 Rule을 이용해서 Left Recursion만 있도록 기존 Production Rule을 재정의한다.
예시) exp -> exp - exp | number의 Right Recursion을 없애보자
반복되는 부분을 분리하기 위해 정의하는 새로운 non-terminal을 K라고 해보자.
K -> (Kexp -) | ɛexp -> Knumber