Python parsec库递归处理中缀加法运算符的问题求解

问题根因 #

你遇到的是递归下降类解析器的经典左递归问题：parsec.py属于自顶向下的递归下降解析器，无法直接处理expr -> expr + 操作数这类左递归规则——如果让加法的左操作数直接取expr，解析器会在没有消费任何输入的情况下反复调用expr，最终触发无限递归。

可扩展解决方案 #

解决这类中缀表达式解析的通用方案是表达式分层，按运算符优先级、结合性拆分解析规则，从结构上规避左递归：

• 把加法的操作数拆成独立的term层级（仅匹配括号表达式或数字，不会递归调用上层的加法规则）
• 加法规则改为匹配「1个term + 若干个+ term的组合」，天然支持左结合的任意长度加法链，且每次解析都会先消费term的输入，完全避免无限递归

修改后的可运行代码如下：

from parsec import *
import re

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),
        ('2 + (5 + (3+4) + 5)', 19),
)


whitespace = regex(r'\s*', re.MULTILINE)
lexeme = lambda p: p << whitespace

lparen = lexeme(string('('))
rparen = lexeme(string(')'))

plus = lexeme(string('+'))
number = lexeme(regex(r'\d+').parsecmap(int))

# 原子操作数：括号表达式 或 数字
@generate
def term():
    res = yield braced ^ number
    return res

# 加法表达式：支持任意长度左结合加法链
@generate
def expr():
    first = yield term
    rest = yield many(plus >> term)
    # 左结合累加所有值
    return first + sum(rest)

# 括号表达式：括号包裹任意合法表达式
@generate
def braced():
    yield lparen
    res = yield expr
    yield rparen
    return res


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}'
    print("所有测试用例通过")

扩展说明 #

这套分层结构的扩展性极强，后续需要新增其他运算符时只需新增对应层级即可：

• 要加乘除优先级：新增factor层级处理乘除链，把原来的term改为仅匹配括号/数字，expr仅处理加减链，优先级自然区分
• 要加减法/其他左结合运算符：直接在对应层级的many规则中新增运算符匹配即可
• 要加右结合运算符（比如幂运算）：把many改为右递归的匹配规则即可

内容的提问来源于stack exchange，提问作者Gregory Kuhn