Наверное, каждому программисту приходилось сталкиваться с задачами вида «прочитать что-то в формате А и произвести с ним некие манипуляции». Будь то json, логи nginx, cfg, sql, yaml, csv или что-то еще. Хорошо, когда можно воспользоваться библиотекой, однако, по разным причинам, это удается не всегда. Тогда и встает вопрос создания собственного парсера для заданного формата. И это, как говорят англичане, часто оказывается PITA (болью в ...). В этой статье я постараюсь облегчить эту боль. Кому интересно, добро пожаловать.

Введение

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

Сразу оговорюсь, тема сама по себе мало того, что ОЧЕНЬ непростая, так еще и до невозможности обширная и все охватить в рамках одной статьи просто не получится. Поэтому я начну от общего и буду переходить к частному, конкретно в этой статье давая скорее обзор инструментария (который, однако, может использоваться для решения вполне конкретных задач парсинга), чем погружаться вглубь концепций. Возможно, если читатели будут заинтересованы, статья превратится в цикл, в котором я могу раскрыть какие-то конкретные вопросы более подробно.

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

Крепитесь, статья большая, некоторые места будут не очень интересными, но без них может быть непонятно.

Основные понятия

Перед разговором по теме стоит определиться с основными понятиями, чтобы не было разночтений. Это глоссарий данной статьи. Он может совпадать с общепринятой терминологией, но вообще говоря, не обязан, поскольку показывает картину, формирующуюся в голове автора.
Итак:

• входной символьный поток (далее входной поток или поток) — поток символов для разбора, подаваемый на вход парсера
• parser/парсер (разборщик, анализатор) — программа, принимающая входной поток и преобразующая его в AST и/или позволяющая привязать исполняемые функции к элементам грамматики
• AST(Abstract Syntax Tree)/АСД(Абстрактное синтаксическое дерево) (выходная структура данных) — Структура объектов, представляющая иерархию нетерминальных сущностей грамматики разбираемого потока и составляющих их терминалов. Например, алгебраический поток (1 + 2) + 3 можно представить в виде ВЫРАЖЕНИЕ(ВЫРАЖЕНИЕ(ЧИСЛО(1) ОПЕРАТОР(+) ЧИСЛО(2)) ОПЕРАТОР(+) ЧИСЛО(3)). Как правило, потом это дерево как-то обрабатывается клиентом парсера для получения результатов (например, подсчета ответа данного выражения)
• CFG(Context-free grammar)/КСГ(Контекстно-свободная грамматика) — вид наиболее распространенной грамматики, используемый для описания входящего потока символов для парсера (не только для этого, разумеется). Характеризуется тем, что использование её правил не зависит от контекста (что не исключает того, что она в некотором роде задает себе контекст сама, например правило для вызова функции не будет иметь значения, если находится внутри фрагмента потока, описываемого правилом комментария). Состоит из правил продукции, заданных для терминальных и не терминальных символов.
• Терминальные символы (терминалы) — для заданного языка разбора — набор всех (атомарных) символов, которые могут встречаться во входящем потоке
• Не терминальные символы (не терминалы) — для заданного языка разбора — набор всех символов, не встречающихся во входном потоке, но участвующих в правилах грамматики.
• язык разбора (в большинстве случаев будет КСЯ(контекстно-свободный язык)) — совокупность всех терминальных и не терминальных символов, а также КСГ для данного входного потока. Для примера, в естественных языках терминальными символами будут все буквы, цифры и знаки препинания, используемые языком, не терминалами будут слова и предложения (и другие конструкции, вроде подлежащего, сказуемого, глаголов, наречий и т.п.), а грамматикой собственно грамматика языка.
• BNF(Backus-Naur Form, Backus normal form)/БНФ(Бэкуса-Наура форма) — форма, в которой одни синтаксические категории последовательно определяются через другие. Форма представления КСГ, часто используемая непосредственно для задания входа парсеру. Характеризуется тем, что определяемым является всегда ОДИН нетерминальный символ. Классической является форма записи вида:
  <определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>
  Так же существует ряд разновидностей, таких как ABNF(AugmentedBNF), EBNF(ExtendedBNF) и др. В общем, эти формы несколько расширяют синтаксис обычной записи BNF.
• LL(k), LR(k), SLR,... — виды алгоритмов парсеров. В этой статье мы не будем подробно на них останавливаться, если кого-то заинтересовало, внизу я дам несколько ссылок на материал, из которого можно о них узнать. Однако остановимся подробнее на другом аспекте, на грамматиках парсеров. Грамматика LL/LR групп парсеров является BNF, это верно. Но верно также, что не всякая грамматика BNF является также LL(k) или LR(k). Да и вообще, что значит буква k в записи LL/LR(k)? Она означает, что для разбора грамматики требуется заглянуть вперед максимум на k терминальных символов по потоку. То есть для разбора (0) грамматики требуется знать только текущий символ. Для (1) — требуется знать текущий и 1 следующий символ. Для (2) — текущий и 2 следующих и т.д. Немного подробнее о выборе/составлении BNF для конкретного парсера поговорим ниже.
• PEG(Parsing expression grammar)/РВ-грамматика — грамматика, созданная для распознавания строк в языке. Примером такой грамматики для алгебраических действий +, -, *, / для неотрицательных чисел является:
  Value < [0-9]+ / '(' Expr ')'
Product < Value (('*' / '/') Value)*
Sum < Product (('+' / '-') Product)*
Expr < Sum

И наконец мы закончили с основными понятиями. Перейдем к выбору способа разбора.

Варианты разбора

Когда мы сталкиваемся с задачей создания парсера, решение сводится, как правило, к 4 основным вариантам:

• Решать задачу в лоб, то есть анализировать посимвольно входящий поток и используя правила грамматики, строить АСД или сразу выполнять нужные нам операции над нужными нам компонентами. Из плюсов — этот вариант наиболее прост, если говорить об алгоритмике и наличии математической базы. Минусы — вероятность случайной ошибки близка к максимальной, поскольку у вас нет никаких формальных критериев того, все ли правила грамматики вы учли при построении парсера. Очень трудоёмкий. В общем случае, не слишком легко модифицируемый и не очень гибкий, особенно, если вы не имплементировали построение АСД. Даже при длительной работе парсера вы не можете быть уверены, что он работает абсолютно корректно. Из плюс-минусов. В этом варианте все зависит от прямоты ваших рук. Рассказывать об этом варианте подробно мы не будем.
• Используем регулярные выражения! Я не буду сейчас шутить на тему количества проблем и регулярных выражений, но в целом, способ хотя и доступный, но не слишком хороший. В случае сложной грамматики работа с регулярками превратится в ад кромешный, особенно если вы попытаетесь оптимизировать правила для увеличения скорости работы. В общем, если вы выбрали этот способ, мне остается только пожелать вам удачи. Регулярные выражения не для парсинга! И пусть меня не уверяют в обратном. Они предназначены для поиска и замены. Попытка использовать их для других вещей неизбежно оборачивается потерями. С ними мы либо существенно замедляем разбор, проходя по строке много раз, либо теряем мозговые клеточки, пытаясь измыслить способ удалить гланды через задний проход. Возможно, ситуацию чуть улучшит попытка скрестить этот способ с предыдущим. Возможно, нет. В общем, плюсы почти аналогичны прошлому варианту. Только еще нужно знание регулярных выражений, причем желательно не только знать как ими пользоваться, но и иметь представление, насколько быстро работает вариант, который вы используете. Из минусов тоже примерно то же, что и в предыдущем варианте, разве что менее трудоёмко.
• Воспользуемся кучей инструментов для парсинга BNF! Вот этот вариант уже более интересный. Во-первых, нам предлагается вариант типа lex-yacc или flex-bison, во вторых во многих языках можно найти нативные библиотеки для парсинга BNF. Ключевыми словами для поиска можно взять LL, LR, BNF. Смысл в том, что все они в какой-то форме принимают на вход вариацию BNF, а LL, LR, SLR и прочее — это конкретные алгоритмы, по которым работает парсер. Чаще всего конечному пользователю не особенно интересно, какой именно алгоритм использован, хотя они имеют определенные ограничения разбора грамматики (остановимся подробнее ниже) и могут иметь разное время работы (хотя большинство заявляют O(L), где L — длина потока символов). Из плюсов — стабильный инструментарий, внятная форма записи (БНФ), адекватные оценки времени работы и наличие записи БНФ для большинства современных языков (при желании можно найти для sql, python, json, cfg, yaml, html, csv и многих других). Из минусов — не всегда очевидный и удобный интерфейс инструментов, возможно, придется что-то написать на незнакомом вам ЯП, особенности понимания грамматики разными инструментами.
• Воспользуемся инструментами для парсинга PEG! Это тоже интересный вариант, плюс, здесь несколько побогаче с библиотеками, хотя они, как правило, уже несколько другой эпохи (PEG предложен Брайаном Фордом в 2004, в то время как корни BNF тянутся в 1980-е), то есть заметно моложе и хуже выглажены и проживают в основном на github. Из плюсов — быстро, просто, часто — нативно. Из минусов — сильно зависите от реализации. Пессимистичная оценка для PEG по спецификации вроде бы O(exp(L)) (другое дело, для создания такой грамматики придется сильно постараться). Сильно зависите от наличия/отсутствия библиотеки. Почему-то многие создатели библиотек PEG считают достаточными операции токенизации и поиска/замены, и никакого вам AST и даже привязки функций к элементам грамматики. Но в целом, тема перспективная.

