使用 Pyparsing 解析逻辑表达式

Question

首先，这不是家庭作业，我正在尝试学习 pyparsing，但我被困在这里了。

我的问题如下，我正在尝试解析像 (abc or def) or def)

这样的语句

我的程序在中缀表达式上乱七八糟 a or b，因为双方本身都可以是表达式，它们又可以是中缀表达式，解析器会递归直到达到递归深度并且没有完成任何工作。

代码如下：

# infix operators are automatically created and dealt with
infix_operators  = ['and', '&', 'or', '|', 'implies', '->']

variable  = Word(alphas)
infix_op  = oneOf(infix_operators, caseless=True)

expr         = Forward()
infix_expr   = (expr + infix_op + expr)
complex_expr = nestedExpr('(', ')', content=expr)
expr        << (infix_expr | complex_expr | variable)

print str(expr.parseString("(abc or def) or def)")[0])

我的问题很简单；在这种情况下如何避免无限循环？

Answer 1

规范解决方案是实现此 BNF 的东西：

atom   := variable | 'True' | 'False' | '(' expr ')'
factor := [ 'not' ]... atom
term   := factor [ '&' factor ]...
expr   := term [ '|' term ]...

解决了左递归问题，因为即使 expr 最终通过 term -> factor -> atom 递归，当它到达 expr，它首先必须解析前导 '('。因此 expr 在首先解析其他元素之前不必首先解析更深的 expr。

这个 BNF 几乎直接转换为 pyparsing 为：

and_ = Keyword('and')
or_ = Keyword('or')
not_ = Keyword('not')
true_ = Keyword('true')
false_ = Keyword('false')

not_op = not_ | '~'
and_op = and_ | '&'
or_op = or_ | '|'

expr = Forward()

identifier = ~(and_ | or_ | not_ | true_ | false_) + Word(alphas)
atom = identifier | Group('(' + expr + ')')
factor = Group(ZeroOrMore(not_op) + atom)
term = Group(factor + ZeroOrMore(and_op + factor))
expr <<= Group(term + ZeroOrMore(or_op + term))

或者你可以使用 pyparsing 的 infixNotation 助手：

expr = infixNotation(true_ | false_ | identifier,
    [
    (not_op, 1, opAssoc.RIGHT),
    (and_op, 2, opAssoc.LEFT),
    (or_op, 2, opAssoc.LEFT),
    ])

infixNotation 由一个基本操作数（在本例中，是一个 alpha 变量名称或布尔文字 true 或 false 之一）构成，后跟一个列表(operator, arity, associativity) 元组，按运算符优先顺序给出。 infixNotation 负责所有递归定义、右结合运算符与左结合运算符的解析，并且还对运算符进行一些前瞻，以避免在没有运算符的情况下为给定的优先级进行额外的运算嵌套.

您可以使用 pyparsing 的 runTests 方法测试此表达式：

expr.runTests("""
    p and not q
    not p or p
    r and (p or q)
    r and p or q
    not q
    q
    """, fullDump=False)

给予：

p and not q
[['p', 'and', ['not', 'q']]]

not p or p
[[['not', 'p'], 'or', 'p']]

r and (p or q)
[['r', 'and', ['p', 'or', 'q']]]

r and p or q
[[['r', 'and', 'p'], 'or', 'q']]

not q
[['not', 'q']]

q
['q']

使用 Pyparsing 解析逻辑表达式

Parsing Logic Expressions with Pyparsing

pyparsing

python-2.7