[컴파일러 이론] 3. Syntax analysis, Parser, CFG, Parse Tree, AST

Syntax analysis, Parser

이번글은 syntax analysis에 대해 알아보자.

코딩을 할때 개발자들을 괴롭히는 syntax error 라는 에러메세지는 많이 보았을 것이다.
이번글은 이와 관련된 것이다.

이전글들에서 얘기한 lexical analysis를 수행하는 scanner는 코드를 토큰들로 나눠주는 역할을 했다.

이번 syntax analysis는 이 토큰들을 활용해 문법에 맞는지를 판단한다. 이 분석을 하는 친구를 Parser라고 한다.

이 Parser가 하는 일을 몇가지 예를 들어보면,
1. 괄호를 열면 닫는 부분이 있는지
2. C언어 같은 경우 뒤에 ;을 잘 썼는지
3. while 뒤에 ( )가 있어 그 안에 반복에 대한 조건문이 있는지

등등 많은 문법을 검증한다.

Scanner는 각 토큰을 규칙에만 맞게 만들면 문법은 신경쓰지 않고 통과된다.
num은 되고, 0num이라는 변수이름은 안되는 것은 알지만,
int num; num='c'; 같은 내용이 잘못된 것인지 모른다.

 

Scanner의 경우 동작원리를 아래처럼 순서를 나눠 알아봤었다.

lexical pattern을 어떻게 규정했는지 → RE를 사용

이 패턴들을 어떻게 탐지하는지 → DFA를 사용

 

Parser의 경우에도 이렇게 순서를 나눠 알아보자.

 

---

Context Free Grammar(CFG)

context free grammar(CFG)라는 것을 먼저 알아봐야한다.

CFG에는 terminal symbol과 non-terminal symbol라는 기호가 있고, 이들 사이의 관계를 나타내는 Production이 있다.

 

<terminal>

Terminal은 앞에서 알아봤던 token이라고 생각하면 된다.

CFG는 어떤 symbol을 다른 symbol로 바꾸는 과정인데, 더 이상 바꿀 수 없는 최종 symbol이라고 생각하면 좋다.

ID, NUM 같은 것들이다.

 

<non-terminal>

이는 바꾸는 과정의 중간 단계에 나오는 symbol들이다.

function, var, expression 같은 것들이 사용된다.

 

<production>

좌변에는 non-terminal 하나, 우변에는 terminal 또는 non-terminal이 여러 개 있을 수 있다.

위의 terminal, non-terminal 설명만 보면 이해가 잘 안가기 때문에 production의 예시를 통해 세가지를 다 같이 이해해보자.

 

<매우 간단한 CFG>

expression → var + var

var → ID | NUM

 

여기서 각 줄이 하나의 production이다.

non-terminal symbol은 expression, var이다.

expression은 +로 연결된 식을 나타낸다.

var은 ID, 즉 변수이름이나 NUM, 숫자를 의미한다.

 

따라서 이 CFG는 변수와 숫자로 이루어진 덧셈 식을 표현하는 문법이 된다.

이 문법은

3+3, temp+4, sum+sum 같은 식을 표현할 수 있다.

 

<조금 복잡한 CFG>

이 CFG는 if else문과 관련된 문법을 정의한다.

 

---

CFG 사용 이유

이제 CFG는 뭔지 알았는데, 이거 왜 쓰지? 라는 생각이 들 수도 있다.

이전 글에서 Scanner 때 사용했던 RE를 사용해서 문법도 규정하면 되지 왜 새로운 CFG를 가져와서 복잡하게 할까?

 

괄호의 쌍을 맞추는 문법을 생각해보자.

예를 들면 {},{{}},{{}{}} 이런 것들이다.

