Compilers course: building compilers is fun and easy

Introduction Slides

This is the repo containing tasks for the compilers course at MIPT.

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, “better write an interpreter instead.”

В течение курса студенты будут иметь возможность своими руками потрогать, продумать и реализовать все аспекты современного компилятора. Начиная с грамматики и парсинга, продолжая системой типов, семантикой языка, модулями, преобразованием в промежуточное представление и поддержкой рантайма языка.

Compilers

Курс создавался с опорой на реализациию компилятора языка Etude, а также многих других:

• Hare ← approachable!
• Rust
• Cproc ← approachable!
• Myrrdin
• Chibicc ← approachable!
• Tinycc
• GHC
• Go
• Ante
• and others...

Стоит отметить компиляторы Hare, Cproc, Chibicc, которые имеют очень доступную кодовую базу (пометка approachable).

Rust и GHC имеют очень хорошие и понятные wiki и статьи:

• Rustc Dev Guide
• The GHC Commentary

Books

Основной книгой в начале курса является Crafting Interpreters by Robert Nystrom.

Я также рекомендую слудующие книги:

• Compilers: Principles, Techniques, and Tools — dragonbook
• A Retargetable C Compiler Design and Implementation — lcc book
• The Implementation of Functional Programming Languages — miranda book
• Basics of Compiler Design (Torben Ægidius Mogensen)
• Introduction to Compilers and Language Design (Prof. Douglas Thain) University of Notre Dame
• Modern Compiler Implementation in ML

Approaches

В своей идее курс содержит два подхода

Во-первых: дать человеку возможность продумать всё самому и погрузиться в грубокие дебри. Это может быть супер весело, но также очень трудозатратно.

Во-вторых: дописывать смысловые части уже готовой реализации. Если сделать всё правильно, то это тоже может быть достаточно интересно и информативно, и гораздо быстрее.

Tasks:

• Lexer
• Ast and Visitors
• Parser
• Symbol Table
• Static Types
• Gen QBE IR
• [Testing [TBD] ]
• Structures + Pointers
• [Type Inference [WIP] ] = HM / Unification + ...