제9장 중간 언어

컴파일러 구성론

강 승 식

9.1 소개

초기의 컴파일러

: one-pass 컴파일러로서 중간코드 생산 없이 직접 목적 코드로 번역

중간코드 사용의 장점

(1) 기능적으로 독립적인 여러 모듈들로 구성 가능

(2) 컴파일러 자체의 portability 증가

(3) 고급 언어와 목적 코드 간의 의미적인 차이를 이어 주는 교량 역할

: 번역 과정이 좀더 쉽게 표현되고 효율적임

(4) 기계와 독립적인 최적화

(5) 인터프리터를 이용하여 실행 가능 : JVM

중간코드 사용의 단점

compile 시간이 더 많이 소요되고 비효율적인 코드 생산

: 최적화를 통해 극복

중간언어의 유형

1. Polish 표기법

infix, prefix, postfix 표기법

2. 3-주소 표기법(N-tuple 표기법)

Triple, Quadruple, Indirect Triple

3. Tree 구조 코드

AST, TCOL, Diana

4. 가상 기계 코드

P-코드, EM-코드, U-코드, 바이트 코드

9.2 Polish 표기법

예1) 산술식 A=B+C*D/E

postfix : ABCD*E/+=

prefix  : =+/E*DCBA

예2) if a then if c-d then a+c else a*c else a+b

postfix : a L1 BZ c d - L2 BZ a c + L3 BR

L2: a c * L3 BR L1: a b + L3:

※ BZ(Branch Zero) --- 조건값이 0이면 선행 label로 분기

BR(무조건 분기) --- 선행 label로 무조건 분기(unconditional branch)

9.3 3-주소 표기법

예4) a = b * (c + d) 에 대한 3-주소 표기법의 예

(t1 := c + d)

(t2 := b * t1)

(a := t2)

∙ 상용 compiler에서 가장 널리 사용되는 표기법

: 특히, 최적화 compiler에서 많이 사용.

∙ 중간 코드를 한 개의 연산자와 그에 해당하는 피연산자들의 tuple형태로 정의

(operator, operand1, operand2, ..., operandn-1)

1. triple 코드 : (연산자, 피연산자1, 피연산자2)

- 각 triple들은 순서대로 numbering되어 연산결과는 그 triple 번호로 저장

최적화할 때 발생하는 코드의 이동으로 triple 코드의 피연산자를 변경해야.

2. quadruple 코드 : (연산자, 피연산자1, 피연산자2, 연산결과)

3. indirect triple 코드 : triple 코드 최적화시의 단점 보완

- triple 코드의 실행 순서를 별도로 테이블화함.

- 최적화시에 테이블의 순서만 변경하고 원래의 triple 코드는 변경하지 않음.

예5) 다음 치환문을 세 가지 표기법으로 나타낸 예

a = b + c * d / e;

f = c * d;

quadruple	triple	indirect triple
		operations	triples
(*, c, d, t1) (/, t1, e, t2) (+, b, t2, t3) (=, t3, a) (*, c, d, t4) (= t4, f)	1. (*, c, d) 2. (/, (1), e) 3. (+, b, (2)) 4. (=, a, (3)) 5. (*, c, d) 6. (=, f, (5))	1. (1) 2. (2) 3. (3) 4. (4) 5. (5) 6. (6)	1. (*, c, d) 2. (/, (1), e) 3. (+, b, (2)) 4. (=, a, (3)) 5. (=, f, (1))

예6) 아래 C 언어에 대한 quadruple 표현

int a, b; float x; ...; x = a + b;

(addi a, b, t1)

(float, t1, , t2)

(set, x, t2)

※ GNU(Gnu is Not Unix) C/C++ 컴파일러

: RTL(Register Transfer Language) 표기법

⇒ N-tuple 표기법에 속함 ( 내부 표현은 tree형태 )

⇒ 파스 트리를 traverse하면서 생성

⇒ 의미 분석 결과를 반영하고, 변수도 base와 offset로 표현

예7) <예6>의 문장에 대한 RTL 표기법

int a, b; float x; ...; x = a + b;

(set (reg:SI 69) (mem:SI (plus:SI (reg:SI 65) (const_int -4))))

(set (reg:SI 70) (mem:SI (plus:SI (reg:SI 65) (const_int -8))))

(set (reg:SI 68) (plus:SI (reg:SI 69) (reg:SI 70)))

(set (mem:SF (plus:SI (reg:SI 65) (const_int -12)))

(float:SF (reg:SI 68)))

- base register : 65,   정수상수: offset

- SI(Single Integer), SF(Single Float) --- machine mode

- a, b를 각각 레지스터 69, 70에 load한 후에 레지스터 68에 저장,

레지스터 68을 실수로 변환하여 x에 저장

9.4 Tree 구조 코드

① 구문 tree ( AST: Abstract Syntax Tree )

최근에 compiler project의 전반부에서 parsing단계와 의미분석 단계를 연결하는 중간 코드로 사용

② TCOL ( Tree-structured COmmon Language )

- CMU에서 수행한 컴파일러-컴파일러 project인 PQCC에서 사용한 중간언어

- AST의 변형 : 역참조(dereferencing), 형변환(type conversion), 형에 따른 연산자 정보 포함

※ AST가 고급언어에 가까운 반면, TCOL은 중간 level이다.

③ Diana ( Descriptive Intermediate Attributed Notation for Ada )

- 컴파일러의 전반부와 후반부 사이의 정보 교환에 적당하게 설계된

Ada 프로그램의 중간 형태  ⇒  attributed parse tree 형태

- Diana의 attribute : 어휘적 속성, 구조적 속성, 의미적 속성, 코드 속성

예 8) AST 표현 예

{	x = 0;

z = z + 2 * y;

while ((x < n) && (v[x] != z)) x = x + 1;

return x;

}

예 9) 아래 C 언어 문장에 대한 AST와 TCOL

int a; float b;

...

b = a + 1;

예 10) 아래 문장에 대한 TCOL

{	int x, y, n;

float v, z;

x = 0;

z = z + 2 * y;

while ((x < n) && (v[x] != z)) x = x + 1;

return x;

}

9.5 가상 기계 코드 ( Abstract Machine Code )

∙ 컴파일러의 이식성 문제  ⇒  portable & adaptable compiler 구현 추세

- 1개의 언어에 대해서 N개의 machine에 구현

- compiler를 목적 기계와 무관한 부분(전반부)과 목적 기계와 관련된 부분

(후반부)으로 분리

- 모든 연산은 stack machine에 근거를 두고 있음

- P-코드, EM-코드, U-코드 등

9.5.1 P-코드

- pascal 컴파일러 제작에 사용된 중간 언어

- P-machine : P-코드에 대한 추상기계로 hypothetical stack machine

(가상스택기계)

9.5.2 EM(Experimental Machine)-코드

Algol-like 원시언어와 byte machine 형태의 목적 기계에 적합한

추상 기계 설정

9.5.3 U-코드

P-코드에서 코드 최적화 기능을 높이기 위해 확장된 중간언어

U-코드 명령어

1. 단일 명령어 : notop, neg

2. 이진 명령어 : add, sub, mult, divop, modop, swp,

andop, orop, gt, lt, ge, le, eq, ne

3. stack 운영  : lod, str, ldc, ldr

4. 제어 흐름   : ujp, tjp, fjp

5. 범위 검사   : chkh, chkl

6. 간접 주소   : ixa, sta

7. 프로시저 명령 : cal, ret, l에, proc, endop

8. 기타 : bgn, sym

예 11) x = a + b *100;을 U-코드로 표현

lod	1 1	/* a */

lod	1 2	/* b */

ldc	100

mult	/* multiplication */

add

str	1 4	/* x */

예 12) if (a > b) a = a + b;를 U-코드로 표현

lod	1 1	/* a */

lod	1 2	/* b */

gt

fjp	next

lod	1 1	/* a */

lod	1 2	/* b */

add

str	1 1	/* a */

next ...

예 13) a[i] = j;를 U-코드로 표현

lod	Bi Oi	/* index i */

ldr	Ba Oa	/* 배열 a의 주소 */

add

lod	Bj Oj	/* load j */

sta	/* stack의 top에 있는 내용을 top-1의 주소에 저장하고 top-- */

9.5.4 바이트 코드

- Java의 중간 언어 코드 : stack 기반의 가상 기계 코드

- JVM(Java Virtual Machine)의 명령어 집합

- 이 기종간의 실행 환경에 적합하도록 설계되어 이식성과 유연성이 좋음

- 인터프리터 방식과 JIT(Just-In-Time) 컴파일러 방식으로 실행

[표 9.1] 바이트 코드의 분류

분류	개수	명령어
수치 연산 명령어	24	iadd, ladd, fadd, dadd, isub, ...
논리 연산 명령어	12	iand, land, ior, ishl, ishr, ...
데이터 형 변환 명령어	15	i2l, i2f, i2d, l2i, ...
상수 관련 명령어	20	bipush, idc, iconst_0, ...
스택 운영 명령어	9	pop, pop2, dup, ...
제어 명령어	28	goto, ifne, jsr, ret, ...
지역변수 조작 명령어	52	iload, istore, ..., aload, astore
배열 조작 명령어	17	aaload, aastore, bastore, ...
객체 및 배열 생성 명령어	4	new, newarray, ...
객체 조작 명령어	6	getfield, getstatic, ...
메소드 호출 명령어	10	invokevirtual, areturn, ...
기타 명령어	5	throw, monitorenter, monitorexit, ...

예 15) [예6]의 문장을 바이트 코드로 표현한 예

제10장 중간 언어의 생성

∙ syntax tree와 semantic tree : 1-to-1 mapping

예1) 생성규칙과 의미규칙의 mapping 예

생성규칙	의미규칙
L→E$ E→E1+T E→T T→T1*F T→F F→(E) F→digit	print(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val*F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval

예2) <예1>의 생성규칙을 단위 프로그램으로 변환 예

생성규칙	단위 프로그램
L→E$ E→E1+T E→T T→T1*F T→F F→(E) F→digit	print VAL[TOP] VAL[TOP-2]:=VAL[TOP-2]+VAL[TOP] none VAL[TOP-2]:=VAL[TOP-2]*VAL[TOP] none VAL[TOP-2]:=VAL[TOP-1] VAL[TOP]:=LEXVAL

예3) if a>b then x:=a else x:=b; 에 대한 Abstract Syntax Tree

예5) 다음 프로그램에 대한 AST와 생성된 코드

init := 10;

value := init + 20 * 2;

예6) mini-pascal에서 배열의 선언과 참조 예

예7) 논리식 a or b and not c 에 대한 U-코드 예

예8) 관계식 a >= b+1 에 대한 AST와 U-코드

예9) if a > max then max := a; 에 대한 AST와 생성된 코드

예10) while문에 대한 AST와 생성된 코드

예11) procedure 정의와 호출문에 대한 U-코드 프로그램

※ U-코드 번역기

제11장 코드 최적화

11.1 기본 block

∙ block이란?

block의 시작과 끝을 제외하고는 block의 내부 또는 외부로 분기가

발생하지 않는 code의 분할 단위

“기본 블록은 leader와 다음 leader 이전에 나타나는 모든 코드들로 구성”

[정의 11.2] 다음 조건을 만족하는 문장을 leader라 한다.

(1) 프로그램의 시작 문장

(2) 조건부 분기 또는 무조건 분기의 목적지에 있는 문장

(3) 조건부 분기 바로 다음에 위치하는 문장

[예] for문에 대한 block 단위 구분

for (i = 0; i < N; i++)

statement1;

statement2;

i = 0;	← 프로그램의 시작

goto L2;

L1:	statement1;	← 분기의 목적지

i++;

L2:	if (i < N) goto L1;	← 분기의 목적지

statement2;	← 조건부 분기문의 다음 문장

※ for문의 flow graph

initial

↓

Block1

↓

Block3  ↔  Block2

↓

Block4

예 1) Bubble sort 프로그램을 기본 블록 단위로 구분하고 흐름 그래프를 작성

for (i = 0; i < N; i++)

for (j = i+1; j < i; j++)

if (a[j] > a[j+1]) {

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

}

1) 기본 블록

i = 0;	← B1

goto iTest;

-----------------------------------

iLoop: j = 0;	← B2

goto jTest;

-----------------------------------

jLoop: t1 = 4 * j;	← B3

t2 = a[t1];

t3 = j + 1;

t4 = 4 * t3;

t5 = a[t4];

if (t2 <= t5) goto jPlus;

-----------------------------------

