Intermediate code generator

high level intermediate representation( parse tree, AST ..)를

low-level intermediate representation ( three address cod, TAC) 로 변환 해야 한다.

 

intermediate representation이 왜 필요할까?

=> machine code는 optimization을 할 때 여러 제약이 존재함

=> 중간 코드를 사용해서 더 쉽게 이해하고 최적화 할 수 있음

=> 중간 코드를 사용하면 더 low cost로 최적화를 할 수 있음

 

이 클래스에서는 대표적으로 AST와 TAC를 이용해 intermediate representation을 쓰고자 한다.

 

AST

=> parsing tree 에서 디테일을 제거한 버전 

 

TAC (Three Address Code) 

=> 각 operation에 opearand가 3개 까지만 존재하는 high level assembly code

=> AST를 linear 하게 만든 것

 

Type of TAC

variable assignment

1) copy operation

=> A = 1, to = 2, A = to

 

2) binary operation

=> A = B + C, to = A || 1 

 

3) unary operation (unary operator 사용 => - , ! )

=> to = -2, to = !true 

 

control flow statements

1) unconditional jump with label

=> goto Ln

...

Ln

...

 

2) conditional branch

=> if x GOTO Ln

 

more

1) Call procedures 

foo(x1, x2) 

=>

param x1

param x2

y = call foo, n

 

2) Array operations

A[i] = B

 

3) Return statements

return x

 

How to represent TAC : Quadruples

quadruples => four fields (op, arg1, arg2, result) ==> linked list로 저장

 

AST to TAC

=> root 의 new guadruple 생성

=> left child의 결과를 arg1에 담고, right child의 결과를 arg2를 담음 

=> left right 결과를 다 받으면 해당 result를 temporary variable을 생성해서 담음

=> quadruple이 다 채워지면 liked list 끝에 붙임

 

... 한번 해보자

 

 

// root

-

arg1

arg2

result

 

// root의 left child의 left child

+	arg1	arg2	result
+	A	arg2	result

 

// root의 leftchild의 right child

*	arg1	arg2	result
*	A	arg2	result
*	A	B	result
*	A	B	t0

 

//root의 right child

+	A	t0	result
+	A	to	t1

 

//root의  right child

-	t1	arg2	result
-	t1	num	result
-	t1	1	t2

 

==> 

 

 

다른 예시도 보자 (while은 rule이 위와 다르다)

개인적인 견해로는 AST 보고 바로 바꾸는거보다 AST를 TAC 줄글로 한번 바꾼다음에 따라가는게 더 쉬울듯

Lo : 
    t0 = x <= y
    if not t0 goto L1
    t1 = x + 1
    x = t1
    goto L0
L1 :