Вариант для распечатки		Пред. тема | След. тема
Форум Разговоры, обсуждение новостей
Изначальное сообщение		[ Отслеживать ]

"Выпуск генератора лексических анализаторов re2c 4.0"	+/–
Сообщение от opennews (??), 21-Ноя-24, 04:24
Опубликован релиз re2c 4.0 - генератора лексических анализаторов (он же компилятор регулярных выражений в код на целевом языке программирования). Re2c специализируется на генерации быстрых и легко встраиваемых лексеров и отличается от более известного аналога Flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP... Подробнее: https://www.opennet.ru/opennews/art.shtml?num=62267
Ответить | Правка | Cообщить модератору

Сообщения

[Сортировка по ответам | RSS]

1. Сообщение от Аноним (1), 21-Ноя-24, 04:24	+/–
Чем он лучше Boost::Spirit?
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #3, #11, #12, #50

2. Сообщение от Аноним (3), 21-Ноя-24, 04:27	+1 +/–
Сложные (по неоднозначностям) языки типа C++ - на нём можно написать?
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #5, #9

3. Сообщение от Аноним (3), 21-Ноя-24, 04:29	+2 +/–
Возможно, тем, что он не сдох как спирит в 2014?
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #1

5. Сообщение от Аноним (5), 21-Ноя-24, 08:43	–1 +/–
>уже поддерживаемым (C/C++, Go, Rust)
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #2 Ответы: #6

6. Сообщение от Аноним (6), 21-Ноя-24, 09:04	+2 +/–
🤦‍ Поддерживается генерация кода на этих языках, а не их разбор.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #5

9. Сообщение от skvadrik (ok), 21-Ноя-24, 10:01	+/–
Лексический анализатор конечно можно, но судя по вопросу о неоднозначностях речь о синтаксическом разборе -- тогда нет конечно, re2c для регулярных грамматик.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #2

11. Сообщение от Аноним (11), 21-Ноя-24, 10:07	+/–
вопрос к сообщению про то что спирит сдox в 14 году, я его использовал активно в 18-19. вполне успешно и живой он был
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #1 Ответы: #13

12. Сообщение от skvadrik (ok), 21-Ноя-24, 10:18	–1 +/–
А Boost::Spirit во время компиляции строит и оптимизирует конечный автомат?
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #1 Ответы: #14

13. Сообщение от Аноним (11), 21-Ноя-24, 10:20	–1 +/–
посмотрел что там у спирита на сайте буста. действительно не развивается давно. последняя верся .78
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #11

14. Сообщение от Аноним (11), 21-Ноя-24, 10:24	+/–
наврятли он что-то оптимизирует. это все шаблонной магией делается. Вся формальная спецификация задается как шаблонный код, те код парсера получается через инстанцирование шаблонного кода в момент компиляции
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #12 Ответы: #17

16. Сообщение от ijuij (?), 21-Ноя-24, 11:17	+1 +/–
Сохранил в закладки. Будет любопытно заюзать инструменты для (code sanitizers, fuzzing, static program analysis) и поискать уязвимости и баги. 😈🐛
Ответить | Правка | Наверх | Cообщить модератору

