Если сравнить с [f]lex, в чём будут ключевые отличия?

Если сравнить с [f]lex, в чём будут ключевые отличия?

- более быстрые лексеры за счёт не-табличной модели, оптимизаций и возможности сконфигурировать лексер с учётом особенностей конкретных входных данных

- отсутствие жёсткого программного интерфейса, что даёт возможность встраивать лексер в очень необычные окружения, или просто с большим удобством и свободой связывать лексер с основной программой

- возможность симнтаксического разбора, а не просто распознавания (англ. «submatch extraction»), основанного на недавно разработанных алгоритмах с минимальным оверхедом

- для кого-то важна лицензия (public domain)

А его можно применять для разбора или валидации заданной разметки XML или json? И оно быстрее чем парсер или regexp?

Ура! Правда, в генте всё ещё 1.1.1.

Уля, потыкай Серёжу палочкой. =)

Если повезёт, вечером будет 1.2. ;)

По умолчанию, re2c парсит выражения вроде «∀x ∃y» как. последовательность 1-битных ASCII-символов

Однобайтных.

Байты кое-где бывают не 8-битными. Тогда уж лучше «8-битных»

А его можно применять для разбора или валидации заданной разметки XML или json?

Для лексического разбора или валидации --- да (re2c умеет разбирать тот же класс формальных грамматик, что и регулярные выражения). Но если имеется в виду разбор контекстно-свободных грамматик (например, вложенные структуры) --- то нет, для такого нужны парсеры или генераторы парсеров вроде bison.

И оно быстрее чем парсер или regexp?

По скорости re2c-генерированный код в десятки раз быстрее чем библиотеки регулярных выражений, просто потому, что в первом случае регулярные выражения компилируются в детерминированный конечный автомат и затем в нативный код, а во втором случае они интерпретируется в недетерминированный конечный автомат или jit-компилируются на ходу, что занимает дополнительное время.

Да уж, однобитные символы, прибитые к полу, это слишком сурово. :D @jollheef поправь пожалуйста.

re2c подходит только для тех случаев, где нужен быстрый фиксированный regexp: парсер командной строки и т.д. Обычный библиотечный regexp, как правило, медленный и его избегают, если можно заменить поисками строки в строке и т.д. Но фиксированый regexp компилируется и оптимизируется заранее и поэтому может быть сравнительно быстрым. Задаёшь правила, а re2c генерирует код на Си с кучей операторов switch и goto. Можно эти правила смешивать с кусками кода на Си или Си++. Жаль, что уж очень мало было документации (что теперь исправлено): наскольно я помню, был только один коротенький вводный текст с примером и мне приходилось заглядывать в код, чтобы разобраться в некоторых деталях.

Я его по коду ninja осваивал

А ASCII вроде вообще 7-битная.

где нужен быстрый фиксированный regexp: парсер командной строки и т.д.

Наоборот :) Как раз в командной строке пофиг, сколько там разбираются ключи. Всё равно куча времени тратится на проверки защиты, расположение и догрузка модулей и т.п.

Ребят, не надо вот этих «громких слов»:

...генератор очень быстрых лексических анализаторов

Судя по комментам, это тупо «генератор быстрых регэкспов», ограничения которых мы знаем и которые далеко не везде можно применять. Так и пишите, чтобы не пудрить людям мозг.

Ограничения регулярных выражений касаются лишь тех случаев, когда ты хочешь одним выражением проверить весь текст. В re2c можно как угодно смешивать правила и код, ты можешь при токенизации выполнять любой код, вызывать любые функции, т.е. менять состояния машины и переключаться на другие правила. В принципе, любой сложности компилятор/интерпретатор можно сделать с использованием re2c, просто это будет выглядеть как ком проводов с изолентой.

На расте аналог есть?

и которые далеко не везде можно применять

Эээ... А можно примеров где regexp-ы нельзя применять для лексического анализа?

Привет семейству умных от еще живых мц-шников :)

В любом языке, где правила разбора зависят от контекста

Судя по комментам, это тупо «генератор быстрых регэкспов»

re2c не генерит регэкспов.

Я правильно понял из ответа, что для разбора XML и JSON эта штука не пригодна, т.к. данные форматы рекурсивны?

Я правильно понял из ответа, что для разбора XML и JSON эта штука не пригодна, т.к. данные форматы рекурсивны?

Да.

(Пригоден для токенизации в связке с bison или другим генератором парсеров.)

генератор очень быстрых лексических анализаторов

Интересно было б посмотреть на задачу, где это очень надо. Ведь за всё надо платить, если у flex всё красиво и понятно, то тут беглое чтение примеров действует отталкивающе, как в кишках копаешься, наверное.

Да никому не интересно, что там можно «смешивать», менять состояния... Если это «чудо» не подходит для разбора любых грамматик - просто закопайте это фуфло и упражняйтесь хотя бы PEG'ами.

Эх жаль что неинтересно, а то этот никто может быть знал бы, что разбор любых грамматик — неразрешимая задача. :)

re2c идеально подходит для чтения конфигурационных файлов, параметров командной строки, рагрузки данных в формате .csv, встроенной командной строки, парсинга http-запросов, когда пишешь веб сервер и даже для создания скриптовых языков. В принципе, если в файле .json или .html нужно найти конкретный элемент (даже сколь угодно вложенный), это можно сделать с помощью re2c. Как правило, решение конкретной задачи проще чем создание «универсального решателя любых задач».

re2c идеально подходит

Я спрашивал о задаче, где надо именно очень быстрый lex. Где можно себя перебороть и воспользоваться нестандартной тулзой с весьма специфическим синтаксисом.

1% оптимизации парсинга http-запросов таким посещаемым сайтам как Facebook экономит столько на счетах за электроэнергию, что окупает им оплату труда целых отделов высококвалифицированных программистов за годы вперёд!

1% оптимизации парсинга http-запросов таким посещаемым сайтам как Facebook

Для http-сервера что-то похожее на regex-ы вообще не нужны, оно, конечно, на них можно изобразить, но это будет натягивание совы на глобус. Это я вам как автор http-сервера говорю.

В описании на http://re2c.org перечислены некоторые проекты, которые используют re2c. Мне лично он пригодился для легковесного JavaScript-движка (лексер и куски стандартной библиотеки), для антивирусного сканера сигнатур (очень быстро искать интересные куски в потоке мусора), для распознавания форматов, и в целом для всяких фильтров.

Как пример ещё большей крайности, регулярные выражения в последнее время стали компилировать в FPGA для фильтрации сетевого трафика.

Вот на опеннете подтверждают про разницу в скорости по сравнению с flex.

для антивирусного сканера сигнатур

Хм, всегда думал, что тут то как раз должны таблицы быть быстрее.

Вот на опеннете подтверждают про разницу в скорости по сравнению с flex.

Ну кто утверждает обратное просто неумеет в код. И да, предыдущее предложение этому не противоречит, так как инструмент должен выбираться по задаче и flex там будет ещё хуже, но сам я поиск сигнатур не писал и полностью не уверен, только общее ощущение.

Автор http-сервера? Я писал игровые бакэнды, фронтенды, ботовые кластеры, кучу всяких скрейперов. Да мало ли где нужна скорость в обработке http-запросов!

Я писал ... Да мало ли где нужна скорость в обработке http-запросов!

Я уже отвечал на это. Обработка запросов по протоколу http с применением лексического анализатора — натягивание совы на глобус. Нафиг оно там не нужно. Если у вас поверх этого наворочен протокол со своим языком, то это другая задача, но там, где выжимают последние микросекунды, там и язык делают с простым лексером и написать конкретный код под конкретную задачу, который будет быстрее, не так и сложно, ибо универсальный генератор всегда проигрывает специализированному.

универсальный генератор всегда проигрывает специализированному

Не знаю относилась ли эта мысль к re2c, но на всякий случай скажу, что главная цель проекта --- чтобы сгенерированный код был не медленнее написанного руками на С (а лучше, быстрее).

а лучше, быстрее

Ох, как же это достало. Ну как у вас это в сознании укладывается?! Быстрее за счёт чего? Использовании simd-инструкций чтоли? Так вроде нет же. Если универсальный генератор делает код на том же языке быстрее, это только доказывает, что изначальный код был неоптимальным, а не то, что это инструмент, который принципиально делающий быстрее. Это же как закон сохранения энергии. Впрочем, как обычно спорить с теми, кто его отрицает совершенно бесполезно...

Быстрее за счёт чего?

За счёт минимизированного конечного автомата. Программисту в голове (или на бумажке) автомат построить сложно, долго и нерасширяемо, и обычно такой код напоминает сложночитаемую лапшу с кучей проверок на конец строки и ошибками. Поэтому обычно используют более стройный, но менее эффективный recursive descent, или на крайняк strcmp в цикле. Сгенерированный код быстрее по той же причине, по которой код на С, скомпилированный оптимизирующим компилятором, обычно быстрее чем вручную писать на ассемблере.

