В четверг 27 января состоялся релиз генератора лексических анализаторов re2c 3.0. Основное изменение — добавлена кодогенерация в Rust.

Напомним, что re2c специализируется на генерации быстрых и легко встраиваемых лексеров. Он отличается от более известного аналога flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP.

На сайте есть много примеров, теперь и на языке Rust.

>>> Подробности

В понедельник 20 июля вышел релиз re2c – генератора быстрых лексических анализаторов. Основные изменения:

• Добавлена поддержка языка Go (включается или опцией --lang go для re2c, или в виде отдельной программы re2go). Документация для C и Go генерируется из одного и того же текста, но с разными примерами кода. Полностью переработана подсистема кодогенерации в re2c, что должно облегчить поддержку новых языков в будущем.

• Добавлена альтернативная система сборки на CMake (спасибо ligfx!). Попытки перевести re2c на CMake предпринимались уже давно, но до ligfx никто не предложил полноценное решение. Старая система сборки на Autotools продолжает поддерживаться и использоваться, и в обозримом будущем нет планов от неё отказаться (отчасти чтобы не создавать проблем разработчикам дистрибутивов, отчасти потому что старая система сборки стабильнее и лаконичнее новой). Обе системы наравне непрерывно тестируются при помощи Travis CI.

• Добавлена возможность задания интерфейсного кода в конфигурациях при использовании обобщённго АПИ (generic API). Раньше большинство АПИ приходилось задавать в форме функций или функциональных макросов. Теперь их можно задавать в форме произвольных строк с именованными шаблонными параметрами вида @@{name} или просто @@ (если параметр один и не возникает неоднозначности). Стиль АПИ задаётся конфигурацией re2c:api:style (значение functions задаёт функциональный стиль, а free-form – произвольный).

• Улучшена работа опции -c, --start-conditions, позволяющей совмещать несколько взаимосвязанных лексеров в одном re2c-блоке. Теперь можно использовать обычные блоки наравне с условными и задавать несколько не связанных условных блоков в одном файле. Улучшена работа опции -r, --reuse (повторное использование кода из одного блока в других блоках) в сочетании с опциями -c, --start-conditions и -f, --storable-state (лексер с сохраняемым состоянием, который можно прервать в произвольном месте и продолжить выполнение позже).

• Исправлена ошибка в недавно добавленном алгоритме обработки конца входных данных (EOF rule), приводившая в редких случаях к неправильной обработке перекрывающихся правил.

• Упрощён процесс бутстрапа. Раньше система сборки пыталась динамически найти уже собранный re2c, который можно было бы использовать для пересборки самого себя. Это приводило к неправильным зависимостям (поскольку граф зависимостей получался динамическим, чего большинство систем сборки не любит). Теперь чтобы пересобрать лексеры, требуется в явном виде сконфигурировать систему сборки и задать переменную RE2C_FOR_BUILD.

Спасибо всем, кто участвовал в подготовке этого релиза!

>>> Подробности

В пятницу 2-го августа вышел релиз re2c — свободного генератора лексических анализаторов для языков C и C++. Напомним, что re2c был написан в 1993 году Питером Бамбулисом как экспериментальный генератор очень быстрых лексических анализаторов, отличающийся от других генераторов скоростью сгенерированного кода и необычно гибким пользовательским интерфейсом, который позволяет легко и эффективно встривать анализаторы в существующую кодовую базу. С тех пор проект развивается сообществом и продолжает оставаться площадкой для экспериментов и исследований в области формальных грамматик и конечных автоматов.

( читать дальше... )

>>> Подробности

RE2C — генератор лексических анализаторов для языков C и C++, созданный в 1993 году Питером Бамбулисом в качестве альтернативы небезызвестному Flex. Основной целью RE2C является генерация очень быстрых лексеров: по скорости исполнения они должны не уступать коду, написанному и оптимизированному вручную (в пределах разумного). В отличие от Flex, RE2C не использует табличную модель лексера: он кодирует конечный автомат прямо в виде программы на С, состоящей из меток и условных переходов. Полученный лексер оказывается не только быстрее, но часто ещё и меньше [1] (RE2C минимизирует конечный автомат и применяет ряд других оптимизаций). Другая особенность RE2C — отсутствие жёсткого интерфейса: в отличие от Flex, он не генерирует код «обвязки» между лексером и внешним миром. Ответственность за написание этого кода остаётся на пользователе, что даёт большую свободу и позволяет приспосабливать лексеры к уже существующему программному окружению.

Смена мажорной версии (впервые за всю историю проекта) объясняется не поломкой обратной совместимости, а нетривиальным расширением возможностей генератора: кроме обычного распознавания регулярных грамматик (англ. recognition) RE2C теперь умеет частичный синтаксический разбор (англ. submatch extraction). Эта возможность легко реализуема на основе недетерминированных автоматов, и поэтому давно присутствует во многих утилитах (grep, sed), библиотеках регулярных выражений (RE2) и языках (Perl, JS). А вот в генераторах лексеров эта возможность обычно отсутствует (Lex, Flex, Quex), корректно работает только на малой части случаев (Ragel) или реализована путём серьёзного усложнения модели (Tlex). Одно из следствий невозможности синтаксического разбора средствами детерминированных конечных автоматов — изначально поломанный оператор предпросмотра в Lex и Flex.

Алгоритм разбора, заложенный в основе RE2C, был предложен Вилле Лаурикари в 2000 году [2]. Этот алгоритм хорош тем, что усложняет модель вычислений ровно настолько, насколько того требует детализация синтаксического разбора в каждом конкретном случае: для обычных задач распознавания модель Лаурикари соответствует простому детерминированному автомату. RE2C использует «улучшенную и дополненную» версию алгоритма, предложенную автором сего поста [3].

[1] Cтатья 1993 года, в которой проведён сравнительный анализ RE2C, Flex и других генераторов

[2] Статья 2000 года, которая описывает быстрый алгоритм разбора

[3] Статья 2017 года, которая описывает новый ещё более быстрый алгоритм разбора

>>> Подробности