17. Сообщение от skvadrik (ok), 21-Ноя-24, 11:28	+1 +/–
У re2c ещё есть то преимущество по сравнению с другими компиляторами регулярных выражений, что он использует конечные автоматы с тэгами (https://en.wikipedia.org/wiki/Tagged_Deterministic_Finite_Au...), что позволяет ему делать не просто распознавание, но и захват (submatch extraction). Обычно или компилируется (и тогда нет захвата), или а рантайме матчится (и тогда захват есть, но не так быстро).
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #14 Ответы: #23, #25, #26

18. Сообщение от Аноним (18), 21-Ноя-24, 11:48	+/–
А ассемблер поддерживается?
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #19, #44

19. Сообщение от skvadrik (ok), 21-Ноя-24, 12:03	+1 +/–
Нет, и пока в планах этого нет. Для компилируемых языков обычно оптимизирующий компилятор решают эту задачу, и лезть туда надо только если заведомо есть что ускорить (т.е. по какой-то причине компилятор не умеет генерить эффективный код именно для такого типа исходников, и нельзя его пофиксить). В re2c можно проводить более высокоуровневые оптимизации (например, читать и матчить по нескольку байт за раз -- но даже тут много проблем с выравниванием и т.д.). А какой ассемблер вас интересует? Для каких задач/сред это может пригодиться, где С тулчейн не подойдёт?
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #18

20. Сообщение от Аноним (20), 21-Ноя-24, 12:08	+/–
Осталось понять, зачем для окамла или хаскеля брать этот инструмент, а не их родные.
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #21

21. Сообщение от skvadrik (ok), 21-Ноя-24, 12:25	+1 +/–
Для окамла пользователи попросили: https://github.com/skvadrik/re2c/issues/449, для хаскеля он может оказаться быстрее чем alex (это ещё надо потестировать), но вообще было полезно добавить поддержку просто чтобы убедиться в том, что синтаксические файлы достаточно гибкие для чистого функционального ЯП.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #20 Ответы: #31

22. Сообщение от Аноним (6), 21-Ноя-24, 13:55	+3 +/–
Уля, спасибо что не бросаете. Отдельная благодарность за Zig и за внешнюю конфигурацию синтаксиса в целом. Традиционно, привет Серёже. =) p.s. В Gentoo пока всё ещё 3.1.
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #30, #35

23. Сообщение от qq (??), 21-Ноя-24, 15:35	+/–
Tagged Deterministic Finite Automaton), The article that you're looking for doesn't exist.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #17

25. Сообщение от Уля (?), 21-Ноя-24, 15:43	+/–
https://en.m.wikipedia.org/wiki/Tagged_Deterministic_Finite_...
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #17

26. Сообщение от Аноним (26), 21-Ноя-24, 16:37	+/–
такого в спирите нет, там никакого рантайма. все скомпилено из шаблонов и прибито
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #17

27. Сообщение от Аноним (27), 21-Ноя-24, 17:43	+/–
Ничего не понял. Что этот анализатор лексических генераторов делает?
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #28, #37, #43

28. Сообщение от Аноним (6), 21-Ноя-24, 17:51	+2 +/–
Генерит по описанию лексики исходник на выбранном языке, являющийся специализированным быстрым парсером этой лексики. Из подобного — Flex, Bison и т.д.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #27 Ответы: #33

30. Сообщение от skvadrik (ok), 21-Ноя-24, 18:52	+/–
Спасибо за обратную связь. :)
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #22 Ответы: #46

31. Сообщение от Аноним (20), 21-Ноя-24, 19:06	+/–
Что скажите по сравнению с menhir(lr генератор для ocaml) и tree-sitter (glr, с восстановлением после ошибки, с кучей биндингов, у окамла есть типизированный биндинг)? В частности по поводу восстановления после ошибок, с возвратом частично построенного дерева типа такого for (var i = 1;     console.log(i);
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #21 Ответы: #32, #34

32. Сообщение от skvadrik (ok), 21-Ноя-24, 19:26	+/–
Это же генераторы парсеров, а не лексеров. Они для другого типа грамматик: re2c для регулярных, а menhir и tree-sitter для контекстно-свободных. Эти задачи решаются разными алгоритмами (можно, конечно, GLR парсером распознавать регулярные грамматики, но это неэффективно и неудобно). Часто генератор лексеров и парсеров работают в связке.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #31 Ответы: #36

33. Сообщение от skvadrik (ok), 21-Ноя-24, 19:28	+/–
Может из примеров станет понятнее: http://re2c.org/playground
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #28

34. Сообщение от skvadrik (ok), 21-Ноя-24, 19:31	+/–
Вот тут параллель проводили с ocamllex и sedlex: https://github.com/skvadrik/re2c/issues/449#issuecomment-160....
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #31

35. Сообщение от erthink_erthink (?), 21-Ноя-24, 22:31	+/–
Присоединяюсь. Спасибо за лучший инструмент.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #22

36. Сообщение от Аноним (20), 22-Ноя-24, 12:16	+/–
Как-то пропустил, что это только лексер
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #32

37. Сообщение от Аноним (20), 22-Ноя-24, 12:18	+1 +/–
Лексер преобразует строку в поток токенов, а парсер из этих токенов стрит синтаксическое дело. Нужно, если вы хотите как-то обработать исходный код, например, скомпилировать, изменить, или проверить на ошибки
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #27 Ответы: #38

38. Сообщение от skvadrik (ok), 22-Ноя-24, 12:39	+1 +/–
Применений много и помимо разбора исходного кода: разбор логов / конфигов / URL адресов / email адресов / аргументов командной строки / поиск сигнатур в бинарных файлах -- в общем, всё, что не выходит за рамки регулярных грамматик (в частности, не содержит вложенных стуктур и скобочных выражений -- например, HTML регулярными выражениями парсить нельзя: https://stackoverflow.com/questions/1732348/regex-match-open...).
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #37 Ответы: #39

39. Сообщение от Аноним (39), 22-Ноя-24, 22:21	+/–
Классическими регулярками нельзя, расширенными, как в Perl/PCRE, умеющими в рекурсию - можно, но там другая проблема - непредсказуемость вычислительной сложности.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #38 Ответы: #40

40. Сообщение от skvadrik (ok), 22-Ноя-24, 23:04	+/–
Это заблуждение. Для распознавания вложенных структур (простейший пример - скобчных выражений) не годятся ни обычные, ни Perl регулярные выражения. Нету такого способа выразить в регулярном выражении "сматчить N открывающих скобок, потом что-то ещё, а потом N закрывающих" - вот это вот N, что оно оба раза одно и то же, никак не выразить, для этого нужны как минимум контекстно-свободные грамматики. Если вы считаете, что можно, приведите пример регулярного выражения, которое матчит сбалансированные скобочные выражения. [Upd] Оказывается, это я заблуждалась и Perl действительно такое умеет, вот пример: https://stackoverflow.com/a/18653648 . Тут используется синтаксис (?R) чтобы рекурсивно сматчить опять всё выражение.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #39

41. Сообщение от Аноним (41), 23-Ноя-24, 12:34	+/–
Прикольная штука, несколько раз пробовал писать лексеры простых языков. Но когда нужно лексить (лексировать?) что-то более-менее сложное - то становится очень нетривиально. Хотел разбирать данные, которые приходят кусками (например, из сети или если читать файл блоками). В примерах вроде что-то похожее есть, но невероятно заморочено, несколько дней помучался, бросил, написал лексер руками. Для простых языков (DSL) мне оказалось тоже проще писать руками. Там скорость разбора не очень важна, а руками получается вроде как более просто написано, и не нужны лишние зависимости. То есть, наверное, есть приложения для которых это нужный и полезный инструмент, но мне для совсем простого или наоборот сложного не зашло. Все равно удачи авторам, пусть проект развивается дальше!
Ответить | Правка | Наверх | Cообщить модератору
Ответы: #42, #45

42. Сообщение от skvadrik (ok), 23-Ноя-24, 14:31	+/–
Спасибо! У 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).
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #41 Ответы: #47

43. Сообщение от freehck (ok), 23-Ноя-24, 19:04	+/–
> Ничего не понял. Что этот анализатор лексических генераторов делает? Да ничего сложного. Когда ты пишешь новый язык, тебе нужны две вещи: херовина, которая разберёт код нового языка на токены (её называют токенайзером, лексером, лексическим анализитором, lexer), а также херовина, которая токены преобразует в код (её называют парсером, или компилятором; а код, который его выплёвывает -- называется yacc-ом, от yet another compiler compiler). В общем, тебе нужен lex и yacc. Это база. Так вот re2c -- это lex.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #27 Ответы: #48

44. Сообщение от freehck (ok), 23-Ноя-24, 19:14	+/–
> А ассемблер поддерживается? Дорогой, а на кой чёрт в 2024м году писать новый язык на ассемблере? )
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #18

