re2c (re2c)
Re2c | |
---|---|
Тип | свободное и открытое программное обеспечение и генератор лексического анализатора[вд] |
Написана на | Си и C++ |
Операционная система | кроссплатформенность |
Первый выпуск | 1994 |
Последняя версия | |
Репозиторий | github.com/skvadrik/re2c |
Состояние | активное |
Сайт | re2c.org (англ.) |
![]() |
re2c (regular expression to c, regular expression to code) — это свободная утилита–генератор, с открытым исходным кодом, генерирует быстрые и легко встраиваемые лексеры, ориентированна на работу совместно с языками: Си, C++, Go, Rust.
Изначально утилита была создана Питером Бамбулисом (англ. Peter Bumbulis) и описана в его статье[2], позже re2c был передан в общественное достояние и с тех пор поддерживается добровольцами[3].
Утилита отличается от своих более известных аналогов (таких как lex и flex) тем, что имеет гибкий интерфейс взаимодействия (сгенерированный код взаимодействует с внешней программой с помощью примитивов), генерирует оптимизированные нетабличные лексеры, поддерживает захваты (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA).
Утилита в основном распространена в проектах, где требуется высокая скорость анализа синтаксиса, например Ninja[4] и PHP[5].
Философия
[править | править код]Основная цель re2c — генерировать быстрые лексеры[2], по крайней мере настолько же быстрые, как и разумно оптимизированные лексеры, написанные вручную на языке Си. Вместо использования традиционного табличного подхода re2c кодирует сгенерированный конечный автомат непосредственно в форме условных переходов и сравнений. В результате программа работает быстрее, чем её аналог на основе таблиц[2], и её гораздо проще отлаживать и понимать. Более того, такой подход часто приводит к уменьшению размера лексеров[2], поскольку re2c применяет ряд оптимизаций, таких как минимизация ДКА и построение туннельного автомата[6]. Еще одной отличительной особенностью re2c является его гибкий интерфейс. Вместо того, чтобы использовать фиксированный шаблон программы, re2c позволяет программисту написать большую часть кода интерфейса и адаптировать сгенерированный лексер к любой конкретной среде. Основная идея заключается в том, что re2c должен быть абстракцией с нулевыми затратами для программиста, использование утилиты никогда не должно приводить к более медленной работе программы, чем соответствующая реализация с вручную написанным кодом.
Возможности
[править | править код]- Захваты submatch extraction[7] — re2c поддерживает как группы захвата, совместимые с POSIX, так и отдельные тэги[8].
Реализация основана на алгоритме «lookahead-TDFA»[9][10][11];
- Поддержка различных кодировок[12] — re2c поддерживает ASCII, UTF-8, UTF-16, UTF-32, UCS-2 и EBCDIC;
- Гибкий пользовательский интерфейс[13] — сгенерированный код использует несколько примитивных операций для взаимодействия с окружающей средой (считывание входных символов, переход к следующей позиции ввода и т. д.). Пользователи могут переопределять эти примитивы так, как им необходимо;
- Сохраняемое состояние[14] — re2c поддерживает как лексеры pull-модели (когда лексер работает без прерываний и при необходимости извлекает больше входных данных), так и лексеры push-модели (когда лексер периодически останавливается и возобновляется для анализа новых блоков ввода);
- Условия запуска[15] — re2c может генерировать несколько взаимосвязанных уровней, где каждый лексер запускается определенным условием в программе;
- Само-проверка[16] — re2c имеет специальный режим, в котором он игнорирует весь код интерфейса, определенный пользователем, и генерирует автономную программу-скелет. Кроме того, re2c генерирует два файла — один со строками ввода, полученными из обычной грамматики, и один со сжатыми результатами сверки, которые используются для проверки поведения лексера на всех входах. Входные строки генерируются так, чтобы они широко охватывали переходы и пути ДКА. Генерация данных происходит сразу после построения ДКА и до любых оптимизаций, но сам лексер полностью оптимизирован, поэтому программы-скелеты способны выявлять любые ошибки в оптимизации и генерации кода;
- Система предупреждений[17] — re2c выполняет статический анализ программы и предупреждает своих пользователей о возможных неопределённостях или ошибках, таких как неопределённый поток управления, недостижимый код, неправильно экранированные escape-символы и потенциальное неправильное использование примитивов интерфейса;
- Отладка — помимо создания удобочитаемых лексеров, re2c имеет ряд опций, которые выводят различные промежуточные представления сгенерированного лексера, такие как НКА, несколько этапов ДКА и результирующий программный график в формате языка DOT[18].
Синтаксис
[править | править код]Программа re2c может содержать любое количество блоков /*!re2c ... */
. Каждый блок состоит из последовательности правил, определений и конфигураций (их можно смешивать, но, как правило, лучше сначала размещать конфигурации, затем — определения, а затем — правила). Правила имеют вид — REGEXP { CODE }
или REGEXP := CODE;
, где REGEXP
— регулярное выражение, а CODE
— является блоком кода на языке Си. Когда REGEXP
совпадает с входной строкой, поток управления передаётся соответствующему блоку CODE
. Существует одно специальное правило: правило по умолчанию с *
вместо REGEXP
, оно срабатывает, если никакие другие правила не совпадают. re2c имеет семантику жадного соответствия — если несколько правил совпадают, предпочтительным является правило, соответствующее более длинному префиксу, если конфликтующие правила соответствуют одному и тому же префиксу, то более раннее правило имеет приоритет. Определения имеют вид NAME = REGEXP;
(и, соответственно, NAME { REGEXP }
в Flex-совместимом режиме). Конфигурации имеют вид re2c:CONFIG = VALUE;
, где CONFIG
является именем конкретной конфигурации и VALUE
является числом или строкой. Для более расширенного использования ознакомьтесь с официальным руководством re2c[19].
Регулярные выражения
[править | править код]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-программы в файле example.re. Она проверяет, что все входные аргументы являются десятеричными числами. Код для re2c обрамлён в комментариях /*!re2c ... */
[20].
Си:
// re2c $INPUT -o $OUTPUT -i --case-ranges
#include <assert.h>
bool lex(const char *s) {
const char *YYCURSOR = s;
/*!re2c
re2c:yyfill:enable = 0;
re2c:define:YYCTYPE = char;
number = [1-9][0-9]*;
number { return true; }
* { return false; }
*/
}
int main() {
assert(lex("1234"));
return 0;
}
Команда $ re2c -is -o example.c example.re
генерирует приведенный ниже код (example.c). Содержание комментария /*!re2c ... */
заменяются детерминированным конечным автоматом, закодированным в виде условных переходов и сравнений, остальная часть программы дословно копируется в выходной файл. Существует несколько вариантов генерации кода, обычно re2c использует оператор switch
, но он может использовать вложенные операторы if
(как в этом примере с опцией -s
) или генерировать битовые карты и таблицы переходов. Какой вариант лучше, зависит от компилятора языка Си, пользователям re2c предлагается проэкспериментировать.
/* Generated by re2c */
// re2c $INPUT -o $OUTPUT -i --case-ranges
#include <assert.h>
bool lex(const char *s) {
const char *YYCURSOR = s;
{
char yych;
yych = *YYCURSOR;
switch (yych) {
case '1' ... '9': goto yy2;
default: goto yy1;
}
yy1:
++YYCURSOR;
{ return false; }
yy2:
yych = *++YYCURSOR;
switch (yych) {
case '0' ... '9': goto yy2;
default: goto yy3;
}
yy3:
{ return true; }
}
}
int main() {
assert(lex("1234"));
return 0;
}
Go:
//go:generate re2go $INPUT -o $OUTPUT -i
package main
func lex(str string) {
var cursor int
/*!re2c
re2c:define:YYCTYPE = byte;
re2c:define:YYPEEK = "str[cursor]";
re2c:define:YYSKIP = "cursor += 1";
re2c:yyfill:enable = 0;
number = [1-9][0-9]*;
number { return }
* { panic("error!") }
*/
}
func main() {
lex("1234\x00")
}
// Code generated by re2c, DO NOT EDIT.
//go:generate re2go $INPUT -o $OUTPUT -i
package main
func lex(str string) {
var cursor int
{
var yych byte
yych = str[cursor]
switch (yych) {
case '1','2','3','4','5','6','7','8','9':
goto yy2
default:
goto yy1
}
yy1:
cursor += 1
{ panic("error!") }
yy2:
cursor += 1
yych = str[cursor]
switch (yych) {
case '0','1','2','3','4','5','6','7','8','9':
goto yy2
default:
goto yy3
}
yy3:
{ return }
}
}
func main() {
lex("1234\x00")
}
Rust:
// re2rust $INPUT -o $OUTPUT
fn lex(s: &[u8]) -> bool {
let mut cursor = 0;
/*!re2c
re2c:define:YYCTYPE = u8;
re2c:define:YYPEEK = "*s.get_unchecked(cursor)";
re2c:define:YYSKIP = "cursor += 1;";
re2c:yyfill:enable = 0;
number = [1-9][0-9]*;
number { return true; }
* { return false; }
*/
}
fn main() {
assert!(lex(b"1234\0"));
}
/* Generated by re2c */
// re2rust $INPUT -o $OUTPUT
fn lex(s: &[u8]) -> bool {
let mut cursor = 0;
{
#[allow(unused_assignments)]
let mut yych : u8 = 0;
let mut yystate : usize = 0;
'yyl: loop {
match yystate {
0 => {
yych = unsafe {*s.get_unchecked(cursor)};
cursor += 1;
match yych {
0x31 ..= 0x39 => {
yystate = 2;
continue 'yyl;
}
_ => {
yystate = 1;
continue 'yyl;
}
}
}
1 => { return false; }
2 => {
yych = unsafe {*s.get_unchecked(cursor)};
match yych {
0x30 ..= 0x39 => {
cursor += 1;
yystate = 2;
continue 'yyl;
}
_ => {
yystate = 3;
continue 'yyl;
}
}
}
3 => { return true; }
_ => {
panic!("internal lexer error")
}
}
}
}
}
fn main() {
assert!(lex(b"1234\0"));
}
Программные проекты, использующие re2c
[править | править код]- PHP — популярный язык сценариев общего назначения[5];
- Ninja — система сборки, ориентированная на скорость[4];
- SpamAssassin — программа для фильтрации спама электронной почты[21];
- BRL-CAD — программа 3D-моделирования (САПР)[22];
- STEPCode — имплементация стандарта ISO 10303[23];
- Yasm — модульный ассемблер, полная переработка NASM[24];
- Wake — инструмент для сборки от SiFive[25].
См. также
[править | править код]Примечания
[править | править код]- ↑ Release 3.1 — 2023.
- ↑ 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.
- ↑ re2c: authors (англ.). Дата обращения: 11 февраля 2022. Архивировано 21 июля 2011 года.
- ↑ 1 2 Ninja: build.ninja (англ.). Ninja. Дата обращения: 11 февраля 2022. Архивировано 5 мая 2022 года.
- ↑ 1 2 Building PHP (англ.). PHP Internals Book. Дата обращения: 11 февраля 2022. Архивировано 8 мая 2021 года.
- ↑ Joseph Grosch. Efficient Generation of Table-Driven Scanners (англ.) // Software: Practice and Experience 19 : журнал. — 1989. — P. 1089—1103.
- ↑ Submatch extraction, re2c documentation (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ 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 года.
- ↑
Ulya Trofimovich (2017). "Tagged Deterministic Finite Automata with Lookahead". arXiv:1907.08837.
{{cite journal}}
: Cite journal требует|journal=
(справка) - ↑ Ulya Trofimovich. RE2C — a lexer generator based on lookahead TDFA (англ.) // Software Impacts : журнал. — 2020. — Vol. 6. — doi:10.1016/j.simpa.2020.100027.
- ↑ Ulya, Trofimovich Lookahead TDFA in pictures (slides) (англ.) (PDF) (2021). Дата обращения: 11 февраля 2022. Архивировано 27 января 2022 года.
- ↑ re2c: Encoding support (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: Program interface (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: Storable state (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: Start conditions (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: Skeleton (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: Warnings (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ Visualization, re2c documentation (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c: User manual (C) (англ.). Дата обращения: 11 февраля 2022. Архивировано 31 января 2022 года.
- ↑ re2c . Дата обращения: 11 февраля 2022. Архивировано 16 февраля 2022 года.
- ↑ SpamAssassin (sa-compile) (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
- ↑ BRL-CAD (tools: re2c) (англ.). Дата обращения: 11 февраля 2022. Архивировано 11 февраля 2022 года.
- ↑ Build Process (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
- ↑ The Yasm Modular Assembler Project: Key Internal Features (англ.). Дата обращения: 11 февраля 2022. Архивировано 20 января 2022 года.
- ↑ wake (англ.). Дата обращения: 11 февраля 2022. Архивировано 11 февраля 2022 года.
Ссылки
[править | править код]- Официальный сайт (англ.)
- Репозиторий проекта (англ.)