Примеры на C++ для STL и Lemon

Все примеры используют последний на момент публикации стандарт C++ (C++ 2014). Код примеров призван показать современные технологии и приёмы в построении компиляторов и интерпретаторов. С другой стороны, мы не ставим своей целью показать современный подход к построению архитектуры приложений — поэтому в отдельных местах код может быть намерено упрощённым. Тем не менее, мы заботимся о корректности и краткости примеров кода.

Примеры могут использовать Lemon и LLVM. Информация об их установке здесь.

Синтаксический анализ с генератором парсеров Lemon

Lemon — это генератор парсеров, использующих алгоритм LALR для разбора. Генератор принимает на вход аттрибутную BNF-грамматику. В сравнении с Bison:

• плюсы: Lemon генерирует более чистый код на C, имеет систему деструкторов правил.
• минусы: Lemon не поддерживает EBNF, только упрощённый BNF. Это раздувает код.

Примеры последовательно шаг за шагом выращивают интерпретатор.

• lemon-1-calculator реализует калькулятор арифметических выражений: "1 + 2*(7 /21)"
• lemon-2-interpreter реализует многострочный интерпретатор выражений с поддержкой переменных
• lemon-3-error-recovery добавляет восстановление после ошибок разбора
• lemon-4-ast создаёт абстрактное синтаксическое дерево (AST) и интерпретирует его
• lemon-5-minimal-structured добавляет простейший элемент структурного программирования: инструкцию if без ветки else.
• lemon-6-full-structured добавляет новые элементы структурного программирования: циклы while и repeat .. until, опциональный else для if.
• lemon-7-functions добавляет элементы процедурного программирования: пользовательские функции с аргументами, встроенные функции sin и rand, инструкцию return, выражение вызова функции, области видимости переменных в функциях
• lemon-8-types добавляет динамическую типизацию: ранее был доступен только тип Number, теперь же можно использовать String, Number и Boolean, поддерживаются все старые бинарные операции и вывод через print, добавлены новые операторы сравнения < и ==.
• lemon-9-final добавляет финальные улучшения: логические операторы дизьюнкции, коньюнкци и отрицания; список выражений произвольной длины в print.

Подробнее о Lemon

• Реализация парсера C на Lemon (codeproject.com)
• Lemon-грамматика в исходном коде SQLite (github.com)
• Ещё одна Lemon-грамматика в исходном коде SQLite (github.com)

Генерация кода для регистровой машины с помощью LLVM

LLVM — это фреймворк для создания бекендов компилятора, который предоставляет готовый язык для трёхадресного кода "LLVM-IR", а также готовые модули для его оптимизации, верификации и превращения в машинный код. Средствами LLVM можно получить машинный код под любую поддерживаемую платформу в виде объектного файла. Объектный файл затем можно отдать компоновщику для получения исполняемого файла. LLVM поддерживает все современные аппаратные платформы и операционные системы.

Примеры рассчитаны на LLVM 3.8. Они последовательно шаг за шагом выращивают компилятор.

• llvm-1-ir-translator реализует транслятор путём урезания и преобразования примера lemon-8-types. Транслятор ещё не умеет генерировать объектный файл, и вместо этого создаёт промежуточный код на LLVM-IR.
• llvm-2-compiler реализует полноценную компиляцию от исходного языка до машинного кода в объектом файле. Для генерации машинного кода были использованы исходники утилиты llc, входящей в состав LLVM. При этом вырезана вся обработка опций командной строки, оставлен только минимальный процесс генерации машинного кода.
• llvm-3-structured устраняет последствия урезания возможностей: в нём реализованы ветвления и циклы, отсутствующие в предыдущих двух примерах.
• llvm-4-structured окончательно устраняет разницу в возможностях между lemon-8-types и компилятором на базе LLVM. В этом примере кроме типа Number реализованы типы данных Boolean и String, а в грамматику добавлены правила для объявления типов параметров и возвращаемого значения функции.

Для создания примеров на LLVM использовались следующие источники:

• статьи о языке Kaleidoscope (llvm.org)
• инструкция Mapping High-Level Constructs to LLVM IR, написанная Mikael Lyngvig
• справочник по языку LLVM-IR (llvm.org)

Лексический анализ и разбор на базе C++ STL

• std-regex показывает, как применять стандартный класс регулярных выражений std::regex для сопоставления входной строки с образцом или для построчного сканирования ввода.