▲

레츠 빌드 어 컴파일러 다시 보기

 (eli.thegreenplace.net)
1P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 1988~1995년에 발표된 Jack Crenshaw의 ‘Let’s Build a Compiler’ 튜토리얼을 Python과 WebAssembly로 재구현한 프로젝트
  • 원본은 Pascal과 Motorola 68000 어셈블리를 사용했지만, 이번 작업에서는 현대적 환경에서 실행 가능한 코드로 변환
  • 튜토리얼의 핵심은 재귀 하강 파서(recursive-descent parser) 를 직접 구현하고, 초기 단계부터 실제 어셈블리 코드를 생성하는 접근
  • Crenshaw의 방식은 문법 지시적 번역(syntax-directed translation) 을 사용하지만, 타입 처리 단계에서 한계를 드러냄
  • 이번 재구현은 고전 튜토리얼을 현대 개발자들이 직접 실행하고 실험할 수 있는 형태로 복원한 점에서 의의가 있음

고전 튜토리얼의 배경

  • Jack Crenshaw의 ‘Let’s Build a Compiler’ 는 1988~1995년 사이에 발표된 컴파일러 제작 입문서로, 지금도 자주 언급되는 자료
    • 원문은 Pascal로 작성되었고, Motorola 68000 어셈블리 코드를 출력
    • 35년이 지난 2025년에도 Hacker News 등에서 꾸준히 회자됨
  • 글 작성자는 2003년에 이 튜토리얼을 처음 접하고 깊은 인상을 받았으며, 2025년에 다시 이를 Python과 WebAssembly로 옮김

Python 및 WebAssembly로의 재구현

  • 단순히 읽는 것에 그치지 않고, 튜토리얼의 컴파일러를 Python으로 번역하고 WebAssembly(WASM) 를 출력하도록 구현
  • 결과물은 GitHub 저장소(eliben/letsbuildacompiler)에 공개
    • TUTORIAL.md 파일에서 원본 각 파트가 Python 코드로 어떻게 매핑되는지 설명
    • 사용자는 원본 튜토리얼을 읽으며 직접 실행 가능한 코드를 실험 가능

KISS 언어 예제와 WASM 출력

  • Crenshaw가 설계한 KISS 언어의 예제 프로그램을 Python 버전 컴파일러로 컴파일한 결과를 제시
    • 예제는 procedure, while 루프, 값 전달 및 참조 전달을 포함
  • 출력된 WASM 텍스트는 참조 매개변수(by-reference parameter) 처리 로직을 포함하며, 최적화는 거의 적용되지 않음
  • 전역 변수 X가 main 함수에서 암묵적으로 반환되는 부분은 테스트 편의를 위한 장치
  • 생성된 WASM 코드는 실제 실행을 통해 예상 결과를 검증하는 테스트에 사용됨

튜토리얼의 강점

  • Crenshaw의 튜토리얼은 재귀 하강 파서를 단계적으로 구축하며, 복잡한 이론보다 직접 작동하는 코드 생성에 초점을 맞춤
    • 당시에는 lex와 yacc가 표준으로 여겨졌으나, 직접 작성한 파서의 단순성과 명료함이 큰 영향을 줌
    • 이후 20년간 작성자는 수동 재귀 하강 파서를 선호하게 됨
  • 또한 대부분의 강의가 구문 분석에 치중하던 시절, Crenshaw는 초기 단계부터 어셈블리 코드 생성을 다룸

한계와 개선 가능성

  • 튜토리얼은 문법 지시적 번역(syntax-directed translation) 방식을 사용해 파싱 중 바로 코드를 생성
    • 이 접근은 학습에는 유용하지만, 타입 정보를 사전에 알 수 없어 최적화가 어렵다는 한계 존재
  • 특히 타입이 도입되는 14부 이후에는 중간 표현(IR)이나 AST를 활용한 구조적 접근이 필요함이 드러남
  • Crenshaw가 14부 이후 튜토리얼을 중단한 이유는 명시되지 않았으나, 이 한계와 관련이 있을 가능성 언급
  • 작성자는 14부를 전환점으로 삼아 AST 생성 후 타입 검사 및 코드 생성을 수행하는 접근이 더 적합하다고 평가

결론

  • 원본 튜토리얼은 여전히 컴파일러 제작 입문서로서 탁월한 가독성과 실용성을 유지
  • 이번 Python·WASM 버전은 현대 개발자들이 구식 기술 없이 학습할 수 있도록 보완한 구현
  • GitHub 저장소를 통해 누구나 실험 가능하며, 컴파일러 구조를 직접 체험할 수 있는 현대적 재해석으로 평가됨
▲
GN⁺ 2일전  [-]
Hacker News 의견들

  • 프론트엔드의 세부사항에 매몰되지 않고, 초반부터 바로 작동하는 어셈블리 코드를 생성하는 튜토리얼이 마음에 듦
    Ghuloum의 접근법처럼 언어의 아주 작은 부분부터 전체를 세워가며 점진적으로 확장하는 방식이 특히 매력적임
    최근에 발견한 좋은 책은 이 링크인데, C와 x86이 초보자에게는 최적의 타깃은 아니지만 첫 컴파일러를 만들기엔 훌륭한 자료였음
    참고로 Ghuloum의 논문은 여기에 있음

    • 이건 드문 경우지만, 학계식 접근법이 실제로는 실용성과 맞지 않는 예라고 생각함
      과거에는 파싱이 가장 중요한 부분이었기에 커리큘럼이 그렇게 짜였지만, 요즘은 언어 기능을 어떻게 구현하느냐가 더 중요함
      직접 컴파일러를 만든다 해도 이제는 “Claude, 이 문법으로 재귀 하강 파서를 만들어줘”라고 하면 거의 한 번에 결과가 나오는 시대임
    • 학계 연구자와 실무 개발자의 차이를 느꼈음
      학계는 레이어(layer) 기반으로, 실무자는 파이프(pipe) 기반으로 접근하는 경향이 있음
      레이어 방식은 빌드 가능한 코드를 주지만 실행하기 어렵고, 파이프 방식은 실행은 쉬우나 구조화가 약함
      결국 실행 가능한 최소 단위로 나누어 개발하는 게 핵심임

  • 이 글이 정말 핵심을 잘 짚었다고 생각함
    대학 가기 전부터 컴파일러에 관심이 있었는데, 이 자료가 가장 접근하기 쉬운 입문서였음
    17살 때 재귀 하강 파서를 직접 만들어보며 복잡해 보이던 문제도 올바른 기초 단위(primitive) 로 쪼개면 단순해진다는 걸 깨달았음

    • “문제를 올바른 프리미티브로 나누는 것”이 프로그래밍의 진짜 핵심임
      알고리즘에 대한 자료는 많지만, 문제를 어떻게 프리미티브로 접근할지 다루는 자료는 부족함
    • 재귀 하강은 단순히 파서를 만드는 방법이 아니라 프로그램 설계의 교훈이기도 함
      예전에는 yacc 같은 테이블 기반 파서가 주류였지만, 요즘은 재귀 하강이 더 실용적이고 유연함
      LLM 코드 생성 덕분에 이 접근이 더 쉬워졌음
      학습용 토이 컴파일러에서는 AST나 IR, 최적화를 생략하고 바로 코드 생성으로 가도 충분히 유익함
      예전에 회사에서 C의 하위 집합을 지원하는 테스트 도구를 만들 때, 파서가 코드를 생성하는 대신 실행 가능한 데이터 구조를 반환하게 했음
      예를 들어 ForLoopStatement 클래스가 testExpression을 포함하고, Execute() 메서드에서 이를 직접 호출하는 식이었음
    • Niklaus Wirth의 1971년 논문 Program Development by Stepwise Refinement은 이런 사고방식을 가장 일찍 정립한 고전임
      Fred Brooks의 The Mythical Man-Month에서도 언급된 중요한 논문임
    • 요즘은 파싱이 필요할 때마다 파서 조합기(parser combinator) 를 쓰게 됨
      개념적으로 너무 자연스럽고 깔끔함

  • Jack Crenshaw의 튜토리얼이 syntax-directed translation 방식을 사용한다는 설명이 흥미로웠음
    이게 단순히 싱글 패스 컴파일러를 의미하는지, 아니면 더 구체적인 개념인지 궁금함
    정적 타입 언어에서는 타입 기반 최적화가 어렵다는 점은 이해되지만, 타입 검사 수준에도 제약이 있는지 알고 싶음

    • 타깃 언어가 정의 후 사용 규칙을 따르고 복잡한 타입 추론이 없다면, 타입 기반 최적화나 상수 폴딩 정도는 가능함
      하지만 IR이 없으면 LICM, CSE, GVN 같은 고급 최적화는 불가능함
      개인적으로는 함수 단위 2패스 컴파일을 선호함 — 첫 패스에서 IR을 만들고, 바로 코드 생성 후 상태를 버리는 방식으로 빠르고 효율적인 결과를 얻을 수 있음
    • syntax-directed translation은 좀 더 구체적인 개념으로, 소스 코드를 읽으며 즉시 코드 생성을 하는 것을 의미함
      싱글 패스 컴파일러라도 단계를 분리해 마지막에 코드 생성만 수행할 수도 있음

  • Crenshaw의 튜토리얼은 실용적인 수준까지는 가지 않지만, precedence climbing 기법으로 확장하면 훨씬 유용해짐
    관련 글은 이 링크에 잘 정리되어 있음

  • “Let’s Build a Compiler” 관련 스레드를 다시 살펴봤음
    2007년부터 2023년까지 여러 차례 HN에 올라온 기록이 있음
    특히 Jack Crenshaw 인터뷰는 댓글은 없지만 매우 흥미로운 읽을거리였음

    • 네 번째 링크는 Crenshaw의 글이 아니라 같은 제목의 다른 글임
    • Crenshaw 인터뷰 정말 좋았음

  • 개인 프로젝트 홍보 겸 소개: cwerg.org
    Python과 재귀 하강 파싱을 사용하고, IR로 프론트엔드와 백엔드를 분리함
    x86과 ARM용 ELF 바이너리를 생성하며 실사용을 목표로 함
    다만 복잡하고 튜토리얼 스타일은 아님

  • 예전에 USENET의 comp.compilers 뉴스그룹에서 Jack Crenshaw의 튜토리얼을 배웠던 추억이 있음
    참고로 그 그룹은 아직도 활성화되어 있음

  • 현대적인 컴파일러 접근법으로는 이 Cornell 블로그 글을 추천함

    • LLVM 덕분에 컴파일러 제작이 놀라울 정도로 쉬워짐
      사용할 때마다 마치 피라미드 위에 돌 몇 개 얹는 느낌임
    • 하지만 LLVM은 간접적인 접근이라 한계가 있음
      LLVM을 백엔드로 쓰는 언어들은 공통적으로 컴파일 속도가 느림
      Zig는 이를 인식하고 자체 백엔드를 개발 중이고, Rust는 여전히 느린 컴파일에 묶여 있음
      LLVM은 복잡함이 품질을 보장한다는 착각을 주며, 개발자의 자율성을 약화시키는 기술이라고 생각함
      이건 다른 인기 기술(이니셜이 비슷한)과도 닮아 있음

  • 나도 비슷한 이유로 tiny-optimizing-compiler라는 튜토리얼을 작성했음
    컴파일러의 중간단계와 백엔드만 다루는 간결한 예제임
    GitHub 링크

    • 이걸 Lean으로 구현해보면 재미있을 것 같음

  • 어릴 때 이 튜토리얼을 인쇄해서 들고 다니며 읽었음
    짧은 시간에 컴파일러가 완성되는 걸 보는 게 정말 멋졌음
    Beej’s Guide 같은 이런 자료들은 CS 교육에서 가장 가치 있는 문서 중 하나인데, 정당한 평가를 받지 못하고 있음

답변달기