컴파일러 생성기

2026.09.02 18:16

컴파일러 생성기는 명세를 입력으로 받아 컴파일러의 한 단계를 코드로 만들어 내는 도구다. 사람은 “무엇을 인식할 것인가”만 적고, “어떻게 인식할 것인가”에 해당하는 표와 루프는 기계가 채운다.

이런 도구가 성립하려면 그 단계가 기계적으로 유도 가능한 형태여야 한다. 정규표현에서 DFA를 만드는 절차가 있고 문법에서 파싱표를 만드는 절차가 있기 때문에 렉서와 파서에 생성기가 있는 것이지, 컴파일러의 모든 단계에 있는 것이 아니다.

명세와 산출물

주요 생성기의 입출력을 실제로 재 보면 규모의 차이가 드러난다. flex와 bison은 직접 돌린 결과이고, 나머지는 CPython main(3.16.0a0) 저장소의 파일이다.

생성기	명세	산출물
flex	`.l` 14줄	C 1,790줄 (DFA 상태 20, 표 399엔트리)
bison	`.y` 19줄	C 1,562줄 (상태 18, 표 460엔트리)
PEG 생성기	`Grammar/python.gram` 1,661줄	`Parser/parser.c` 39,628줄
ASDL	`Parser/Python.asdl` 154줄	`Python/Python-ast.c` 18,611줄 + 헤더 948줄
cases_generator	`Python/bytecodes.c` 6,690줄	파일 8개 55,533줄

bytecodes.c 하나가 여덟 갈래로 퍼지는 것이 눈에 띈다.

     24,649  Python/executor_cases.c.h
     13,895  Python/generated_cases.c.h
      5,821  Python/optimizer_cases.c.h
        335  Python/record_functions.c.h
        263  Include/opcode_ids.h
      2,153  Include/internal/pycore_opcode_metadata.h
      1,447  Include/internal/pycore_uop_ids.h
      6,970  Include/internal/pycore_uop_metadata.h

명령어 하나를 추가할 때 손으로 고쳐야 할 곳이 여덟 군데 생기는 문제를, 명세를 단일 출처로 만들어 없앤 것이다. 생성된 파일들은 첫 줄에 그렇다고 적어 둔다.

// This file is generated by Tools/cases_generator/opcode_id_generator.py
// from:
// Do not edit!

명세의 모양

무엇을 적게 하느냐가 생성기마다 다르다.

.l은 정규표현과 액션의 쌍이다. 어떤 순서로 문자를 검사할지는 적지 않는다.

{DIGIT}+                     { return INT; }
{LETTER}({LETTER}|{DIGIT})*  { return IDENT; }

.y는 생성규칙과 액션의 쌍이다. shift할지 reduce할지는 적지 않는다.

expr : NUM            { $$ = $1; }
     | expr '+' expr  { $$ = $1 + $3; }
     | '(' expr ')'   { $$ = $2; }
     ;

$$, $1, $3이 구문지시적 변환의 값 스택 슬롯이다. 파서가 expr '+' expr을 expr로 reduce할 때 스택 위 세 자리의 값을 꺼내 새 값을 만든다.

ASDL은 문법이 아니라 자료 구조를 적는다. AST 노드의 모양을 선언하면 C 구조체와 생성자, 파이썬 쪽 노출까지 만들어진다.

module Python
{
    mod = Module(stmt* body, type_ignore* type_ignores)
        | Interactive(stmt* body)
        | Expression(expr body)

