LINUX.ORG.RU

re2c 1.2

 , , ,


6

4

В пятницу 2-го августа вышел релиз re2c — свободного генератора лексических анализаторов для языков C и C++. Напомним, что re2c был написан в 1993 году Питером Бамбулисом как экспериментальный генератор очень быстрых лексических анализаторов, отличающийся от других генераторов скоростью сгенерированного кода и необычно гибким пользовательским интерфейсом, который позволяет легко и эффективно встривать анализаторы в существующую кодовую базу. С тех пор проект развивается сообществом и продолжает оставаться площадкой для экспериментов и исследований в области формальных грамматик и конечных автоматов.

Основные новшества в версии 1.2:

  • Добавлен новый (упрощённый) способ проверки на конец входных данных (англ. «EOF rule»). Для этого добавлена конфигурация re2c:eof, позволяющая выбрать терминальный символ, и специальное правило $, которое срабатывает если лексер успешно достиг конца входных данных. Исторически re2c предоставляет на выбор несколько способов проверки на конец входных данных, варьирующихся по ограниченности, эффективности и простоте применения. Новый способ призван упростить написание кода, при этом оставаясь эффективным и широко применимым. Старые способы по-прежнему работают и могут быть предпочтительными в отдельных случаях.

  • Добавлена возможность включения внешних файлов с помощью директивы /*!include:re2c "file.re" */, где file.re это имя включаемго файла. Re2c ищет файлы в директории включащего файла, а также в списке путей заданных с помощью опции -I. Включённые файлы могут включать другие файлы. Re2c предоставляет «стандартные» файлы в директории include/ проекта — предполагается, что там будут накапливаться полезные определения регулярных выражений, что-то в духе стандартной библиотеки. Пока что по просьбам трудящихся добавлен один файл с определениями категорий Unicode.

  • Добавлена возможность генерировать заголовочные файлы с произвольным содержанием при помощи опций -t --type-header (или соответствующих конфигураций) и новых директив /*!header:re2c:on*/ и /*!header:re2c:off*/. Это может быть полезно в случаях, когда re2c должен сгенерировать определения переменных, структур и макросов, использующихся в других единицах трансляции.

  • Re2c теперь понимает UTF8-литералы и классы символов в регулярных выражениях. По умолчанию, re2c парсит выражения вроде "∀x ∃y" как. последовательность 1-битных ASCII-символов e2 88 80 78 20 e2 88 83 79 (hex-коды), и пользователям приходится экранировать Unicode-символы вручную: "\u2200x \u2203y". Это очень неудобно и неожиданно для многих пользователей (о чём свидетельствуют постоянные баг репорты). Поэтому теперь re2c предоставляет опцию --input-encoding <ascii | utf8>, которая позволяет изменить поведение и распарсить "∀x ∃y" как 2200 78 20 2203 79.

  • Re2c теперь позволяет использовать обычные re2c-блоки в режиме -r --reuse. Это удобно, если входной файл содержит много блоков, и только часть из них нуждается в повторном использовании.

  • Появилась возможность задавать формат предупреждений и сообщений об ошибках с помощью новой опции --location-format <gnu | msvc>. GNU-формат отображается как filename:line:column:, а MSVC-формат — как filename(line,column). Эта возможность может пригодиться любителям IDE. Также была добавлена опция --verbose, которая выводит краткое победоносное сообщение в случае успеха.

  • Был доработан режим «совместимости» с flex — исправлены некоторые ошибки разбора и неправильный приоритет операторов в редких случаях. Исторически опция -F --flex-support позволяет писать код вперемешку в стиле flex и в стиле re2c, что немного затрудняет синтаксический разбор. Режим совместимости с flex редко используется в новом коде, но re2c продолжает поддерживать его для обратной совместимости.

  • Оператор вычитания символьных классов / теперь применяется до разворачивания кодировки, что позволяет применять его в большем числе случаев, если используется кодировка с переменной длиной символа (например UTF8).

  • Выходной файл теперь создаётся атомарно: re2c сначала создаёт временный файл и пишет в него результат, а потом переименовывает временный файл в выходной одной операцией.

  • Документация была дописана и переписана; в частности, были добавлены новые главы про заполнение буфера и про способы проверки на конец входных данных. Новая документация собрана в виде исчерпывающейго одностраничного мануала с примерами (одни и те же исходники отрисовываются в manpage и в онлайн-документацию). Были предприняты слабые попытки улучшить читаемость сайта на телефонах.

  • С точки зрения разработчиков, re2c обзавёлся более полноценной подсистемой отладки. Отладочный код теперь отключён в релизных сборках и может быть включен с помощью configure-опции --enable-debug.

Этот релиз занял долгое время — почти целый год. Большинство времени, как всегда, ушло на разработку теоретической базы и написание статьи «Efficient POSIX Submatch Extraction on NFA». Алгоритмы, описанные в статье, реализованы в экспериментальной библиотеке libre2c (сборка библиотеки и бенчмарков выключена по умолчанию и включается configure-опцией --enable-libs). Библиотека задумана не как конкурент уже существующим проектам вроде RE2, а как исследовательская площадка для разработки новых алгоритмов (которые потом могут использоваться в re2c или в других проектах). Также это удобно с точки зрения тестирования, бенчмарков и создания биндингов к другим языкам.

Cпасибо от разработчиков re2c всем, кто помог этому релизу состояться, и в целом сообществу за идеи, баг репорты, патчи, боевой дух и т.д. ;]

>>> Подробности

Ответ на: комментарий от XMs

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

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

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

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

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

skvadrik ()
Ответ на: комментарий от anonymous

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

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

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

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

skvadrik ()
Ответ на: комментарий от anonymous

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

svyatozar ()
Последнее исправление: svyatozar (всего исправлений: 1)
Ответ на: комментарий от svyatozar

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

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

matumba ★★★★★ ()

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

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

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

matumba ★★★★★ ()
Ответ на: комментарий от matumba

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

svyatozar ()
Ответ на: комментарий от Lucky

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

Да.

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

skvadrik ()

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

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

vodz ★★★★ ()
Последнее исправление: vodz (всего исправлений: 1)
Ответ на: комментарий от svyatozar

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

matumba ★★★★★ ()
Ответ на: комментарий от vodz

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

svyatozar ()
Ответ на: комментарий от svyatozar

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

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

vodz ★★★★ ()
Ответ на: комментарий от vodz

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

svyatozar ()
Ответ на: комментарий от svyatozar

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

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

vodz ★★★★ ()
Последнее исправление: vodz (всего исправлений: 2)
Ответ на: комментарий от vodz

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

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

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

skvadrik ()
Ответ на: комментарий от skvadrik

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

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

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

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

vodz ★★★★ ()
Последнее исправление: vodz (всего исправлений: 1)
Ответ на: комментарий от svyatozar

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

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

vodz ★★★★ ()
Ответ на: комментарий от vodz

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

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

skvadrik ()
Ответ на: комментарий от skvadrik

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

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

vodz ★★★★ ()
Ответ на: комментарий от vodz

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

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

skvadrik ()
Ответ на: комментарий от skvadrik

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

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

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

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

vodz ★★★★ ()
Последнее исправление: vodz (всего исправлений: 1)
Ответ на: комментарий от vodz

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

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

skvadrik ()
Ответ на: комментарий от skvadrik

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

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

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

goto-vlad ()
Ответ на: комментарий от skvadrik

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

anonymous ()
Ответ на: комментарий от goto-vlad

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

skvadrik ()
Ответ на: комментарий от skvadrik

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

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

vodz ★★★★ ()
Ответ на: комментарий от skvadrik

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

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

goto-vlad ()