Pull to refresh

Comments 24

UFO just landed and posted this here
Нет, бенчмаркинг не делал. По поводу результатов, приведенных вами — интересно, но при быстром взгляде не понятно, что есть что. Легенда была бы к месту.
Возможно, заморочусь и сделаю сравнение для парсеров «нативных», на регулярках и generic-ов (LL/LR/PEG) для чего-нибудь популярного, наподобие json. Брут-форсы писать не буду, ибо лень, разве что чей-нибудь найду для копи-паста :). Действительно, любопытно посмотреть динамику, в зависимости от размера файла (и, возможно, от сложности структуры).
UFO just landed and posted this here
Полагаю, все во многом зависит от алгоритма построения, он может существенно отличаться, все-таки. Как дойдут руки, сделаю бенч для python/json, по хорошему стоит взять несколько библиотек. В конце концов, никто не гарантирует, что создатели AST-парсеров не используют регулярки ВНУТРИ.
1. TestRig (который ANTLR grun) мне почему-то отвечает одно и то же:
Can't load calc as lexer or parser


Версия ANTLR ровно по указанному URL.

2. По поводу ассоциативности — Вы не пробовали вместо

stmt: term | term addop stmt;

написать

stmt: term | stmt addop term;

?

по документации — ANTLR спокойно отрабатывает такую левую рекурсию.
1. Есть предположение, что grun тупо запускается не из той папки. Проверьте, что созданные java-файлы находятся там, где вы запускаете визуализатор.
2. Попробовал, заработало. Ценное замечание, спасибо, простые решения самые правильные, обновил статью.
Тема интересная, как -то была идея сделать парсер на bnf для последующей конвертации в другие форматы, но что-то сходу не пошло и забросил, обошёлся регулярками, хотя понимаю что это кривой способ, но время на сделать по нормальному не выделил.
Я правильно понимаю что конвертацию в другие форматы мы должны делать в listener'ах?
Если речь об ANTLR — да. Но и здесь есть ньюансы — можете посмотреть ссылку на пример грамматики калькулятора на гитхаб.
Если речь в общем, то есть обоснованное предположение, что быстрее работает привязка функций к грамматическим конструкциям без построения дерева.
Интересно в общем случае и скорее важнее не скорость а ясность и читаемость, может есть какой-то пример полного цикла парсинга с последующей конвертацией?
PEG в статье.
Если вас чем-то описанный случай не устраивает, предложите простой use-case, может быть, добавлю
LL(k), которые всегда в принципе можно свести к LL(1), на самом деле всегда лучше писать руками или парсер-комбинаторами(ну тот же калькулятор, описанный). Да, надо знать матчасть. Но, при использовании описанных инструментов, даже PEG, на самом деле нужно знать еще больше матчасти :)

Также, имхо, нужно было бы упомянуть, что до стадии парсера, желательно иметь стадию лексера (которую можно и на регулярках заимплементить) — оно такое дело значительно всё упрощает. Кроме PEG, возможно, в случае реализации в виде packrat-парсера.

Ну и кстати, в случае реальных языков программирования, один хрен придется почти всё руками делать — почти у всех языков грамматики контекстно-зависимые. (даже у какого-нибудь лиспа — backquote синтаксис, например)

А так, хорошая статья, жду продолжения. Интересно было бы про GLR подробно почитать — информации про них вообще очень мало в интернете, а на русском вообще ноль.
Таки с чего вы решили, что LL(k) сводимо к LL(1)?
Насчет матчасти — тоже довольно странный вывод. Нет, разумеется, можно все тупо зазубрить и писать программу, толком не понимая, что и почему, но «это не наш метод» (с). Лучше один раз понять, чем 10 раз запомнить (а мы все прекрасно помним, что запомненное без понимания выветривается из памяти весьма быстро).

Про лексеры пожалуй соглашусь. Но, пожалуй, они войдут в следующую статью цикла.
Насчет контекстно-зависимых — дааа? Сам я на лиспе не программирую, но, вроде бы, вот это: cuiwww.unige.ch/isi/bnf/LISP/BNFlisp.html Бнф-грамматика для Lisp.
Грамматика для того же питона так же в открытом доступе и, как я понимаю, используется при компиляции языка. Да и вообще, почти все ЯП неплохо укладываются в БНФ (иначе были бы проблемы с парсингом и компиляцией)

Про продолжение — если не будет других запросов, следующая статья будет обзорно именно по АЛГОРИТМАМ парсинга, ну, плюс, о лексерах. Основное — идеи, лежащие в основе каждого алгоритма. Если кому-то будет интересна математика, это уже отдельно.

Еще, не соглашусь с вашим призывом переписывать велосипед. Не нужно это, скорее даже вредно. Вроде бы есть (планирую попробовать чуть позже) разные «оптимизированные» парсеры общего назначения. Наверняка, там много своих ограничений, но тем не менее. И вероятность того, что ваш велосипед будет лучше я оцениваю как весьма низкую. Другое дело, если на вашем любимом ЯП нормальной библиотеки нет. Тогда да, вперед и с песней. И лучше с результатами на гитхабе, чтобы следующему не пришлось повторять.
Таки с чего вы решили, что LL(k) сводимо к LL(1)?

Да практически из определения. Сводится оно с помощью левой факторизации.
www.egtry.com/compiler/ll/left_factoring

cuiwww.unige.ch/isi/bnf/LISP/BNFlisp.html Бнф-грамматика для Lisp.

Нет, это оооочень упрощенная грамматика простейших S-выражений, а не какого-либо из лиспов :)

Грамматика для того же питона так же в открытом доступе и, как я понимаю, используется при компиляции языка.

trevorjim.com/python-is-not-context-free
Вкратце, у Питона лексер на себя слишком много берет. В целом, у него КЗ-грамматика.

Да и вообще, почти все ЯП неплохо укладываются в БНФ (иначе были бы проблемы с парсингом и компиляцией)

Дык и есть проблемы :) И их руками и решают.

Вроде бы есть (планирую попробовать чуть позже) разные «оптимизированные» парсеры общего назначения.

Если знать матчасть, то написать руками простейший парсер куда проще, чем бодаться с генераторами вроде ANTLR/etc, что вы вобщем-то, неплохо показали в своей статье :)
Спорить не буду, не математик. Возможно, да, возможно, есть какие-то нюансы.
По поводу трудности освоения инструментов — даже спорить не буду. НО. Лучше освоить инструмент, чем писать каждый раз велосипед, это моё ИМХО. Если у вас это вызывает сомнение, значит просто инструмент ненадлежащего качества. Тогда стоит написать ИНСТРУМЕНТ лучше. А не переписывать всякий раз с нуля :)
По поводу оптимизаций я имел в виду не ANTLR, а что-то наподобие ragel или re2c. То есть инструмент, оптимизирующий саму работу с КА при парсинге, за счет чего и сам парсинг будет быстрее.
Только что скачал со ссылки и открыл. Может быть, вы просто не установили djvu-viewer?
и ПДФ тоже, а какого размера книжки? у меня они закачались по 35к плус-минус все. Заранее спасибо
03 Lexical Analysis.pdf — 52k, качается, открывается
Ахо, часть 1, djvu 6.2 мб -//-
перекачал, работает
tnx
У него чуть отличается формат, поэтому двойные кавычки заменим на одинарные и чуть перепишем регулярное выражение, а так же добавим обозначение для WS, который в предыдущем инструменте задавался по умолчанию.

Некорректно называть лексемы регулярными выражениями.


Левую рекурсию в нашем случае можно устранить просто переписав на правую.

В ANTLR 4 поддерживается левая и правая рекурсия одновременно:


expr
    : expr '+' expr
    | Id
    ;

В ANTLR есть правила парсера и грамматические правила.

Правила парсера и лексера (или токенайзера).


В частности, в правилах парсинга нет регулярных выражений.

Опять регулярные выражения. Их нигде нет, а в парсере тоже можно использовать повторение, отрицание: a*, ~a. В том числе не жадное: .+?.


так же поддерживает инлайн функции (пусть и несколько в ином формате)

Не только функции. Это вставки произвольного кода.


Как видно, ассоциативность здесь “правая”. А операции сложения-вычитания, умножения-деления — левые. Я честно пытался несколько дней (sic!) найти решение (разумеется, я занимался этим не все время, но в сумме убил на это часов 12-15). Маркеры ассоциативности, кучи мануалов, переформулирование грамматики…. Не получилось. Я уверен, что решение есть. Более того, пример грамматики калькулятора есть здесь. Но я хотел найти своё решение, по возможности, в терминах общей грамматики. В конце концов, целью было НАУЧИТЬСЯ, а не решить задачу.

Элементарно же. Что значит общая грамматика?


grammar calc;

stmt : term (addop term)*;
term : factor (mulop factor)*;
factor : '(' stmt ')' | NUMBER;

addop : '+' | '-';
mulop : '*'|'/'; 
NUMBER: [0-9]+|[0-9]+.[0-9]+;
WS : [ \t\r\n]+ -> skip ;

Но почему бы не изучить возможности инструмента и сразу не использовать левую рекурсию, с помощью которой запись получится лаконичней, а скорость работы сгенерированных парсеров — выше. Маркеры ассоциативности вообще только для левой рекурсии используются.


grammar calc;

stmt
    : stmt mulop stmp
    | stmt addop stmt
    | '(' stmt ')'
    | NUMBER
    ;

addop : '+' | '-';
mulop : '*'|'/'; 
NUMBER: [0-9]+|[0-9]+.[0-9]+;
WS : [ \t\r\n]+ -> skip ;

И я признаю свою неудачу. Да, задача решаема. Но пользуясь только документацией и поиском на общие темы, мне её решить не удалось. Причины… Во-первых, исключая книгу по ANTLR, доступные в сети источники не отличаются подробностью и выразительностью. Во-вторых, в сети масса материалов по разным (не совместимым) версиям ANTLR. Нет, я все понимаю, развитие и прочее.

Куча разжеванного материала по ANTLR. Не понимаю, что вам не удалось найти. Вот например материал на уровень от новичков до профессионалов: The ANTLR mega tutorial. Моя статья, которая включает и практику: Теория и практика парсинга исходников с помощью ANTLR и Roslyn.


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

О какой обратной совместимости идет речь? По-моему автор наоборот слишком консервативен и не вводит новые фичи.

Спасибо за содержательный коментарий.
Моё знакомство с ANTLR было знакомством нуба. С точки зрения такого нуба, для таких же нубов.
Соответственно, я попытался с ним познакомиться с налета, используя доки с гитхаба, с сайта, поиск по интересующим темам (конкретным, вроде, как обойти левую рекурсию) в интернете. Набредал на пдф-ки и несколько вопросов на stackoverflow. Оттуда же и сомнения в обратной совместимости, люди обсуждали список ключей парсера v2 и v3 и им было грустно.
Мануалы как таковые серьезно не искал, каюсь, наверное стоило. Вообще, идея была — программист берет абсолютно незнакомый инструмент, разбирается за пару часов, пишет работающий код. С этой точки зрения мне ANTLR не зашел. Вполне вероятно, я сам себе злобный буратино, однако, подозреваю, описанный мной сценарий — то, к чему будет стремиться среднестатистический программист, столкнувшись с подобной задачей.
Естественно, для того, чьё знакомство с инструментом заметно глубже мои слова напоминают детский лепет, но мой опыт с этим инструментом показал [мне], что он имеет несколько более высокий порог вхождения, чем я предполагал. Только и всего. Мне этого вывода было достаточно.
Оттуда же и сомнения в обратной совместимости, люди обсуждали список ключей парсера v2 и v3 и им было грустно.

Ну так на это и мажорные версии, что в них может не быть обратной совместимости. В перспективе нужно от нее отказываться, чтобы инструмент не захламлялся. В ANTLR 4 очень лаконичные грамматики получается. Если бы еще универсальные вставки кода, то не было бы цены...

Для полноты статьи возможно стоило указать готовые парсеры для некоторых типов текста, такие как MS IE в варианте ActiveX для разбора HTML (часто использую) и консольных утилит universal-ctags|ctags|etags для множества языков программирования (недавно ознакомился).
Понимаю, что основной упор у вас идет на объяснение принципа грамматик, но для кого-то готовый инструмент нужен уже сейчас.

Sign up to leave a comment.

Articles