Решаем задачу парсинга

Пойдем по-порядку, варианты brute-force и regexp пропускаем.

BNF

Вот и настало время чуть подробнее остановиться на алгоритмах разборщика, вернее на используемых ими грамматиках. Итак, наиболее часто встречаются GLR (до O(L^3) или до O(L^4), как говорят некоторые источники (antlr)), LR, LALR и LL — все в пределах O(L). Наибольшей “прожорливостью” обладает GLR — она способна лучше обрабатывать неоднозначности грамматики, но за счет этого и более медленна. То есть если рассматривать “размер” класса обрабатываемых парсером грамматик(назовем его мощностью парсера), то при прочих равных, мощности распределятся так GLR > LR > LALR > SLR > LL. Потребление ресурсов, соответственно, близко к обратному. Но вернемся к грамматикам.

Составление или поиск грамматики для LR-парсера в целом достаточно просто и высок шанс, что составленный вами “на коленке” BNF будет спокойно воспринят парсером и обработан. Главное, грамматика должна быть полной, то есть описывать все возможные ситуации входного потока, кроме того попробуйте сами понять навскидку, можно ли зная k следующих символов (в зависимости от выбранного LR-парсера) однозначно определить, какое именно правило должно применяться.

Для LR-парсера могут возникать конфликты следующего вида:

1. Перенос-свертка (shift-reduce): NT ::= x NT | x. Где длина x > k. Решается так: NT ::= xK; K ::= K | e
2. Свертка-свертка (reduce-reduce):
   NT :: = e
A ::= NT
B ::= NT
D ::= B u v | A u w, где длина u > k
   Решается так:
   R ::= Au
J ::= Bu
D ::= Rw | Jv
   

Для LL-парсера характерны конфликты вида (необходимо, но не достаточно, их переформулировать, по запросу могу остановиться на LL(k) грамматиках подробнее в следующей статье):

Левая рекурсия: NT ::= NT x | y, где x, y — произвольные строки терминалов/не терминалов, но y не начинается с NT

Пример: E ::= E + T | T. Можно переформулировать, как:

E ::= T Z
Z ::= ‘+’ TZ | x

Левая факторизация: NT ::= ax | ay, где a — строка длины > k нашего парсера. Решается еще проще: NT ::= aC; C = x|y

Итак, что мы будем решать?

Ну, допустим, это будет простой калькулятор:

OPERATOR        ::= "+ "| "-" | "*" | "/"
    STMT            ::= "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT
    FLOAT           ::= INT "." INT
    INT             ::= (POSITIVE_DIGIT INT | DIGIT ) | DIGIT
    POSITIVE_DIGIT  ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
    DIGIT           ::= POSITIVE_DIGIT | "0"

