개요

컴파일러의 중간 언어와 중간 코드 생성에 대해 알아본다. 이 글은 내공 있는 프로그래머로 길러주는 컴파일러의 이해의 내용을 기반으로 함을 미리 밝힌다. 책 내용이 괜찮으니 관심있으신 분들은 사보는것을 추천한다.(필자는 이해관계자는 아님을 밝힌다.)

목차

컴파일러 강의 다른 포스팅은 아래의 링크를 참고하자.

학습목표

  • 중간 언어
  • 구문 지시적 번역
  • 중간 코드 생성

중간 언어

  • 중간 언어의 개념

    • 중간코드는 구문 분석 단계에서 만들어진 구문트리를 이용하여 생성되거나, 한 문법 규칙이 감출될 때마다 구문 지시적 번역으로 생성이 이뤄진다. 중간 코드를 생성하는데는 중간언어를 사용한다.

  • 아래와 같이 중간코드를 통해 M(전단부) * N(후단부)대신 M + N개의 컴파일러로 해결할 수 있다.

중간언어의 장단점

  • 장점
    • 기계 독립적인 이식성 높은 컴파일러
    • 기계 독립적인 최적화
    • 인터프리터를 이용하여 실행할 수 있는 장점
  • 단점
    • 단계가 하나 더있으므로 상대적으로 컴파일 시간이 더 소모

중간 코드를 생성하는 방법

  • 중간코드 생성기

  • 구문 지시적 번역

중간 언어의 종류: 후위 표기법

  • 후위 표기법에
  • Triple, 간접 Triple, Quadruple
  • 구문 트리

  • P-코드, 바이트코드

  • 후위 표기법

    • 피연산자가 연산자보다 먼저 나오는 형태
    • 코드를 이동할 수 없으므로 최적화에 부적합한 형태

후위표기법 예제

트리 순회 방법

  • preorder
  • postorder
  • inorder
  • 위 예제의 inorder는?
    • postorder : ABC * DE / + =
    • inorder : A = B * C + D / E

3-주소 코드

  • 코드 재구성이 편리하여 코드 최적화에 적합
  • 레지스터 기반 목적 기계코드 변환이 편리해 상용 컴파일러에서 가장 많이 사용
  • 치환 연산자의 오른쪽 부분이 1개의 단항, 이항 또는 논리 연산자와 피연산자로 구성되고, 치환 연산자의 왼쪽 부분은 식별자 또는 주소를 표현하여 하나의 코드 내에서 3개의 주소를 나타내는 형식의 중간 코드

3-주소 코드 예제

3-주소 코드 표현 예제

  • 3주소 코드를 실제 컴파일러에서 구현하는 방법
    • Triple : 결과값을 저장하는 피연산자가 존재하지 않음
    • Quadruple : 결과값을 저장하는 피연산자가 존재
    • 간접 Triple : Triple에서 코드 이동시 발생하는 단점을 보완

Triple 표현 방법

간접 Triple 표현 방법

Quadruple 표현 방법

Triple/간접 Triple/Quadruple 비교

트리구조 코드

  • 소스 프로그램의 의미를 보다 시각적으로 표현가능
  • 코드의 특성상 손쉽게 재구성이 가능하므로 최적화 컴파일러의 IL로 가장 적합한 표현
  • 트리구조 표현 방법
    • 파스트리
    • 구문 분석을 하는 데 시간이 많이 걸리고 메모리의 낭비를 초래한다는 것 때문에 IL로는 부적당
    • 구문트리
    • 파스 트리에서 의미 없는 논터미널을 제거하고 의미 있는 정보만을 트리 구조로 표현한 구문 트리(Syntax Tree)를 사용
    • 구문 트리는 상수 또는 변수를 나타내는 터미널 노드와 연산자를 나타내는 논터미널 노드로 구성되며, 연산자의 피연산자들이 자식 노드로 연결되는 부분 트리를 구성

파스트리/구문트리 예제

가상 기계 코드

  • 최근에는 컴파일러를 소스 언어에만 관계된 전단부와 목적 기계에만 관계된 후단부로 분리 하고, 잘 정의된 인터페이스를 사용하여 이 사이를 연결함으로 써 쉽게 이식되고 재목적이 가능한 컴파일러를 제작하는 추
  • 이와 같은 방법으로 만든 컴파일러를 재목적 컴파일러(retargetable compiler)라 하는데, 컴파일러를 한 기계에서 다른 기계로 이식하는 문제를 이렇게 후단부만 변경함으로써 쉽게 해결

