А что такое Compiler Frontend?

Все статьи / А что такое Compiler Frontend?

Compiler Frontend — первый из двух ключевых компонентов компилятора, о котором можно сказать следующее:

Frontend получает на вход текст программы
если в тексте есть синтаксические и семантические ошибки, Frontend находит их
если текст корректен, Frontent строит абстрактное синтаксическое дерево (AST), хранящее логическую модель файла исходного кода
превращение текста в AST происходит в три этапа: сначала текст делится на токены (лексический анализ), затем токены собираются по грамматике в AST (синтаксический анализ), а затем AST проходит постобработку (семантический анализ)

Интересный факт: в интерпретаторах тоже есть Frontend, а вот Backend может не существовать — для интерпретации достаточно выполнить обход AST, последовательно вычисляя значения в нелистовых узлах. В интерпретаторах промышленного уровня качества Backend есть, и он генерирует байткод виртуальной машины.

Три стадии: лексический, синтаксический, семантический анализ

Исходя из иерархии грамматик Хомского, языки делятся на четыре уровня. Выпишем последние три в обратном порядке:

регулярные грамматики: с ними справляется лексический анализ; синтаксический тоже справится
контекстно-свободные грамматики: синтаксический анализ с ними справится
контекстно-зависимые грамматики: синтаксический анализ с ними напрямую не справится

К сожалению, все промышленные языки программирования относятся к контекстно-зависимым грамматикам. Поэтому в ход идут две хитрости:

из языка выделяют синтаксис (syntax) - его контекстно-свободную часть, и семантику (semantic) - дополнительные правила, которые дополняют синтаксис до полноценного языка
- примеры семантики: правила проверки типов в выражениях, запрет на использование переменной до её объявления и так далее
- после выделения синтаксиса для него пишут грамматику (контекстно-свободную), и по грамматике пишут парсер (parser)
поскольку контекстно-свободная грамматика всё ещё остаётся сложной, из неё выделяют регулярную подграмматику
- выделяют токены: идентификаторы, литералы и так далее
- выделяют элементы, не входящие в грамматику: пробельные символы и комментарии
- пишут лексер (lexer), который принимает на вход текст и превращает поток символов в поток токенов

Разделение синтаксиса и семантики необходимо - потому что не существует эффективных алгоритмов разбора контекстно-зависимых грамматик. Разделение на синтаксический и лексический анализ не обязательно с точки зрения теории, но всегда используется на практике: это упрощает парсер грамматики, уменьшает объём работ и количество ошибок в компиляторе.

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

Синтаксический анализ — ядро фронтенда, в самых простых языках (уровня калькулятора с переменными) это вообще единственный этап обработки текста во фронтенде.

Формальный язык имеет грамматику, которая описывает файл с исходным кодом как набор рекурсивных конструкций (заданных правилами грамматики). Обычно грамматика делится на следующие уровни:

выражения (expressions), рекурсивно состоящие из атомов (переменных и литералов), унарных и бинарных операций (арифметических, логических и т.д.), вызовов функций
- термины: expression, function call, binary operator, unary operator, variable, literal
инструкции (statements), которые делятся на категории: управляющие инструкции (ветвления, циклы), инструкции-выражения (такие, как вызов метода), инструкции-присваивания, инструкции-блоки (в языке C++ инструкция-блок - это {}) и специальные инструкции (например, в Python это assert и delete)
объявления (declarations) и определения (definitions), которые делятся на категории: объявления и определения функций, классов, глобальных переменных

Цель синтаксического анализа - построить AST. Этой цели добиваются, соединяя парсер грамматики (grammar parser) и семантические действия (semantic actions).

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

Цель лексического анализа - превратить поток символов в поток токенов (токены - это идентификаторы, литералы и так далее). В коде компилятора токен обычно представляют каким-либо value-типом, например, структурой в языке C++. Разобрать текст на токены можно с помощью ДКА (теория гласит, что это можно сделать одним проходом по строке без возвратов - и генераторы лексических анализаторов именно так и делают).

Хороший класс, представляющий лексический анализатор, хранит ссылку на исходный код (в виде строки или потока) и по запросу возвращает очередной токен.

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

Семантический анализ обычно реализуют как серию обходов по AST, т.е. обычных проходов по дереву с выполнением каких-либо действий в каждом узле. Реализовать каждый обход, не меняя постоянно классы AST, можно с помощью паттерна проектирования Visitor. В этом случае семантический анализ выполняется несколькими классами, каждый из которых реализует одну проверку путём обхода дерева.

Набор семантических проверок может быть очень широким. Примеры:

проверка типов в выражениях
проверка определения всех переменных до их первого использования
проверка использования break только внутри циклов или switch

Важная часть семантического анализа - области видимости (scopes). В современных областях области видимости обычно лексические (lexical scopes). Чтобы понять, как работают области видимости, достаточно хорошо освоить механизм замыканий (closures).

Что надо знать до разработки фронтенда

Для реализации фронтенда простейшего, процедурного языка понадобится:

Владеть паттернами проектирования: Посетитель (Visitor), Фасад (Facade)
Владеть структурами данных: деревья, строки
Понимать структуру формальных языков: выражения (expressions), инструкции (statements), области видимости переменных (scopes), подпрограммы (subroutines)

Для реализации бекенда объектно-ориентированного языка также нужно:

Знать детали работы языка C++: что такое раскрутка стека при выбросе исключения (stack unwinding), кодирование имён (name mangling), как устроены vtable и как реализовать полиморфизм с помощью hash-таблицы методов

Обработка ошибок во фронтенде

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

Современные компиляторы практикую восстановление после ошибок для того, чтобы пользователь мог сразу определить и исправить больше одной ошибки. Кроме того, многие современные компиляторы обслуживают задачи IDE по анализу кода. Для IDE восстановление после ошибки просто необходимо: едва ли вы обрадуетесь, если одна лишняя запятая в вашем коде напрочь уничтожит подсветку и автодополнение.

Для обработки ошибочных конструкций во фронтенде есть всего несколько подходов:

1) Добавлять правила, порождающие ошибки.

Например, лексер может считать, что любая подстрока, сответствующая регулярному выражению /[0-9]+[A-Za-z0-9]*/ является ошибочной, т.к. в ней целое число склеено с идентификатором без пробелов и разделителей (например, 01abcd).
Парсер может обрабатывать специальным правилом появление else без if - если он этого не сделает, пользователь может получить десяток различных ошибок вместо одной

2) Пропускать ввод и восстанавливаться по специальным символам и токенам

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

Пример кода с пропущенной кавычкой:

let str = "Hello, World!
alert(str);

Парсер может восстанавливаться по-разному в зависимости от контекста:

при ошибке парсинга выражения можно пропускать всё до разделителя инструкций (например, “;”), потому что такой разделитель не может встретиться в выражении
при ошибке парсинга инструкции в C-подобных языках можно пропускать всё до закрывающей фигурной скобки, потому что скобка закрывает блок

Читать далее

Лексика:

Синтаксис:

Семантика: