[Study] Abstract Syntax Tree (AST)

이전 포스트 중에서 Left Recursive와 Right Recursive를 설명하면서 Parse Tree 라는 것을 잠깐 언급한 적이 있다.

말 그대로 해당 구문을 분석한 것이다. 그때 어떤 방향으로 분석하는지에 따라서 결과가 다르게 나올 수 있다고 했었다. 그런데 사실 이걸 판단하는 단계는 이전 과정에서 끝나는 것이고, 이 parse 방향이 정해지면 사실 결과만 빼놓고는 필요없는 내용이다. 우리가 필요로 하는 것은 terminal로 구성된 syntax일 뿐이다. 그래서 위의 parse tree 중 derivation 과정을 제외하고 필수적인 정보만 담은 tree를 Abstract Syntax Tree(AST)라고 한다. 물론 이름에서 담고 있듯 축약만 하고 있는 거지 Parse Tree와 동일한 정보를 가지고 있다. 가령 이렇게 축약되는 것을 말한다.

물론 이전 단계에선 괄호까지 terminal이냐 nonterminal이냐를 분석하고 그에 따른 precedence를 따지기도 했었지만 그게 결정되고 난 후에는 굳이 그 과정을 찾지 않고 결과만 보여주는 것으로 표현할 수 있다는 것이다. 둘다 똑같이 id + ( id + id ) 를 표현하고 있다. 자 그럼 위의 예제를 가지고 계속 AST가 어떤식으로 프로그래밍화되는지를 소개하고자 한다. 원래는 다음과 같은 grammar가 있다고 가정한다.

E -> E+T | T

T -> T*F | F

F -> (E) | id

이것에 대한 AST를 찾기 위해서는 각각의 경우에 대한 class를 정한 후에 해당 조건이 되었을 때 해당 class를 return 하게 하는 것이 가장 일반적인 방법이다. 

일단 위의 grammar에서 필요한 token들이 뭐가 있을까? E, T, F, id 라고 할 수 있을 것이다. 그리고 지금 두개의 token과 한개의 operator가 합쳐진  Binary operation 형태도 눈에 띈다. 이것에 대해서 정의를 class로 해주자는 것이다. 

그러면 다음과 같이 될 것이다.

class BinaryOp : public Node

{

public:

BinaryOp(Op op, Node *left, Node *right) : _op(op), _left, _right(right){};

private:

Op _op;

Node *_left, *right;

}; // Binary Operation이 나왔을 때 수행

 class Ident : public Node

{

public:

Ident(Symbol *ident) : _ident(ident){};

private:

Symbol *_ident;

}; //id가 나왔을 때 수행

function E()

{

...

};

function T()

{

...

};

function F()

{

...

};

이런 식으로 구성을 할 수 있다. 그럼 앞에서 정의한 grammar는 다음과 같이 다시 정의해볼 수 있겠다.

이 과정을 Syntax를 바로 코드로 변환시킨다고 해서 Syntax-Directed Translation이라고 한다. 결국 이 과정을 통해서 앞에서 언급했던 AST를 구하는 것이 최종 목적이 되겠다.

예를 들어서 1 + ( 2 + 3 ) 이라는 식을 AST로 바꿔보자. 어떻게 보면 앞에서 나왔던 예제를 계속 응용한 꼴이다.

일단 parser는 왼쪽부터 읽기 때문에 맨 처음으로는 1과 어떤 Expression과의 Binary Operation으로 구성되어 있다는 것을 알 것이다. 그럼 첫번째 E로 정의되어 있는 E->E+T에 따라서 BinaryOp('+',O,X)를 return 할 것이다. O는 당연히 id이기 때문에 맨마지막의 new Ident()를 return 한다. 

 그 후에는 E 역시 Nonterminal이기 때문에 분해하는 과정을 한번 더 거치는데 역시 어떤 것들끼리의 합이므로 이 역시 BinaryOp()을 return 한다. 그 후에는 Parser는 2+3 이란 괄호안에 있는 연산을 또 분석하고 이에 대한 결과가 id+id 라는 것까지 얻어낼 수 있다. 즉 이런 과정을 거친 후에 다음과 같은 Tree가 나오게 된다. 

방향은 대충 저런식으로 보면 될거 같다. 아무튼 이렇게 얻은 결과를 AST로 바꿔보면 다음과 같이 축약된다.

지금까지 AST에 대해서 정리하고 구하는 방법을 예를 통해서 소개해봤다. 그런데 지금까지 진행방향을 보면 위에서 하나씩 쪼개서 각각이 Node가 되게끔 만들고 이에 해당하는 값을 return 하는 형식으로 되어 있다. 이런 접근 방식을 보통 위에서 아래로 가는 방식이라 하여 Top-Down Approach 라고 한다. 반대로 하나하나의 node로부터 최종적으로 parent Node를 찾고 특성을 분석하는 방식을 Bottom-up Approach라고 하는데 사실 이 개념은 Programming Language에만 국한된것이 아니라 접근 방법에 대한 정의이다. 그래서 어떤 수식으로부터 답을 유추할 때도 이런 개념이 적용되곤 한다. 아무튼 이 다음 포스트에서는 Top -Down Parsing이 어떻게 되는지를 조금더 정리해보고자 한다.

여담 :

 AST에 대한 자료를 찾다가 지식인중에 재미있는 답변글이 달려있어서 올려본다. 말그대로 초등학생 질문에 대학교 지식으로 답변을 달아준 형식인데, 오히려 이런 PL에 관한 정리가 잘 되어 있는 거 같아서.. 궁금한 사람은 링크를 통해서 가보면 될 듯.