The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Выпуск генератора лексических анализаторов re2c 4.0

20.11.2024 19:36

Опубликован релиз re2c 4.0 - генератора лексических анализаторов (он же компилятор регулярных выражений в код на целевом языке программирования). Re2c специализируется на генерации быстрых и легко встраиваемых лексеров и отличается от более известного аналога Flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP.

В релизе 4.0 коренным образом переработана подсистема генерации кода, что позволило добавить поддержку восьми новых языков (D, Haskell, Java, JavaScript, OCaml, Python, V, Zig) в дополнение к уже поддерживаемым (C/C++, Go, Rust), а также реализовать общий механизм добавления новых языков через конфигурационные файлы.

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

Теперь вся эта логика перенесена в синтаксические файлы - текстовые конфигурационные файлы, которые могут быть предоставлены пользователем (по умолчанию re2c использует стандартные). Исходный код re2c полностью свободен от деталей конкретного языка и полагается только на синтаксический файл. Пользователь может частично переопределить существующий синтаксический файл или написать новый с нуля. Для всех официально поддерживаемых языков есть полная документация с примерами.

В релиз также вошло много других изменений для упрощения пользовательского интерфейса и улучшения работы с захватывающими группами (capturing groups). Добавлена онлайн-среда для редактирования и компиляции примеров.

  1. Главная ссылка к новости (http://re2c.org/releases/relea...)
  2. OpenNews: Выпуск генератора лексических анализаторов re2c 3.0
  3. OpenNews: Выпуск генератора лексических анализаторов re2c 1.2
  4. OpenNews: Выпуск генератора лексических анализаторов re2c 2.0
Автор новости: skvadrik
Лицензия: CC BY 3.0
Короткая ссылка: https://opennet.ru/62267-re2c
Ключевые слова: re2c
При перепечатке указание ссылки на opennet.ru обязательно


Обсуждение (43) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, Аноним (1), 04:24, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Чем он лучше Boost::Spirit?
     
     
  • 2.3, Аноним (3), 04:29, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Возможно, тем, что он не сдох как спирит в 2014?
     
  • 2.11, Аноним (11), 10:07, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    вопрос к сообщению про то что спирит сдox в 14 году, я его использовал активно в 18-19. вполне успешно и живой он был
     
     
  • 3.13, Аноним (11), 10:20, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • –1 +/
    посмотрел что там у спирита на сайте буста. действительно не развивается давно. последняя верся .78
     
  • 2.12, skvadrik (ok), 10:18, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • –1 +/
    А Boost::Spirit во время компиляции строит и оптимизирует конечный автомат?
     
     
  • 3.14, Аноним (11), 10:24, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    наврятли он что-то оптимизирует. это все шаблонной магией делается. Вся формальная спецификация задается как шаблонный код, те код парсера получается через инстанцирование шаблонного кода в момент компиляции
     
     
  • 4.17, skvadrik (ok), 11:28, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    У re2c ещё есть то преимущество по сравнению с другими компиляторами регулярных выражений, что он использует конечные автоматы с тэгами (https://en.wikipedia.org/wiki/Tagged_Deterministic_Finite_Automaton), что позволяет ему делать не просто распознавание, но и захват (submatch extraction). Обычно или компилируется (и тогда нет захвата), или а рантайме матчится (и тогда захват есть, но не так быстро).
     
     
  • 5.23, qq (??), 15:35, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Tagged Deterministic Finite Automaton),

    The article that you're looking for doesn't exist.

     
  • 5.25, Уля (?), 15:43, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    https://en.m.wikipedia.org/wiki/Tagged_Deterministic_Finite_Automaton
     
  • 5.26, Аноним (26), 16:37, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    такого в спирите нет, там никакого рантайма. все скомпилено из шаблонов и прибито
     
  • 2.50, parad (ok), 11:41, 25/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    лет 10 назад был у нас коллега, который один модуль переписал на спирите (до этого весь парсинг осуществлялся руками написанными свичами). да, возможно он где-то напортачил (хотя сомневаюсь - толковый парень), но на выходе получили:
    плюсы:
    1. код стал красивым, компактным, легко читаемым.
    минусы:
    1. падение производительности модуля в х раз (точную цифру не помню, но она была огромной). к вопросу о производительности
    2. абсолютная невозможность отладки - стектрейс глубиной примерно 10-20 занимал около 10 экранов. по прилёту коры человек предпочитал вдумчиво рассматривать свой код, нежеле разбираться с каскадом шаблонов в дампе.
    3. пришлось апгрейдит железо, тк 4гб памяти на виртуалке стало недостаточно чтобы скомпилировать этот файл в последовательной компиляции, не говоря о том что до этого можно распараллеливать сборку.
    по итогу даже фанаты буста на тот момент заключили что это не пригодное к использованию овно (понятно почему не развивается). и трудно найти что-то хуже. в качестве исследования мы перепробовали тогда еще пачку альтернатив (включая re2c) - все они были лучше. в итоге остановились на ragel.
    так что твой вопрос не верен. правильно спросить - что может быть хуже чем spirit.
     

  • 1.2, Аноним (3), 04:27, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Сложные (по неоднозначностям) языки типа C++ - на нём можно написать?
     
     
  • 2.5, Аноним (5), 08:43, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • –1 +/
    >уже поддерживаемым (C/C++, Go, Rust)
     
     
  • 3.6, Аноним (6), 09:04, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +2 +/
    🤦‍

    Поддерживается генерация кода на этих языках, а не их разбор.

     
  • 2.9, skvadrik (ok), 10:01, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Лексический анализатор конечно можно, но судя по вопросу о неоднозначностях речь о синтаксическом разборе -- тогда нет конечно, re2c для регулярных грамматик.
     

  • 1.16, ijuij (?), 11:17, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Сохранил в закладки. Будет любопытно заюзать инструменты для (code sanitizers, fuzzing, static program analysis) и поискать уязвимости и баги. 😈🐛

     
  • 1.18, Аноним (18), 11:48, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    А ассемблер поддерживается?
     
     
  • 2.19, skvadrik (ok), 12:03, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Нет, и пока в планах этого нет. Для компилируемых языков обычно оптимизирующий компилятор решают эту задачу, и лезть туда надо только если заведомо есть что ускорить (т.е. по какой-то причине компилятор не умеет генерить эффективный код именно для такого типа исходников, и нельзя его пофиксить). В re2c можно проводить более высокоуровневые оптимизации (например, читать и матчить по нескольку байт за раз -- но даже тут много проблем с выравниванием и т.д.).

    А какой ассемблер вас интересует? Для каких задач/сред это может пригодиться, где С тулчейн не подойдёт?

     
  • 2.44, freehck (ok), 19:14, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > А ассемблер поддерживается?

    Дорогой, а на кой чёрт в 2024м году писать новый язык на ассемблере? )

     

  • 1.20, Аноним (20), 12:08, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Осталось понять, зачем для окамла или хаскеля брать этот инструмент, а не их родные.
     
     
  • 2.21, skvadrik (ok), 12:25, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Для окамла пользователи попросили: https://github.com/skvadrik/re2c/issues/449, для хаскеля он может оказаться быстрее чем alex (это ещё надо потестировать), но вообще было полезно добавить поддержку просто чтобы убедиться в том, что синтаксические файлы достаточно гибкие для чистого функционального ЯП.
     
     
  • 3.31, Аноним (20), 19:06, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Что скажите по сравнению с menhir(lr генератор для ocaml) и tree-sitter (glr, с восстановлением после ошибки, с кучей биндингов, у окамла есть типизированный биндинг)? В частности по поводу восстановления после ошибок, с возвратом частично построенного дерева типа такого
    for (var i = 1;
        console.log(i);
     
     
  • 4.32, skvadrik (ok), 19:26, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Это же генераторы парсеров, а не лексеров. Они для другого типа грамматик: re2c для регулярных, а menhir и tree-sitter для контекстно-свободных. Эти задачи решаются разными алгоритмами (можно, конечно, GLR парсером распознавать регулярные грамматики, но это неэффективно и неудобно). Часто генератор лексеров и парсеров работают в связке.
     
     
  • 5.36, Аноним (20), 12:16, 22/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Как-то пропустил, что это только лексер
     
  • 4.34, skvadrik (ok), 19:31, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Вот тут параллель проводили с ocamllex и sedlex: https://github.com/skvadrik/re2c/issues/449#issuecomment-1601284862.
     

  • 1.22, Аноним (6), 13:55, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +3 +/
    Уля, спасибо что не бросаете. Отдельная благодарность за Zig и за внешнюю конфигурацию синтаксиса в целом. Традиционно, привет Серёже. =)

    p.s. В Gentoo пока всё ещё 3.1.

     
     
  • 2.30, skvadrik (ok), 18:52, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Спасибо за обратную связь. :)
     
     
  • 3.46, freehck (ok), 19:25, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Спасибо за обратную связь. :)

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

     
  • 2.35, erthink_erthink (?), 22:31, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Присоединяюсь.

    Спасибо за лучший инструмент.

     

  • 1.27, Аноним (27), 17:43, 21/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Ничего не понял. Что этот анализатор лексических генераторов делает?
     
     
  • 2.28, Аноним (6), 17:51, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Генерит по описанию лексики исходник на выбранном языке, являющийся специализированным быстрым парсером этой лексики. Из подобного — Flex, Bison и т.д.
     
     
  • 3.33, skvadrik (ok), 19:28, 21/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Может из примеров станет понятнее: http://re2c.org/playground
     
  • 2.37, Аноним (20), 12:18, 22/11/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Лексер преобразует строку в поток токенов, а парсер из этих токенов стрит синтаксическое дело. Нужно, если вы хотите как-то обработать исходный код, например, скомпилировать, изменить, или проверить на ошибки
     
     
  • 3.38, skvadrik (ok), 12:39, 22/11/2024 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Применений много и помимо разбора исходного кода: разбор логов / конфигов / URL адресов / email адресов / аргументов командной строки / поиск сигнатур в бинарных файлах -- в общем, всё, что не выходит за рамки регулярных грамматик (в частности, не содержит вложенных стуктур и скобочных выражений -- например, HTML регулярными выражениями парсить нельзя: https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml).
     
     
  • 4.39, Аноним (39), 22:21, 22/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Классическими регулярками нельзя, расширенными, как в Perl/PCRE, умеющими в рекурсию - можно, но там другая проблема - непредсказуемость вычислительной сложности.
     
     
  • 5.40, skvadrik (ok), 23:04, 22/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Это заблуждение. Для распознавания вложенных структур (простейший пример - скобчных выражений) не годятся ни обычные, ни Perl регулярные выражения. Нету такого способа выразить в регулярном выражении "сматчить N открывающих скобок, потом что-то ещё, а потом N закрывающих" - вот это вот N, что оно оба раза одно и то же, никак не выразить, для этого нужны как минимум контекстно-свободные грамматики. Если вы считаете, что можно, приведите пример регулярного выражения, которое матчит сбалансированные скобочные выражения.

    [Upd]

    Оказывается, это я заблуждалась и Perl действительно такое умеет, вот пример: https://stackoverflow.com/a/18653648 . Тут используется синтаксис (?R) чтобы рекурсивно сматчить опять всё выражение.

     
  • 2.43, freehck (ok), 19:04, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Ничего не понял. Что этот анализатор лексических генераторов делает?

    Да ничего сложного. Когда ты пишешь новый язык, тебе нужны две вещи: херовина, которая разберёт код нового языка на токены (её называют токенайзером, лексером, лексическим анализитором, lexer), а также херовина, которая токены преобразует в код (её называют парсером, или компилятором; а код, который его выплёвывает -- называется yacc-ом, от yet another compiler compiler).

    В общем, тебе нужен lex и yacc. Это база.

    Так вот re2c -- это lex.

     
     
  • 3.48, Аноним (48), 12:56, 24/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    А, потом пользователи твоего языка пусть трахомудохаются с багами трудно-определяемого характера... Зато ты с съэкономишь себе время(м.б., а м.б.и наоборот) и повысишь ЧСВ.
     
     
  • 4.49, freehck (ok), 13:02, 24/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    О, это очень показательно: Аноним считает, что изучать теоретическую базу программирования -- это в целом не нужно. И я очень поддерживаю позицию данного Анонима. Распространение подобных взглядов в индустрии косвенным образом влияет на деньги, которые люди готовы заплатить лично мне. Так что слушайте Анонима, Аноним херни не посоветует! =)
     

  • 1.41, Аноним (41), 12:34, 23/11/2024 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Прикольная штука, несколько раз пробовал писать лексеры простых языков. Но когда нужно лексить (лексировать?) что-то более-менее сложное - то становится очень нетривиально.
    Хотел разбирать данные, которые приходят кусками (например, из сети или если читать файл блоками). В примерах вроде что-то похожее есть, но невероятно заморочено, несколько дней помучался, бросил, написал лексер руками.
    Для простых языков (DSL) мне оказалось тоже проще писать руками. Там скорость разбора не очень важна, а руками получается вроде как более просто написано, и не нужны лишние зависимости.
    То есть, наверное, есть приложения для которых это нужный и полезный инструмент, но мне для совсем простого или наоборот сложного не зашло.
    Все равно удачи авторам, пусть проект развивается дальше!
     
     
  • 2.42, skvadrik (ok), 14:31, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Спасибо! У 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).

     
     
  • 3.47, Аноним (41), 21:28, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    Вы очень любезны, благодарю.
    Сейчас мне это уже не актуально, сделал вручную сканирование с помощью trie, но если бы опять понадобилось, то, наверное, смотрел бы немного в другом направлении.
    Насколько я понимаю, для высокопроизводительных лексеров (которые прожевывают гигабайты данных в секунду) на x64 и ARM платформах сейчас лучше писать вручную SIMD-лексеры, как это делает например Daniel Lemire.
    Если бы кто-то сделал генератор SIMD-лексеров, и если бы эти лексеры работали со скоростью скажем до 20-30% хуже чем написанные вручную, было бы очень интересно.
    И у меня есть личный заскок - очень плохо понимаю и умею писать регулярки, особенно сложные. То есть в основном как-то получается написать, но постоянно ошибаюсь, приходится тестировать и все время возникает какая-то неуверенность. Если бы в генераторе лексера использовалось что-то похожее на (E)BNF, мне кажется некоторым пользователям с такими же проблемами (а вдруг нас много?) было бы немного проще.
    Это не претензии к вам, у вас отличный инструмент, просто комментарий человека со стороны.
     
  • 2.45, freehck (ok), 19:23, 23/11/2024 [^] [^^] [^^^] [ответить]  
  • +/
    > Для простых языков (DSL) мне оказалось тоже проще писать руками.

    Хех. При всём уважении: этот тезис СИЛЬНО зависит от того, на каком языке вы его (DSL) пишете. =)

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Партнёры:
    PostgresPro
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2025 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру