Как стать автором
Обновить
1359.49
Timeweb Cloud
То самое облако

Нюансы разработки парсера для своего языка программирования

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров11K

image


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


Я решил не сильно париться, поэтому использовал библиотеку 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 можно почитать тут.


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


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


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


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


Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале

Теги:
Хабы:
Всего голосов 25: ↑23 и ↓2+28
Комментарии55

Публикации

Информация

Сайт
timeweb.cloud
Дата регистрации
Дата основания
Численность
201–500 человек
Местоположение
Россия
Представитель
Timeweb Cloud