За счёт минимизированного конечного автомата.

Да. Но можно выстроить логическую цепочку: конечный автомат на табличках от flex — медленнее, развёрнутые таблички в код от re2c — быстрее, значить заточенный код специально под задачу — ещё быстрее. В конце концов, если человеку это сложно и долго, то можно просто взять и подправить код, сгенерированный универсальным генератором под задачу.

или на крайняк strcmp в цикле

Между прочим, strcmp юзает simd :) Только вначале, чтобы заюзать strcmp, надо токенизировать. :)

Между прочим, strcmp юзает simd

вносите царя

вносите царя

найди укрытие понадежнее

Для XML и JSON есть Lemon, от создателя SQLite

значить заточенный код специально под задачу

Непонятно, что значит «заточить автомат под какую-то задачу»? Нетривиальные оптимизации вроде использования того факта, что верхний регистр в ASCII от нижнего отличается одним битом?

Нетривиальные оптимизации вроде использования того факта, что верхний регистр в ASCII от нижнего отличается одним битом?

Я, конечно, не супер-программист, но я бы не назвал эту оптимизацию нетривиальной, в любом musl’е можно подсмотреть:

(((unsigned)(a)|32)-'a') < 26

По-моему, посмотреть что из себя в двоичном коде представляют обрабатываемые данные это не «нетривиальные оптимизации», а то, с чего стоит начинать.

С алгоритмической точки зрения они нетривиальные, потому что основаны на ad-hoc факте, специфичном для конкретных данных. Такие вещи в генераторе оптимизируются уже после более общих оптимизаций вроде минимизации, тунельного автомата, удаления дохлого кода и т.д.

Непонятно, что значит «заточить автомат под какую-то задачу»?

Любой лексический анализатор похож на FIM, если все состояния учтены. Если его пишут под задачу, значить затачивают. Мы же ищем любой способ под последние микросекунды? Значить в ход пойдут любые способы, ускоряющие эту задачу, а не вообще. Например, если в потоке появляется ошибка, то на ней ускоряться не обязательно, её можно перенести в область неоптимального многочисленного сравнения, а наиболее вероятностные правильные состояния сделать первыми. Ну или сделать несколько разных функций lex() в зависимости от текущего состояния. С тем же ascii иногда намного быстрее таки узнать тип символа таки табличкой.

С алгоритмической точки зрения они нетривиальные

С этим соглашусь, просто я отвечал на тезис именно о регистре ASCII-символов.
А так, проект полезен, хотя бы ради того, чтобы прочесть сгенерированный код и подумать «А что, так можно было?».

Как он по сравнению с ragel?

storable-state не работает?

#include <stdio.h>
#include <string.h>

enum result_t { error = -1, ok = 0, pending = 1 };
struct context_t { int s; unsigned a; char c; };

enum result_t parse(struct context_t* ctx, const char* YYCURSOR, const char* YYLIMIT)
{
	#define YYFILL(V) return pending
	#define yych ctx->c
	#define yyaccept ctx->a
	#define state ctx->s
	#define YYGETSTATE() state
	#define YYSETSTATE(V) state=V

	const char* YYMARKER;
	/*!re2c
		re2c:define:YYCTYPE=char;

		version = 'http/' [0-9]+ "." [0-9]+;
		status = [0-9]{3};
		method = [^ %]+;
		uri = [^ %]+;
		reason = [^%]*;
		response = version " " status " " reason "%";
		request = method " " uri " " version "%";

		response | request { return ok; }
		* { return error; }
	*/

	#undef YYGETSTATE
	#undef YYSETSTATE
	#undef state
	#undef yyaccept
	#undef yych
	#undef YYFILL
}

int main(int ac, char* av[])
{
	int i =0;
	enum result_t r = pending;
	struct context_t ctx = {-1,0,'\0'};

	while (++i < ac) if ((r=parse(&ctx,av[i],av[i]+strlen(av[i]))) <= 0) break;

	if (r) fputs(r == error?"400 Bad Response\n":"incomplete data\n",stderr);
	return r;
}

$ re2c -f -i -W -o ururu.c ururu.re
$ gcc -std=c89 -pedantic-errors -Wall -Wextra -Os -o ururu ururu.c
$ ./ururu 'GET /api/v2/ururu HTTP/1.1%' #ok
$ ./ururu 'GET /api/v2/ururu HTTP/1.' '1' '%' #error
400 Bad Response