LINUX.ORG.RU

re2c 1.0

 , , ,


7

4

RE2C — генератор лексических анализаторов для языков C и C++, созданный в 1993 году Питером Бамбулисом в качестве альтернативы небезызвестному Flex. Основной целью RE2C является генерация очень быстрых лексеров: по скорости исполнения они должны не уступать коду, написанному и оптимизированному вручную (в пределах разумного). В отличие от Flex, RE2C не использует табличную модель лексера: он кодирует конечный автомат прямо в виде программы на С, состоящей из меток и условных переходов. Полученный лексер оказывается не только быстрее, но часто ещё и меньше [1] (RE2C минимизирует конечный автомат и применяет ряд других оптимизаций). Другая особенность RE2C — отсутствие жёсткого интерфейса: в отличие от Flex, он не генерирует код «обвязки» между лексером и внешним миром. Ответственность за написание этого кода остаётся на пользователе, что даёт большую свободу и позволяет приспосабливать лексеры к уже существующему программному окружению.

Смена мажорной версии (впервые за всю историю проекта) объясняется не поломкой обратной совместимости, а нетривиальным расширением возможностей генератора: кроме обычного распознавания регулярных грамматик (англ. recognition) RE2C теперь умеет частичный синтаксический разбор (англ. submatch extraction). Эта возможность легко реализуема на основе недетерминированных автоматов, и поэтому давно присутствует во многих утилитах (grep, sed), библиотеках регулярных выражений (RE2) и языках (Perl, JS). А вот в генераторах лексеров эта возможность обычно отсутствует (Lex, Flex, Quex), корректно работает только на малой части случаев (Ragel) или реализована путём серьёзного усложнения модели (Tlex). Одно из следствий невозможности синтаксического разбора средствами детерминированных конечных автоматов — изначально поломанный оператор предпросмотра в Lex и Flex.

Алгоритм разбора, заложенный в основе RE2C, был предложен Вилле Лаурикари в 2000 году [2]. Этот алгоритм хорош тем, что усложняет модель вычислений ровно настолько, насколько того требует детализация синтаксического разбора в каждом конкретном случае: для обычных задач распознавания модель Лаурикари соответствует простому детерминированному автомату. RE2C использует «улучшенную и дополненную» версию алгоритма, предложенную автором сего поста [3].

[1] Cтатья 1993 года, в которой проведён сравнительный анализ RE2C, Flex и других генераторов

[2] Статья 2000 года, которая описывает быстрый алгоритм разбора

[3] Статья 2017 года, которая описывает новый ещё более быстрый алгоритм разбора

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



Проверено: Pinkbyte ()

корректно работает только на малой части случаев (Ragel)

Чё? Ragel это же просто язык описания КА. Каким боком тут синтаксический разбор, да ещё и некорректно работающий?

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

Конечные автоматы --- формализм, на котором основано распознавание регулярных языков: они позволяют эффективно определить, принадлежит ли слово заданному регулярному языку (что то же самое, матчится ли строка заданным регулярным выражением).

Ragel действительно является языком описания конечных автоматов. Каждый автомат описывается в виде регулярного выражения. Ragel позволяет комбинировать автоматы с помощью разных операторов (объединение, конкатенация, пересечение и т.д.). С каждым автоматом ассоциируются блоки кода, которые исполняется по различным событиям, связанным с этим автоматом, например при «входе» и при «выходе».

Всё это функционирует очень удобно и интуитивно понятно, до тех пор пока не возникает проблема неоднозначности. Например, два автомата могут оба матчить слово «Петя», но выполнять при этом разные действия (один пишет на экран «молодец», а второй — «плохой человек»). Объединение таких автоматов приводит к неоднозначности, какое из двух действий выполнять. Неоднозначность может быть и более хитрая: например, конкатенация двух «перекрываюшихся» автоматов (каноничный пример — С++ комментарии any* :>> '*/', где any* матчит '*/', и нужен специальный оператор :>> чтобы исправить ситуацию).

Ragel-мануал содержит целую главу (4), посвящённую разрешению такого рода конфликтов. Механизм разрешения основан на привязывании приоритетов к переходам конечного автомата: с помощью разных директив и операторов пользователь может вручную сообщить Ragel, как именно следует разрешить тот или иной конфликт. Этот механизм не универсальный: он хорошо работает в простых случаях, но в общем случае требует хорошего понимания конечных автоматов, постоянной бдительности и, в худшем случае, загромождения кода малопонятными операторами и директивами.

А возникает проблема неоднозначности как раз при переходе от простого распознавания (матчит/не матчит) к разбору (если матчит, то как: где конец одного автомата и началр другого и т.д.). Задача синтксического разбора регулярных языков не может быть решена на обычных ДКА.

