python - Pyparsing 使用 Forward 解析递归表达式

Question

我正在尝试递归地解析一个表达式。我遵循了一些教程，看起来 Forward() 是我需要的类。然而，一些看似简单的事情却给我带来了麻烦。

这是我写的代码

from pyparsing import *
exp = Forward()
integer = Word(nums)
exp << (integer | (exp + '+' + exp))
input = "1+1"
print exp.parseString(input)

我希望它返回 ['1','+','1'] 但它只返回 ['1']

非常感谢您的帮助。

Answer 1

这里有几个问题。按重要性升序排列:

1. 如果解析后的内容后有额外的文本，parseString 不会引发异常。使用 exp.parseString(input, parseAll=True)
2. '|'是 MatchFirst，而不是 MatchLongest。由于您的整数是第一个，因此它将首先匹配。然后解析器在“+”上失败了。如果您想要最长的匹配，请使用“^”运算符。
3. 要点:一旦您转换为“^”(或重新排序表达式以将 exp + exp 放在前面，整数之前)，您会发现自己超出了最大递归深度。那是因为此解析器具有 exp 的左递归定义。 .也就是说，解析 exp , 它必须解析 exp ，为此它必须解析 exp等。一般来说，许多已发布的 BNF 使用递归来描述这种重复结构，但 pyparsing 不会为此工作进行必要的先行/回溯。尝试 exp <<= integer + ZeroOrMore('+' + integer) | '(' + exp + ')' - 这个表达式不是左递归的，因为在解析嵌套的 exp 之前你必须经过左括号.

编辑: 抱歉，我之前的建议有点太快了，这是进行递归表达式解析的正确方法:

from pyparsing import *

exp = Forward()
LPAR, RPAR = map(Suppress, "()")
integer = Word(nums)
term = integer | Group(LPAR + exp + RPAR)
exp << term + ZeroOrMore('+' + term)

input = "(1+1) + 1"
print(exp.parseString(input))

打印

[['1', '+', '1'], '+', '1']

如果您跟踪代码，您将看到递归:exp使用 term 定义, 和 term使用 exp 定义. fourFn.py例子最接近这种风格；自从写了那个，我添加了 infixNotation pyparsing 的方法，这将允许您编写:

exp = infixNotation(integer, [
                    ('+', 2, opAssoc.LEFT),
                    ])

infixNotation在内部处理递归定义，隐式定义 '(' + exp + ')'表达式，并使实现具有操作优先级的操作符系统变得容易。