Intermediate Code Generation

Intermediate code는

● semantic analysis 단계에서 만들어진 syntax tree를 이용하여 생성되거나,

● 문법 규칙이 reduce 될 때마다 syntax-directed translation으로 생성된다.

● intermediate code를 생성하는 데는 intermediate language를 사용한다.

 

컴파일러의 frontend와 backend를 연결해주는 기능을 한다.

 

 

Intermediate Code 생성 방법

● intermediate code generator (ICG)를 이용

       ○ 파스 트리 또는 구문 트리를 순회하면서 효과적인 intermediate code를 생성

 

 

● syntax-directed translation (SDT) 방법

      ○ CFG의 각 생성 규칙에 의미 수행 코드를 기술하고 parser에 의해 실행

      ○ LR parsing에서,

            ■ shift action에 syntax analyzer를 호출

            ■ reduce action에 적용된 규칙과 일치하는 의미 수행 코드 실행한다.

 

 

 

중간 언어 표기법

 

● Reverse Polish Notation (Postfix Notation)

● Three-address Code (Triples, Indirect Triples, Quadruples)

● Tree structure (Parse tree, Syntax tree)

● Virtual machine code (P-code, EM-code, U-code, Bytecode)

 

 

Postfix Notation

 

Reverse Polish Notation (Postfix Notation)

● 가장 오래된 notation 중 하나

      ○ 포트란 컴파일러에서 산술식을 위한 중간 언어로 사용

      ○ 인터프리터 언어인 베이직의 중간 언어로 사용

● 트리를 Postorder로 순회하여 표현 (L-R-Root)

● 장점:

      ○ 연산자 스택을 이용하여 쉽게 연산할 수 있음

      ○ 소스 프로그램으로부터의 변환이 비교적 쉽고 빠르게 이뤄짐

      ○ 인터프리터를 이용하는 언어의 중간 언어로 적합

● 단점:

      ○ 코드를 이동할 수 없음

      ○ 최적화에는 부적합

 

Note:

● Prefix Notation: 트리를 Preorder로 순회하여 표현 (Root-L-R)

● Infix Notation: 트리를 Inorder로 순회하여 표현 (L-Root-R)

 

 

Example ) 산술식 A = B * C + D / E가 다음과 같이 구문 트리로 표현되어 있을 때

                      이를 Prefix, Infix, Postfix notation으로 나타내보자.

 

 

 

Prefix : = A + * B C / D E   

Infix : A = B * C + D / E

Postfix : A B C * D E / + =      

 

 

Three-address Code

 

3-address code

● 코드의 재구성이 편리하기 때문에 코드 최적화에 적합

● 레지스터 기반 object code로의 변환이 편리하기 때문에 상용화 컴파일러에서 많이 사용

● 치환 연산자의 rhs가 1개의 unary, binary, or logical operator 와 operand으로 구성

● 치환 연산자의 lhs는 id 또는 addr을 표현하여 하나의 코드 내에서 3개의 주소를 나타냄.

 

일반적인 형식: A = B op C

● Operand A, B, C는 id, constant, 또는 temporary variable.

● Operator op는 unary, binary or logical operator.

 

예시) Assignment: A = B op C

● op는 binary operator (두개의 operand를 필요)

● A는 결과 값을 저장하는 주소이며, B와 C는 binary operator op의 operand

 

Assignment: A = op B

● op는 unary operator (하나의 operand를 필요)

● A는 결과 값을 저장하는 address이며, B는 unary operator op의 operand

 

Assignment: A = B

 

Unconditional branch: GOTO L 

● L: 레이블. L이 있는 3-주소 코드를 표시한다.

 

예시) Conditional branch: if A relop B GOTO L

● A와 B는 relational operator (relop)의 operand

● 관계를 만족하면 true 레이블 L에 대한 3-주소 코드를 실행하고 관계를 만족하지 않으면 false 바로

      다음 문장이 실행된다

 

프로시저 호출문

Param A1

Param A2

⋮

Param An

Call P, n     => P(procedure), n(the number of actual parameter)

[여기서 n은 호출에서의 actual parameter 개수이고 P는 프로시저의 이름에 해당된다.

  이러한 코드는 호출 P(A1, A2, …, An)의 3-주소 코드이다.]

 

Index assignment: A = B[i], A[i] = B

Pointer assignment: A = &B, A = *B, *A = B

 

Example ) Assignment A = -B * (C + D)를 3-address code로 나타내보자.

 

(1) T1 = -B

(2) T2 = C + D

(3) T3 = T1 * T2

(4) A = T3

 

 

3-address Code Implementation

 

triples:

● 결과 값을 저장하는 피연산자가 존재하지 않고

quadruples:

● 결과 값을 저장하는 피연산자가 존재

Indirect triples:

● triples 방법에서 코드 이동 시 발생하는 단점을 보완

 

 

Triples

● 기본 연산을 나타내기 위해 각 명령어가 , , 와 같은 3개의 필드로 구성 된다.

● 순서에 따라 번호가 부여된다.

      triple의 결과값은 그 triple 번호에 할당하여, 오직 3개의 필드인 <operator>, <operand - 1>, <operand - 2>

      가 있는 레코드를 구성할 수 있다.

 

 

Quadruples

● 각 명령어가 <op>, <operand - 1>, <operand - 2>, <결과>와 같은 4개의 필드로 구성

● <결과>는 연산의 결과를 저장하고 일반적으로 임시 변수가 사용됨

● Object code 생성 시에는 target machine의 레지스터 또는 메모리에 배정된다.

 

장단점: quadruple 표현 방법은 triple 표현 방법과 달리 결과 주소 부분을 포함하고 있으므로 코드의 이동이

              편리하여 최적화를 수행하는 데 적합하다.

              하지만 많은 임시 변수를 관리해야 하는 단점이 있다.

 

 

Indirect Triples

● 코드 최적화에 부적당한 triple 표현 방법의 단점을 보완

● triple의 수행 순서를 별도의 표에 저장한다.

● 코드 최적화 시에 표의 순서만 변경하고 원래의 triple을 변경하지 않아서, 최적화 보다 쉽게 수행

 

 

Example ) 다음 assignment를 triples, indirect triples, quadruples로 표현해보자.

A = B + C * D / E F = C * D

 

 

Tree-structure Code

 

소스 프로그램을 프로그램의 의미를 보다 시각적으로 표현할 수 있는 방법 코드의 특성상 손쉽게 재구성이

가능하므로 최적화 컴파일러의 IL로 가장 적합한 표현

 

소스 프로그램의 트리 구조 표현 방법

● 파스 트리

      ○ 구성하는 과정은 syntax analysis 과정에서 syntax-directed 방법으로 쉽게 이루어지나 중복된 정보를

           많이 포함하고 있으므로 parsing 하는 데 시간이 많이 걸리고 메모리의 낭비를 초래하여 IL로는 부적합.

      ○ 보다 효율적인 표현방법이 필요

● 추상 구문 트리 (Abstract Syntax Tree)

      ○ 파스 트리에서 의미 없는 논터미널을 제거하고 의미 있는 정보만을 트리 구조로 표현한 구문 트리.

      ○ 구문 트리는 constant, variable을 나타내는 터미널 노드와 operator를 나타내는 논터미널 노드로 구성

      ○ Operand은 해당되는 operator의 child 노드로 연결

 

 

Example ) 다음 문법에서 입력 문자열 id + id * id에 대한 파스 트리와 구문 트리를 만들어보자.

① E → E + T ② E → T ③ T → T * F

④ T → F ⑤ F → (E) ⑥ F → id

 

 

 

Virtual Machine Code

 

컴파일러를 frontend와 backend로 분리 하고, 잘 정의된 인터페이스를 사용하여 두 단계를 연결함으로써

쉽게 이식되고 재목적이 가능한 컴파일러를 제작하는 추세이다.

 

이와 같은 방법으로 만든 컴파일러를 재목적 컴파일러(retargetable compiler)라 하는데, 컴파일러를

한 기계에서 다른 기계로 이식하는 문제를 backend만 변경함으로써 쉽게 해결할 수 있다.

 

 

 

P-Code

 

p-코드는 컴퓨터에 별도의 컴파일러가 없어도 p-코드 인터프리터만 있으면 프로그램을 간단히 실행시킬 수 있다.

하지만 target code로 번역되는 한 단계가 추가되므로 실행 시간이 느리다는 것이 단점

 

p-machine는 모든 연산이 스택에서 행해지는 스택 컴퓨터로 5개의 특수 레지스터와 메모리로 구성되어 있다.

 

레지스터의 종류와 기능은 다음과 같다.

● program counter, PC : 코드 지역에서 현재 명령어의 위치를 가리킨다.

● stack pointer, SP : 스택의 톱을 가리킨다.

● mark pointer, MP : 활성 스택 프레임 active stack frame의 시작을 가리킨다.

● extreme pointer, EP : 현재 사용할 수 있는 가장 큰 스택의 위치를 가리킨다

● new pointer, NP : 힙의 톱을 가리킨다.

 

메모리는 워드 단위로 된 선형 배열 형태로, p-코드 명령어가 저장되는 코드 부분과 자료가 저장되는

자료 부분으로 이뤄진다.

힙(heap)은 스택을 향해 커지며, EP가 NP보다 더 커지면 그 기계의 메모리가 모두 사용되었다는 것을 의미한다.

 

스택 프레임은 어떤 함수의 호출에 따라서 그와 관계되는 모든 자료를 저장해두는 스택 영역으로, 호출된 프로그램의 프레임이 스택 속에 순차적으로 쌓인다.

 

 

 

Syntax-directed Translation 

 

각 production rule에 해당하는 의미 수행 코드(semantic action code)를 직접 기술

● CFG의 각 production rule 은 컴파일러에 속하는 변수 값 계산, 중간 코드 생성, 에러 메시지 출력, 기호표 등과

      관련된 서브프로그램이나 의미 수행 코드로 구 성

● 즉, production rule과 그에 해당하는 의미 규칙을 결합

 

 

다음과 같은 생성 규칙과 의미 규칙이 있다고 하자.

 

E → E1 + E2 {E.VAL = E1.VAL + E2.VAL}

● 생성 규칙의 lhs와 관련된 번역 E.VAL은 rhs의 E와 관 련된 번역 E1.VAL과 E2.VAL을 더하여 구한다

● 터미널 기호 +는 의미 규칙에 의해 수학적인 의미로 번역

 

구문 지시적 번역기의 구현

● Bottom-up parser에 대해 합성 속성 값을 저장할 수 있 는 스택 내 새로운 필드를 구현하여 사용한다.

● 예를들어 X → ABC는 오른쪽 그림과 같이 구성할 수 있다.

 

 

Example )

Syntax-directed translation 방법과 annotated parse tree를 이용하여 정수 operand과 +, * operator를

가진 calculator 프로그램을 설계해보자.

그리고 설계된 계산기 프로그램에서 입력 문자열 23 * 5 + 4$(입력의 마지막은 문자 $로 표시)를 parsing해 보자.

* 각 프로그램이 수행된 다음에는 새로운 스택의 톱이 NTOP으로 설정된다.

 

 

 

annotated parse tree 먼저 만든 후에 parsing을 하단 왼쪽부터 진행하면 된다.

 

 

Intermediate Code Generation

 

중간 코드를 생성하는 방법

● Syntax-directed translation으로 parsing 과정에서 중간 코드를 생성하는 방법

● 파스 트리 또는 구문 트리와 같은 중간 표현으로부터 중간 코드를 생성하는 방법

 

Syntax-directed translation

● 단점: 소스 프로그램에 구문 에러(syntax error)가 발생하면 에러 발생 전까지 수행한 중 간 코드 생성이

      무의미해지므로 시간 낭비를 초래하며, 생성 규칙의 감축 순서에 따라 중 간 코드를 생성하므로 구현이 복잡

● 장점: 하지만 구문 분석 과정에서 직접 중간 코드를 생성하므로 소스 프로그램에 구문 에러가 없는 경우에는

      오히려 빠르게 중간 코드를 생성할 수 있음

 

소스 프로그램에 대해 중간 표현을 생성한 후 중간 코드를 생성하는 방법

● 중간 코드 생성에 필요한 의미 있는 정보만을 파스 트리 또는 구문 트리에 저장하고 있으 므로 코드 생성기의

     구현이 매우 용이하지만, 컴파일러의 크기가 커지고 컴파일 시간이 길어진다.

 

 

Boolean Expression

 

논리식(부울식, boolean expression)은 논리 값을 계산하거나, if 또는 while 문에서 조건식을 계산하는데 사용

논리식은 and, or, not과 같은 논리 연산자와 부울 변수이거나 관계식으로 표현되는 피연산자로 구성

 

E → E or E | E and E | not E | (E) | id relop id | true | false

 

● relop는 ＜, ≦, =, ≠, ＞, ≧와 같은 6개의 관계 연산자이고

● 논리 연산자 or와 and는 왼쪽 결합 법칙을 만족하며,

● 연산자 우선순위는 or가 가장 낮고 다음은 and, not 순서라고 가정한다. (not > and > or)

 

if, while 문: short circuit 방법 사용

● E1 or E2에서 E1이 true라면 E2 를 검사할 필요 없이 전체 식의 값이 true

● 이와 같이 논리식의 한 부분을 검사하지 않아도 된다면 컴파일러는 하나의 표현식만을 계산하게 함으로써

     최적화할 수 있다.

 

논리식을 3-address 코드로 번역:

● true: 1, false: 0, left-associative.

 

논리식 A or B and not C에 대한 3-addr 코드는 논리 연산자의 우선순위가 not, and, or이므로 다음과 같다.

 

1: T1 = not C

2: T2 = B and T1

3: T3 = A or T2

 

관계식 A ＜ B는 조건문 if A ＜ B then 1 else 0과 일치하므로 3-addr 코드로 변환하면 다음과 같다.

 

1: if A < B GOTO 4

2: T = 0

3: GOTO 5

4: T = 1

5:

 

논리식 A ＜ B or C에 대한 3-주소 코드는 다음과 같다:

 

1: if A < B GOTO 4

2: T1 = 0

3: GOTO 5

4: T1 = 1

5: T2 = T1 or C

 

 

Backpatch

 

논리식이나 분기문의 경우 처음에는 정확한 분기 목적지를 판단할 수 없으므로 분기 목적지를 결정하지 않고

분기 리스트에 저장한 후, 추후 적당한 레이블을 생성하여 분기 목적지인 레이블을 완성하는 것.

 

 

1. E → E1 or ME2

2. E → E1 and ME2

3. E → not E1

4. E → (E1)

5. E → id1 relop id2

6. E → true

7. E → false

8. M → ε

 

truelist, falselist

● true나 false에 대한 분기는 완성되지 않은 상태로 남아있으며, truelist 혹은 falselist에 저장된다.

● E → E1 and ME2에서

      ○ E1이 false이면 E도 false이므로 E1.falselist는 E.falselist에 포함된다.

      ○ E1이 true이면 E2도 검사해야 하므로 E1.truelist의 목적지는 E2에 의해 생성되는 코드의 시작부분이다.

● 이 목적지는 논터미널 M으로 구할 수 있으며, 생성규칙 M → ε 은 다음과 같은 의미 수행 규칙을 갖는다.

     {M.quad = nextquad}

 

backpatch(p, i)

● p 리스트에 있는 코드들의 목적지를 i로 설정한다.

 

makelist(i)

● 각 quad 문장 i를 포함하는 리스트를 생성 (GOTO라고 보면 편하다)

 

merge(i, j)

● i 리스트와 j 리스트를 병합

 

 

Example )

다음 논리식에 대한 주석 파스 트리를 만들고, 백패칭을 이용 하여 quadruple 코드로 만들어보자.

 

A ＜ B or C ＜ D and F ＜ G 

 

1. A < B 에 대한 논리식을 살펴보자.

100 if A < B GOTO _

101 GOTO _

이때, E.t = {100}, E.f = {101}, M.quad = {102} 가 된다.

 

2. C < D 에 대한 논리식을 살펴보자.

102 if C < D GOTO _

103 GOTO _

이때, E.t = {102}, E.f = {103}, M.quad = {104} 가 된다.

 

3. F < G 에 대한 논리식을 살펴보자.

104 if F < G GOTO _

105 GOTO _

이때, E.t = {104}, E.f = {105} 이다.

 

4. 위 문장을 나열하자.

100 if A < B GOTO _

101 GOTO _

102 if C < D GOTO _

103 GOTO _

104 if F < G GOTO _

105 GOTO _

 

5. 그 다음은 and가 or보다 순서가 빠르므로 C < D and F < G를 살펴본다.

    E -> E1 and E2 에서 backpatch(E1, falselist, M.quad) 를 만족한다.

    E1.t = {102} 이므로 102에 있는 문장의 분기 목표가 M.quad(104)가 되어 다음과 같이 된다.

 

102 if C < D GOTO 104

 

이어서 E.t = E2.t 이므로 E.t = {104} 가 된다.

또한 E.f = Merge(E1.f, E2.f)이므로 E.f = {103, 105} 가 된다.

따라서 다음과 같은 문장이 생성된다.

 

100 if A < B GOTO _

101 GOTO _

102 if C < D GOTO 104

103 GOTO _

104 if F < G GOTO _

105 GOTO _

 

6. 다음 순서로 A < B or M E로 E -> E1 or M E2 의 의미 분석 규칙에 의하면 backpatch(E1.f, M.quad) 에

    따라 E1.f = {101}, M.quad = {102} 이므로 다음과 같이 생성된다.

 

101 GOTO 102

 

E.t = merge(E1.t, E2.t) = {100, 104}

E.f = E2.f = {103, 105} 이므로 다음과 같다.

 

100 if A < B GOTO _

101 GOTO 102

102 if C < D GOTO 104

103 GOTO _

104 if F < G GOTO _

105 GOTO _