skvadrik ()

он кодирует конечный автомат прямо в виде программы на С, состоящей из меток и условных переходов

Разве это не работа синтаксического анализатора?

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

А возникает проблема неоднозначности как раз при переходе от простого распознавания (матчит/не матчит) к разбору (если матчит, то как: где конец одного автомата и началр другого и т.д.). Задача синтксического разбора регулярных языков не может быть решена на обычных ДКА.

А зачем проектировать грамматику, включающую неоднозначность? Плюс разве нельзя в yacc/bison расставить приоритеты для терминалов и тем самым решить проблему?

lochness ()

А он умеет работать в потоковом режиме (запрашивать чтение очередного куска документа, когда распарсил весь предыдущий и нужны еще данные), чтобы можно было анализировать данные, когда они передаются и сообразить, что данные не того формата, нужно считать еще или весь документ получен и пора генерировать ответ (т.е. когда не знаешь, сколько данных нужно принять, и по полученному формату распознаешь нужно ли читать еще)?

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

Если я правильно понимаю, то вопрос заключается в том, можно ли, распарсив часть данных, остановить лексер, дождаться новых данных и возобновить разбор с того места где лексер остановился.

Это обычно называется «push-model», в противовес «pull-model». Такое да, можно. Вот соответствующий кусок мануала: http://re2c.org/manual/features/state/state.html

А ещё есть пример в re2c/examples/push_model/push.re

skvadrik ()

А сравнение производительности с flex где-нибудь есть? Я было думал самому сравнить, но перевод с flex выглядит как много работы на попробовать.

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

А зачем проектировать грамматику, включающую неоднозначность?

Проектировать сильно неоднозначную грамматику действительно глупо, но тут немного другая ситуация: есть лексическая грамматика, заданная в виде регулярных выражений. Пока эти выражения просто матчат (да/нет), всё ок. Но вдруг надо для какой-то конкретной части регулярного выражения узнать, какому куску входной строки она соответствует (submatch, captures, и т.д.). И это вызывает неоднозначность.

Плюс разве нельзя в yacc/bison расставить приоритеты для терминалов и тем самым решить проблему?

YACC и Bison --- это уровнем выше, для контекстно-свободных грамматик. RE2C и Flex --- для регулярных.

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

Там в новости ссылка [1], по ней статья в которой сравнение производительности. Более нового нет, но есть в планах.

перевод с flex выглядит как много работы на попробовать

Вообще RE2C частично поддерживает Flex-синтаксис (-F --flex-syntax флаг), то есть сами правила можно теоретически копипастить. Но обвязку да, надо подгонять. И от качества подгона сравнение может сильно измениться.

skvadrik ()

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

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

YACC и Bison --- это уровнем выше, для контекстно-свободных грамматик. RE2C и Flex --- для регулярных.

Это очень интересно. Спасибо за разъяснения. Почитаю ссылки после «Книги дракона».

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

принадлежит ли слово заданному регулярному языку (что то же самое, матчится ли строка заданным регулярным выражением).

Надо только уточнить, что здесь речь не идёт о POSIX {B,E}RE. Они сильнее, чем регулярные грамматики.

Задача синтксического разбора регулярных языков не может быть решена на обычных ДКА.

Ну вообще-то любая регулярная грамматика сводится именно к ДКА. Или что такое «синтаксический разбор регулярного языка»?

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

Надо только уточнить, что здесь речь не идёт о POSIX {B,E}RE. Они сильнее, чем регулярные грамматики.

POSIX BRE/ERE поддерживают две возможности, выходящие за рамки обычных (в математическом смысле) регулярных выражений: 1) обратные ссылки (backreferences) и 2) частичный синтаксический разбор с помощью круглых скобок (submatch extraction, capturing parentheses). Всё остальное — синтаксический сахар и сложности в реализации не представляет.

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

А вот синтаксический разбор как раз удалось реализовать эффективно — в этом основное достижение RE2C-1.0. Под «эффективно» я подразумеваю «на совсем слегка усложнённых ДКА, а не НКА» — посколько на НКА он давно реализован и используется во всяких grep, sed, RE2 (речь о гугловской библиотеке, не путать с RE2C) и прочем. Моя статья как раз описывает новый алгоритм, чтобы разработчики других генераторов вроде Flex могли тоже реализовать его на радость пользователям.

Кроме того, RE2C опционально поддерживает именно POSIX-семантику разбора и POSIX-синтаксис с круглыми скобками (опция -P --posix-captures): каждое под-выражение матчит наиболее длинную подстроку. Этого тоже было непросто добиться и долгое время считалось невозможным.