t6 = 4 * j;	← B4

temp = a[t6];

t7 = j + 1;

t8 = 4 * t7;

t9 = a[t8];

a[t10] = t9;

t11 = j + 1;

t12 = 4 * t11;

a[t12] = temp;

-----------------------------------

jPlus:  j++;	← B5

-----------------------------------

jTest: if (j < i) goto jLoop;	← B6

-----------------------------------

iPlus: i++;	← B7

-----------------------------------

iTest: if (i < N) goto iLoop	← B8

2) 흐름 그래프

11.2 지역 최적화 ( local optimization )

① 공통 부분식 제거 ( common subexpression elimination )

a = b + c + d;

e = b + c + f;

k = (b + c) * g;

⇒

t = b + c;

a = t + d;

e = t + f;

k = t * g;

② Strength Reduction

a = x ^ 2;   ⇒  a = x * x;

y = 3 * a;   ⇒  y = a + a + a;

x = a / 5;   ⇒  x = a * 0.2;

x = a / 4;   ⇒  x = a >> 2;

③ 상수 폴딩(constant folding)과 상수 전파(constant propagation)

- constant folding : compile-time에 상수식을 직접 계산하여 사용하는 것

<예> x = a + 2 * 3; 에서 2*3을 컴파일시에 계산하여

x = a + 6; 으로 변환.

- constant propagation : 고정된 값을 갖는 변수를 상수로 대치하는 것

<예> i = 2; ......; t1 = 4*i;   ⇒  i = 2; ......; t1 = 4*2;

④ 대수학적 간소화 ( algebraic simplification )

x = a + 0;   ⇒   x = a;

x = 1 * a;   ⇒   x = a;

constant * symbol   ⇒   symbol * constant

t1 = 4 * j - 1;	t1 = 4 * j - 1;

......	⇒   ......

t7 = t1 + 1;	t7 = 4 * j;

11.3 루프 최적화 ( loop optimization )

① Loop invariant ( loop 불변 코드 )

for (i=0; i < N; i++)

c[i] = 2 * (p-q) * (n-i+1) / (sqr(n) + n);

⇒

t1 = 2 * (p-q);

t2 = n+1;

t3 = sqr(n) + n;

for (i=0; i < N; i++)

c[i] = t1 * (t1-i) / t3;

② Strength reduction

for (i=0; i < N; i++)

sum = sum + a[i];

※ 위 for문에서 offset 계산시에 곱셈 대신에 덧셈으로 처리

i = 1;

loop:

if (i >= N) then goto exit;

...

t1 = 4 * i;	→	t1 = t1 + 4;

t2 = a[t1];

...

goto loop;

exit:

③ Loop unrolling

for (i=0; i < N; i++)

a[i] := 0;

⇒

for (i=0; i < N; i+=2) {

a[i] = 0;

a[i+1] = 0;

}

④ 루프 융합 ( loop fusion )

ꠐ	for (i = 0; i < N; i++) {

for (i = 0; i < N; i++) a[i] = 0;	ꠐ	a[i] = 0;

for (i = 0; i < N; i++) b[i] = x[i] + y;   ꠐ	b[i] = x[i] + y;

ꠐ	}

⑤ 영으로의 count ( count up to zero )

for (i = 0; i < n; i++) {	ꠐ	for (i = N-1; i >= 0; i--) {

⋯ i ⋯	/* a[i] = 0; */	ꠐ            ⋯ n-i+1 ⋯	/* a[i] = 0; */

}	ꠐ	}

11.4 전역 최적화 ( global optimization )

① 공통 부분식 제거

block간에 나타나는 전역변수에 대한 공통 부분식 제거

② 전역 상수 folding과 propagation

기본 블록 이전에 상수값으로 주어진 값을 미리 계산

a = 1;

b = 2;

...

t = a * b;	→	t = 2;

if (t == 2) ...	→	if (2 = 2) ...

③ Unreachable code의 제거

i = 2;

if ( i == 2 ) {

.....

} else {

.....

}

④ 조건문의 재구성

if ( x > 1 )	ꠐ

;            ꠐ    if ( x <= 1) {

else {          ꠐ	A;

A;           ꠐ    }

}               ꠐ

⑤ 연속 GOTO의 축약

goto labelA;      ꠐ	goto labelB;

......          ꠐ	......

labelA: goto labelB;      ꠐ   labelA: goto labelB;

11.5 기계 종속적 최적화

① 중복된 load 명령 제거

원시 program:	실행 코드:

LOAD   R1, Y

x = y;	STORE  R1, X

z = x + 1;	LOAD   R1, X

ADD    R1, 1

STORE  R1, Z

② 효율적인 명령어 선택

LOAD	R1, I

i = i + 1;	ADD	R1, 1

STORE	R1, I

※ inc 명령이 있다면 3개의 명령을 1개로 줄일 수 있다.

③ register 할당

register의 수는 모든 변수를 수용할 수 없으므로 효율적으로 활용.

④ 연산 순서 : 적은 수의 register를 사용하도록 연산 순서 조정

⑤ Peephole optimization

- peephole --- 목적 코드를 관찰하는 작은 window

- 목적 코드를 부분적으로 관찰하면서 최적화 수행

제12장 symbol table

symbol들에 관한 정보를 관리하는데 사용되는 자료구조

12.1 symbol table의 기능

어휘 분석 단계에서 인식되는 명칭(변수, 함수)들에 대해서 그 속성 수집

⇒ parsing, 의미 분석, 코드 생성시에 활용

12.2 symbol table의 내용

(1) symbol name

(2) symbol type

(3) scope level

(4) offset ( 상대주소 )

(5) 배열의 차원수

(6) 기타 속성들

※ symbol table의 일반적인 형태

name	type	level	offset	차원수	기타 속성들
first cnt def and ptr stk mid	2 1 2 2 1 1 1	0 0 0 1 1 1 1	0 8 12 0 40 44 64	0 0 0 2 0 1 0

※ name string들을 string pool에 저장하여 memory 절약하는 방법

name		attributes
index	length	type	level	offset	others
0 5 8 ...	5 3 3 ...

string pool:

firstcntdefandptrstkmid...

12.3 symbol table의 운영

symbol의 삽입, 삭제, 검색

12.4 symbol table의 구성

(1) unsorted symbol table

linear search

(2) sorted symbol table

binary search

(3) tree-structured symbol table

(4) hash table

12.5 블록구조 언어에 대한 symbol table

stack 구조로 구현

제13장 에러 처리

13.1 에러의 종류

• Error 발생 원인

1. 프로그램의 설계 명세서(design spec.) 오류

2. 부적합한 알고리즘 사용

3. 알고리즘을 잘못 구현했거나 언어를 잘못 선택

4. 프로그램의 입력 오류 : typing error

5. program이 compiler나 기계의 한계를 벗어난 경우

• parsing 단계에서 나타나는 일반적인 error

1. 괄호가 빠진 경우 --- 왼쪽 괄호와 오른쪽 괄호의 개수가 다른 경우

2. 불필요한 comma의 삽입

3. semicolon과 colon의 잘못 사용

4. keyword를 틀리게 쓴 경우 : swtich

