Re2c - Re2c

re2c
Оригинальный автор (ы)Питер Бумбулис
изначальный выпускоколо 1994; 26 лет назад (1994)[1]
Стабильный выпуск
2.0 / 20 июля 2020 г.; 4 месяца назад (2020-07-20)
Репозиторийgithub.com/ skvadrik/ re2c
ТипЛексический анализатор генератор
ЛицензияВсеобщее достояние
Интернет сайтre2c.org

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

Философия

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

Функции

  • Извлечение подматча:[9] re2c поддерживает как POSIX-совместимые группы захвата, так и автономные теги [10] (с крайним левым жадным устранением неоднозначности и необязательной обработкой повторяющегося субматча). Реализация основана на алгоритме lookahead-TDFA. [11]
  • Поддержка кодирования:[12] re2c поддерживает ASCII, UTF-8, UTF-16, UTF-32, UCS-2 и EBCDIC.
  • Гибкий пользовательский интерфейс:[13] сгенерированный код использует несколько примитивных операций для взаимодействия с окружающей средой (чтение вводимых символов, переход к следующей позиции ввода и т. д.); пользователи могут переопределить эти примитивы так, как им нужно.
  • Состояние хранения:[14] re2c поддерживает оба тянуть-модель лексеры (когда лексер работает без прерываний и при необходимости получает дополнительные данные) и пуш-модель лексеры (когда лексер периодически останавливается и возобновляет синтаксический анализ новых блоков ввода).
  • Условия запуска:[15] re2c может генерировать несколько взаимосвязанных лексеров, каждый из которых запускается определенным условие в программе.
  • Самостоятельная проверка:[16] re2c имеет специальный режим, в котором он игнорирует весь используемый код интерфейса и генерирует автономный скелет программа. Кроме того, re2c генерирует два файла: один со входными строками, полученными из обычной грамматики, и второй со сжатыми результатами сопоставления, которые используются для проверки поведения лексера на всех входных данных. Входные строки создаются таким образом, что они полностью охватывают переходы и пути DFA. Генерация данных происходит сразу после построения DFA и до любых оптимизаций, но сам лексер полностью оптимизирован, поэтому скелетные программы способны обнаруживать любые ошибки при оптимизации и генерации кода.
  • Предупреждения:[17] re2c выполняет статический анализ программы и предупреждает пользователей о возможных недостатках или ошибках, таких как неопределенный поток управления, недостижимый код, неправильно сформированные escape-символы и потенциальное неправильное использование примитивов интерфейса.
  • Отладка. Помимо создания удобочитаемых лексеров, re2c имеет ряд опций, которые сбрасывают различные промежуточные представления сгенерированного лексера, такие как NFA, несколько этапов DFA и получившийся граф программы в Формат DOT.[18]

Синтаксис

Программа re2c может содержать любое количество / *! re2c ... * / блоков.Каждый блок состоит из последовательности правила, определения и конфигурации(их можно смешивать, но обычно лучше сначала указать конфигурации, затем определения, а затем правила). Правила имеют вид REGEXP {CODE} или REGEXP: = КОД; где РЕГЭКСП это регулярное выражение и КОД это блок кода C. Когда РЕГЭКСП соответствует входной строке, поток управления передается в связанный КОД. Есть одно особое правило: правило по умолчанию с * вместо того РЕГЭКСП; он запускается, если не совпадают другие правила. re2c имеет жадный семантика соответствия: если совпадают несколько правил, предпочтительнее правило, соответствующее более длинному префиксу; если конфликтующие правила совпадают с одним и тем же префиксом, приоритет имеет более раннее правило. ИМЯ = REGEXP; (а также ИМЯ {REGEXP} в Flex режим совместимости) .Конфигурации имеют вид re2c: CONFIG = VALUE; где КОНФИГУРАЦИЯ название конкретной конфигурации и ЦЕНИТЬ - это число или строка. Для более продвинутого использования см. официальное руководство по re2c.[19]

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

re2c использует следующий синтаксис для регулярных выражений:

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

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

пример

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

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

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

/ * Сгенерировано re2c 1.2.1 в пятницу 23 августа 21:59:00 2019 * /#включают <stdio.h>статический int lex(const char *YYCURSOR){    const char *YYMARKER;    {	char yych;	yych = *YYCURSOR;	если (yych == '0') перейти к гг4;	++YYCURSOR;гг3:	{ printf("эээ п"); вернуть 1; }гг4:	yych = *(YYMARKER = ++YYCURSOR);	если (yych != 'Икс') перейти к гг3;	yych = *++YYCURSOR;	если (yych >= 0x01) перейти к yy8;yy6:	YYCURSOR = YYMARKER;	перейти к гг3;yy7:	yych = *++YYCURSOR;yy8:	если (yych <= '@') {		если (yych <= 0x00) перейти к гг9;		если (yych <= '/') перейти к yy6;		если (yych <= '9') перейти к yy7;		перейти к yy6;	} еще {		если (yych <= 'F') перейти к yy7;		если (yych <= '`') перейти к yy6;		если (yych <= 'f') перейти к yy7;		перейти к yy6;	}гг9:	++YYCURSOR;	{ printf("шестнадцатеричный п"); вернуть 0; }}}int основной(int argc, char **argv){    за (int я = 1; я < argc; ++я) {        lex(argv[я]);    }    вернуть 0;}

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

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

  1. ^ а б c d е Бумбулис, Питер; Дональд Д., Коуэн (март – декабрь 1993 г.). «RE2C: более универсальный генератор сканеров». Письма ACM по языкам и системам программирования. 2 (1–4).
  2. ^ "Авторы, документация re2c".
  3. ^ «Сборка PHP». Книга о внутренностях PHP. Получено 2020-07-20.
  4. ^ "SpamAssassin (sa-compile)".
  5. ^ "Ниндзя: build.ninja". Ниндзя. Получено 2020-07-20.
  6. ^ "BRL-CAD (инструменты: re2c)".
  7. ^ http://stepcode.github.io/docs/build_process/
  8. ^ Джозеф, Грош (1989). «Эффективное создание настольных сканеров». Практика и опыт работы с программным обеспечением 19: 1089–1103.
  9. ^ "Извлечение подматча, документация re2c".
  10. ^ Вилле, Лаурикари (2000). «НКА с помеченными переходами, их преобразование в детерминированные автоматы и применение в регулярные выражения» (PDF). Седьмой международный симпозиум по обработке строк и поиску информации, 2000 г. SPIRE 2000. Труды.
  11. ^ Уля, Трофимович (2017). «Детерминированные конечные автоматы с тегами с прогнозированием». arXiv:1907.08837 [cs.FL ].
  12. ^ "Кодировки, документация re2c".
  13. ^ "Программный интерфейс, документация re2c".
  14. ^ «Сохраняемое состояние, документация re2c».
  15. ^ «Условия запуска, документация re2c».
  16. ^ "Скелет, документация re2c".
  17. ^ "Предупреждения, документация re2c".
  18. ^ "Визуализация, документация re2c".
  19. ^ "Руководство пользователя (C), документация re2c".
  20. ^ "Официальный сайт".

внешняя ссылка