Ну вообще-то любая регулярная грамматика сводится именно к ДКА. Или что такое «синтаксический разбор регулярного языка»?

Распознавание регулярных грамматик сводится к ДКА (recognition) — ответ на вопрос «матчит / не матчит». Генераторы лексеров обычно только это и умеют. А синтаксический разбор это когда можно кроме «да / нет» ещё и узнать «как именно», то есть какая часть входной строки соответствует конкретному под-выражению.

Синтаксически это обычно выражается круглыми скобками, но тот же оператор предпросмотра или контекста (lookahead, trailing context) по сути решает ту же задачу: это как отдельно стоящая непарная скобка. Многие генераторы (Lex, Flex) сначала ошибочно добавили его, а потом поняли что правильно реализовать его не могут.

К несчастью различие между распознаванием и разбором тонкое, и даже в родной англоязычной терминологии его непросто объяснть: все давно привыкли, что в POSIX ERE скобки означают «запомнить соответствующую подстроку», а во Flex они просто переопределяют приоритет операторов.

skvadrik ()

Годно. Надо как-нибудь добавить поддержку Go.

Статья 2017 года

Строки в колонках не выровнены. Не знаю, может, в LaTeX это сложно сделать.

anonymous ()

Остро не хватает оператора $ (конец данных). Как, например, реализовать такое:

    /*!re2c
        aaa = "a"+;

        *   { return false; }
        aaa { return true; }
    */


Определить YYFILL? Но ведь он не знает, найдена ли хоть одна буква, и одинаково сработает при пустой строке и в конце строки из «a».

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

В простом примере выше можно, конечно, проверять в YYFILL, пуста ли строка. А если эти a+ стоят в конце длинной цепочки правил? Как определить, сматчено выражение полностью или нет?

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

Подозреваю пример не полный, потому что в этом случае вообще никакой YYFILL не нужен. Если строка null-терминированная:

    /*!re2c
        *           { return false; }
        [a]+ [\x00] { return true; }
    */

Если не null-терминированная, но известна длина строки, то [--input custom] и перегрузить YYPEEK как в примере http://re2c.org/examples/example_16.html :

#   define YYPEEK (cur < lim ? *cur : 0)
    /*!re2c
        *           { return false; }
        [a]+ [\x00] { return true; }
    */
skvadrik ()
Ответ на: комментарий от anonymous

Не ясно из описания, что надо сделать и какие ограничения на входные данные. Особенно непонятно, зачем:

проверять в YYFILL, пуста ли строка

Проверка на конец входных данных может быть основана или на терминальном спец-символе, или на явном сравнении текущей позиции с позицией конца данных.

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

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

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

Надо как-нибудь добавить поддержку Go.

Да! И Rust. И будет 2.0 с multitarget. :)

Cтроки в колонках не выровнены.

Хм, где? Горизонтально вроде норм, а вертикально там заглавия в тексте (балансируются так же как основной текст).

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

Строка не NULL-терминированная, длина известна (см. string и []byte в Go). Второй пример вроде как сработает, но он с тем же успехом вернёт true и не в конце строки, если в строке попадётся реальный ноль. А это нехорошо.

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

Значит пока так:

#   define YYPEEK (cur < lim ? *cur : 0)
    /*!re2c
        *           { return false; }
        [a]+ [\x00] { return cur == lim; }
    */
Громоздковато, согласна. Так было бы лучше:
    /*!re2c
        *      { return false; }
        [a]+ $ { return true; }
    */
Будем думать.

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

В профессиональных издательских системах вроде Scribus для этого специальная опция есть: выровнять по линии шрифта. Для статьи не так важно.

У меня есть такое наколенное поделие для преобразования регекспов в конечные автоматы. Там куча своих проблем, но $ матчится легко и просто. Правда, большие регекспы может просто не осилить.

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

Я не разбираюсь в go, но код выглядит коротко и аккурано. :)

Правда, большие регекспы может просто не осилить.

Кажется он там запускал re2dfa на 1.9-мегабайтный регексп. Шутник. :D Для больших или просто особо раздувающихся при детерминизации регекспов нужны совсем другие техники, гибридные автоматы (смесь НКА и ДКА) и программная поддержка счётчиков (counted repetition), если их детерминизировать.

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

Задача синтксического разбора регулярных языков не может быть решена на обычных ДКА.

Ну то есть если применять язык описания КА для решения задачи, которая с помощью КА не решается в принципе, то какая-то фигня получится? Гениально! Даже удивительно, как до этого раньше никто не додумался :-D

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

Советую обратить внимание на слово «обычных» и на отсутствие оборота «фигня получится» в моём комментарии. Ragel не плох, а ограничен.

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

skvadrik ()