5. 불필요한 blank가 삽입된 경우 : /* comment * /

※ C 언어에서 --- 조건식의 동등 비교를 ‘=’로 사용한 경우

13.2 에러 탐지 및 보고

• 효과적인 debugging을 위해서 자세하고 완벽한 error message를 출력해야 함.

1. error message는 소스 program의 입장에서 error를 지적해야 한다.

2. 프로그래머가 이해하기 쉬워야 한다.

3. 문제를 국소화하여 에러를 자세히 지적해야 한다.

4. 중복된 error message를 출력하지 않아야 한다.

13.3 단계별 오류 처리

13.3.1 어휘 분석 단계  ⇒  lexical error

철자 오류 발견 -- minimum-distance matching을 이용하여 철자를 수정함으로써 부가되는 오류를 피할 수 있다.

예1) Fortran 문장

IF문이 길어 두 개 라인으로 구성하려고 했는데

문장 연속 문자 ‘1’을 8번째 칸에 잘못 썼을 경우(7번째 칸에 써야 함)

IF (long condition .OR. X

1.LT. Y) GOTO 30

연산자 “.GE.”를 “.EG.”로 잘못 쓴 경우 --> 가장 비슷한 것으로 인식

13.3.2 parsing 단계  ⇒  syntax error

- 대부분의 오류가 parsing 단계에서 발생

- 발견된 오류를 복구(error recovery)하고 parsing을 계속한다.

예) 7장 [예14]의 파싱표를 이용하여 (id + ) * id 를 파싱할 때

예2) 에러 처리 루틴을 포함한 LL 파싱 : 그림 13.2, 13.3

e1: id나 좌측 괄호로 시작하는 오퍼런드가 와야 하는데 연산자나 우측괄호 혹은

입력의 끝이 발견되었을 경우

처리방법: 입력에 id를 넣는다

메 시 지: Missing operand

e2: 스택의 top에 우측괄호가 있으나 입력에 나타나지 않을 경우

처리방법: 스택으로부터 우측괄호를 pop한다.

메 시 지: Missing right parenthesis

e3: 입력은 남아 있으나, 스택이 empty인 경우

처리방법: 입력에 남아 있는 모든 심벌을 제거한다.

메 시 지: Unexpected 현재 입력 심벌

예3) 에러 처리 루틴을 포함한 LR 파싱 : 그림 13.4, 13.5, 13.6

E -> E + E | E * E | ( E ) | id

e1: operand, 즉 id 혹은 좌측괄호가 기대되는 상태 0,2,4,5에서 +, * 혹은

입력의 끝이 발견되었을 때

처리방법: 가상의 id를 스택에 넣고 상태를 3으로 한다. 이것은 0,2,4,5

상태에서 id에 대한 goto 행동을 한 것과 같은 상태이다.

메 시 지: Missing operand

e2: 상태 0,1,2,4,5에서 우측괄호를 만났을 때

처리방법: 다음 입력 심벌인 우측괄호를 제거한다.

메 시 지: Unbalanced right parenthesis

e3: 연산자 혹은 우측괄호가 기대되는 상태 6과 연산자가 기대되는 상태 1에서

id나 좌측괄호가 나오는 경우

처리방법: 스택에 +를 넣고 상태는 4로 만든다.

메 시 지: Missing operator

e4: 상태 6에서 연산자나 우측괄호가 나와야 하는데 입력의 끝을 만나는 경우

처리방법: 스택에 우측괄호를 넣고 상태를 9로 놓는다.

메 시 지: Missing right parenthesis

- 입력 스트링 “id + )” 의 파싱 과정

※ 오류 복구 방법 : panic mode

(1) semicolon이나 end와 같은 delimiter 혹은 문법에서 정의한 synchronizing

token을 만날 때까지 input symbol을 무시한다.

(2) parsing을 계속할 수 있도록 stack의 내용을 조정한다.

13.3.3 의미 분석 단계  ⇒  semantic error 또는 logical error

- 문법적으로 오류가 없으나 의미가 틀린 error

- 실행은 되지만 결과가 틀린 경우

예) 파스칼의 아래 문장에서 A, B, C의 type이 다른 경우

A := B + C;

제14장 컴파일러 자동화 도구

14.1 scanner 생성기 : LEX

LEX 구현 단계

① 정규표현의 인식

② 정규표현을 NFA로 변환

③ NFA를 DFA로 변환

④ DFA의 상태수 최소화

14.2 parser 생성기

(1) YACC --- Bell Lab의 Stephen Johnson, LR parsing

(2) 스탠포드 PGS --- LALR(1) parsing

(3) 위스콘신 PGS --- LALR(1) parsing

- SCANGEN(SCANner GENerator) : 어휘분석기

- ECP(an Error Correcting Parser generator)

14.3 코드 생성의 자동화

(1) 해석적 코드 생성 방식 ( interpretative code generation )

가상기계에 대한 code를 생성한 후에 목적 기계에 대한 code의 생성은

macro 확장이나 schema를 이용한다.

(2) 패턴 일치 코드 생성 방식 ( pattern-matched code generation )

target 명령어 집합을 pattern tree 형태로 수록하여

일치되는 tree에 대한 code를 자동으로 생성

(3) table을 이용한 코드 생성 방식

목적 기계에 대한 기계 표현을 받아들여 LR 파싱 알고리즘에 기초를 둔

이론을 적용하여 code 생성에 필요한 table을 생성

14.4 컴파일러-컴파일러 시스템

컴파일러를 구현하는 전 과정을 자동화 --- PQCC, ACK system