P-코드

  • p-코드는 컴퓨터에 별도의 컴파일러가 없어도 p-코드 인터프리터만 있으면 프로그램을 간단히 실행시킬 수 있다. 하지만 목적 코드로 번역되는 한 단계가 추가되므로 실행 시간이 느리다는 것이 단점

바이트코드

  • 바이트코드는 이기종 간의 실행 환경에 적합하도록 설계되어 이식성과 유연성이 좋고, 인터프리터 방식과 JIT( just-in-time) 컴파일러 방식에 의해 실행

구문 지시적 번역

  • 각 생성규칙에 해당하는 의미 수행코드를 직접 기술
  • 변수값 계산, 중간코드 생성, 에러 메세지 출력, 기호표 삽입
  • 의미수행코드

  • 예를 들아 다음과 같은 생성 규칙과 의미규칙이 있다고 가정하자
    • $ E -> E_1 + E_2$, {$E.VAL = E_1.VAL + E_2.VAL$ }
    • 중괄호전은 생성 규칙
    • 중괄호 뒤는 의미 규칙

구문 지시적 번역기의 구현

  • 감축이 발생할 때 감축되는 생성규칙의 오른쪽 문법기호에 대해 스택에 나타나는 속성을 가지고 새로운 합성 속성 값을 계산
  • 상향식 구문 분석기는 구문 분석된 부분트리에 대한 정보 저장을 위해 스택을 사용
  • ABC가 X로 감축 될 때 C.VAL는 VAL[TOP], B.VAL는 VAL[TOP-1], A.VAL는 VAL[TOP-2]에 있다. 감축이 일어난 후 TOP이 2만큼 감소하고, VAL[TOP]은 X.VAL의 값을 갖게 된다.

주석 파스트리 예제

구문 지시적 번역기 예제

중간코드 생성방법

  • 구문 분석 과정에서 중간코드 생성
    • 구문 에러시 코드생성이 무의미하므로 시간낭비 초래
    • 구현이 복잡함
    • 구문 에러가 없는 경우 빠르게 중간코드 생성 가능
  • 중간 표현을 생성 후 중간코드 생성
    • 중간 코드 생성에 필요한 정보만 저장하고 있으므로 코드 생성기 구현이 용이
    • 컴파일러 크기가 커지고 컴파일 시간이 길어짐

중간코드 생성

백패칭

테스트

중간 언어란?

중간코드는 구문 분석 단계에서 만들어진 구문트리를 이용하여 생성되거나, 한 문법 규칙이 감출될 때마다 구문 지시적 번역으로 생성이 이뤄진다. 중간 코드를 생성하는데는 중간언어를 사용한다.

중간언어의 장단점

  • 장점
    • 이식성 높은 컴파일러
    • 기계 독립적인 최적화
    • 인터프리터 사용 가능성
  • 단점
    • 컴파일 시간이 추가로 필요하고 비효율적인 목적 기계 코드가 생성됨

후위 표기법, 3주소코드, p-코드, 바이트 코드의 특징

C := (B * A) + D를 3-주소 코드, triple, 간접 triple, quadruple로 나타내시오

A. 3주소 코드 표현

T1 = B * A
T2 = T1 + D
C = T2

B. Triple 표현

번호 OP 피연산자1 피연산자2
[0] * B A
[1] + [0] D
[2] = C [1]

C. 간접 Triple 표현

수행순서
[0]
[1]
[2]
번호 OP 피연산자1 피연산자2
[0] * B A
[1] + [0] D
[2] = C [1]

D. Quadruple

번호 OP 피연산자1 피연산자2 결과
[0] * B A T1
[1] + T1 D T2
[2] = T2 C

다음 식을 triple, 간접 triple, quadruple로 바꾸시오

코드는 아래와 같음

A <- B + C * D / E - F
G <- C * D / E
번호 Triple 간접 Triple Quadruple
[0] *,C,D *,C,D *,C,D,T1
[1] /,[0],E /,[0],E /,T1,E,T2
[2] +,B,[1] +,B,[1] +,B,T2,T3
[3] -,[2],F -,[2],F -,T3,F,T4
[4] =,A,[3] =,A,[3] =,T4,A
[5] *,C,D =,G,[1] *,C,D,T5
[6] /,[5],E /,T5,E,T6
[7] =,G,[6] =,T6,G

구문 지시적 번역에 따라 (4 * 7 + 1) * 2에 대한 주석 파스트리를 구성하시오.