컴파일러 원리 다시 보기

컴파일러

컴파일러 또한 하나의 프로그램으로, 특정 언어(소스 언어)로 작성된 프로그램을 읽어 들여 이를 다른 언어(타겟 언어)로 작성된 동등한 프로그램으로 번역합니다.

즉, 소스 프로그램을 입력받아 타겟 프로그램을 출력하는 프로그램으로, 소스 프로그램을 의미적으로 동등한 타겟 프로그램으로 매핑할 수 있습니다.

       컴파일러
소스 프로그램 -------> 타겟 프로그램

소스 프로그램은 일반적으로 가독성이 좋은 문자열이며, 타겟 프로그램은 여러 가지 형태가 있습니다:

• 기계어, 예를 들어 C 언어를 컴파일하여 얻은 실행 가능한 이진 프로그램

• 중간 바이트코드, 예를 들어 Java를 컴파일하여 얻은 JVM용 .class 파일

• 문자열, 예를 들어 Babel을 통해 변환된 JavaScript 코드

사실 이것은 번역입니다. 예를 들어 문자열에서 기계어로 컴파일하는 것은 사람이 이해할 수 있는 코드 언어를 기계가 "이해"(식별 및 실행)할 수 있는 기계 언어로 번역하는 것이며, 사용자는 타겟 프로그램을 통해 기계와 상호작용할 수 있게 됩니다.

         타겟 프로그램
사용자 입력 ---------> 출력

P.S. 컴파일러와 매우 유사한 것은 인터프리터이며, 차이점은 타겟 프로그램을 생성하는 단계가 없다는 것입니다.

                 인터프리터
소스 프로그램 & 사용자 입력 -------> 출력

런타임에 해석하여 실행하므로, 일반적으로 인터프리터 언어의 실행 효율은 컴파일 언어보다 낮습니다.

컴파일 과정

두 부분으로 나뉩니다:

• 분석: 소스 프로그램을 여러 부분으로 나누고 구문 구조를 더해 중간 표현 형식과 심볼 테이블(symbol table)을 생성합니다.

• 합성: 중간 표현 형식 및 심볼 테이블을 바탕으로 타겟 프로그램을 구성합니다.

전형적인 컴파일러의 처리 단계는 다음과 같습니다:

(입력) 캐릭터 스트림
|
|- 어휘 분석기(lexer)
|  (생성) 심볼 스트림
|  (생성) 심볼 테이블
|- 구문 분석
|  (생성) 구문 트리
|- 의미 분석
|  (생성) 구문 트리
|- 중간 코드 생성기
|  (생성) 중간 표현 형식
|- 기계 독립적 코드 최적화기
|  (생성) 중간 표현 형식
|- 코드 생성기
|  (생성) 타겟 기계어
|- 기계 의존적 코드 최적화기
v
(출력) 타겟 기계어

이 중 주요 단계는 어휘 분석, 구문 분석, 의미 분석 및 코드 생성이며, 중간 코드 생성과 두 단계의 최적화는 선택 사항입니다.

어휘 분석(lexical analysis)

컴파일 작업의 첫 번째 단계로, 목표는 문자 스트림을 토큰(token) 시퀀스로 변환하는 것입니다.

Takes raw input, which is a stream of characters, and converts it into a stream of tokens, which are logical units, each representing one or more characters that "belong together."

예를 들어:

// 입력
position = initial + rate * 60

// 출력
[
  (id, 1),
  (=),
  (id, 2),
  (+),
  (id, 3),
  (*),
  (number, 4)
]

구체적인 과정은 문자를 하나씩 스캔하며 주석과 공백 문자를 제거하고, 문자 스트림을 어소(lexeme)로 분리하는 것입니다:

position,=,initial,+,rate,*,60

그런 다음 어소를 토큰 형식으로 변환합니다:

(token-name, attribute-value)

토큰은 문자 위의 첫 번째 추상화 계층입니다. 이러한 키-값 쌍 형태인 이유는 이후 대부분의 단계에서 유형(token-name)에만 집중하면 되고, 마지막에 코드를 생성할 때만 상세 값 정보(attribute-value)가 필요하기 때문입니다. 여기서 token-name은 구문 분석 단계에서 필요한 추상 기호(예: id는 식별자를 나타냄)이며, attribute-value는 심볼 테이블에서 해당 어소의 인덱스입니다:

[
  (1, position),
  (2, initial),
  (3, rate),
  (4, 60)
]

심볼 테이블

심볼 테이블은 컴파일러가 소스 프로그램 구성에 관한 다양한 정보를 저장하기 위해 사용하는 데이터 구조입니다.

분석 단계에서 생성되고 합성 단계에서 사용됩니다:

결과적으로 심볼 테이블의 역할은 선언된 위치의 정보를 실제로 사용되는 위치로 전달하는 것입니다.

어휘 분석기가 가진 정보가 제한적(어소 리터럴)이기 때문에 생성된 심볼 테이블은 기본 정보(어소 리터럴과 식별자의 매핑 관계)만 포함하며, 이후 구문 분석기가 의미 정보를 바탕으로 기존 심볼 테이블 항목을 사용할지 아니면 새 항목을 생성할지 결정합니다.

또한 심볼 테이블은 전역에 하나만 있는 것이 아니라 각 스코프마다 독립적인 심볼 테이블이 존재합니다. 이는 동일한 식별자가 프로그램의 서로 다른 선언 블록에서 중복되어 나타날 수 있도록, 즉 서로 다른 스코프 아래의 변수명이 충돌하지 않도록 하기 위함입니다. 동시에 가장 인접한 중첩(most-closely) 규칙을 지원하기 위해 이러한 심볼 테이블들을 중첩 계층에 따라 연결하여 트리 구조를 형성함으로써 상속, 클로저 등의 언어적 특성을 지원합니다.

P.S. 키워드도 식별자처럼 심볼 테이블에 저장되며, 테이블 조회 시 반환 코드를 통해 구분됩니다.

구문 분석(syntax analysis)

구문 분석 단계에서는 token-name을 가져와 구문 구조를 설명하는 트리 형태의 중간 표현을 생성하며, 동시에 구문 오류를 검증합니다.

Check input is well-formed and build a parse tree or similar representation of input.

예를 들어 추상 구문 트리(abstract syntax tree)는 전형적인 중간 표현 형식 중 하나로, 소스 프로그램의 계층적 구문 구조를 설명할 수 있습니다. 트리의 각 노드는 연산을 나타내고 자식 노드는 해당 연산의 피연산자를 나타냅니다:

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      (number, 4)

구문 트리는 문자 위의 두 번째 추상화 계층입니다. 여기서부터 우선순위와 결합성의 개념이 등장하며, 연산은 이러한 규칙에 따라 피연산자와 매칭되어 고유한 트리 구조를 생성해야 합니다(구문에 모호성이 없어야 함). 이 단계에서는 괄호가 짝이 맞는지 등 입력된 소스 프로그램의 형식이 올바른지 확인할 수 있습니다.

문맥 자유 문법

언어의 구문 구조는 보통 문맥 자유 문법(context-free grammar)으로 정의됩니다. 예를 들어:

if (expression) statement else statement

이에 대응하는 생성 규칙(production)은 다음과 같습니다:

stmt -> if (expr) stmt else stmt

여기서 expr, stmt와 같은 변수는 논터미널(nonterminal)이며, 터미널(terminal, if, ()와 같은 어휘 요소) 시퀀스를 나타냅니다.

문맥 자유 문법은 4가지 요소로 구성됩니다:

• 터미널 집합: 언어의 기본 기호 집합

• 논터미널 집합: 구문 변수라고도 하며, 터미널 시퀀스로 대체될 수 있음

• 생성 규칙 집합: 특정 구성을 쓰는 방식을 나타냄

• 시작 기호: 시작점으로 지정된 하나의 논터미널

시작 기호에서 출발하여 논터미널을 오른쪽의 생성 규칙 몸체로 계속해서 교체하는 과정을 유도(derivation)라고 합니다. 시작 기호에서 유도될 수 있는 모든 터미널 시퀀스의 집합이 해당 문법이 정의하는 언어입니다. 반대로 말하면 언어는 생성 규칙을 따르는 일련의 터미널 문자열입니다.

예를 들어 CSS의 속성 선언에 대응하는 문법은 다음과 같습니다:

// 터미널
ident	[-]?{nmstart}{nmchar}*
// 논터미널
IDENT	{ident}
// 생성 규칙
property    : IDENT;

P.S. 시작 기호는 stylesheet이며 대응하는 생성 규칙은 stylesheet : [ CDO | CDC | S | statement ]*;입니다. 자세한 내용은 CSS 핵심 구문을 참조하세요.

우선순위와 결합성

연산의 우선순위와 결합성 또한 생성 규칙에 의해 정의됩니다. 예를 들어:

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

의미는 다음과 같습니다:

