re2c 1.0

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

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

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

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

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

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

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

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

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

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

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

молодцы, круто

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

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

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

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

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

Уля, спасибо за новость.

Молодцы. Долгой жизни проекту.

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

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

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

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

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

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

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

спасибо!

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

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

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

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

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

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

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

Надо только уточнить, что здесь речь не идёт о 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 они просто переопределяют приоритет операторов.

Чому гентушнеки не в курсе?

Офигеть, дайте две!

https://packages.gentoo.org/packages/dev-util/re2c

Сейчас начал искать — оказывается, много лет назад на Хабре уже была тематическая статья. На русском. С примерами.

https://habrahabr.ru/post/117843/

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

Статья 2017 года

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

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

    /*!re2c
        aaa = "a"+;

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

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

http://re2c.org/examples/example_15.html прочёл. Ответа не даёт.

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

Подозреваю пример не полный, потому что в этом случае вообще никакой 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; }
    */

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

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

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

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

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

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

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

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

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

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

Горизонтально.

https://i.imgur.com/Gg0sRdb.png

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

#   define YYPEEK (cur < lim ? *cur : 0)
    /*!re2c
        *           { return false; }
        [a]+ [\x00] { return cur == lim; }
    */

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

А, спасибо. Сходу не удаётся выровнять.

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

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

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

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

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

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

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

[uaer]maxcom совсем охуел.

[uaer]maxcom совсем охуел.

maxcom совсем охуел.

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

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