phdru.name / Russian / Software / Python
ПППП - приемлемо-поганые питоновские парсеры.
Прошу прощения за заголовок, но для питона пока нет хороших генераторов парсеров. А жаль.
Впрочем, эта информация, возможно, устарела, и неполна. Ещё один обзор парсеров можно найти на http://www.nedbatchelder.com/text/python-parsers.html.
Тут мне понадобилось грамматику отпарсить и код по ней генерить. Я пошёл поискать, какие генераторы парсеров есть для питона. Нашёл пять штук, из них PLex оказался генератором исключительно сканеров, а не парсеров.
Остальные 4 - это знаменитый SPARK, SimpleParse/mxTextTools, PLY и Yapps2. У всех у них есть достоинства и недостатки. Делюсь накопленным опытом.
Самое большое достоинство Yapps2 - он генерит парсеры в офлайне. На файл с грамматикой EBNF натравливается программа, которая генерит питоновский модуль. Второе большое достоинство - он действительно понимает EBNF, включая *, +, ?, () и даже литеральные строки, что позволяет писать грамматику
rule cmp_expr: cmp_func "\(" name "," name_or_num "\)"
rule cmp_func: "eq" | "neq" | "lt" | "le" | "gt" | "ge" | "like" | "null" (SPARK и PLY такого не позволяют - cmp_func и скобки должны быть токенами от сканера.)
Самый большой его недостаток - он не хочет бороться с неоднозначностью грамматики и имеет трудности с рекурсией. В доке рассказано, как в таких случаях рефакторить грамматику, но я не стал с этим возиться. Генератор парсеров должен генерить парсеры сам.
Со SPARK и PLY я продвинулся дальше. Я написал парсеры для для своих выражений, и написал процедуры генерации кода из AST.
Оба модуля довольно похожи по использованию (в доке сказано, что PLY заимствовал много идей из SPARK). Недостатком PLY является то, что он использует большое количество глобальных переменных, то есть в программе, использующей PLY, может быть только один парсер. Зато PLY быстрее - 10000 циклов вызова парсера (только парсера, без генерации кода) с PLY занимает 13 секунд, со SPARK - 50. Но всё же SPARK мне нравится больше - более объектно-ориентированный подход, без глобальных переменных. Зато у PLY хороший механизм отладки - он генерит текстовый файл, в котором расписаны все состояния парсера и таблица переходов. Плюс у PLY есть механизм кеширования - при импорте он генерит питоновский код сканера и парсера, и скидывает их в lextab.py и yacctab.py. При изменении моей программы он их сам перегенерил, но как это будет работать среди большого количества модулей, а не программ - я не знаю. В принципе PLY был разработан в университете, для обучения студентов - отсюда его ограничения, и отсюда же его средства отладки. А зато у SPARK механизм генерации AST полностью отдан пользователю - используй классы, какие сам захочешь, поэтому обойти дерево AST после SPARK у меня получилось проще, чем с PLY. Впрочем, может это я перемудрил... точнее, недомудрил с PLY, и он тоже позволил бы мне построить дерево из моих классов.
Вот ещё недостатки SPARK:
Если наследоваться от GenericParser, то методы парсера, соответствующие правилам грамматики, будут вызывать в момент срабатывания правила. Если наследоваться от GenericASTBuilder (как это сделал я) - методы вызываться не будут, о чём там в комментарии сказано. Патч, для того чтобы они вызывались, займёт пару строк...
SPARK из дистрибутива глючит с Питоном 2.2. Патч для лечения и вовсе занимает одну строку.
Вот добрался и до mxTextTools/SimpleParse. Получилось довольно быстро - SimpleParse съедает на вход вполне себе EBNF с * и +, рекурсивные грамматики понимает, работает быстро - 10000 циклов у меня прошло за 10 секунд. Правда, на выходе не совсем нормальное дерево...
Достоинства: mxTextTools, написано на C, это НЕ регулярные выражения; SimpleParse воспринимает на вход почти нормальный EBNF.
Недостатки - это не LL/LR/LALR парсер, mxTextTools использует свой собственный алгоритм, который может отпарсить весь остаток текста, чтобы узнать, под какое правило подходит следующий символ; полностью отсутствует управление построением AST; сообщения об ошибке не выдаются - только флаг ok или не ok; сложные грамматики могут вызывать переполнение стека в рекурсивной версии mxTextTools, а нерекурсивную надо отдельно компилять.
Всё же SimplePasre мне понравился больше других. Второе место (первое не получил никто). Бронзовая медаль уходит к SPARK.
Вот ещё мелкий недостаток SimpleParse - опреатор / - это не |. В классических парсерах оператор | матчит все подвыражения, и выбирает из них наиболее длинное. В SimpleParse оператор / выбирает первое подошедшее. Например, надо писать не
name_or_num := name / integer / float а
name_or_num := name / float / integer Иначе парсинг вещественного числа споткнётся на точке.
Эта страница https://phdru.name/Russian/Software/Python/pppp.html была сгенерирована 14.07.2021 в 00:38:06 из шаблона CheetahTemplate pppp.tmpl; Некоторые права зарезервированы. Вы можете узнать о технических аспектах этого сайта.