Анализ кода Python с помощью PyParsing?

Question

Я пытаюсь написать Pyparsing код, способный разбора кода Python (я знаю, что модуль AST существует, но это будет лишь отправной точкой. - Я в конечном счете хочу разобрать больше, чем просто код Python)

в любом случае, я полагаю, я просто начать писать что-то, способное анализировать классический

print("Hello World!") 

Так вот что я писал:

from pyparsing import (alphanums, alphas, delimitedList, Forward, 
         quotedString, removeQuotes, Suppress, Word) 

expr = Forward() 
string = quotedString.setParseAction(removeQuotes) 
call = expr + Suppress('(') + Optional(delimitedList(expr)) + Suppress(')') 
name = World(alphas + '_', alphanums + '_') 
expr <<= string | name | call 

test = 'print("Hello World!")' 
print(expr.parseString(test)) 

Когда я сделать это, хотя, это просто выплевывает:

['print'] 

Какая технически действительная expr - вы можете ввести ее в REPL, и нет никакой проблемы в ее анализе, даже если это бесполезно.

Так что я подумал, может быть, что я хочу, чтобы перевернуть вокруг name и call в моем expr определению, поэтому предпочел бы возвращение call с до name с, как это:

expr <<= string | call | name 

Теперь я получаю максимум глубина рекурсии превысила ошибку. Это также имеет смысл:

1. Проверяет, является ли это expr.
   1. Проверяет, является ли это string, это не так.
   2. Проверяет, является ли это call.
      1. Необходимо набрать expr, вернитесь к началу внешнего списка.

Так что мой вопрос ... как я могу определить call и expr так, что я не в конечном итоге с бесконечной рекурсии, но и так, что он не останавливается, когда он видит имя и игнорирует аргументы?

Является ли код Python слишком сложным для обработки PyParsing? Если нет, существует ли ограничение на то, что PyParsing может обрабатывать?

(Примечание. - Я включил общие тег parsing, abstract-syntax-tree и bnf, потому что я подозреваю, что это общерекурсивная проблема определения грамматики, а не что-то обязательно специфично для pyparsing)

Answer 1

Вашей грамматика леворекурсивный : expr ожидает call, который ожидает expr, который ожидает call ... Если PyParsing не может обрабатывать левую рекурсию, вам нужно сменить грамматику на то, с чем может работать PyParsing.

Один подход, чтобы удалить прямой леворекурсивные, чтобы изменить правила gramar такие нам:

A = A b | c 

в

A = c b* 

В вашем случае, левая рекурсия непрямого: это Безразлично 't происходит в expr, но в подпункте (call):

E = C | s | n 
C = E x y z 

Чтобы удалить косвенную левую рекурсию, вы обычно поднимите определение подглавного правила на основное правило. К сожалению, это устраняет оскорбительное подчиненное правило из грамматики - другими словами, вы теряете структурную выразительность, когда вы это делаете.

В предыдущем примере, с косвенной рекурсией удалены, будет выглядеть следующим образом:

E = E x y z | s | n 

На данный момент, у вас есть прямой леворекурсивные, который легче трансформировать. Когда вы имеете дело с этим, результат был бы что-то подобное - в псевдо EBNF:

E = (s | n) (x y z)* 

В вашем случае, определение Expr стало бы:

Expr = (string | name) Args* 
Args = "(" ExprList? ")" 
ExprList = Expr ("," Expr)*