Re2c

re2c (regular expression to c, regular expression to code) — это свободная утилита–генератор с открытым исходным кодом, она генерирует быстрые и легко встраиваемые лексеры, ориентирована на работу совместно с языками: Си, C++, D, Go, Haskell, Java, JavaScript, OCaml, Python, Rust, Swift, и Zig.

Изначально утилита была создана Питером Бамбулисом () и описана в его статье, позже re2c был передан в общественное достояние и с тех пор поддерживается добровольцами.

Утилита отличается от своих более известных аналогов (таких как lex и flex) тем, что имеет гибкий интерфейс взаимодействия (сгенерированный код взаимодействует с внешней программой с помощью примитивов), генерирует оптимизированные нетабличные лексеры, поддерживает захваты (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA).

Утилита в основном распространена в проектах, где требуется высокая скорость анализа синтаксиса, например Ninja и PHP.

Философия Основная цель re2c — генерировать быстрые лексеры, по крайней мере настолько же быстрые, как и разумно оптимизированные лексеры, написанные вручную на языке Си. Вместо использования традиционного табличного подхода re2c кодирует сгенерированный конечный автомат непосредственно в форме условных переходов и сравнений. В результате программа работает быстрее, чем её аналог на основе таблиц, и её гораздо проще отлаживать и понимать. Более того, такой подход часто приводит к уменьшению размера лексеров, поскольку re2c применяет ряд оптимизаций, таких как минимизация ДКА и построение туннельного автомата. Еще одной отличительной особенностью re2c является его гибкий интерфейс. Вместо того, чтобы использовать фиксированный шаблон программы, re2c позволяет программисту написать большую часть кода интерфейса и адаптировать сгенерированный лексер к любой конкретной среде. Основная идея заключается в том, что re2c должен быть абстракцией с нулевыми затратами для программиста, использование утилиты никогда не должно приводить к более медленной работе программы, чем соответствующая реализация с вручную написанным кодом.

Возможности Захваты submatch extraction — re2c поддерживает как группы захвата, совместимые с POSIX, так и отдельные тэги. Реализация основана на алгоритме «lookahead-TDFA»; Поддержка различных кодировок — re2c поддерживает ASCII, UTF-8, UTF-16, UTF-32, UCS-2 и EBCDIC; Гибкий пользовательский интерфейс — сгенерированный код использует несколько примитивных операций для взаимодействия с окружающей средой (считывание входных символов, переход к следующей позиции ввода и т. д.). Пользователи могут переопределять эти примитивы так, как им необходимо; Сохраняемое состояние — re2c поддерживает как лексеры pull-модели (когда лексер работает без прерываний и при необходимости извлекает больше входных данных), так и лексеры push-модели (когда лексер периодически останавливается и возобновляется для анализа новых блоков ввода); Условия запуска — re2c может генерировать несколько взаимосвязанных уровней, где каждый лексер запускается определенным условием в программе; Самопроверка — re2c имеет специальный режим, в котором он игнорирует весь код интерфейса, определенный пользователем, и генерирует автономную программу-скелет. Кроме того, re2c генерирует два файла — один со строками ввода, полученными из обычной грамматики, и один со сжатыми результатами сверки, которые используются для проверки поведения лексера на всех входах. Входные строки генерируются так, чтобы они широко охватывали переходы и пути ДКА. Генерация данных происходит сразу после построения ДКА и до любых оптимизаций, но сам лексер полностью оптимизирован, поэтому программы-скелеты способны выявлять любые ошибки в оптимизации и генерации кода; Система предупреждений — re2c выполняет статический анализ программы и предупреждает своих пользователей о возможных неопределённостях или ошибках, таких как неопределённый поток управления, недостижимый код, неправильно экранированные escape-символы и потенциальное неправильное использование примитивов интерфейса; Отладка — помимо создания удобочитаемых лексеров, re2c имеет ряд опций, которые выводят различные промежуточные представления сгенерированного лексера, такие как НКА, несколько этапов ДКА и результирующий программный график в формате языка DOT.

Синтаксис Программа re2c может содержать любое количество блоков /*!re2c ... */. Каждый блок состоит из последовательности правил, определений и конфигураций (их можно смешивать, но, как правило, лучше сначала размещать конфигурации, затем — определения, а затем — правила). Правила имеют вид — REGEXP { CODE } или REGEXP := CODE;, где REGEXP — регулярное выражение, а CODE — является блоком кода на языке Си. Когда REGEXP совпадает с входной строкой, поток управления передаётся соответствующему блоку CODE. Существует одно специальное правило: правило по умолчанию с * вместо REGEXP, оно срабатывает, если никакие другие правила не совпадают. re2c имеет семантику жадного соответствия — если несколько правил совпадают, предпочтительным является правило, соответствующее более длинному префиксу, если конфликтующие правила соответствуют одному и тому же префиксу, то более раннее правило имеет приоритет. Определения имеют вид NAME = REGEXP; (и, соответственно, NAME { REGEXP } в Flex-совместимом режиме). Конфигурации имеют вид re2c:CONFIG = VALUE;, где CONFIG является именем конкретной конфигурации и VALUE является числом или строкой. Для более расширенного использования ознакомьтесь с официальным руководством re2c.

Регулярные выражения re2c использует следующий синтаксис для регулярных выражений: "foo" строковый литерал с чувствительностью к регистру; 'foo' строковый литерал без чувствительности к регистру; [a-xyz], [^a-xyz] класс символов (с возможностью отрицания); . любой возможный символ, кроме символа новой строки; R \ S разница в классах символов; R* нуль или большее количество совпадений с символом R; R+ одно или большее количество совпадений с символом R; R? необязательное совпадение с символом R (нуль или одно); R{n} повторение R точно n раз; R{n,} повторение R по крайней мере n раз; R{n,m} повторение R от n до m раз; (R) просто R (круглые скобки используются для переопределения приоритета или для соответствия в стиле POSIX); R S конкатенация R, за которой следует S; R | S альтернатива R или S; R / S поиск с опережением () R, за которой следует S; name регулярное выражение, определенное как name (за исключением режима совместимости с Flex); @stag s-метка (с — метка или тэг) — сохраняет последнюю позицию ввода, в которой @stag совпадает с переменной с именем stag; #mtag m-метка — сохраняет все позиции ввода, в которых #mtag совпадает с переменной с именем mtag.

Классы символов и строковые литералы могут содержать следующие escape-последовательности: \a, \b, \f, \n, \r, \t, \v, \\, восьмеричного вида \ooo и шестнадцатеричного вида \xhh, \uhhhh, \Uhhhhhhhh.

Примеры кода

Программные проекты, использующие re2c PHP — популярный язык сценариев общего назначения; Ninja — система сборки, ориентированная на скорость; SpamAssassin — программа для фильтрации спама электронной почты; BRL-CAD — программа 3D-моделирования (САПР); STEPCode — имплементация стандарта ISO 10303; Yasm — модульный ассемблер, полная переработка NASM; Wake — инструмент для сборки от SiFive.

См. также

Синтаксис Синтаксический анализ Лексический анализ Подсветка синтаксиса Стандарт оформления кода Lex

Flex Bison Компилятор Интерпретатор Транслятор

Примечания

Ссылки

Официальный сайт Репозиторий проекта

Категория:Инструменты компиляции Категория:Программное обеспечение в общественном достоянии Категория:Генераторы лексических анализаторов