• factor: 어떤 연산자에 의해서도 분리될 수 없는 표현식으로 피연산자의 최소 단위입니다. 숫자이거나 괄호로 보호된 표현식입니다.

• term: 높은 우선순위의 연산자(*와 /)에 의해서는 분리될 수 있지만, 낮은 우선순위의 연산자(+와 -)에 의해서는 분리될 수 없는 표현식입니다.

• expr: 일반적인 표현식으로 위의 어떤 연산자에 의해서도 분리될 수 있습니다.

따라서 우선순위를 제어하는 아이디어는 각 우선순위마다 전용 논터미널을 두어, 해당 우선순위 또는 그보다 높은 우선순위의 연산자에 의해 분리될 수 있는 표현식을 나타내는 것입니다.

의미 분석

이 단계에서는 입력된 구문 구조가 언어적 요구 사항을 충족하는지 몇 가지 정적 검사를 수행합니다:

• 타입 검사(type checking): 예를 들어 각 연산자가 매칭되는 피연산자를 가졌는지, 배열 인덱스의 데이터 타입이 올바른지 확인합니다.

• 타입 변환(coercion): 예를 들어 피연산자에 대해 암시적 타입 변환을 수행합니다.

예를 들어:

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      inttofloat
        (number, 4)

P.S. 여기서 inttofloat는 정수형을 부동 소수점형으로 바꾸는 단항 연산을 나타내며 타입 변환 중에 삽입된 동작입니다.

중간 코드 생성

구문 분석과 의미 분석이 완료된 후, 기계어와 유사한 중간 표현을 생성할 수 있습니다. 이 표현 형식은 두 가지 특징이 있습니다:

• 생성이 용이함 (단순한 중간 표현이므로 생성 비용이 너무 높아서는 안 됨)

• 기계어로 번역하기 쉬움 (단계적으로 타겟 언어에 접근함)

예를 들어 3주소 코드(three-address code)는 어셈블리 명령어와 유사한 전형적인 중간 표현 형식입니다:

t1 = inttofloat(number4)
t2 = id3 * t1
t2 = id2 + t2
id1 = t3

코드 최적화

두 가지로 나뉩니다:

• 기계 독립적 최적화: 더 나은 타겟 프로그램을 생성하기 위한 중간 표현 대상의 최적화입니다. 예를 들어 Closure Compiler가 JS 코드에 대해 수행하는 루프 최적화, 도달 불가능한 코드 제거, 중복 코드 단순화 등이 있습니다.

• 기계 의존적 최적화: 타겟 프로그램 대상의 최적화로 CPU 레지스터, 메모리 참조 등을 다룹니다. 목표는 병렬성, 메모리 계층 구조 등 컴퓨터 아키텍처 특성을 최대한 활용하는 것입니다.

전자는 중간 코드 생성 단계 이후에 발생하고 후자는 타겟 프로그램 생성 이후에 발생하는 출고 전 마지막 공정입니다.

P.S. 예를 들어 이전 단계의 inttofloat 타입 변환은 컴파일 시에 완료될 수 있으며(60을 60.0으로 변환), 이는 기계 독립적 최적화에 해당합니다.

코드 생성

중간 표현 형식을 입력받아 타겟 언어를 출력합니다. 예를 들어 기계어를 생성하려면 각 변수에 레지스터나 메모리 위치를 지정한 후 중간 표현을 동등한 기계 명령어 시퀀스로 번역해야 합니다.

최적화된 3주소 코드에 대응하는 기계어(어떤 언어인지 모르겠지만 어셈블리처럼 보임)는 다음과 같습니다:

LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1

2개의 레지스터 R1과 R2를 사용하여 id3를 읽어 R2에 넣고 60.0을 곱해 그 결과를 다시 R2에 넣습니다... 마지막으로 R1의 값을 id1에 해당하는 메모리 주소에 넣어 대입을 완료합니다.

기계 의존적 최적화를 고려하지 않는다면 컴파일 과정은 여기서 끝납니다. 논리적으로 어휘 분석, 구문 분석, 의미 분석, 코드 생성이라는 4가지 필수 단계를 거칩니다. 실제 구현에서는 이러한 단계들이 반드시 명확한 경계를 가지는 것은 아니며 성능 향상을 위해 최대한 한 번의 패스(pass)로 여러 공정을 완료하려고 노력합니다.

참고 자료

• 《컴파일러 원리》(용 북 제2판)

• http://infolab.stanford.edu/~ullman/dragon/slides1.pdf

• Compiler Design - Code Optimization

• Compiled language