Генератор парсера Lemon LALR(1)

1. Обзор

Парсер языка SQL для SQLite генерируется с помощью программы-генератора кода «Lemon». Программа Lemon считывает грамматику входного языка и генерирует C-код для реализации парсера этого языка.

1.1. Файлы и документация Lemon

Lemon не имеет собственного репозитория исходных кодов. Вместо этого Lemon состоит из нескольких файлов в дереве исходных кодов SQLite:

• lemon.html → Исходная подробная документация по использованию и справочник программиста для Lemon.

• lemon.c → Исходный код утилиты, которая считывает файл грамматики и генерирует соответствующий C-код парсера.

• lempar.c → Шаблон для сгенерированного C-кода парсера. Утилита «lemon» считывает этот шаблон и вставляет дополнительный код, чтобы сгенерировать парсер.

2. Преимущества Lemon

Lemon генерирует LALR(1) парсер. Его работа похожа на более известные инструменты Yacc и Bison, но Lemon добавляет важные улучшения, включая:

• Синтаксис грамматики менее подвержен ошибкам — используются символические имена для семантических значений вместо обозначений позиций типа «$1» из Yacc.

• В Lemon вызывающий функция токенизации (лексический анализатор) вызывается парсером. Yacc работает наоборот: парсер вызывает токенизатор. Подход Lemon является рекурсивным и потокобезопасным, в то время как Yacc использует глобальные переменные и поэтому не является ни тем, ни другим. Рекурсивность особенно важна для SQLite, так как некоторые SQL-запросы делают рекурсивные вызовы парсеру. Например, при разборе оператора CREATE TABLE SQLite рекурсивно вызывает парсер для генерации оператора INSERT для добавления новой записи в таблицу sqlite_schema.

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

2.1. Использование Lemon в SQLite

Lemon используется в двух местах в SQLite.

Основное использование Lemon — создание парсера языка SQL. Файл грамматики (parse.y) компилируется Lemon в parse.c и parse.h. Файл parse.c включается в сводный файл без дальнейших изменений.

Lemon также используется для генерации парсера для выражений шаблонов запросов в расширении FTS5. В этом случае входной файл грамматики — fts5parse.y.

2.2. Настройки Lemon, особенно для SQLite

Одним из преимуществ размещения инструментов генерации кода как части проекта является возможность оптимизации инструментов для удовлетворения конкретных потребностей всего проекта. Lemon извлек выгоду из этого эффекта.

На протяжении многих лет генератор парсеров Lemon был расширен и улучшен, чтобы предоставить новые возможности и улучшить производительность SQLite.

Некоторые конкретные улучшения Lemon, специально разработанные для использования в SQLite, включают:

• Lemon имеет понятие «запасного» токена. Язык SQL содержит большое количество ключевых слов, и эти ключевые слова могут сталкиваться с именами идентификаторов. Lemon позволяет назначать некоторые ключевые слова как имеющие возможность «запасного» использования в качестве идентификатора. Если ключевое слово появляется в потоке входных токенов в контексте, который в противном случае был бы синтаксической ошибкой, токен автоматически преобразуется в его запасной вариант перед появлением синтаксической ошибки. Эта функция позволяет парсеру быть очень толерантным к зарезервированным словам, используемым как идентификаторы, что часто возникает в языке SQL.

• В поддержку цели 100%-ного тестирования MC/DC для SQLite, код парсера, сгенерированный Lemon, не имеет недостижимых ветвей и содержит дополнительную (выбираемую во время компиляции) инструментацию, полезную для измерения покрытия тестами.

• Lemon поддерживает условную компиляцию правил файла грамматики, таким образом, можно сгенерировать разные парсеры в зависимости от параметров компиляции.

• В целях повышения производительности, допускаются действия в грамматике входных данных Lemon, которые содержат комментарии вида «/*A-overwrites-Z*/», чтобы указать, что семантическое значение «A» в правой части правила может непосредственно перезаписать семантическое значение «Z» в левой части. Эта простая оптимизация уменьшает количество операций стека в детерминированном автомате с магазиной, используемом для разбора входной грамматики, и, следовательно, улучшает производительность парсера. Она также делает сгенерированный код немного меньше.

Разбор SQL-запросов является значительным потребителем циклов процессора в любом движке SQL-базы данных. Постоянные усилия по оптимизации SQLite привели к тому, что разработчики потратили много времени на настройку Lemon для генерации более быстрых парсеров. Эти усилия принесли пользу всем пользователям генератора парсеров Lemon, а не только SQLite. Но если бы Lemon был отдельно поддерживаемым инструментом, было бы сложнее внести согласованные изменения как в SQLite, так и в Lemon, и в результате оптимизации было бы сделано меньше. Таким образом, тот факт, что инструмент генерации парсеров включен в дерево исходных кодов SQLite, оказался чистым преимуществом как для самого инструмента, так и для SQLite.

3. История Lemon

Lemon был первоначально написан D. Richardem Hippom (также создателем SQLite), когда он учился в аспирантуре в Университете Дьюка в период с 1987 по 1992 год. Точная дата создания Lemon утеряна, но, вероятно, это было где-то около 1990 года. Lemon генерирует LALR(1) парсер. Существовал сопутствующий инструмент генерации LL(1) парсеров под названием «Lime», но исходный код Lime утерян.

Исходный код Lemon первоначально был написан как отдельные файлы исходного кода, и только позже был объединен в один файл «lemon.c».

Автор Lemon и SQLite (Hipp) сообщает, что его навыки программирования на C значительно улучшились благодаря изучению исходного кода Tcl от Джона Оустерхаута. Hipp обнаружил и изучил Tcl в 1993 году. Lemon был написан до этого, а SQLite — после. Существует явное различие в стилях кодирования этих двух продуктов, при этом SQLite выглядит чище, понятнее и проще в обслуживании.