중간 언어

중간 코드(intermediate code)

- 구문 분석 단계에서 만들어진 구문 트리를 이용하여 생성되거나 한 문법 규칙이 감축될 때마다 구문 지시적 변역으로 생성이 이뤄짐

- 중간 코드를 생성하는데는 중간 언어를 사용

 

소스 프로그램 -> 컴파일러 전단부 -> 중간 코드 -> 컴파일러 후단부 -> 목적 코드

 

컴파일러 개발 초기에는 프로그래밍 언어 N개 목적 기계 M개이면 n*m개의 컴파일러 필요

-> 중간 언어의 필요성

 

UNCOL(universal compiler oriented language)의 개념,

N개의 언어를 위한 컴파일러 전단부와

M개의 기계를 위한 후단부를

공통된 가상 기계로 연결 시.. 이상적으론 N + M개의 컴파일러로 해결 가능

 

IL 사용의 장점

1. 소스 프로그램과 목적 기계의 특성에 독립적인 이식성 높은 컴파일러 개발 가능

2. 기계 독립적인 최적화를 수행하여 목적 기계 코드로 바뀐 상태에서 행하는 것보다 훨씬 효율적인 최적화

3. 인터프리티브 컴파일링 시스템에서 인터프리터를 이용해서 실행 가능

 

IL 사용의 단점

- 소스 프로그램을 직접 목적 기계 코드로 생성하는 것보다 컴파일 시간이 더 걸리고 비효율적인 목적 기계 코드를 생성

 

중간 코드를 생성하는 방법

- 중간 코드 생성기(intermediate code generator, ICG)를 이용하는 방법과 구문 지시적 번역(syntax-directed translation, SDT)로 나뉨

 

중간 코드 생성기

- 소스 프로그램에 대한 구문 분석기의 출력을 입력으로 받아 중간 언어를 생성하는 컴파일 과정의 단계

- 중간 코드 생성기는 파스 트리 또는 구문 트리를 순회하며 효과적인 중간 코드를 생성

 

구문 지시적 번역

- 문맥 자유 문법으로 표현되는 각 생성 규칙에 대해 부 프로그램이나 의미 수행 코드를 기술하고, 의미 수행 코드는 구문 분석기에 의해 호출되어 실행

 

중간 언어의 종류

- 폴란드식 표기법, 역폴란드식 표기법 -> 전위 표기법, 후위 표기법

- 3-주소 코드 -> Triple, 간접 triple, Quadruple

- 트리 구조 코드 -> AST

- 가상 기계 코드  -> P-코드, 바이트 코드

 

후위 표기법(역폴란드식 표기법)

- 중간 언어로 가장 오래된 것 중 하나

- 산술식에서 피연산자가 연산자보다 먼저 나오는 형태

- 코드를 이동할 수 없어 최적화에는 부적합한 형태

 

A = B * C + D / E

가 ABC*DE/+=이 됨

 

연산자 중 순위가 가장 낮은 연산자를 중심 연산자라 함

중심 연산자를 부모 노드에 놓고 왼쪽 부분을 왼쪽 서브 트리, 오른쪽 부분은 오른쪽 서브 트리로

이를 재귀적으로 만들면 트리 구조로 됨

 

이렇게 트리 구조로 만들어놓고

전위 순회(루트->왼->오) 

후위 순회(왼->오->루트)

중위 순회(왼->루트->오)

로 순회하면 해당하는 표기법이 됨

 

 

3-주소 코드

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

- 레지스터 기반 목적 기계 코드로의 변환이 편리하여 상용 컴파일러에서 가장 많이 사용

- 치환 연산자의 오른쪽 부분이 1개의 단항, 이항 또는 논리 연산자와 피연산자로 구성

- 왼쪽 부분은 식별자 또는 주소를 표현하여 하나의 코드 내에서 3개의 주소를 나타내는 형식의 중간 코드

 

일반적인 3-주소 코드

- A = B op C

- 피연산자인 A, B, C는 식별자, 상수 또는 컴파일러가 내부적으로 생성한 임시 변수

- 연산자인 op는 단항 및 이항 산술 연산자 또는 논리 연산자

 

예시

A = B op C

A = op C

A = B

GOTO L 형식의 무조건 분기문

if A relop B GOTO L과 같은 조건 분기문

- 여기서 A와 B는 관계 연산자(relop)의 피연산자

등..

 

3-주소 코드로 표현하기

치환문 A = -B * (C + D)

풀이

T1 = -B

T2 = C + D

T3 = T1 * T2

A = T3

 

실제 구현을 위해선 triple, quadruple, 간접 triple 표현 방법 등을 사용

- triple은 결과값을 저장하는 피연산자가 존재하지 않음

- quadruple은 결과 값을 저장하는 피연산자가 존재

- 간접 triple 표현 방법은 triple 방법에서 코드 이동 시 발생하는 단점을 보완

 

Triple 표현 방법

- 하나의 기본 연산: <연산자> <피연산자-1> <피연산자-2> 세 개의 필드로 구성

- 임시 변수가 기호표에 들어가는 것을 피하기 위해 순서에 따라 번호가 부여, triple의 결과는 번호에 할당

- 최적화에서 발생하는 코드 이동 시 triple 코드의 피연산자 도한 바꿔야 하니 최적화에 부적합

 

간접 Triple 표현 방법

- 수행 순서를 별도의 표에 저장하여 코드 최적화 시 표 순서만 변경하고 원래의 triple은 변경 안하는 거

- 최적화 때문

 

quadruple 표현 방법

- <op> <피연산자-1> <피연산자-2> <결과>와 같은 4개의 필드

- 결과는 <op> 연산의 결과를 저장하고 일반적으로 임시 변수가 사용, 실제로 목적 기계 코드 생성 시 목적 기계의 레지스터 혹은 메모리에 배정

- 코드 이동이 편리해서 최적화에 적합하나 많은 임시 변수를 관리해야 함

 

예시

A = B + C * D / E

F = C * D

triple		간접 triple		quadruple
[0]	<*, C, D>	1.[0]	[0]<*, C, D>	<*, C, D, T1>
[1]	</, [0], F>	2.[1]	[1]</, [0], F>	</, T1, E, T2>
[2]	<+, B, [1]>	3.[2]	[2]<+. B, [1]>	<+, B, T2, T3>
[3]	<=, A, [2]>	4.[3]	[3]<=, A, [2]>	<=, T3, A>
[4]	<*, C, D>	5.[0]	[4]<=, F, [0]>	<*, C, D, T4>
[5]	<=, F, [4]>	6.[4]		<=, T4, F>

* 6.[4]는 6번째로 실행되는데 실제 참조 트리플은 4번이라는 뜻

 

 

트리 구조 코드

- 소스 프로그램을 시각적으로 표현할 수 있는 방법

- 코드의 특성 상 손쉽게 재구성이 가능하여 최적화 컴파일러의 IL로 가장 적합

 

표현 방법

파스 트리

- 구성하는 과정은 구문 분석 과정에서 문법 지시적인 방법으로 손쉽게 이루어지나 불필요한 중복된 정보를 너무 많이 내포

- 시간이 많이 걸리고 메모리의 낭비를 초래하여 IL로 부적합

 

추상 구문 트리(Abstract Syntax Tree)

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

- 상수 또는 변수를 나타내는 터미널 노드와 연산자를 나타내는 논터미널 노드로 구성

- 연산자의 피연산자들이 자식 노드로 연결되는 서브 트리를 구성 

 

 

가상 기계 코드

- 최근에는 컴파일러를 소스 언어에만 관계된 전단부와, 목적 기계에만 관계된 후반부로 분리

- 인터페이스로 이 사이를 연결하여 쉽게 이식되고 재목적이 가능한 컴파일러를 제작

- 재목적 컴파일러(retargetable compiler), 컴파일러를 한 기계에서 다른 기계로 이식하는 문제를 이렇게 후단부만 변경하여 쉽게 해결 가능함

- 가상 기계는 컴퓨팅 환경을 소프트웨어로 구현한 것

 

가상 기계의 설계

- 소스 언어의 기본 연산과 자료 모드에 근거

- 기본 연산은 소스 프로그램을 구성하는 가장 간단하고 대부분인, 직접적인 연산에 대응

- 기본적인 자료 모드는 소스 언어의 가장 간단한 형

- 기본적인 모드와 연산들이 가상 머신의 명령어를 결정

* 실제 컴퓨터에 효율적으로 설치 가능한지 여부도 고려

 

P-코드

- 별도의 컴파일러가 없어도 p-코드 인터프리터만 있으면 프로그램을 간단히 실행 가능

- 단, 목적 코드로 번역되는 한 단계가 추가되므로 실행 시간이 느리다는 단점

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

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

- 프로그램 계수기(PC), 스택 포인터, 극단 포인터, 뉴 포인터, 마크 포인터

 

극단 포인터가 뉴 포인터보다 커지면 그 계의 메모리가 모두 사용되었다는 것

 

종류 및 기능은 다음과 같다

- 프로그램 계수기(PC) : 코드 지역에서 현재 명령어의 위치를 가리킴

- 스택 포인터(SP) : 스택의 톱

- 마크 포인터(MP) : 활성 스택 프레임의 시작

- 극단 포인터(EP) : 현재 사용할 수 있는 가장 큰 스택의 위치

- 뉴 포인터(NP) : 힙의 톱

 

바이트코드

- 자바에서 지원하는 중간 언어, 스택 기반 가상 기계 코드

 

자바 컴파일러

- 자바 프로그램을 입력으로 받아 플랫폼에 독립적인 JVM 상에서 동작하는 명령어 집합인 바이트 코드를 생성

- 바이트코드는 이기종 간 실행 환경애 적합하도록 설계되어 이식성과 유연성이 좋음

- 인터프리터 방식과 JIT 컴파일러 방식에 의해 실행, 확장자는 .Class

 

바이트 코드에서 하나의 명령어 형식은 연산 코드(operation code) 부분과 연산 코드에 따라 여러 개의 피연산자 부분으로 구성

햔재 바이트코드는 230개의 명령어로 구성

 

바이트코드만의 특징

1. 네트워크 상에서 전송 효율을 위해 코드를 가능한 한 작고 간결하게 설계

2. 자바 언어의 기능을 반영하는 명령어가 존재. 특히 배열, 클래스, 예외, 스레드를 직접 다루는 명령어

3. 자료형에 따라 명령어가 각기 따로 존재. 예를 들어 iadd는 int 덧셈, fadd는 flaot 덧셈

4. 복합 기능을 가진 명령어를 제공. pop2는 스택에서 연속 두번 삭제