Недавно прочитал на Хабре статью Свой язык, или как я устал от ассемблера и С, и невольно взглядом зацепился за один абзац:

Я решил не сильно париться, поэтому использовал библиотеку parglare. Она очень легкая и удобная, всем рекомендую. Для описания синтаксиса парсер принимает строку в соответствующем формате, использует регулярные выражения (не надо осуждать регулярки, они всесильны!).

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

Ведь в жизни практически любого программиста может наступить момент, когда ему в голову приходит светлая идея — разработать свой собственный язык программирования. Может быть и не ради захвата мира, наравне с C/C++, Python или хотя бы PHP, а в качестве личного пет-проекта, с которым он, длинными зимними вечерами будет оттачивать собственное мастерство.

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

Это история — заметки на память о муках выбора связки лексер-парсер для разбора грамматики NewLang. А так же попытка описать и систематизировать выводы об особенностях разных анализаторов с которыми пришлось поработать при выборе парсера для разбора грамматики у своего языка программирования.

Используемые термины.

Чтобы было понятно, о чем в дальнейшем пойдет речь.

Лексер — компьютерная программа или библиотека, в задачи которой входит разделить входной поток данных на отдельные, не связанные между собой отдельные фрагменты, которые принято называть токенами или лексемами.

Парсер — на основе последовательности токенов выполняется синтаксический анализ, например строит абстрактное синтаксическое дерево (AST).

Заход № 1 — Flex + Bison

GitHub — westes/flex: The Fast Lexical Analyzer — scanner generator for lexing in C and C++
Bison — GNU Project — Free Software Foundation

После прочтения умных книжек я начал с классики Flex + Bison. Это старые и давно отработанные приложения с широчайшими возможностями по настройке с помощью которых можно описать синтаксис и получить исходные файлы лексера и парсера для языка практически с любой грамматикой.

К сожалению, у этих старичков очень большой порог входа и тяжелая наследственность. Чего только стоит определение собственного класса лексера через #define, а так же отсутствие нормальной поддержки С++. Вынужденные танцы с бубном для пасинга отдельной строки, когда не требуется анализировать файл целиком и прочие не всегда очевидные проблемы и разные не понятные условности.

Другими словами, через несколько недель безуспешных мучений я решил посмотреть альтернативы, а так как начальный файл лексики после экспериментов с Flex + Bison кое-как уже был сделан, то следующая связка была Flex + lemon.

Заход № 2 — Flex + Lemon

The Lemon LALR(1) Parser Generator

Тут все оказалось до примитивности просто и понятно. Реально очень быстрый старт с боевыми примерами, очень наглядный и понятный способ записи правил (по сравнению с Bison). Все хорошо кроме одного, хорошее быстро заканчивается, если приходится анализировать более одной строки.

По сути, Lemon с Bison, это как Инь и Янь. Lemon простой и удобный для работы с одной строкой (для этого он и создавался), а Bison супер-пупер-мега комбайн для парсинга файлов любых размеров.

Поэтому, поиски связки лексер + парсер продолжились и после прочтения очередной статьи, что парсеры языков можно делать на регулярках, решил посмотреть, что есть в этом направлении:

Заход № 3 парсер на регулярках re2c

Из описания re2c:

По сути, на этой штуке можно писать лексические анализаторы прямо на коленке за несколько минут.

    /*!re2c
        re2c:define:YYPEEK       = "*cursor";
        re2c:define:YYSKIP       = "++cursor;";
        re2c:define:YYBACKUP     = "marker = cursor;";
        re2c:define:YYRESTORE    = "cursor = marker;";
        re2c:define:YYBACKUPCTX  = "ctxmarker = cursor;";
        re2c:define:YYRESTORECTX = "cursor = ctxmarker;";
        re2c:define:YYRESTORETAG = "cursor = ${tag};";
        re2c:define:YYLESSTHAN   = "limit - cursor < @@{len}";
        re2c:define:YYSTAGP      = "@@{tag} = cursor;";
        re2c:define:YYSTAGN      = "@@{tag} = NULL;";
        re2c:define:YYSHIFT      = "cursor += @@{shift};";
        re2c:define:YYSHIFTSTAG  = "@@{tag} += @@{shift};";
    */

Показалось, что это самый удобный способ указания шаблонов для парсера! Достаточно описать в комментариях нужные шаблоны, напустить на исходный файл компилятор регулярок и все готово! Но нет, действительно, это только показалось.

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

После этого решил с ним не заморачиваться и посмотреть альтернативы классическим лексерам и парсерам.

Заход № 4 — flex (flexcpp) + bisoncpp

Тогда как у традиционных flex + bison поддержка С++ реализована через одно место на уровне — работает и не трогай, то решил посмотреть их альтернативную реализация flexcpp + bisoncpp с нативной поддержкой С++.

