Воспользуемся инструментами для парсинга 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-парсера могут возникать конфликты следующего вида: Перенос-свертка: ::= x | x. Где длина x > k. Решается элементарно: ::= x; ::= | e Свертка-свертка: :: = e ::= ::= ::= u v | u w, где длина u > kРешается так: ::= u ::= u ::= w | v Для LL-парсера характерны конфликты вида (необходимо, но не достаточно, их переформулировать, по запросу могу остановиться на LL(k) грамматиках подробнее в следующей статье): Левая рекурсия: ::= x | y, где x, y - произвольные строки терминалов/не терминалов, но y не начинается с Пример: E ::= E + T | T. Можно переформулировать, как: E ::= T Z Z ::= ‘+’ TZ | x Левая факторизация: ::= ax | ay, где a - строка длины > k нашего парсера. Решается еще проще: ::= a; = x|y Итак, что мы будем решать? Ну, допустим, это будет простой калькулятор: ::= "+ "| "-" | "*" | "/" ::= "(" ")" | | | ::= "." ::= ( | ) | ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" ::= | "0" Если читатель попробует найти грамматику калькулятора в интернете, он увидит что часто операции сложения/вычитания и умножения/деления обрабатываются разными грамматическими конструкциями. Это сделано специально, чтобы учесть в грамматике такой момент, как приоритет операций (а также раскрыть неоднозначности грамматики). Мы это сделаем дальше по ходу статьи. Пробуем найти нативное Python-решение, находим их много https://wiki.python.org/moin/LanguageParsing Используем 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"