Лучшие вопросы
Таймлайн
Чат
Перспективы

Re2c

генератор быстрых и легко встраиваемых лексеров. Из Википедии, свободной энциклопедии

Remove ads

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

Краткие факты Тип, Написана на ...
Remove ads

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

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

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

Remove ads

Философия

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

Remove ads

Возможности

Суммиров вкратце
Перспектива
  • Захваты 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].
Remove ads

Синтаксис

Суммиров вкратце
Перспектива

Программа 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.

Remove ads

Примеры кода

Суммиров вкратце
Перспектива
Примеры программы на различных языках

Далее приведён пример простой 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"));
}
Remove ads

Программные проекты, использующие re2c

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

См. также

Примечания

Loading content...

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads