python语法分析器中运算符的递归处理

Question

我正在努力学习如何使用parsec。

我正在努力处理递归定义，以处理中缀形式的加法运算符

我知道为什么下面的代码不起作用，但我不知道如何修复它。

from parsec import *
test_strings = (
('1', 1),
('123', 123),
('(( 123))', 123),
('((1+2))', 3),
('1+2+3', 6),
('1+2+3+4', 10),
('(4 + 5 + 2)', 11),
('(4 + 5) + 2', 9),
('2 + (4 + 5)', 11),
('2 + (5 + (3+4))', 14),
('2 + ((3+4) + 5)', 14), #these don't work
('2 + (5 + (3+4) + 5)', 19), #these don't work
)

whitespace = regex(r's*', re.MULTILINE)
lexeme = lambda p: p << whitespace
lparen = lexeme(string('('))
rparen = lexeme(string(')'))
no_paren = many(none_of('()'))
plus = lexeme(string('+'))
number = lexeme(regex(r'd+').parsecmap(int))
@generate
def addition():
e1 = yield braced | number
yield plus
e2 = yield expr
return e1 + e2
@generate
def braced():
yield lparen
es = yield braced ^ expr
yield rparen
return es

expr = braced ^ addition ^ number

if __name__ == '__main__':
for s, expected in test_strings:
print(f'testing expression {s}')
res = expr.parse(s)
assert res == expected, f'for {s}, expected {expected}, got {res}'

addition显然是错误的，但如果我试图让左操作数(e1(的类型为expr，那么我们将得到无限递归。这是有意义的，因为这个递归定义不会在每次调用中消耗任何东西。

我正在寻找的解决方案是可以扩展到处理嵌套表达式的解决方案，一旦我对这个问题进行了排序，嵌套表达式将变得更加复杂。

Answer 1

好的，我可以处理这些更改：

@generate
def addition():
e1 = yield (braced | number)
yield plus
e2 = yield expr
return e1 + e2
@generate
def braced():
yield lparen
es = yield expr
yield rparen
return es
expr = addition ^ (braced | number)