[Info] Ragel State Machine Compiler

[nsentinel]

Оставлю в Issue, так как не увидел способа связаться по другому, но можно вполне закрывать/удалять.

Существует Ragel State Machine Compiler, возможно будет интересно на него посмотреть, в целом как раз более-менее заточен на так сказать расширенную обработку регулярных выражений. При этом оптимизация делается как на уровне генератора, так и средствами выбранного компилятора.

Пакет ragel включен во многие дистрибутивы или досточно легко билдится, правда более старая ветка 6.XX как более стабильная.

GitHub: https://github.com/adrian-thurston/ragel

Рекомендую также глянуть на документацию, либо сбилдить из исходников (там есть генератор), либо скачать для любой из версий для ознакомления, например: https://www.colm.net/files/ragel/ragel-guide-6.10.pdf

Возможно пригодится: https://github.com/calio/ragel-cheat-sheet

[Panzerschrek]

Почитал описание. Похоже на аналог RegPanzer - только с большим количеством фич и с компиляциией через Си/C++/Asm, а не через llmv-ный код.
Можно, наверное, как-нибудь сравнить производительность RegPanzer и Ragel. Но вот в самой библиотеке RegPanzer сомневаюсь, что Ragel будет нужен.

[nsentinel]

Да, так и есть. Ragel очень давно существует, его например тот же Яндекс для создания паука и парсинга веба использовал. Возможно в сети остались их доклады на эту тему если поискать, там была затронута тема производительности и его использования в больших проектах.

Достаточно многие проекты используют там где нужен разбор строк, например, для быстрого парсинга HTTP или разработки lexer. На вскидку по теме пожно почитать к примеру - https://dgryski.medium.com/speeding-up-regexp-matching-with-ragel-4727f1c16027 или https://blevesearch.com/news/Faster-Tokenization-with-Ragel-generated-FSM/

Что касается производительности - с помощью Ragel можно написать к примеру однопроходных разбор (того же stream), когда разбор и выделение/обработка данных делаются одновременно. Есть несколько вариантов генерации итогового кода для представления КА (binary search table-driven, binary search, expanded actions, flat table-driven, flat table, expanded actions, goto-driven, goto expanded actions, goto in-place actions). goto expanded actions и goto in-place actions дают очень неплохую скорость, если размер кода не проблема. Оптимизация делается и для итогового КА (используется алгоритм, аналогичный Hopcroft’s state minimization algorithm). Ну и конечный результат ничего не мешает скомпилировать тем же clang со всеми включёнными оптимизациями.

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

В RegPanzer в целом он не нужен конечно, но показалось, что будет полезно знать о его существовании :)