re2c
| Оригинальный автор(ы) | Питер Бумбулис |
|---|---|
| Первоначальный выпуск | около 1994 года [1] |
| Стабильная версия | 3.1 [2] 
/ 19 июля 2023 г |
| Репозиторий | github |
| Тип | лексического анализатора Генератор |
| Лицензия | Общественное достояние |
| Веб-сайт | re2c |
re2c — с открытым исходным кодом бесплатный генератор лексеров для C , C++ , Go и Rust . Он компилирует декларативные спецификации регулярных выражений в детерминированные конечные автоматы . Первоначально написано Питером Бумбулисом и описано в его статье: [1] re2c стал общественным достоянием и с тех пор поддерживается волонтерами. [3] Это генератор лексеров, принятый в таких проектах, как PHP , [4] СпамАссасин , [5] Система сборки ниндзя [6] и другие. Вместе с генератором парсера Lemon используется re2c в BRL-CAD . [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*ноль или более вхожденийRR+одно или несколько вхожденийRR?ноль или одно появлениеRR{n}повторениеRточноnразR{n,}повторениеRпо меньшей мереnразR{n,m}повторениеRотnкmраз(R)толькоR; круглые скобки используются для переопределения приоритета или для соответствия в стиле POSIX.R Sконкатенация:Rс последующимSR | Sальтернатива:RилиSR / 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:enable = 0;
end = "\x00";
hex = "0x" [0-9a-fA-F]+;
* { printf("err\n"); return 1; }
hex end { printf("hex\n"); return 0; }
*/
}
int main(int argc, char **argv)
{
for (int i = 1; i < argc; ++i) {
lex(argv[i]);
}
return 0;
}
При условии, re2c -is -o example.c example.re генерирует код ниже (example.c).
Содержание комментария /*!re2c ... */ заменяются детерминированным конечным автоматом
кодируется в виде условных переходов и сравнений; остальная часть программы дословно копируется в выходной файл.
Существует несколько вариантов генерации кода; обычно re2c использует switch заявления,
но он может использовать вложенные if утверждения (как в этом примере с -s вариант),
или генерировать растровые изображения и таблицы переходов.
Какой вариант лучше, зависит от компилятора C;
Пользователям re2c рекомендуется экспериментировать.
/* Generated by re2c 1.2.1 on Fri Aug 23 21:59:00 2019 */
#include <stdio.h>
static int lex(const char *YYCURSOR)
{
const char *YYMARKER;
{
char yych;
yych = *YYCURSOR;
if (yych == '0') goto yy4;
++YYCURSOR;
yy3:
{ printf("err\n"); return 1; }
yy4:
yych = *(YYMARKER = ++YYCURSOR);
if (yych != 'x') goto yy3;
yych = *++YYCURSOR;
if (yych >= 0x01) goto yy8;
yy6:
YYCURSOR = YYMARKER;
goto yy3;
yy7:
yych = *++YYCURSOR;
yy8:
if (yych <= '@') {
if (yych <= 0x00) goto yy9;
if (yych <= '/') goto yy6;
if (yych <= '9') goto yy7;
goto yy6;
} else {
if (yych <= 'F') goto yy7;
if (yych <= '`') goto yy6;
if (yych <= 'f') goto yy7;
goto yy6;
}
yy9:
++YYCURSOR;
{ printf("hex\n"); return 0; }
}
}
int main(int argc, char **argv)
{
for (int i = 1; i < argc; ++i) {
lex(argv[i]);
}
return 0;
}
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д и Бумбулис, Питер; Дональд Д., Коуэн (март – декабрь 1993 г.). «RE2C: более универсальный генератор сканеров» . Письма ACM о языках и системах программирования . 2 (1–4): 70–84. дои : 10.1145/176454.176487 . S2CID 14814637 .
- ^ «Выпуск 3.1» . 19 июля 2023 г. Проверено 3 августа 2023 г.
- ^ «Авторы, документация re2c» .
- ^ «Создание PHP» . Книга «Внутренности PHP» . Проверено 20 июля 2020 г.
- ^ «SpamAssassin (будет скомпилирован)» .
- ^ «Ниндзя: build.ninja» . Ниндзя . Проверено 20 июля 2020 г.
- ^ «BRL-CAD (инструменты: re2c)» .
- ^ «Процесс сборки» .
- ^ Джозеф, Грош (1989). «Эффективное создание настольных сканеров». Программное обеспечение: практика и опыт 19 : 1089–1103.
- ^ «Извлечение подсоответствий, документация re2c» .
- ^ Вилле, Лаурикари (2000). «НКА с тегированными переходами, их преобразование в детерминированные автоматы и применение к регулярным выражениям» (PDF) . Седьмой международный симпозиум по обработке строк и поиску информации, 2000. SPIRE 2000. Труды .
- ^ Уля, Трофимович (2017). «Тегированные детерминированные конечные автоматы с прогнозом вперед». arXiv : 1907.08837 [ cs.FL ].
- ^ Уля, Трофимович (2020). «RE2C — лексерный генератор, основанный на опережающем TDFA» . Влияние программного обеспечения . 6 : 100027. doi : 10.1016/j.simpa.2020.100027 .
- ^ Уля, Трофимович (2021). «Прогнозируемый TDFA в картинках (слайды)» (PDF) .
- ^ «Кодировки, документация re2c» .
- ^ «Программный интерфейс, документация re2c» .
- ^ «Сохраняемое состояние, документация re2c» .
- ^ «Условия запуска, документация re2c» .
- ^ «Скелет, документация re2c» .
- ^ «Предупреждения, документация re2c» .
- ^ «Визуализация, re2c-документация» .
- ^ «Руководство пользователя (С), документация re2c» .
- ^ «Официальный сайт» .