Computer Science

Учебник Компиляторы для начинающих

19 уроков · 6 разделов · бесплатно, без регистрации

Каждый раз, когда вы запускаете программу, где-то внутри работает машина, превращающая текст вашего кода в действия процессора. Этот курс открывает её капот: вы узнаете, как компилятор и интерпретатор читают исходный текст, разбивают его на токены, проверяют по грамматике, строят дерево и в итоге выполняют. Мы не ограничимся теорией — на чистом Python из стандартной библиотеки вы соберёте настоящий лексер, парсер методом рекурсивного спуска, построите AST и напишете интерпретатор арифметических выражений, который реально считает. Курс для тех, кто уже пишет на Python и хочет понять, что происходит под капотом языков программирования.

Курс «Компиляторы: как устроены языки» состоит из 6 разделов и 19 уроков: Что такое компилятор, Лексический анализ, Грамматики и BNF, Синтаксический анализ и AST, Семантика, IR и виртуальная машина и Оптимизации, проект и инструменты. Уроки идут по порядку — от основ к более сложным темам, в каждом есть объяснение с примерами, а в конце — вопросы для самопроверки. К урокам привязаны задачи с автоматической проверкой: прочитали тему — сразу закрепили её кодом.

Программа курса

1 Что такое компилятор
1. Зачем нужен компилятор
  Что делает компилятор, почему процессор не понимает текст программы и как трансляция превращает исходный код в исполнимый.
2. Компилятор, интерпретатор и JIT
  Чем компилятор отличается от интерпретатора, что такое байткод, как работает JIT-компиляция и почему Python и Java сочетают подходы.
3. Конвейер компиляции: этапы
  Из каких фаз состоит компилятор: лексический, синтаксический и семантический анализ, генерация промежуточного кода, оптимизация и кодогенерация.
2 Лексический анализ
1. Токены и лексемы
  Что такое токен, чем лексема отличается от токена, какие бывают типы токенов и зачем лексер отбрасывает пробелы.
2. Пишем лексер на Python
  Пошагово пишем рабочий лексер арифметических выражений на чистом Python: чтение символов, распознавание чисел и операторов, поток токенов.
3. Лексер с заглядыванием вперёд
  Зачем лексеру заглядывать на символ вперёд, как распознавать многосимвольные операторы и числа с точкой, и где границы лексического анализа.
3 Грамматики и BNF
1. Формальные грамматики
  Что такое формальная грамматика, терминалы и нетерминалы, продукции и стартовый символ, и зачем грамматика нужна компилятору.
2. BNF и EBNF
  Нотации BNF и EBNF для записи грамматик: продукции, альтернативы, повторения и необязательные части, отличия двух нотаций.
3. Контекстно-свободные грамматики и приоритет
  Что такое контекстно-свободная грамматика, как уровни нетерминалов кодируют приоритет операторов и почему умножение связывает сильнее сложения.
4 Синтаксический анализ и AST
1. Рекурсивный спуск
  Метод рекурсивного спуска для парсинга: одна функция на каждый нетерминал грамматики, как читать токены и проверять синтаксис.
2. Абстрактное синтаксическое дерево
  Что такое AST, чем оно отличается от дерева разбора, как представить узлы дерева классами Python и почему AST удобнее для дальнейших фаз.
3. Обход AST
  Как обходить AST рекурсивно, паттерн visitor, вычисление выражения через обход дерева и печать дерева в разных порядках.
5 Семантика, IR и виртуальная машина
1. Семантический анализ и таблица символов
  Что проверяет семантический анализ, зачем нужна таблица символов, как отслеживать объявленные переменные, области видимости и типы.
2. Промежуточное представление и байткод
  Что такое промежуточное представление, зачем компилятор генерирует байткод, как обход AST порождает стековые инструкции push и операции.
3. Стековая виртуальная машина
  Как работает стековая виртуальная машина, цикл выборки и исполнения инструкций, исполнение байткода калькулятора на Python.
6 Оптимизации, проект и инструменты
1. Оптимизации компилятора
  Обзорно об оптимизациях компилятора: свёртка констант, удаление мёртвого кода, упрощение выражений — что это и зачем нужно.
2. Проект: интерпретатор арифметики, часть 1
  Сквозной проект: собираем лексер и парсер арифметических выражений на Python, строим AST из потока токенов с учётом приоритета.
3. Проект: интерпретатор арифметики, часть 2
  Завершаем сквозной проект: добавляем вычисление AST, собираем функцию calc и обрабатываем ошибки полного интерпретатора арифметики на Python.
4. Инструменты: ANTLR и LLVM
  Краткий обзор промышленных инструментов компиляции: генератор парсеров ANTLR и инфраструктура LLVM, что они автоматизируют и когда полезны.

Программа курса

1 Что такое компилятор

2 Лексический анализ

3 Грамматики и BNF

4 Синтаксический анализ и AST

5 Семантика, IR и виртуальная машина

6 Оптимизации, проект и инструменты