Нюансы разработки парсера для свего языка программирования
Недавно прочитал на Хабре статью Свой язык, или как я устал от ассемблера и С, и невольно взглядом зацепился за один абзац:
Я решил не сильно париться, поэтому использовал библиотеку 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 можно почитать тут.
Самое главное при разработке грамматики!
Но самый важный совет мне подсказал друг, который некогда участвовал в проекте по разработке парсера для языка программирования. И в правильности его совета — пиши тесты для грамматики — я убеждался уже множество раз. Даже так, ПИШИ ТЕСТЫ ДЛЯ ГРАММАТИКИ.
Тесты для грамматики языка гораздо более важная вещь, чем любой из используемых инструментов. Только тесты позволяют убедиться в том, что новая фича в языке не сломала старые наработки. А если все же сломала, то в первую очередь нужно добавить новый тест, который бы фиксировал сломавшийся сценарий и только после этого можно будет со спокойной душой продолжать эксперименты с новыми грамматическими конструкциями.
И удачи всем языкописателям!
