▲

컴파일러를 만들고 싶은가? 이 두 편의 논문만 읽으면 된다 (2008)

 (prog21.dadgum.com)
1P by GN⁺ 4시간전 | ★ favorite | 댓글 1개
  • 대부분의 컴파일러 교재는 이론 중심으로 방대해, 초보자가 실제 작동하는 컴파일러를 구현하기 어렵다는 문제 제기
  • 이를 극복할 실용적 자료로 Jack Crenshaw의 “Let’s Build a Compiler!” 시리즈가 소개되며, 단일 패스 구조의 간결한 Pascal 컴파일러를 다룸
  • 이 튜토리얼은 구문 분석과 코드 생성의 결합, 최소한의 최적화, 그리고 C·Forth 버전을 통해 실험적 학습을 지원
  • 두 번째 자료인 “A Nanopass Framework for Compiler Education” 논문은 수많은 단순 변환(pass) 으로 구성된 모듈형 컴파일러 구조를 제시
  • 두 자료를 통해 실제 구현 경험을 쌓은 뒤에야, 필요하다면 전통적 교재(Dragon Book) 을 참고해 심화 학습을 진행할 수 있음

컴파일러 학습의 현실과 두 편의 핵심 논문

  • 기존 컴파일러 서적은 지나치게 방대하고 난해해, 초보자가 실제 동작하는 컴파일러를 작성하기 어렵다는 지적
    • 대부분의 책이 정규식 변환, 문법 이론 등 방대한 주제를 다루며 실용적 출발점을 제공하지 않음
    • 이로 인해 “컴파일러는 어렵다”는 오해와 신화가 형성됨
  • 이러한 인식을 깨는 대표 자료로 Jack Crenshaw의 “Let’s Build a Compiler!” 시리즈가 소개됨
    • 1988년에 시작된 이 튜토리얼은 Turbo Pascal 수준의 단일 패스 컴파일러를 다룸
    • 구문 분석과 코드 생성을 결합한 구조로, 최소한의 최적화만 수행
    • 원래 Pascal로 작성되었으며, 이후 C 버전과 Forth 번역판도 존재
    • Forth 버전은 상호작용적 언어 특성 덕분에 실험과 이해가 용이함
  • Crenshaw 시리즈의 한계는 프로그램의 내부 표현(추상 구문 트리, AST) 이 없다는 점
    • Pascal에서는 트리 조작이 복잡해 생략되었으나, Python, Ruby, Erlang, Haskell, Lisp 같은 고수준 언어에서는 손쉽게 구현 가능
    • 이러한 언어들은 본래 트리 구조 데이터 조작을 위해 설계됨
  • 두 번째로 추천되는 자료는 Sarkar, Waddell, Dybvig의 논문 “A Nanopass Framework for Compiler Education”
    • 핵심 개념은 “컴파일러는 프로그램의 내부 표현을 단계적으로 변환하는 일련의 과정”이라는 점
    • 수십~수백 개의 단순한 변환(pass) 으로 구성된 구조를 제안
    • 각 변환은 가능한 한 단순하게 유지하고, 변환 간 결합을 피함
    • 프레임워크는 각 패스의 입력과 출력을 명시적으로 정의
    • 구현 언어는 Scheme이며, 동적 타입 기반으로 런타임 검증 수행
  • 이 두 자료를 통해 실제 컴파일러를 작성한 후, 필요하다면 Dragon Book 같은 전통적 교재로 심화 학습을 이어갈 수 있음
    • 그러나 이 두 자료만으로도 충분히 실용적 컴파일러 제작 경험을 얻을 수 있음

함께 보면 좋은 글 β

