Реализация Parsec на Python?
Недавно я написал синтаксический анализатор на Python с использованием Ply (это повторная реализация yacc на Python). Когда я почти закончил работу с синтаксическим анализатором, я обнаружил, что грамматика, которую мне нужно проанализировать, требует от меня поиска во время синтаксического анализа, чтобы сообщить лексеру. Без поиска информации лексеру я не могу правильно проанализировать строки на языке.
Учитывая, что я могу управлять состоянием лексера из правил грамматики, я думаю, что решу свой вариант использования с помощью таблицы поиска в модуле синтаксического анализатора, но это может стать слишком сложным для поддержки / тестирования. Итак, я хочу знать о некоторых других вариантах.
В Haskell я бы использовал Parsec, библиотеку функций синтаксического анализа (известных как комбинаторы). Есть ли реализация Parsec на Python? Или, возможно, какая-то другая производственная библиотека, полная функций синтаксического анализа, чтобы я мог создать контекстно-зависимый парсер на Python?
Обновлено: все мои попытки контекстного анализа потерпели неудачу. По этой причине я не ожидаю, что ANTLR будет здесь полезен.
Ответы 6
Вариант, который вы можете рассмотреть, если вам подходит LL-парсер, - это попробовать ANTLR, он также может генерировать python (на самом деле это LL (*), как они его называют, * обозначает количество опережающих просмотров, с которыми он может справиться с).
У вас есть * предварительный просмотр с ANTLR, и при необходимости вы можете добавить синтаксис и предикаты в свою грамматику (также существуют предикаты семантики). используйте antlrwork, это действительно полезно для разработки / отладки грамматики (antlr.org/works/index.html). На сайте ANTLR есть и готовые грамматики.
Есть ANTLR, то есть LL (*), есть PyParsing, который более дружественен к объектам и вроде как DSL, а затем есть Парсинг, который похож на Menhir OCaml.
Сейчас я исследую PyParsing, он выглядит ближе всего к Parsec из всех, что я видел. Я пока принимаю ваш ответ. Будем надеяться, что PyParsing работает :) Спасибо!
Я обеспокоен прочтением этого в документации PyParsing: производительность pyparsing может быть медленной для сложных грамматик и / или больших входных строк.
ANTLR великолепен и имеет дополнительное преимущество работы на нескольких языках.
PySec - еще один монадический парсер, я мало о нем знаю, но стоит посмотреть здесь
Я считаю, что пипарсинг основан на тех же принципах, что и parsec.
Ничто не мешает вам отклонить ваш синтаксический анализатор от «контекстно-свободного» пути с помощью PLY. Вы можете передавать информацию в лексер во время синтаксического анализа и, таким образом, достичь полной гибкости. Я почти уверен, что таким образом вы сможете анализировать все, что захотите, с помощью PLY.
Например, учитывать - это парсер для ANSI C, написанный на Python с PLY. Он решает классическую проблему C typedef - идентификатора (из-за которой грамматика C не зависит от контекста) путем заполнения таблицы символов в синтаксическом анализаторе, который используется в лексере для разрешения имен символов как типов, так и нет.
В моем случае мне нужно больше, чем позволяет традиционный синтаксический анализ. Все мои попытки написать традиционный контекстно-свободный синтаксический анализатор провалились по теоретическим причинам. На данный момент я почти уверен, что мне нужно как минимум условное лексирование. Будет ли применяться ANTLR?