re2c

re2c — бесплатный генератор лексеров с открытым исходным кодом для C , C++ , Go и Rust . Он компилирует декларативные спецификации регулярных выражений в детерминированные конечные автоматы . Первоначально написанный Питером Бумбулисом и описанный в его статье, ^[1] re2c был выложен в открытый доступ и с тех пор поддерживается добровольцами. ^[3] Это генератор лексеров, принятый в таких проектах, как PHP , ^[4] SpamAssassin , ^[5] Система сборки Ninja ^[6] и других. Вместе с генератором парсера Lemon в BRL-CAD используется re2c . ^[7] Эта комбинация также используется со STEPcode, реализацией стандарта ISO 10303 . ^[8]

Философия

Основная цель re2c — создание быстрых лексеров: ^[1] по крайней мере так же быстро, как разумно оптимизированные лексеры C , написанные вручную. Вместо использования традиционного табличного подхода re2c кодирует сгенерированный конечный автомат непосредственно в форме условных переходов и сравнений. Полученная программа работает быстрее, чем ее аналог, управляемый таблицами ^[1] , и ее гораздо проще отлаживать и понимать. Более того, этот подход часто приводит к уменьшению лексеров ^[1] , поскольку re2c применяет ряд оптимизаций, таких как минимизация DFA и построение туннельного автомата. ^[9] Еще одной отличительной особенностью re2c является его гибкий интерфейс: вместо использования фиксированного шаблона программы re2c позволяет программисту писать большую часть кода интерфейса и адаптировать сгенерированный лексер к любой конкретной среде. Основная идея заключается в том, что re2c должен быть абстракцией с нулевой стоимостью для программиста: его использование никогда не должно приводить к более медленной программе, чем соответствующая реализация, написанная вручную.

Функции

• Извлечение подсоответствий: ^[10] re2c поддерживает как POSIX-совместимые группы захвата, так и отдельные теги ^[11] (с крайним левым жадным устранением неоднозначности и дополнительной обработкой повторяющихся совпадений). Реализация основана на алгоритме Lookahead-TDFA. ^{[12] [13] [14]}

• Поддержка кодировки: ^[15] re2c поддерживает ASCII, UTF-8, UTF-16, UTF-32, UCS-2 и EBCDIC.
• Гибкий пользовательский интерфейс: ^[16] сгенерированный код использует несколько примитивных операций для взаимодействия с окружающей средой (чтение входных символов, переход к следующей позиции ввода и т. д.); пользователи могут переопределить эти примитивы так, как им нужно.
• Сохраняемое состояние: ^[17] re2c поддерживает как лексеры модели извлечения (когда лексер работает без прерываний и при необходимости извлекает больше входных данных), так и лексеры модели push (когда лексер периодически останавливается и возобновляется для анализа новых фрагментов ввода).
• Условия запуска: ^[18] re2c может генерировать несколько взаимосвязанных лексеров, где каждый лексер запускается определенным условием в программе.
• Самопроверка: ^[19] re2c имеет специальный режим, в котором он игнорирует весь используемый код интерфейса и генерирует автономную скелетную программу. Кроме того, re2c генерирует два файла: один с входными строками, полученными из обычной грамматики, и другой со сжатыми результатами сопоставления, которые используются для проверки поведения лексера на всех входных данных. Входные строки генерируются так, что они полностью охватывают переходы и пути DFA. Генерация данных происходит сразу после построения DFA и перед любой оптимизацией, но сам лексер полностью оптимизирован, поэтому скелетные программы способны выявить любые ошибки в оптимизации и генерации кода.
• Предупреждения: ^[20] re2c выполняет статический анализ программы и предупреждает пользователей о возможных недостатках или ошибках, таких как неопределенный поток управления, недоступный код, неправильно сформированные escape-символы и потенциальное неправильное использование примитивов интерфейса.
• Отладка. Помимо генерации удобочитаемых лексеров, re2c имеет ряд опций, которые сбрасывают различные промежуточные представления сгенерированного лексера, такие как NFA , несколько этапов DFA и результирующий граф программы в формате DOT . ^[21]

Синтаксис

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

Обычные выражения

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, но Sне потребляется
• nameрегулярное выражение, определенное как name(кроме режима совместимости Flex )
• @stags -тег : сохраняет последнюю входную позицию, в которой @stagесть совпадения, в переменной с именемstag
• #mtagm -тег : сохраняет все входные позиции, в которых #mtagесть совпадения, в переменной с именемmtag

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

Пример

Вот очень простая программа на re2c (example.re). Он проверяет, что все входные аргументы являются шестнадцатеричными числами. Код re2c заключен в комментарии /*!re2c ... */, все остальное — простой код на C. Более сложные примеры см. на официальном сайте re2c. ^[23]

