Re2c

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Re2c
Тип свободное и открытое программное обеспечение и генератор лексического анализатора[d]
Написана на Си и C++
Операционная система кроссплатформенность
Первый выпуск 1994[1]
Последняя версия
Состояние активное
Сайт re2c.org​ (англ.)
Логотип Викисклада Медиафайлы на Викискладе

re2c — это свободная утилита–генератор, с открытым исходным кодом, генерирует быстрые и легко встраиваемые лексеры, ориентированна на работу совместно с языками: Си, C++, Go, Rust.

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

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

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

Философия[править | править код]

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

Возможности[править | править код]

  • Захваты submatch extraction[8] — re2c поддерживает как группы захвата, совместимые с POSIX, так и отдельные тэги[9].

Реализация основана на алгоритме «lookahead-TDFA»[10][11][12];

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

Синтаксис[править | править код]

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

Регулярные выражения[править | править код]

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 поиск с опережением (англ. lookahead) R, за которой следует S;
  • name регулярное выражение, определенное как name (за исключением режима совместимости с Flex);
  • @stag s-меткаангл. tag — метка или тэг) — сохраняет последнюю позицию ввода, в которой @stag совпадает с переменной с именем stag;
  • #mtag m-метка — сохраняет все позиции ввода, в которых #mtag совпадает с переменной с именем mtag.

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

Примеры кода[править | править код]

Программные проекты используещие re2c[править | править код]

  • PHP — популярный язык сценариев общего назначения[6];
  • Ninja — система сборки ориентированная на скорость[5];
  • SpamAssassin — программа для фильтрации спама электронной почты[22];
  • BRL-CAD — программа 3D моделирования (САПР)[23];
  • STEPCode — имплантация стандарта ISO 10303[24];
  • Yasm — модульный ассемблер полная переработка NASM[25];
  • Wake — инструмент для сборки от SiFive[26].

См. также[править | править код]

Примечания[править | править код]

  1. (unspecified title)doi:10.1145/176454.176487
  2. https://github.com/skvadrik/re2c/releases/tag/3.0 — 2022.
  3. 1 2 3 4 Bumbulis Peter, Donald D. Cowan. RE2C: a more versatile scanner generator (англ.) // Association for Computing Machinery, New York, NY, United States : журнал. — 1993. — 3—12 (vol. 2, no. 1—4). — P. 70—84. — ISSN 1057-4514. — doi:10.1145/176454.176487.
  4. re2c: authors (англ.). Дата обращения: 11 февраля 2022. Архивировано 21 июля 2011 года.
  5. 1 2 Ninja: build.ninja (англ.). Ninja. Дата обращения: 11 февраля 2022. Архивировано 5 мая 2022 года.
  6. 1 2 Building PHP (англ.). PHP Internals Book. Дата обращения: 11 февраля 2022. Архивировано 8 мая 2021 года.
  7. Joseph Grosch. Efficient Generation of Table-Driven Scanners (англ.) // Software: Practice and Experience 19 : журнал. — 1989. — P. 1089—1103.
  8. Submatch extraction, re2c documentation (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  9. Ville Laurikari. NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions (англ.) // Seventh International Symposium on String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. : журнал. — 2000. Архивировано 8 февраля 2022 года.
  10. Ulya Trofimovich (2017). “Tagged Deterministic Finite Automata with Lookahead”. arXiv:1907.08837.
  11. Ulya Trofimovich. RE2C — a lexer generator based on lookahead TDFA (англ.) // Software Impacts : журнал. — 2020. — Vol. 6. — doi:10.1016/j.simpa.2020.100027.
  12. Ulya, Trofimovich Lookahead TDFA in pictures (slides) (англ.) (PDF) (2021). Дата обращения: 11 февраля 2022. Архивировано 27 января 2022 года.
  13. re2c: Encoding support (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  14. re2c: Program interface (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  15. re2c: Storable state (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  16. re2c: Start conditions (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  17. re2c: Skeleton (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  18. re2c: Warnings (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  19. Visualization, re2c documentation (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  20. re2c: User manual (C) (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
  21. re2c. Дата обращения: 11 февраля 2022. Архивировано 16 февраля 2022 года.
  22. SpamAssassin (sa-compile) (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
  23. BRL-CAD (tools: re2c) (англ.). Дата обращения: 11 февраля 2022. Архивировано 11 февраля 2022 года.
  24. Build Process (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
  25. The Yasm Modular Assembler Project: Key Internal Features (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
  26. wake (англ.). Дата обращения: 11 февраля 2022. Архивировано 11 февраля 2022 года.

Ссылки[править | править код]