Если читатель попробует найти грамматику калькулятора в интернете, он увидит что часто операции сложения/вычитания и умножения/деления обрабатываются разными грамматическими конструкциями. Это сделано специально, чтобы учесть в грамматике такой момент, как приоритет операций (а также раскрыть неоднозначности грамматики). Мы это сделаем дальше по ходу статьи.

Пробуем найти нативное Python-решение, находим их много.

1. Используем parglare. Это библиотека/cli-tool на Python, реализующий LR/GLR парсер c достаточно широким спектром возможностей (инлайн-функции, приоритизация, деревья, внятный анализ грамматики, визуализатор КА, получающегося при обработке грамматики).
   
   

   pip install parglare

   
   Переформулируем наш калькулятор так, как просит parglare
   
   

   OPERATOR        : "+ "| "-" | "*" | "/" | =
       STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT
       FLOAT           : INT "." INT
       INT             : (POSITIVE_DIGIT INT | DIGIT ) | DIGIT
       POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
       DIGIT           : POSITIVE_DIGIT | "0"

   
   Достаточно? Сохраним в calc.pg и воспользуемся cli-tool
   
   

   pglr --debug check calc.pg
   Error in file "/home/survivor/tests/calc.pg" at position 1,42 => "" | "/" | *=\nSTMT    ". Expected: Name or StrTerm or RegExTerm
   

   
   Упс! кажется, что-то лишнее. Бинго! я зачем-то вставил | = после “/” (нет, я-то знаю, откуда он там (но к теме статьи это не относится) ). Главное в том, что программа нам четко на это указала. Далее после исправления программа поругается еще на отсутствие; в конце обозначения нетерминала и на скобочку в правиле INT. Переформулированный вариант будет выглядеть так:
   
   

   STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT;
   OPERATOR        : "+ "| "-" | "*" | "/";
   FLOAT           : INT "." INT;
   INT             : POSITIVE_DIGIT INT | POSITIVE_DIGIT DIGIT | DIGIT;
   POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";
   DIGIT           : POSITIVE_DIGIT | "0";

   
   В итоге, pglr все нравится и он нам скажет:
   
   

   Grammar ok! 

   
   НО:
   
   

   There are 4 Shift/Reduce conflicts.
   Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.
   There are 7 Reduce/Reduce conflicts.
   Try to resolve manually or use GLR parsing.
   

   
   Ну, а выше по выводу debug можно прочитать их красивое (и понятное) описание. Ну что ж, давайте подумаем. Во первых, давайте не будем самыми умными и выкинем нафиг positive_digit. Если кто-то напишет 0034 — во первых, он сам себе злобный буратино, а во вторых, большинство ЯП, в том числе Python при конвертации этого в число не скажут нам ничего и просто выдадут 34. Прекрасно, это сильно поможет. Во-вторых, нафиг отсюда разделение на int/float, для простоты предположим что все числа с плавающей точкой. Также, pglr понимает регулярные выражения в BNF, воспользуемся этим. Получим:
   
   

    STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT;
   OPERATOR        : "+ "| "-" | "*" | "/";
   FLOAT           : /\d+(\.\d+)?/;

   
   и по-прежнему
   
   

   There are 4 Shift/Reduce conflicts.
   Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.

   
   Ну, как бы то ни было, грамматика
   
   

   *** GRAMMAR ***
   Terminals:
   +  EOF ) ( FLOAT STOP * / - \d+(\.\d+)? EMPTY
   NonTerminals:
   OPERATOR S' STMT
   Productions:
   0: S' = STMT STOP
   1: STMT = STMT OPERATOR STMT
   2: STMT = ( STMT )
   3: STMT = FLOAT
   4: OPERATOR = + 
   5: OPERATOR = -
   6: OPERATOR = *
   7: OPERATOR = /

   
   Попробуем реально распарсить что-нибудь.
   
   

   from parglare import Grammar
   from parglare import Parser
   
   grammar = Grammar.from_file(‘calc.pg’)
   parser = Parser(grammar, build_tree=True, prefer_shifts=True)
   result = parser.parse('1 + 2 / (3 - 1 + 5)')

   
   Получаем:
   
   

   result
   <NonTerm(start=0, end=19, sym=STMT)>

   
   можем получить result.children и далее по дереву. Можем заодно подсчитать итоговое выражение, но делать это здесь не будем. Важно, что мы получили доступ к дереву объектов, для терминальных символов так же их “значение” и можем делать с этим все, что пожелаем.
   
   Если мы хотим поправить конфликтные ситуации, как еще можно разрешить конфликты грамматики?
   
   Есть несколько вариантов:
   
   
   • Решить задачу переформулировав грамматику
     Например, так:
     
     

     STMT : TERM | STMT ADDOP TERM ;
     TERM : FACTOR | FACTOR MULOP FACTOR ;
     FACTOR : "(" STMT ")" | NUMBER;
     ADDOP : "+" | "-";
     MULOP : "*"|"/"; 
     NUMBER: /\d+(\.\d+)?/;

     
     Как видим, задача усложнилась, но не слишком. Тем более, если мы будем делать разбор именно такого дерева, нам будет проще.
   • Использовать средства самого parglare
     
     В этом случае решение более частное, но в ряде случаев более удобное. Parglare предоставляет хороший инструментарий для приоритезации правил, к примеру, для арифметических выражений можно выставить приоритет операции и ассоциативность (с какой стороны выполняется данная операция — слева направо или справа налево) чем приоритет выше, тем операция выполнится раньше (относительно остальных), к примеру, наша грамматика в такой нотации может выглядеть вот так:
     
     

     STMT :  STMT ADDOP STMT {1, left}
     	|  STMT MULOP STMT {2, left}
     | "(" STMT ")" | NUMBER;
     ADDOP : "+" | "-";
     MULOP : "*"|"/"; 
     NUMBER: /\d+(\.\d+)?/;

     
     Парсится, но работает не правильно. Например, для
     
     1 + 2 / (3 - 1 + 5)
     
     получаем (при не-древовидном парсинге)
     
     

     ['1', u'+', ['2', u'/', [u'(', ['3', u'-', ['1', u'+', '5']], u')']]]

     
     что, очевидно, не соответствует ожидаемому результату:
     
     

     ['1', u'+', ['2', u'/', [u'(', [['3', u'-', '1'], u'+', '5'], u')']]]

     
     
   
   Мораль — лучше использовать стандартные описанные в BNF моменты. Блестящие и прикольные штуки блестят и прикольны, но не всегда работают. Или я не умею их готовить. А большинство библиотек парсинга — имеют версию alpha | beta.
   
   По словам автора об этом баге, он происходит из-за того, что, по сути своей, ассоциативность (left) парсера на уровне алгоритма означает — предпочитать reduce, а не shift. То есть, по сути, если есть возможность “обрубить” правило, или продолжить в его рамках — лучше обрубить. Поскольку парсинг идет слева направо, это и означает левую ассоциативность. Причина же ошибки в том, что не определена приоритетность для правил внутри ADDOP/MULOP, что ломает все правило.
   
   Однако, даже если мы зададим приоритетность (например:
   
   ADDOP: “+” {1}
| “-” {1}), работать все равно не будет, уже из-за другой ошибки.
   
   Напоследок пример с инлайн-функциями, привязываемыми непосредственно к правилам, из документации parglare.
   
   

   from parglare import Parser, Grammar
   
   grammar = r"""
   E: E '+' E  {left, 1}
   | E '-' E  {left, 1}
   | E '*' E  {left, 2}
   | E '/' E  {left, 2}
   | E '^' E  {right, 3}
   | '(' E ')'
   | number;
   number: /\d+(\.\d+)?/;
   """
   
   # Define inline functions bound to grammar rule
   actions = {
       "E": [lambda _, nodes: nodes[0] + nodes[2], # for rule[0]  “+”
             lambda _, nodes: nodes[0] - nodes[2], # for rule[1]  “-”
             lambda _, nodes: nodes[0] * nodes[2], # for rule[2]  “*”
             lambda _, nodes: nodes[0] / nodes[2], # for rule[3]  “/”
             lambda _, nodes: nodes[0] ** nodes[2], # for rule[4]  “^”
             lambda _, nodes: nodes[1], # for rule[5]  “()” - just get the middle
             lambda _, nodes: nodes[0]],  # for rule[6]  just get node
       "number": lambda _, value: float(value), # for rule - convert to float
   }
   
   g = Grammar.from_string(grammar)
   parser = Parser(g, debug=True, actions=actions)
   
   result = parser.parse("34 + 4.6 / 2 * 4^2^2 + 78")
   
   print("Result = ", result)
   
   # Output
   # -- Debuging/tracing output with detailed info about grammar, productions,
   # -- terminals and nonterminals, DFA states, parsing progress,
   # -- and at the end of the output:
   # Result = 700.8

   
   
2. Дальше попробуем standalone-инструмент ANTLR.
   
   Установка довольно простая, для linux это
   
   

   $ cd /usr/local/lib
   $ curl -O http://www.antlr.org/download/antlr-4.7.1-complete.jar
   $ export CLASSPATH=".:/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH"
   $ alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
   $ alias grun='java org.antlr.v4.gui.TestRig'

   
   Для того, чтобы работать на python2, нужно еще доустановить
   
   

   pip install antlr4-python2-runtime

   
   Дальше попробуем сделать для него грамматику. У него чуть отличается формат, поэтому двойные кавычки заменим на одинарные и чуть перепишем регулярное выражение, а так же добавим обозначение для WS, который в предыдущем инструменте задавался по умолчанию. Левую рекурсию в нашем случае можно устранить просто переписав на правую.
   
   Важный момент! В ANTLR есть правила парсера и грамматические правила. К появлению узла в результирующем AST ведут правила парсинга. Кроме того, существует некоторое различие, что можно/нельзя в грамматических/правилах парсинга. В частности, в правилах парсинга нет регулярных выражений. Кроме того, парсер должен получить входное правило, стартовый нетерминал (вообще, все несколько сложнее, но в нашем случае вполне хватает и этого). Вообще, стоит заметить, что ANTLR имеет довольно мощный синтаксис, так же поддерживает инлайн функции (пусть и несколько в ином формате) и “не попадающие в дерево” нетерминалы и кое-что еще. В итоге, наша грамматика выглядит так:
   
   

   grammar calc;
   stmt : term | term addop stmt ;
   term : factor | factor mulop factor ;
   factor : '(' stmt ')' | NUMBER;
   addop : '+' | '-';
   mulop : '*'|'/'; 
   NUMBER: [0-9]+|[0-9]+.[0-9]+;
   WS : [ \t\r\n]+ -> skip ;

   
   Файл при этом называется calc.g4 (Это важно! название файла должно совпадать с названием грамматики внутри).
   
   Создадим java-парсер.
   
   

   antlr4 calc.g4
   javac calc*.java
   grun calc stmt -gui

   
   Дальше даем ему какой-то инпут (например, 1 + 2 / (3 - 1 + 5)) и нажимаем конец строки (ctrl-d на *nix, ctrl-z на windows) и смотрим на результат. Нам показали красивое дерево разбора, еще и интерактивное. Можно посмотреть, покрутить узлы, подумать, экспортировать в качестве картинки.
   
   Создадим python2-парсер:
   
   

   antlr4 -Dlanguage=Python2 calc.g4

   
   
   Далее, мы можем навесить на грамматику листенеры и наслаждаться.
   
   

   import sys
   from antlr4 import *
   from calc_bakLexer import calc_bakLexer
   from calc_bakListener import calc_bakListener
   from calc_bakParser import calc_bakParser
   
   
   class StmtPrinter(calc_bakListener):
       def __init__(self):
           self.map_results = {}
           self.result = 0
   
       def exitStmt(self, ctx):
           print("Oh, a stmt! {}".format(ctx.getText()))
   
   
   
   def main(argv):
       input = FileStream(argv[1])
       print(input)
       lexer = calc_bakLexer(input)
       stream = CommonTokenStream(lexer)
       parser = calc_bakParser(stream)
       tree = parser.stmt()
       printer = StmtPrinter()
       walker = ParseTreeWalker()
       walker.walk(printer, tree)
   
   if __name__ == '__main__':
       main(sys.argv)

   
   … Наслаждаться неправильно работающей программой. Вернее, правильно, но неожиданно.
   
   

   python ./calc_antlr_min.py ./example.antlr 
   1 + 2 / (3 - 1 + 5)
   
   Oh, a stmt! 5
   Oh, a stmt! 1+5
   Oh, a stmt! 3-1+5
   Oh, a stmt! 2/(3-1+5)
   Oh, a stmt! 1+2/(3-1+5)
   

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

   Update

   
   Как верно замечено, одна голова хорошо, а две лучше.
   Переформулирование грамматики с право-ассоциативной на левую выполняется буквально «щелчком пальцев» (Спасибо Valentin Nechayev netch80 за дополнение) — нужно всего лишь заменить
   

   stmt : term | term addop stmt ;
   

   
   на
   

   stmt : term | stmt addop term ;
   

   
   Левую рекурсию в данном случае ANTLR обрабатывает без вопросов (видимо, благодаря каким-то оптимизациям). Вывод простых листенеров в этом случае
   

   python ./calc_antlr_min.py ./example.antlr 
   1 + 2 / (3 - 1 + 5)
   
   Oh, a stmt! 1
   Oh, a stmt! 3
   Oh, a stmt! 3-1
   Oh, a stmt! 3-1+5
   Oh, a stmt! 1+2/(3-1+5)

   
   
   

PEG

По сути, являются упрощенной формой BNF, но знать об этом программисту, в целом, не обязательно. В отличие от BNF, изначально больше похожи на регулярные выражения. По сути, можно было бы сказать, что это BNF с возможностью использовать регулярные выражения “по стандарту” (причем, что приятно, не только внутри нетерминальной строки, но и в некоторой степени в самом выражении (PEG поддерживает конструкции вида A = B ( X C)* или, к примеру Z = R (K)?, читаемые как “A состоит из B и любого количества повторений X и C, стоящих последовательно” и “Z состоит из R и следующего за ним K 0 или 1 раз”). Но, на мой взгляд, это все же не главное. Главное в том, что PEG изначально спроектирован, как грамматики ПАРСЕРА. А с какой главной проблемой сталкиваются парсеры, в том числе BNF? Неоднозначность выбора! Для решения этой проблемы в PEG присутствует замечательный оператор последовательного или “/”. В отличие от оператора “|”, который описывает равнозначные альтернативы, “/” четко указывает порядок разрешения правила. Например, A / B / C / D указывает: сравнить с A, если не подходит, сравнить с B, если не подходит, сравнить с C и т.д. По этой причине, оперирование PEG-грамматиками ПРОЩЕ. И еще, рекомендация — если вам безразличен порядок выполнения сравнения, лучше писать “/”. Это уменьшит количество неоднозначных для парсера ситуаций. Однако, как и с любым инструментом, с этим следует обращаться с осторожностью.
Еще, будьте внимательны, создатели PEG-парсеров ещё более подвержены желанию понимать стандарт так, как им хочется, поэтому лексика разных реализаций может существенно различаться.

Итак, перейдем к практике.

Используем Arpeggio от автора parglare:

pip install arpeggio

Дальше разбираемся с документацией и узнаем, что рекомендованным для работы с AST для этой библиотеки является шаблон посетитель (visitor), весьма похожий на рекомендованный в ANTLR слушатель (listener). К счастью, здесь для всего эксперимента мне хватило часа, все оказалось не сложно:

from arpeggio.cleanpeg import ParserPEG
from arpeggio import PTNodeVisitor, EOF, visit_parse_tree
# Setting up our simple grammar
calc_grammar = """
number = r'\d+(\.\d+)?'
factor = number / "(" stmt ")"
term = factor (mulop factor)*
stmt = term (addop term)*
addop = "+" / "-"
mulop = "*" / "/"
calc = stmt EOF
"""

#Creating a visitor class to calculate the result
class CalcVisitor(PTNodeVisitor):

    def visit_number(self, node, children):
        return float(node.value)

    def visit_factor(self, node, children):
        # Children are list-like structure of VISITED node results
        # visits are made from depth to top
        return children[0]

    def visit_term(self, node, children):
        # For such rules you may use, for example children["factor"]
        # Though, you need to know, that children["factor"] is a list of ALL
        # factor's of this term
        if len(children) == 1:
            return children[0]
        else:
            res = children[0]
            for i in xrange(len(children) / 2):
                if children[2 * i + 1] == '*':
                    res *= children[2 * (i + 1)]
                else:
                    res /= children[2 * (i + 1)]
            return res

    def visit_stmt(self, node, children):
        if len(children) == 1:
            return children[0]
        else:
            res = children[0]
            for i in xrange(len(children) / 2):
                if children[2 * i + 1] == '+':
                    res += children[2 * (i + 1)]
                else:
                    res -= children[2 * (i + 1)]
            return res

# Don’t forget about root rule for your parser, as it will be produced as
# a parsing result
parser = ParserPEG(calc_grammar, "calc")
input_expr = "(4-1)*5+(2+4.67)+5.89/(1.2+7)"
print(input_expr)
parse_tree = parser.parse(input_expr)

result = visit_parse_tree(parse_tree, CalcVisitor(
    #debug=True
))
print(result)
input_expr = "1 + 2 / (3 - 1 + 5)"
print(input_expr)
parse_tree = parser.parse(input_expr)

result = visit_parse_tree(parse_tree, CalcVisitor(
    #debug=True
))
print(result)

При запуске выведет следующее:

python ./calc_arpeggio.py 
(4-1)*5+(2+4.67)+5.89/(1.2+7)
22.3882926829
1 + 2 / (3 - 1 + 5)
1.28571428571

Если есть желание посмотреть, как посетитель обходит дерево, можно раскомментировать debug

Как мы видим, грамматика претерпела небольшие, но важные изменения. В частности, если мы обратим внимание на правила stmt и term, то будет понятно, что они имеют произвольное число элементов. Соответственно, благодаря этому, обработка ассоциативности математических операций целиком и полностью на нашей совести. Несмотря на эти изменения, программа остается простой и понятной.

Общие выводы

На самом деле, выводов несколько:

• Не так страшен чёрт, как его малюют. Создание парсера с помощью инструмента, дело, в общем, посильное. Достаточно изучить общие принципы и потратить полдня на изучение конкретного инструмента, после чего в дальнейшем все уже будет намного проще. А вот велосипеды изобретать — не надо. Особенно, если вам не особенно важна скорость парсинга и оптимизации.
• Грамматики имеют собственную ценность. Имея перед глазами грамматику, гораздо проще оценить, будут ли при использовании составленного по ней парсера возникать ошибки.
• Инструмент можно найти всегда. Возможно, не на самом привычном языке, но почти на всех они есть. Если не повезло, и его все-таки нет, можно взять что-нибудь легко используемое (что-то на js, python, lua или ruby — тут уж кому что больше нравится). Да, получится “почти stand-alone в рамках проекта”, но в большинстве случаев этого достаточно.
• Все инструменты (немного) различаются. Иногда это “:” вместо “=” в BNF, иногда различия более обширны. Не надо этого пугаться. В крайнем случае, переделка грамматики под другой инструмент займет у вас минут 20. Так что если есть возможность достать где-то грамматику, а не писать её самому, лучше это сделать. Но перед использованием все равно лучше её проверьте. Все мы люди, всем нам свойственно ошибаться…
• При прочих равных, лучше используйте более “разговорчивый” инструмент. Это поможет избежать ошибок составления грамматики и оценить, что и как будет происходить.
• Если для вас в первую очередь важна скорость разбора, боюсь, вам придется либо пользоваться инструментом для C (например, Bison), либо решать проблему “в лоб”. Так же, следует задуматься о том, нужен ли вам именно парсинг (об этом стоит задуматься в любом случае, но в случае скоростных ограничений — особенно). В частности, для многих задач подходит токенизация — разбиение строки на подстроки с использованием заданного разделителя или их набора. Возможно, это ваш случай.

Заключение

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

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

Как и обещал, несколько полезных ссылок по теме статьи:

• В википедии, на английском (на русском статьи существенно меньше):
  СFG
  BNF
  LL
  LR
  PEG
• Если кому-то нужно более серьёзное чтиво, тоже для человека “без математического бекграунда”, могу посоветовать книгу А. Аxo, Дж. Ульман “Теория синтаксического анализа, перевода и компиляции”. Есть, например, здесь. При желании находится достаточно легко, в русском переводе.