[CP] Abstract Syntax Tree(AST)

2023학년도 2학기 충남대학교 조은선 교수님의 컴파일러개론 수업 정리자료입니다.

 

 

 

 

📁 Parse Tree

Parse Tree(파스트리)란 유도과정을 트리로 나타낸 것을 말한다.

 

terminal이 leaf노드, non-terminal이 중간노드를 이루며, 좌측 유도인지 우측 유도인지는 파스트리에 표현되지 않는다.

 

 

 

 

 

📁 Abstract Syntax Tree(AST)

Abstact Syntax Tree(AST)란 파스트리에서 불필요한 정보를 제거한 트리 형태의 자료구조를 말한다.

 

 

abstract class Expr{}

class Add extends Expr {
	Expr left, right;
	Add(Expr L, Expr R) {
		left=L; right=R;
	}
}

class Num extends Expr {
	int value;
	Num(int v) {value = v;}
}

struct tokenType {
	int tokenNumber;
	char * tokenValue;
}

typedef struct nodeType{
	struct tokenType token; // 의미 있는 token 만 다룸
	struct nodeType * son;
	struct nodeType * brother;
}

왼쪽은 JAVA 코드, 오른쪽은 C코드의 AST

 

대표적인 예시로, JAVA 코드와 C코드를 AST로 변환해 볼 수 있다.

 

 

 

 

🌱 AST 만들기

AST를 만드는 방법은 두 가지가 있다.

 

1. 파싱 단계에서 만드는 방법
2. 만들어진 파스트리를 순회하면서 만드는 방법

 

 

1. 파싱단계에서 만드는 방법

LL파싱의 경우, production rule derivation(생성 규칙 유도) 시에 AST를 생성한다.

 

recursive descent parser에서 nonterminal의 procedure를 변경하여 생성할 수 있다. 위 예시의 경우는 nonterminal인 S의 procedure가 변경되었다.

 

 

 

LR 파싱의 경우, reduce할 때 AST를 생성한다.

 

shift를 할 때는, 현재 shift한 terminal이 의미있는 terminal일 경우 단말 노드를 생성한다.

reduce를 할 때는, 의미있는 생성규칙인 경우 지금까지 만들었던 노드를 묶어 subtree를 생성하고, 의미가 없는 경우 넘어간다.

밑에서 두번째 줄 reduce S -> E+S 부분을 살펴보자.

 

이전까지 num 노드 세개와 2+3 노드가 만들어져있는 상태이다. 이 reduction이 진행된 이후에 1 + (2+3) 노드가 생성되어, 아래 그림의 오른쪽과 같은 형태가 된다.

 

 

 

 

2. 만들어진 파스트리를 순회하면서 만드는 방법

SDD를 이용해서 AST를 만들 수 있다.

 

1. Lex

 

2. Yacc

 

 

 

 

 

📁 On-the-fly Evaluation

AST 노드의 방문 순서대로 따라서 평가하는 방법을 on-the-fly evaluation이라고 한다.

 

가장 효과적이지만 다음과 같은 제한이 존재한다.

• S-attributed SDD : synthesized attr만 가지고 있는 경우에만 가능하다.
• L-attributed SDD : synthesized attr만 가지고 있거나 혹은 값이 왼쪽에서 오른쪽으로 계산되는 경우에만 가능하다.