컴파일러를 만들고 싶나요? 이 두 논문만 읽어보세요 (2008)

Source: Hacker News

Overview

프로그래밍에 대해 아무것도 모른다고 가정하고 배우고 싶다고 생각해 보세요. Amazon.com에서 Knuth가 쓴 The Art of Computer Programming이라는 강력히 추천되는 책들을 보고 구입합니다. 이제 모든 프로그래밍 서적이 그 수준으로 쓰여 있다고 상상해 보세요.

그것이 컴파일러 작성에 관한 책들의 상황입니다.

책 자체가 나쁜 것은 아니지만 범위가 너무 넓습니다. 저자들은 너무 많은 정보를 제공해서 어디서 시작해야 할지 알기 어렵게 만듭니다. 일부 책은 다른 책보다 낫지만, 많은 책이 정규 표현식을 실행 가능한 상태 머신으로 변환하는 장, 다양한 문법 종류 등을 다루는 두꺼운 장을 포함하고 있습니다. 그 모든 것을 힘들게 읽고 나면 지식은 늘었지만 실제로 작동하는 컴파일러를 작성하는 데는 한 걸음도 가까워지지 않았습니다.

놀랍지 않게도, 이러한 책들의 난해함이 컴파일러가 만들기 어렵다는 신화를 만들었습니다.

Jack Crenshaw’s Let’s Build a Compiler!

이 신화를 깨는 최고의 자료는 1988년에 시작된 Jack Crenshaw의 시리즈 Let’s Build a Compiler! 입니다. 복잡해 보이는 주제를 1학년 프로그래밍 수업에 적합하도록 만드는 뛰어난 기술 문서입니다. Crenshaw는 Turbo Pascal 스타일의 컴파일러에 초점을 맞춥니다: 단일 패스, 파싱과 코드 생성이 뒤섞여 있으며 결과 코드에 가장 기본적인 최적화만 적용됩니다.

• 원본 튜토리얼은 Pascal을 구현 언어로 사용했지만, C 버전도 제공됩니다.
• 진정으로 모험을 즐기는 사람들을 위해 Marcel Hendrix가 만든 Forth 번역 이 있습니다; Forth는 인터랙티브하기 때문에 C나 Pascal 소스보다 실험하고 이해하기가 더 쉽습니다.

Crenshaw 시리즈에서 눈에 띄게 빠진 부분은 프로그램의 내부 표현—추상 구문 트리(abstract syntax tree)입니다. 이 단계를 건너뛰는 것은 유연성을 포기할 의향이 있다면 가능하지만, 빠진 주요 이유는 Pascal에서 트리를 조작하는 것이 나머지 코드의 단순성과 충돌하기 때문입니다. Python, Ruby, Erlang, Haskell, Lisp와 같은 고수준 언어에서는 트리와 같은 데이터 구조를 만들고 조작하는 것이 매우 쉬워, 바로 이러한 언어들이 강점으로 삼는 부분입니다.

A Nanopass Framework for Compiler Education

Sarkar, Waddell, Dybvig가 쓴 논문 A Nanopass Framework for Compiler Education 은 보완적인 접근법을 소개합니다. 핵심 아이디어는 컴파일러가 프로그램 내부 표현에 대한 일련의 변환일 뿐이라는 점입니다. 저자들은 수십 개 혹은 수백 개의 컴파일러 패스를 사용하고, 각 패스를 가능한 한 단순하게 유지하며, 변환을 결합하지 않고 별도로 유지할 것을 주장합니다. 제목에 있는 프레임워크는 각 패스의 입력과 출력을 명시합니다. 구현은 Scheme으로 이루어졌으며, 동적 타입 언어이기 때문에 데이터는 런타임에 검증됩니다.

After You’ve Built a Few Compilers

컴파일러를 한두 개 만들고 나면, 악명 높은 Dragon Book 혹은 그 대안에 투자할지 결정할 수 있습니다—아마도 전혀 필요하지 않을 수도 있습니다.