Comments 24
Возможно, заморочусь и сделаю сравнение для парсеров «нативных», на регулярках и generic-ов (LL/LR/PEG) для чего-нибудь популярного, наподобие json. Брут-форсы писать не буду, ибо лень, разве что чей-нибудь найду для копи-паста :). Действительно, любопытно посмотреть динамику, в зависимости от размера файла (и, возможно, от сложности структуры).
Can't load calc as lexer or parser
Версия ANTLR ровно по указанному URL.
2. По поводу ассоциативности — Вы не пробовали вместо
stmt: term | term addop stmt;
написать
stmt: term | stmt addop term;
?
по документации — ANTLR спокойно отрабатывает такую левую рекурсию.
Я правильно понимаю что конвертацию в другие форматы мы должны делать в listener'ах?
Также, имхо, нужно было бы упомянуть, что до стадии парсера, желательно иметь стадию лексера (которую можно и на регулярках заимплементить) — оно такое дело значительно всё упрощает. Кроме PEG, возможно, в случае реализации в виде packrat-парсера.
Ну и кстати, в случае реальных языков программирования, один хрен придется почти всё руками делать — почти у всех языков грамматики контекстно-зависимые. (даже у какого-нибудь лиспа — backquote синтаксис, например)
А так, хорошая статья, жду продолжения. Интересно было бы про GLR подробно почитать — информации про них вообще очень мало в интернете, а на русском вообще ноль.
Насчет матчасти — тоже довольно странный вывод. Нет, разумеется, можно все тупо зазубрить и писать программу, толком не понимая, что и почему, но «это не наш метод» (с). Лучше один раз понять, чем 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. То есть инструмент, оптимизирующий саму работу с КА при парсинге, за счет чего и сам парсинг будет быстрее.
У него чуть отличается формат, поэтому двойные кавычки заменим на одинарные и чуть перепишем регулярное выражение, а так же добавим обозначение для 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 для множества языков программирования (недавно ознакомился).
Понимаю, что основной упор у вас идет на объяснение принципа грамматик, но для кого-то готовый инструмент нужен уже сейчас.
Парсеры, обработка текста. Просто о сложном. CFG, BNF, LL(k), LR(k), PEG и другие страшные слова