만약 {*}*같은 RE를 만든다고 해도, 두 개의 *연산은 반복횟수가 똑같다는 보장이 없다. 그냥 {{{{{}}같은 것도 포함되는 것이다.

괄호가 열린 개수에 따라 DFA 상에서 모두 다른 state가 필요한데, 개수가 무한하기 때문에 표현이 불가능하다.

RE는 표현력이 낮기 때문에 CFG가 필요하다.

 

---

몇 가지 CFG 예시

예시1

이런 Grammer G가 있다고 하자.

abcba, acca, aba, abcbcba 중에 이 G가 표현할 수 있는 L(G)에 포함되는 string은 무엇일까?

S → aXa → abYa → aba 의 과정으로 aba를 얻을 수 있기 때문에 L(G)에 aba는 포함된다.

 

---

예시2

왼쪽의 사진에 있는 CFG를 이용해 if(ID==ID) ID=ID; 를 만들어보자.

오른쪽 사진처럼 production을 계속하다가 모든 symbol이 terminal이 되면 끝낼 수 있다.

---

Parse tree, AST

어떤 식이 이렇게 CFG를 이용해 규정해놓은 문법들에 부합하는지 아닌지 어떻게 알 수 있을까?

위의 예시들처럼 무작정 production을 계속해보면서 최종 식이 나오는지 시도해보는 것은 딱 봐도 효율적이지 못하다.

그래서 나오게 된 것이 Parse tree와 AST이다.

---

Parse tree

 

이 production에 따른 변형(derivation)을 Tree 형식으로 표현한 것이다.

Parse tree에는 몇가지 특징이 있다.

 

1. leaf node는 terminal이다.

2. internal node에는 non-terminal 이 있다.

3. operation 들의 순서(우선순위)도 보여줄 수 있다.

4.in-order traversal(중위 순회)를 하면 original input이 나온다.

 

오른쪽 트리를 보면 곱하기의 우선순위가 더하기의 순위보다 높게 그려진 것을 볼 수 있다.

 

 

 

 

---

Derivation Order

S에서 시작해 id · id + id를 만들 때, 방식이 두 가지가 있다.

중간 과정에서 나오는 non-terminal에 대해 production을 적용하는데,

왼쪽부터 나오는 non-terminal에 대해 먼저 적용할 수도 있고 오른쪽부터 적용할 수도 있다.

이를 각각 left-most derivation, right-most derivation이라고 한다.

사람에게는 아무래도 왼쪽에서부터 바꾸는 것이 익숙할 것이기 때문에, 여기서 예시로는 right-most derivation을 보자.

처음 S → S Op S의 적용은 두 트리 모두 똑같다. derivation을 할 non-terminal이 S하나만 있기 때문이다.

 

이제 S Op S에서 어떤 쪽의 S에 대해 먼저 변환을 진행할지, 여기서 갈리게 된다.

right-most derivation은 오른쪽의 S에 대해 S → id를 먼저 진행한다.

그 이후 Op → + , S → S Op S 순서로 진행한다.

 

---

Ambiguous Grammar

그런데, 위의 두 가지 다른 방식으로 생성된 parse tree를 가만 보면, 문제가 좀 있다.

두 가지 방식으로 생성된 tree가 다른 결과를 내놓기 때문이다.

같은 production들을 적용했는데 순서를 다르게 적용했다고 다른 expression이 나오면 선택이 필요해진다.

이 경우 문제는 production들, 즉 grammar 자체가 이렇게 설계된 것이고, 이런것을 ambiguous grammar라고 한다.

 

<연산자 ambiguity>

위의 left-most derivation방식의 tree를 보면, 더하기의 우선순위가 더 높다. 즉 id · (id + id)처럼 계산된다.

하지만 id · id + id 라는 식을 사람의 관점에서 본다면 당연히 곱하기를 먼저 하는게 맞다.

이런 식으로 사람은 당연히 생각하는 우선순위를 컴퓨터가 안다고 생각하고 grammar를 만들면 위와 같은 현상이 벌어진다.

 

몇가지 예시가 더 있는데

a-b-c 와 a-(b-c)

a^b^c 와 a^(b^c) 등이다.

빼기처럼 왼쪽부터 계산해야하는 것은 left associatvie, 거듭제곱처럼 오른쪽에서부터 계산해야하는 것은 right associative한 연산자라고 표현한다.

a<b<c처럼 부등호는 두개의 대상에 대해서만 연산이 가능할 경우처럼, 3개 사이의 연산이 문법적으로 맞지 않는 non associative한 연산자도 있다.

 

이제 이런 연산자의 ambiguity를 없애보자.

grammar를 조금 바꾸면 해결이 된다.

중간에 T라는 non-terminal을 무조건 거쳐야 terminal로 갈 수 있게 하므로써 우선순위가 지정되었다.

위의 3가지 종류의 연산자에 ambiguity해결법은 아래와 같다.

 

<if else ambiguity>

다른 ambiguity의 예시로 if else 문과 관련된 것이 있다.

if E1 then if E2 then E3 else E4 라는 식을 생각해보자.

아래처럼 두개의 해석이 가능하다.

이런 경우를 막기 위해 사람들은 빼기는 앞에서부터 하기로 정한 것처럼 else는 가장 가까운 then과 짝(match)을 지어주기로 했다.

이렇게 ambiguity를 없애주는 grammar는 아래와 같다.

unambiguous if-then-else

---

AST

공부할 때 parse tree를 몇번 그려보면 그리는 것이 좀 귀찮게 느껴진다.

그래서 불필요한 부분을 좀 제외한 Abstract Syntax Tree(AST)라는 것을 만들었다.

---

지금까지의 내용을 정리해보면

Scanner는 사람이 작성한 코드를 단어별로 쪼개 분석해서 parser한테 넘겨주면,

parser는 문법에 맞는지 판별한다.

 

parser는 먼저 CFG를 사용해 문법을 정의하고,

이 CFG의 문법에 맞는지 평가할 때 만들어지는 구조가 parse tree이다.

이 parse tree가 잘 만들어지면 입력된 식이 grammar에 맞는 입력이라는 것을 알 수 있다.

 

여태까지는 S → S + S | id 같은 production이 있다면

두 가지의 선택지 중에 사람이 알아서 선택해서 parse tree를 그리는 것으로 가정했다.

다음 글에서는 실제 컴퓨터가 어떻게 올바른 선택을 해야할지, 즉 컴퓨터가 CFG에서 parse tree를 만드는 법을 알아보자.