45. Сообщение от freehck (ok), 23-Ноя-24, 19:23	+/–
> Для простых языков (DSL) мне оказалось тоже проще писать руками. Хех. При всём уважении: этот тезис СИЛЬНО зависит от того, на каком языке вы его (DSL) пишете. =)
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #41

46. Сообщение от freehck (ok), 23-Ноя-24, 19:25	+/–
> Спасибо за обратную связь. :) Я не юзал, но мельком глянул код, и нахожу его достойным и годным. Я такое редко говорю. Потому -- моё почтение.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #30

47. Сообщение от Аноним (41), 23-Ноя-24, 21:28	+/–
Вы очень любезны, благодарю. Сейчас мне это уже не актуально, сделал вручную сканирование с помощью trie, но если бы опять понадобилось, то, наверное, смотрел бы немного в другом направлении. Насколько я понимаю, для высокопроизводительных лексеров (которые прожевывают гигабайты данных в секунду) на x64 и ARM платформах сейчас лучше писать вручную SIMD-лексеры, как это делает например Daniel Lemire. Если бы кто-то сделал генератор SIMD-лексеров, и если бы эти лексеры работали со скоростью скажем до 20-30% хуже чем написанные вручную, было бы очень интересно. И у меня есть личный заскок - очень плохо понимаю и умею писать регулярки, особенно сложные. То есть в основном как-то получается написать, но постоянно ошибаюсь, приходится тестировать и все время возникает какая-то неуверенность. Если бы в генераторе лексера использовалось что-то похожее на (E)BNF, мне кажется некоторым пользователям с такими же проблемами (а вдруг нас много?) было бы немного проще. Это не претензии к вам, у вас отличный инструмент, просто комментарий человека со стороны.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #42

48. Сообщение от Аноним (48), 24-Ноя-24, 12:56	+/–
А, потом пользователи твоего языка пусть трахомудохаются с багами трудно-определяемого характера... Зато ты с съэкономишь себе время(м.б., а м.б.и наоборот) и повысишь ЧСВ.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #43 Ответы: #49

49. Сообщение от freehck (ok), 24-Ноя-24, 13:02	+/–
О, это очень показательно: Аноним считает, что изучать теоретическую базу программирования -- это в целом не нужно. И я очень поддерживаю позицию данного Анонима. Распространение подобных взглядов в индустрии косвенным образом влияет на деньги, которые люди готовы заплатить лично мне. Так что слушайте Анонима, Аноним херни не посоветует! =)
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #48

50. Сообщение от parad (ok), 25-Ноя-24, 11:41	+/–
лет 10 назад был у нас коллега, который один модуль переписал на спирите (до этого весь парсинг осуществлялся руками написанными свичами). да, возможно он где-то напортачил (хотя сомневаюсь - толковый парень), но на выходе получили: плюсы: 1. код стал красивым, компактным, легко читаемым. минусы: 1. падение производительности модуля в х раз (точную цифру не помню, но она была огромной). к вопросу о производительности 2. абсолютная невозможность отладки - стектрейс глубиной примерно 10-20 занимал около 10 экранов. по прилёту коры человек предпочитал вдумчиво рассматривать свой код, нежеле разбираться с каскадом шаблонов в дампе. 3. пришлось апгрейдит железо, тк 4гб памяти на виртуалке стало недостаточно чтобы скомпилировать этот файл в последовательной компиляции, не говоря о том что до этого можно распараллеливать сборку. по итогу даже фанаты буста на тот момент заключили что это не пригодное к использованию овно (понятно почему не развивается). и трудно найти что-то хуже. в качестве исследования мы перепробовали тогда еще пачку альтернатив (включая re2c) - все они были лучше. в итоге остановились на ragel. так что твой вопрос не верен. правильно спросить - что может быть хуже чем spirit.
Ответить | Правка | Наверх | Cообщить модератору
Родитель: #1

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема