Опубликован релиз re2c 4.0 - генератора лексических анализаторов (он же компилятор регулярных выражений в код на целевом языке программирования). Re2c специализируется на генерации быстрых и легко встраиваемых лексеров и отличается от более известного аналога Flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP...Подробнее: https://www.opennet.dev/opennews/art.shtml?num=62267
Чем он лучше Boost::Spirit?
Возможно, тем, что он не сдох как спирит в 2014?
вопрос к сообщению про то что спирит сдox в 14 году, я его использовал активно в 18-19. вполне успешно и живой он был
посмотрел что там у спирита на сайте буста. действительно не развивается давно. последняя верся .78
А Boost::Spirit во время компиляции строит и оптимизирует конечный автомат?
наврятли он что-то оптимизирует. это все шаблонной магией делается. Вся формальная спецификация задается как шаблонный код, те код парсера получается через инстанцирование шаблонного кода в момент компиляции
У re2c ещё есть то преимущество по сравнению с другими компиляторами регулярных выражений, что он использует конечные автоматы с тэгами (https://en.wikipedia.org/wiki/Tagged_Deterministic_Finite_Au...), что позволяет ему делать не просто распознавание, но и захват (submatch extraction). Обычно или компилируется (и тогда нет захвата), или а рантайме матчится (и тогда захват есть, но не так быстро).
Tagged Deterministic Finite Automaton),The article that you're looking for doesn't exist.
https://en.m.wikipedia.org/wiki/Tagged_Deterministic_Finite_...
такого в спирите нет, там никакого рантайма. все скомпилено из шаблонов и прибито
лет 10 назад был у нас коллега, который один модуль переписал на спирите (до этого весь парсинг осуществлялся руками написанными свичами). да, возможно он где-то напортачил (хотя сомневаюсь - толковый парень), но на выходе получили:
плюсы:
1. код стал красивым, компактным, легко читаемым.
минусы:
1. падение производительности модуля в х раз (точную цифру не помню, но она была огромной). к вопросу о производительности
2. абсолютная невозможность отладки - стектрейс глубиной примерно 10-20 занимал около 10 экранов. по прилёту коры человек предпочитал вдумчиво рассматривать свой код, нежеле разбираться с каскадом шаблонов в дампе.
3. пришлось апгрейдит железо, тк 4гб памяти на виртуалке стало недостаточно чтобы скомпилировать этот файл в последовательной компиляции, не говоря о том что до этого можно распараллеливать сборку.
по итогу даже фанаты буста на тот момент заключили что это не пригодное к использованию овно (понятно почему не развивается). и трудно найти что-то хуже. в качестве исследования мы перепробовали тогда еще пачку альтернатив (включая re2c) - все они были лучше. в итоге остановились на ragel.
так что твой вопрос не верен. правильно спросить - что может быть хуже чем spirit.
Сложные (по неоднозначностям) языки типа C++ - на нём можно написать?
>уже поддерживаемым (C/C++, Go, Rust)
🤦Поддерживается генерация кода на этих языках, а не их разбор.
Лексический анализатор конечно можно, но судя по вопросу о неоднозначностях речь о синтаксическом разборе -- тогда нет конечно, re2c для регулярных грамматик.
Сохранил в закладки. Будет любопытно заюзать инструменты для (code sanitizers, fuzzing, static program analysis) и поискать уязвимости и баги. 😈🐛
А ассемблер поддерживается?
Нет, и пока в планах этого нет. Для компилируемых языков обычно оптимизирующий компилятор решают эту задачу, и лезть туда надо только если заведомо есть что ускорить (т.е. по какой-то причине компилятор не умеет генерить эффективный код именно для такого типа исходников, и нельзя его пофиксить). В re2c можно проводить более высокоуровневые оптимизации (например, читать и матчить по нескольку байт за раз -- но даже тут много проблем с выравниванием и т.д.).А какой ассемблер вас интересует? Для каких задач/сред это может пригодиться, где С тулчейн не подойдёт?
> А ассемблер поддерживается?Дорогой, а на кой чёрт в 2024м году писать новый язык на ассемблере? )
Осталось понять, зачем для окамла или хаскеля брать этот инструмент, а не их родные.
Для окамла пользователи попросили: https://github.com/skvadrik/re2c/issues/449, для хаскеля он может оказаться быстрее чем alex (это ещё надо потестировать), но вообще было полезно добавить поддержку просто чтобы убедиться в том, что синтаксические файлы достаточно гибкие для чистого функционального ЯП.
Что скажите по сравнению с menhir(lr генератор для ocaml) и tree-sitter (glr, с восстановлением после ошибки, с кучей биндингов, у окамла есть типизированный биндинг)? В частности по поводу восстановления после ошибок, с возвратом частично построенного дерева типа такого
for (var i = 1;
console.log(i);
Это же генераторы парсеров, а не лексеров. Они для другого типа грамматик: re2c для регулярных, а menhir и tree-sitter для контекстно-свободных. Эти задачи решаются разными алгоритмами (можно, конечно, GLR парсером распознавать регулярные грамматики, но это неэффективно и неудобно). Часто генератор лексеров и парсеров работают в связке.
Как-то пропустил, что это только лексер
Вот тут параллель проводили с ocamllex и sedlex: https://github.com/skvadrik/re2c/issues/449#issuecomment-160....
Уля, спасибо что не бросаете. Отдельная благодарность за Zig и за внешнюю конфигурацию синтаксиса в целом. Традиционно, привет Серёже. =)p.s. В Gentoo пока всё ещё 3.1.
Спасибо за обратную связь. :)
> Спасибо за обратную связь. :)Я не юзал, но мельком глянул код, и нахожу его достойным и годным. Я такое редко говорю. Потому -- моё почтение.
Присоединяюсь.Спасибо за лучший инструмент.
Ничего не понял. Что этот анализатор лексических генераторов делает?
Генерит по описанию лексики исходник на выбранном языке, являющийся специализированным быстрым парсером этой лексики. Из подобного — Flex, Bison и т.д.
Может из примеров станет понятнее: http://re2c.org/playground
Лексер преобразует строку в поток токенов, а парсер из этих токенов стрит синтаксическое дело. Нужно, если вы хотите как-то обработать исходный код, например, скомпилировать, изменить, или проверить на ошибки
Применений много и помимо разбора исходного кода: разбор логов / конфигов / URL адресов / email адресов / аргументов командной строки / поиск сигнатур в бинарных файлах -- в общем, всё, что не выходит за рамки регулярных грамматик (в частности, не содержит вложенных стуктур и скобочных выражений -- например, HTML регулярными выражениями парсить нельзя: https://stackoverflow.com/questions/1732348/regex-match-open...).
Классическими регулярками нельзя, расширенными, как в Perl/PCRE, умеющими в рекурсию - можно, но там другая проблема - непредсказуемость вычислительной сложности.
Это заблуждение. Для распознавания вложенных структур (простейший пример - скобчных выражений) не годятся ни обычные, ни Perl регулярные выражения. Нету такого способа выразить в регулярном выражении "сматчить N открывающих скобок, потом что-то ещё, а потом N закрывающих" - вот это вот N, что оно оба раза одно и то же, никак не выразить, для этого нужны как минимум контекстно-свободные грамматики. Если вы считаете, что можно, приведите пример регулярного выражения, которое матчит сбалансированные скобочные выражения.[Upd]
Оказывается, это я заблуждалась и Perl действительно такое умеет, вот пример: https://stackoverflow.com/a/18653648 . Тут используется синтаксис (?R) чтобы рекурсивно сматчить опять всё выражение.
> Ничего не понял. Что этот анализатор лексических генераторов делает?Да ничего сложного. Когда ты пишешь новый язык, тебе нужны две вещи: херовина, которая разберёт код нового языка на токены (её называют токенайзером, лексером, лексическим анализитором, lexer), а также херовина, которая токены преобразует в код (её называют парсером, или компилятором; а код, который его выплёвывает -- называется yacc-ом, от yet another compiler compiler).
В общем, тебе нужен lex и yacc. Это база.
Так вот re2c -- это lex.
А, потом пользователи твоего языка пусть трахомудохаются с багами трудно-определяемого характера... Зато ты с съэкономишь себе время(м.б., а м.б.и наоборот) и повысишь ЧСВ.
О, это очень показательно: Аноним считает, что изучать теоретическую базу программирования -- это в целом не нужно. И я очень поддерживаю позицию данного Анонима. Распространение подобных взглядов в индустрии косвенным образом влияет на деньги, которые люди готовы заплатить лично мне. Так что слушайте Анонима, Аноним херни не посоветует! =)
Прикольная штука, несколько раз пробовал писать лексеры простых языков. Но когда нужно лексить (лексировать?) что-то более-менее сложное - то становится очень нетривиально.
Хотел разбирать данные, которые приходят кусками (например, из сети или если читать файл блоками). В примерах вроде что-то похожее есть, но невероятно заморочено, несколько дней помучался, бросил, написал лексер руками.
Для простых языков (DSL) мне оказалось тоже проще писать руками. Там скорость разбора не очень важна, а руками получается вроде как более просто написано, и не нужны лишние зависимости.
То есть, наверное, есть приложения для которых это нужный и полезный инструмент, но мне для совсем простого или наоборот сложного не зашло.
Все равно удачи авторам, пусть проект развивается дальше!
Спасибо! У re2c действительно не очень простой интерфейс. Если нужна помощь, можно завести баг на гитхабе (https://github.com/skvadrik/re2c/issues, вот ещё каналы связи: http://re2c.org/index.html#bugs-patches). Таких багов много, они обычно за полдня закрываются и проблему совместными усилиями решаем. Можно в личку на почту.Уточню, что оба режима, и читать кусками, и ожидать ввода откуда-то извне (когда лексер отдаёт управление, т.н. "push-model" лексер) поддерживаются. Чтение кусками требует буферизации (http://re2c.org/manual/manual_c.html#buffer-refilling). Ожидание ввода требует сохраняемого состояния (http://re2c.org/manual/manual_c.html#storable-state).
Вы очень любезны, благодарю.
Сейчас мне это уже не актуально, сделал вручную сканирование с помощью trie, но если бы опять понадобилось, то, наверное, смотрел бы немного в другом направлении.
Насколько я понимаю, для высокопроизводительных лексеров (которые прожевывают гигабайты данных в секунду) на x64 и ARM платформах сейчас лучше писать вручную SIMD-лексеры, как это делает например Daniel Lemire.
Если бы кто-то сделал генератор SIMD-лексеров, и если бы эти лексеры работали со скоростью скажем до 20-30% хуже чем написанные вручную, было бы очень интересно.
И у меня есть личный заскок - очень плохо понимаю и умею писать регулярки, особенно сложные. То есть в основном как-то получается написать, но постоянно ошибаюсь, приходится тестировать и все время возникает какая-то неуверенность. Если бы в генераторе лексера использовалось что-то похожее на (E)BNF, мне кажется некоторым пользователям с такими же проблемами (а вдруг нас много?) было бы немного проще.
Это не претензии к вам, у вас отличный инструмент, просто комментарий человека со стороны.
> Для простых языков (DSL) мне оказалось тоже проще писать руками.Хех. При всём уважении: этот тезис СИЛЬНО зависит от того, на каком языке вы его (DSL) пишете. =)