Compiler 6 - Intermediate code generator

 Intermediate code generator
syntax part의 첫 요소인 intermediate code generator는 high level intermediate representation(AST)를 low-level intermediate representation(three address code)로 바꾸는 작업을 한다.

AST 등도 HLL에 비하면 low level이지만, 아직 machine level에 비하면 높다. 따라서 이를 더 낮추는 과정이다. 이를 하는 이유는 intermediate 단계에서 최적화 하는 것이 machine level에서 하는 것 보다 더 간단하고 쉽기 때문이다. 또한, AST보다는 machine level에 더 가까워 machine code로 변환하는데도 적은 노력이 든다.

일반적으로 각 compiler 들은 여러 개의 intermediate representation 들을 가진다. 왜냐하면, 각각이 가지고 있는 information과 특징들이 달라 optimization 할 수 있는 것들이 다르기 때문이다. 그 중에서 AST(Abstract Syntax Tree)와 TAC(Three Address Code)를 알아보자.

AST는 앞서 살펴본 것 처럼, 필요없는 정보들을 제거하고 간단하게 나타내어 linked-list 형태로 semantic action을 나타낼 수 있다. (parse tree without useless parsing detail)


TAC(also called as high level assembly code)
TAC는 이름에서 알 수 있듯이 최대 3개의 operand를 가지는 high level assembly code로 AST를 linear하게 표현한 것이다. 따라서 AST를 travel하며 TAC를 생성할 수 있다.

이는 operand와 operator로 표현된다.
- operands(=addresses) : identifier(explicit variable), constant, temporary variable(t0, t1)
- operator(=intstruction) : *, +, -, =
이들을 활용하여 나타낼 수 있는 operation들은 copy operation : (t0 = 2), binary operation (A=B+3), unary operation(t0 = -2, t1 = !true) 등이 있다.

이외에도 jump(unconditional jump), GOTO(conditional branch) 등 assembly 언어에서 사용되는 문구가 그대로 사용될 수 있다.
n개의 parameter를 가지는 procedure call도 call foo, n으로 가능하다. (n 개의 param을 앞에 선언) array operation과 return stmt도 일반적인 문법과 같이 사용할 수 있다.

TAC는 앞서 컴구에서 배운 것 명령어와 비슷하게 op, arg1, arg2, result 형태의 linked list로 구현된다. 이를 quadruple이라 한다.
AST를 travel하며 TAC construction rule을 따르면, TAC를 생성할 수 있다. (AST의 각 node를 방문할 때마다 semantic action이 실행 -> 노드를 생성하고 연결하는 작업을 실행)

- create new quadruple with op
- arg1 = left child's computation result
- arg2 = right child's computation result
- result = new temporary variable ti
- store newly created quadruple into end of linked list

이를 반복하면, AST의 각 node를 quadruple로 나타내는 일련의 linked list를 생성할 수 있다.