re2c-1.0
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 года, которая описывает новый ещё более быстрый алгоритм разбора
>>> Подробности