▲
GN⁺ 4시간전  [-]
Hacker News 의견들

  • Donald Knuth의 『The Art of Computer Programming』은 여전히 집필 중이며, 이제는 컴파일러 주제를 다루지 않을 가능성이 높음
    나는 저자의 주장에 동의하지 않음. 『Dragon Book』(Aho 외 저)의 2장은 독립적으로 읽어도 충분한 컴파일러 입문서로서 완결성이 있음
    또 다른 훌륭한 입문서는 Niklaus Wirth의 『Compilers』로, 100쪽도 안 되는 분량에 완전한 컴파일러의 소스 코드와 명확한 설명이 담겨 있음
    이 두 책으로 고등학생 때 직접 컴파일러를 만들 수 있을 만큼 배웠음

    • 『Dragon Book』은 훌륭하지만 입문서로는 부적절함. 나도 이 책 때문에 컴파일러를 포기할 뻔했음
      실습 중심으로 실제 컴파일러 제작 과정을 따라가는 책이 훨씬 낫다고 생각함
      참고 자료는 이 링크에 정리되어 있음
    • 『Dragon Book』은 파싱 중심이라 백엔드나 최적화에 관심 있다면 추천하지 않음
      2판에는 데이터 흐름 분석이 추가되었지만, 현대 컴파일러(GCC, LLVM 등)의 핵심인 SSA(Static Single Assignment) 형식은 단 한 페이지만 다룸
      최신 백엔드를 만들려면 SSA 이론을 별도로 공부해야 함
    • Niklaus Wirth의 『Compilers』는 여기서 볼 수 있음
    • Knuth의 사이트에 따르면, Volume 7에서 컴파일러 기술을 다룰 계획이 여전히 있음
      TAOCP 공식 페이지 참고
    • Knuth의 중간 이름은 처음 알았는데, 기사에는 굳이 넣지 않아도 될 듯함

  • Abdulaziz Ghuloum의 논문 An Incremental Approach to Compiler Construction은
    “컴파일러는 마법 같은 존재”라는 인식을 깨고, 인터프리터처럼 쉽게 컴파일러를 만들 수 있음을 보여줌
    Scheme 언어의 큰 부분을 지원하며 Intel x86용 어셈블리를 생성하는 컴파일러를 단계적으로 구축하는 과정을 자세히 설명함

  • 최근 메타 컴파일러와 적응형 컴파일(Adaptive Compilation), JIT 컴파일러 등으로 컴파일러 기술이 크게 발전했음
    Alan Kay의 연구 그룹 VPRI는 복잡성 문제를 다룸
    관련 자료: Ometa 논문, Adaptive Compilation 영상, Alan Kay 강연

  • 책을 읽는 좋은 조언을 들었음 — 책은 RAM처럼 임의 접근(random access) 가능하다는 것임
    필요한 부분만 골라 읽으면 두꺼운 책도 부담이 덜함
    다만, 무엇을 모르는지 모를 때는 이 방식이 통하지 않음. 그래서 가벼운 입문서의 중요성이 큼

    • 대부분의 책에는 불필요한 세부 내용이 너무 많아 건너뛰게 됨. 반면 기술서는 너무 어려워 한 부분을 이해하려면 몇 시간씩 공부해야 함
    • 나는 책을 끝까지 읽지 않으면 의미를 얻기 어렵다고 느낌. 요즘은 좋은 참고서 역할을 하는 자료들이 인터넷으로 옮겨감
    • 내 기술 서적의 상당 부분은 특정 질문에 대한 참조용으로 사용함

  • 요즘은 『Crafting Interpreters』가 많이 추천됨
    Nanopass 논문 링크는 깨졌음

    • “컴파일러 책”이라고 해도 다루는 범위가 제각각이라, 내가 원하는 부분과 다를 때가 많음
      그래서 『Crafting Interpreters』의 핵심을 정리한 치트시트를 만들었음
      책은 단순한 매뉴얼이 아니라 경험 중심의 학습서로, visitor 패턴 등 저자의 즐거움이 녹아 있음
    • 『Crafting Interpreters』는 훌륭하지만, 타입 시스템·최적화·링킹을 다루는 동반서가 있으면 완벽할 것 같음
    • 혼자 공부하기에 정말 좋은 책임
    • 대학 시절 수업 대기 중에 완독했음. Nanopass는 아직 안 써봤지만 다른 링크로 시도해볼 예정임
    • Nanopass 논문은 이 GitHub 저장소에 보존되어 있음

  • 최근 재미로 토이 컴파일러를 만들고 있음
    복잡한 파싱 이론이나 DSL 대신 Megaparsec 파서 콤비네이터를 사용함
    파싱 로직이 명확하고 재사용이 쉬우며, 전통적인 lexer/parser 분리의 번거로움이 없음

    • 나는 LL/LR 파서 생성기보다 재귀 하강 파서가 실용적이라고 생각함
      버그가 적고, 오류 진단이 좋으며, 대부분의 언어(C#, Rust 등)도 이 방식을 씀
      tree-sitter도 훌륭하지만 의존성이 많음. 반면 재귀 하강은 의존성 없는 간결한 구현이 가능함
    • 그래도 lexer/parser 분리를 유지하는 게 낫다고 생각함
      파서 콤비네이터 접근법의 장점은 lexer와 parser 모두 같은 파서 타입으로 다룰 수 있다는 점임
      공백 처리나 토큰화 문제를 깔끔하게 해결할 수 있음

  • 죽은 링크였던 Nanopass 논문은 여기서 볼 수 있음

  • 나에게 컴파일러를 가르쳐준 건 1978년 BYTE 매거진의 Tiny Pascal 컴파일러 기사였음
    최적화는 Stanford의 Ullman과 Hennessy가 진행한 여름 강좌에서 배웠음
    코드 생성기는 직접 만든 독창적인 방식이었음
    『Dragon Book』은 가지고 있지만 실제로 읽은 적은 없음

    • 해당 BYTE 매거진은 archive.org에서 볼 수 있음

  • Nanopass 접근법의 핵심은 패스의 개수가 아니라, 각 패스마다 명시적인 입력·출력 언어를 정의한다는 점임
    이 구조적 사고 덕분에 실행 전에 많은 버그를 잡을 수 있음
    Crenshaw의 튜토리얼도 훌륭하지만, 이런 언어 불변성 관리가 진짜 확장 가능한 컴파일러를 만드는 차이점임

  • UC Irvine 시절, Niklaus Wirth의 제자 Michael Franz 교수의 CS241 수업에서 최적화 컴파일러를 구현했던 기억이 있음
    DLX라는 가상 머신용 바이트코드를 생성하는 과제였음
    관련 자료는 DLX 아키텍처 설명과
    레지스터 할당 알고리즘 참고 이미지에서 볼 수 있음

답변달기
긱뉴스에 GeekBadge 기능이 추가되었습니다. 긱배지로 자신을 표현해 보세요.