[컴개/CI] AST

Parse Tree

파스트리는 유도 과정을 트리로 나타낸 것이다.

leaf node는 terminal, 중간 노드는 non-terminal을 의미하고,

좌측유도인지, 우측유도인지는 표현이 되지 않는다.

위의 파스트리는 유도를 나타내기 위한 불필요한 부분이 존재한다.

트리 자체로 우선 순위를 나타낼 수 있으므로 괄호 또한 불필요하다.

 

AST(Abstract Syntax Tree)

이때, 위의 파스트리에서 불필요한 부분을 모두 삭제한 것을 AST라고 한다.

다양한 언어로 위와 같은 AST 형태를 나타낼 수 있다.

 

위는 자바 코드로 작성한 AST 자료구조이다. Add와 Num 모두 Expr 클래스를 상속하고 있으므로 인자를 받을 때 Num인지, Add인지 구분할 필요가 없다.

 

그러나 각 클래스에 따라 자식으로 가지는 노드의 개수가 다른데, Add의 자식 개수는 2개, Num의 자식 개수는 1개이다. 즉, 각 클래스에 대해 자식 개수가 가변적이다. 이러한 경우 handling이 편하도록 각 노드를 binary로 만든다.

 

 

AST 만들기

1. 파싱 단계에서 만들기

- LL: production rule derivation

- LR: reduce

 

2. 만들어진 파스트리를 순회하면서 만들기

- SDD를 사용하여 만들기 (Yacc에서 AST 만들 때 SDD 사용)

 

파싱 단계에서 만들기 - LL

 

Recursive descent parser에서 non-terminal 프로시저를 변형한다.

 

아래의 코드로 변형하면 메소드에서 리턴 타입이 만들어지고, 각 노드에 대한 값을 받아와 변수에 저장한 후 해당 변수를 묶어서 새로운 노드를 생성하여 돌려준다.

 

파싱 단계에서 만들기 - LR

Shift a

- 의미있는 terminal일 경우 단말 노드를 만든다.

 

Reduce A -> X1X2X3...

- 의미 있는 생성 규칙의 경우 지금까지 만든 노드를 묶어 subtree를 구성한다.

- 의미 있는 생성 규칙이 아닌 경우 skip한다.

 

위와 같은 생성 규칙에서 '1 + 2 + 3'을 파싱하여 AST를 만들어보자.

 

이때, S -> E는 의미 없는 생성 규칙이므로 해당 노드는 생성하지 않는다.

 

 

왼쪽이 reduce 전, 오른쪽이 reduce 이후 모습이다.

S + E가 S로 reduce된 모습을 확인할 수 있다.

 

이때, 스택의 옆에 자리가 하나씩 있는데, 이 자리는 reduce되며 생성된 특정 노드에 대한 포인터(또는 객체 아이디)를 가진다.

 

SDD로 AST 만들기-Yacc

 

위 사진에서 NUM 토큰은 Lex에서 yylval.val로 값을 가져올 수 있고, val의 타입은 int이다.

또한 expr의 결과값을 semantics action에서 내어줄 수 있고, 그 생김새는 node이다.

이때 속성으로 node값을 가지는데, node라는 어트리뷰트를 통해 제어를 해준다.

 

Evaluation 방법

우리가 구문분석기의 결과로 tree를 받았을 때 노드를 방문하고 일을 하게 되는데 그 일을 evaluation이라고 한다.

각 노드가 가지는 결과값을 하나씩 얻어내면서 트리를 방문하기 때문인데,

이러한 evaluation 방법은 여러가지가 존재한다.

 

1. AST depth fisrt visit(DFS) 방법으로 방문할 때의 evaluation 순서를 따라가기

- 가장 많이 사용되는 방법이다.

 

2. 가장 efficient한 방법 알아내서 그 순서대로 방문하기

- 하지만, restriction이 있다.

 

속성에는 synthesized attr.과 inherited attr.이 존재한다.

synthesized attr.은 자식이 주는 값을 그대로 가공하면 부모의 값이 되었지만, 

inherited attr.은 다루기 까다로웠다.

 

각 속성에 따라 SDD를 두 종류로 구분할 수 있다.

 

S-attributed SDD

synthesized attr.만 가지고 있는 경우다.

 

L-attributed SDD

S-attributed SDD에서 확장된 경우로 synthesized attr.만 가지고 있거나, 값이 왼쪽에서 오른쪽으로 흘러 계산이 되는 경우를 모두 포함한다.