    stmt = FunctionDef(identifier name, arguments args,
                       stmt* body, expr* decorator_list, expr? returns, ...)

*는 리스트, ?는 선택적 필드다. 154줄로 파이썬 AST 전체를 정의한다.

bytecodes.c는 명령어 정의를 적는다. 스택 효과를 (입력 -- 출력)으로 선언하면 프레임 크기 계산에 쓰이는 표가 따로 생성된다.

op(_GUARD_TOS_INT, (value -- value)) {
    PyObject *value_o = PyStackRef_AsPyObjectBorrow(value);
    EXIT_IF(!_PyLong_CheckExactAndCompact(value_o));
}

macro(BINARY_OP_ADD_INT) =
    _GUARD_TOS_INT + _GUARD_NOS_INT + unused/5 + _BINARY_OP_ADD_INT + ...;

문법 밖으로 뺀 것

생성기는 명세를 그대로 받지 않는다. 명세가 결정적이지 않으면 거절하거나 경고한다. 그래서 결정을 도울 선언을 문법 바깥에 두는 장치가 생긴다.

앞의 .y에는 우선순위 선언이 있었다.

%left '+' '-'
%left '*' '/'

이 두 줄을 지우고 다시 돌리면 문법은 그대로인데 결과가 달라진다.

calc2.y: conflicts: 16 shift/reduce
State 14 conflicts: 4 shift/reduce
State 15 conflicts: 4 shift/reduce
State 16 conflicts: 4 shift/reduce

expr '+' expr 형태는 그 자체로 모호하다. 1+2*3에서 expr + expr까지 읽었을 때 *를 shift할지 expr로 reduce할지 문법만으로는 정해지지 않는다. 상태 수는 18개로 같고 표의 어느 칸에 두 행동이 함께 들어가느냐만 달라진다.

문법 변환에서 본 방식은 계층을 쪼개는 것이었다. E → E + T, T → T * F처럼 우선순위마다 논터미널을 만들면 모호성이 사라진다. %left는 그 계층을 만들지 않고 “같은 자리에서 충돌하면 왼쪽 것을 먼저 reduce하라”는 규칙을 표 생성 단계에 직접 주는 것이다. 문법은 사람이 읽기 좋은 모양으로 두고 결정만 밖에서 내린다.

같은 발상이 여러 곳에 있다. flex는 최장 일치와 규칙 순서로 정하고, PEG는 ordered choice로 먼저 쓴 대안이 이기게 하고, Pratt 파싱은 아예 정수 비교로 대체한다. 우선순위를 문법의 형태로 표현할 것인가 선언으로 뺄 것인가의 차이다.

생성하지 않는 쪽

생성기를 쓰면 명세가 단일 출처가 되고 손으로 유지할 코드가 줄어든다. 대가는 산출물을 읽을 수 없다는 것이다. 스캐너가 이상하게 동작할 때 볼 것은 생성된 C가 아니라 .l과 flex -b 리포트이고, 파서가 충돌을 내면 bison -v가 뽑는 상태 보고서를 봐야 한다. 디버거가 가리키는 줄 번호도 생성 파일 기준이다. 빌드에 생성 단계가 들어오는 것도 비용이다.

그래서 실무의 선택은 갈린다. GCC와 Clang은 렉서와 파서를 모두 손으로 짜고, CPython은 렉서를 손으로 짜되 파서는 PEG로 생성한다. 렉서를 손으로 짜는 이유는 들여쓰기나 f-string 중첩처럼 정규표현으로 표현되지 않는 요구가 실제 언어에 많기 때문이고, 파서를 생성하는 이유는 문법이 크고 자주 바뀌며 명세 자체를 관리해야 하기 때문이다.

한편 AST 정의와 명령어 정의는 손으로 쓰지 않는다. 파싱 알고리즘과 달리 이 둘은 같은 정보를 여러 파일에 중복해서 적는 문제라, 중복을 없애는 것만으로 생성기가 값을 한다. bytecodes.c 6,690줄이 55,533줄로 퍼지는 비율이 그 값의 크기다.

참고

컴파일러 오토마타 계층 컴파일러 인라인 캐싱과 특수화 컴파일러 중간언어 컴파일러 코드 최적화 컴파일러 클로저와 셀 컴파일러 트리 순회와 바이트코드