[Compiler Design] SDD / AST

 

 

 

Lexical Analysis와 Syntax Analysis가 끝나면 이제 Semantic Analysis를 수행해야 한다.

어휘 분석 -> 구문 분석 -> 의미 분석 

 

Syntax-Directed Definition

일단 파싱은 제대로 된다고 가정하고, Production 규칙마다 해야 할 일을 적어놓는다. (Semantic Action)

파서 생성기인 yacc 에서 정말 많이 사용된다.

 

Semantic Action을 수행할 때는 메모리가 필요하다.

 

 

 

E -> E + E 라는 규칙에서, 각 E를 구분해서 사용해야 함.

 

E + E 의 결과가 되는 메모리가 있다 ($$)

 

Yacc/Bison

$1과 $3 값이 잘 계산되어있다고 할 때, 이 값을 가지고 $$를 채워넣는다.

 

ANTLR

$expr = $unary_expr; 로 해석됨 

 

 

 

Local 변수와 Global 변수를 생각하자.

$$ / $1 / $2 / expr / unary_expr 은 Local 변수 느낌임. 룰 바깥에서는 다르게 동작한다..  당연한소리긴함;;

 

Parse Tree가 모두 만들어진 후, 각 노드를 순회하면서 각 노드에 해당하는 Action을 수행하는게 일반적이고..

Parse Tree를 만들면서 Action을 수행하는 경우도 있다. 

 

 

 

 

 

일단 괄호는 Parse Tree를 만들때 이미 모두 고려된다.

첫 번째 예시처럼 $$를 num을 저장하는 저장소로 볼 수도 있고, 두 번째 예시처럼 $.$를 struct로 보고 여러 변수를 저장할 수도 있다.

 

 

 

 

Lex 에서 0-9 까지 매치된다면 타입 변환 후 yylval에 저장한다.

Yacc 에서 struct 스타일을 사용했다면, Lex에서도 struct 스타일을 사용하도록 일치시켜줘야한다.

 

%union {...} 에서 struct를 정의하고 사용한다.

 

 

LL 에서는 보통 Parse Tree를 모두 만들어진 후 Semantic Action을 수행한다.

그리고 ANTLR도 LL 파서 계열임.

 

일단 루트부터 노드를 방문한다. 다 방문했다면 빠져나온다.

여기서 방문하는건 Enter. 빠져나오는건 Exit.

 

ANTLR의 Listener는 enterProgram / exitProgram 같은 스켈레톤 함수를 제공하고, 개발자는 해당  함수를 오버라이드해서 자기 입맛대로 구현하는 방식이다.

 

 

 

 

 

이제 타입을 지정해보자. T -> int 면 T.type을 intType이라는 상수로 지정해준다.

변수 선언 D 는 타입과 id로 구성된다. id는 변수 그 자체.

근데 그냥 너무 직관적임 규칙대로 쭉 따라가면 됨. int a,b,c,d; 이런 구문도 지원한다.

 

변수 리스트를 활용하는 오른쪽처럼 정의하는 경우가 더 많다. 

 

 

 

 

---

 

 

 

 

 

 

 

Parse Tree는 구문 분석 과정에서의 유도 과정을 트리 형태로 보여준다.

우측유도, 좌측유도 등 유도 순서는 보여주지 않음.

 

다만 그릴 때 좌측유도는 왼쪽부터 그리고

우측유도는 오른쪽 부터 그린다.

 

그런데 사실.. 트리에는 괄호가 필요 없음. 있어 봤자 아무런 도움도 안 된다.

괄호는 구문 분석 단계에서만 필요하고, 트리가 만들어진 후에는 필요 없는 정보가 됨.

 

트리에서 불필요한 정보를 모두 제거한 형태를 AST (Abstract Syntax Tree) 라고 부른다. 

 

 

 

 

 

 

소스코드로 AST를 표현하면 위와 같다.

자바와 C로 구현한 예시인데.. C에서는 N-array Tree를 Binary Tree처럼 구현하는 형태를 사용한다.

 

파싱 단계에서 AST 만들기

LL 파서 - 문법 규칙이 Derivation 될 때 AST를 만든다.

Recursive Descent Parser에서 각 함수가 노드를 반환하는 형식으로 변형한다.

 

LR 파서 - Reduce 동작이 수행될 때 AST를 만든다.

Shift 할 때 그 터미널이 AST에 의미 있는 Terminal이면 해당 Terminal에 대한 Leaf Node를 생성한다.

Reduce 할 때 스택에 이미 만들어져 있던 노드를 가져오고, 해당 노드를 자식으로 삼는 SubTree를 구성한다.

 

Parse Tree를 만들고 Traverse 하며 만들기

SDD를 사용할 수 있다. Yacc이나 ANTLR가 이 방식을 사용함.

 

 

 

 

Lex는 NUM 토큰을 Yacc에게 반환한다.

%union으로 Terminal 및 Non-Terminal이 가질 수 있는 값의 타입을 정의한다.