#include <stdio.h> static int lex ( const char * YYCURSOR ) { const char * YYMARKER ; /*!re2c  re2c:define:YYCTYPE = char;  re2c: yyfill: включить = 0;         конец = "\x00";  шестнадцатеричный = "0x" [0-9a-fA-F]+; * { printf("ошибка\n"); возврат 1; }  hex end { printf("hex\n"); вернуть 0; }  */ }int main ( int argc , char ** argv ) { for ( int i = 1 ; i < argc ; ++ i ) { lex ( argv [ i ]); } вернуть 0 ; }                  

Учитывая это, re2c -is -o example.c example.reгенерируется приведенный ниже код (example.c). Содержимое комментария /*!re2c ... */подменяется детерминированным конечным автоматом , закодированным в виде условных переходов и сравнений; остальная часть программы дословно копируется в выходной файл. Существует несколько вариантов генерации кода; обычно re2c использует switchоператоры, но он может использовать вложенные ifоператоры (как в этом примере с -sопцией) или генерировать растровые изображения и таблицы переходов. Какой вариант лучше, зависит от компилятора C; Пользователям re2c рекомендуется экспериментировать.

/* Сгенерировано re2c 1.2.1 в пятницу, 23 августа, 21:59:00 2019 г. */ #include <stdio.h> static int lex ( const char * YYCURSOR ) { const char * YYMARKER ; { чар yych ; yych = * YYКУРСОР ; if ( yych == '0' ) перейти к yy4 ; ++ YYКУРСОР ; yy3 : { printf ( «ошибка \n » ); вернуть 1 ; } yy4 : yych = * ( YYMARKER = ++ YYCURSOR ); if ( yych != 'x' ) перейти к yy3 ; yych = *++ YYCURSOR ; если ( yych >= 0x01 ) перейти к yy8 ; yy6 : YYCURSOR = YYMARKER ; перейти к гг3 ; yy7 : yych = *++ YYCURSOR ; yy8 : if ( yych <= '@' ) { if ( yych <= 0x00 ) перейти к yy9 ; if ( yych <= '/' ) перейти к yy6 ; if ( yych <= '9' ) перейти к yy7 ; перейти к yy6 ; } else { if ( yych <= 'F' ) перейти к yy7 ; if ( yych <= '`' ) перейти к yy6 ; if ( yych <= 'f' ) перейти к yy7 ; перейти к yy6 ; } yy9 : ++ YYCURSOR ; { printf ( "шестнадцатеричный \n " ); вернуть 0 ; } }                                                                                   }int main ( int argc , char ** argv ) { for ( int i = 1 ; i < argc ; ++ i ) { lex ( argv [ i ]); } вернуть 0 ; }                  

Смотрите также

• Сравнение генераторов парсеров

Рекомендации

1. Бумбулис, Питер; Дональд Д., Коуэн (март – декабрь 1993 г.). «RE2C: более универсальный генератор сканеров». Письма ACM о языках и системах программирования . 2 (1–4): 70–84. дои : 10.1145/176454.176487 . S2CID  14814637.
2. «Выпуск 3.1». 19 июля 2023 г. Проверено 3 августа 2023 г.
3. «Авторы, документация re2c» .
4. «Создание PHP». Книга «Внутренности PHP» . Проверено 20 июля 2020 г.
5. "SpamAssassin (sa-компиляция)" .
6. "Ниндзя: build.ninja" . Ниндзя . Проверено 20 июля 2020 г.
7. «BRL-CAD (инструменты: re2c)» .
8. «Процесс сборки».
9. Джозеф, Грош (1989). «Эффективное создание настольных сканеров». Программное обеспечение: практика и опыт 19 : 1089–1103.
10. «Извлечение совпадений, документация re2c» .
11. Вилле, Лаурикари (2000). «НКА с тегированными переходами, их преобразование в детерминированные автоматы и применение к регулярным выражениям» (PDF) . Седьмой международный симпозиум по обработке строк и поиску информации, 2000. SPIRE 2000. Труды .
12. Уля, Трофимович (2017). «Тегированные детерминированные конечные автоматы с прогнозом вперед». arXiv : 1907.08837 [cs.FL].
13. Уля, Трофимович (2020). «RE2C — лексерный генератор, основанный на опережающем TDFA». Влияние программного обеспечения . 6 : 100027. doi : 10.1016/j.simpa.2020.100027 .
14. Уля, Трофимович (2021). «Прогнозируемый TDFA в картинках (слайды)» (PDF) .
15. «Кодировки, документация re2c» .
16. «Интерфейс программы, документация re2c» .
17. «Сохраняемое состояние, документация re2c» .
18. «Условия запуска, документация re2c» .
19. «Скелет, документация re2c» .
20. «Предупреждения, документация re2c» .
21. «Визуализация, документация re2c» .
22. «Руководство пользователя (C), документация re2c» .
23. "Официальный сайт" .

Внешние ссылки

• Официальный веб-сайт