Первое впечатление было, то что доктор прописал!

Синтаксис записи лексики хоть немного и отличается от классической, но это не принципиально. Зато есть нативная и логичная поддержка С++ без оберток и выкрутасов, и как дополнительный плюс — более удобный синтаксис указания правил в парсере. Но и тут не обошлось без шероховатостей.

В шаблонах правил bisoncpp не поддерживает юникод (хотя сам лексер-парсер с ним справляется на ура), и совсем не понятная ситуация с поддержкой. Как я понял, разработчиком является вроде бы один человек, но пообщаться с ним насчет ошибок при обработке русских символов так и не получилось.*

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

---

*) Через два года мой тикет был закрыт с комментарием, что поддерживаются только ascii символы.

Заход № 5 — неродной парсер ANTLR

От использования ANTLR (от англ. ANother Tool for Language Recognition — «ещё одно средство распознавания языков») — генератора нисходящих анализаторов для формальных языков, я решил сразу отказать из-за того, что он написан на Java,.

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

Таким образом я опять вернулся к старичкам Flex и Bison, с которых все и начиналось.

Заход № 6, последний — возвращение к Flex + Bison

Все описанные выше эксперименты заняли в общем итоге несколько месяцев, в результате которых были написаны килобайты исходного кода и тестовых примеров, прочитано десятки статей и как результат — возврат к изначальной связке Flex + Bison, но уже с солидным багажом опыта в применении различных вариантов лексеров-парсеров.

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

Выводы на память

В итоге для себя решил следующее: если нужен простенький шаблонизатор, то идеальный вариант re2c (если почему-то не подходит regexp). Если требуется анализировать синтаксис сложнее обычных регулярок, но в одну строку, то идеальной будет связка flex+lemon, а если нужна серьезная артиллерия, то тут однозначно flex + bison.

От связки flexcpp + bisoncpp отказался совсем. Что с поддержкой — не понятно, синтаксис от классики отличается не очень сильно (хотя тоже нужно ломать голову), а обход выявленных косяков не стоят того синтаксического сахара.

И по итогам множества экспериментов с разными вариантами синтаксиса удалось сформулировать пару важных архитектурных моментов, которые могут очень сильно упростить жизнь создателям языком программирования:

Стратегия обработки ошибок синтаксиса

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

Но если грамматика языка очень сложная (привет C++), и её описание становится сложной задачей, то можно отказался и от анализа ошибок синтаксиса непосредственно в парсере! То есть, лучше сделать максимально широкую лексику (даже с теми вариантами, которые являются для языка ошибочными), но ловить эти ошибки уже при анализе AST!

В этом случае, поддерживать описание грамматики языка становится значительно проще (меньше синтаксических правил, проще их формальное описание и т.д.), а самое главное, при описании грамматики не нужно думать про lval или rval, где можно указывать ссылку, а где нет — т. е. можно указывать все и везде, а вот анализ допустимости использования конкретных терминов будет выполняться позднее при анализе AST.

Отказа от полного анализа грамматики языка на уровне лексера — парсера и перенос проверки корректности синтаксических конструкций на этап разбора синтаксического дерева позволяет в разы, если не на порядки сократить и значительно упростить описание грамматических правил!

Подобное допущение очень полезно на начальном этапе создания языка (можно сосредоточиться на общей концепции, вместо постоянных правок в грамматике), а так же значительно упростить в будущем поддержку и/или расширение синтаксиса.

Макросы и модификация грамматики в Runtime

Какими бы мощными не были flex+bison, но у этой связки есть одна архитектурная проблема. Логика flex и bison построена на конечных автоматах и изменить грамматику языка во время выполнения приложения невозможно, тем более Bison сам вызывает лексер для получения очередной порции данных и ему очень непросто подсунуть измененные данные прямо во время работы. А так хотелось сделать возможность раскрытия макросов и модификации синтаксиса за один проход анализатора!

Для этого пришлось переделать логику работы flex+bison, чтобы парсер получал данные из лексера не напрямую из yylex, а через функцию — прокси. Эта промежуточная функция, складывает считанные лексемы во внутренний буфер. Данные в буфере анализируется на предмет наличия макросов и только после их раскрытия, лексемы отдаются в парсер из вершины буфера по одной за раз. Подробнее о макросах NewLang можно почитать тут.

Самое главное при разработке грамматики!

Но самый важный совет мне подсказал друг, который некогда участвовал в проекте по разработке парсера для языка программирования. И в правильности его совета — пиши тесты для грамматики — я убеждался уже множество раз. Даже так, ПИШИ ТЕСТЫ ДЛЯ ГРАММАТИКИ.

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

И удачи всем языкописателям!