在PyParsing中简单递归下降

Question

我试着把这段代码改成我正在做的一个编程语言处理项目的样子，但我遇到了一个问题，下面是一个简化版：

op = oneOf( '+ - / *')
lparen, rparen = Literal('('), Literal(')')

expr = Forward()
expr << ( Word(nums) | ( expr + op + expr ) | ( lparen + expr + rparen) )

我尝试了很多不同的修改，通常像这样尝试：

print(expr.parseString('1+2'))

会返回 ['1']。而如果我用下面这个，就会陷入深度递归：

print(expr.parseString('(1+2)'))

我在简单递归方面缺少了什么，导致我无法解析任意的算术表达式，比如 1+(2 * 3-(4*(5+6)-(7))...？

Answer 1

像这样的语法：

expr :: expr op expr

很难处理，因为它的递归总是向左深入。

一个正常的算术语法大概是这样的：

expr :: mulxp | mulxp '+' expr
mulxp :: atom | atom '*' expr
atom :: Word(nums) | '(' + expr + ')'

基本上，你不会看到 S :: S；每当一个非终结符出现在语法的一行的左右两边时，中间必须有一些具体的内容供解析器使用。

Answer 2

这大概是你想要的内容吗…？

from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf

def Syntax():
    op = oneOf( '+ - / *')
    lpar  = Literal( '(' )
    rpar  = Literal( ')' )
    num = Word(nums)

    expr = Forward()
    atom = num | ( lpar + expr + rpar )
    expr << atom + ZeroOrMore( op + expr )
    return expr


if __name__ == "__main__":

    expr = Syntax()

    def test(s):
        results = expr.parseString( s )
        print s,'->', results

    test( "(9 + 3)" )
    test( "(9 + 3) * (4 / 5)" )

发射

(9 + 3) -> ['(', '9', '+', '3', ')']
(9 + 3) * (4 / 5) -> ['(', '9', '+', '3', ')', '*', '(', '4', '/', '5', ')']

? 这个“锚定”了递归，通过把一个“原子”（数字或带括号的表达式）和一个“表达式”（一个或多个“原子”中间有运算符）分开。

Answer 3

哇，看来pyparsing真的很受欢迎啊！感谢Alex和John对这个问题的解答。你们的回答都很到位。不过我想再补充几句：

1. 如果我们不显示开括号和闭括号，并且用Group把括号里的表达式分组，pyparsing会给出一个更有结构的结果，这个结果更接近于抽象语法树（AST）。

   from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf,Group
   
   def Syntax():
       op = oneOf('+ -')
       lpar  = Literal( '(' ).suppress()
       rpar  = Literal( ')' ).suppress()
       num = Word(nums)
       expr = Forward()
       atom = num | Group(lpar + expr + rpar)
       expr << atom + ZeroOrMore(op + atom)
       return expr
   
   if __name__ == "__main__":
       expr = Syntax()
       def test(s):
           results = expr.parseString(s)
           print s,'->', results
   
       test( "(9 + 3)" )
       test( "(9 + 3) * (4 / 5)" )
   

   这样就能得到：

   (9 + 3) -> [['9', '+', '3']]
   (9 + 3) * (4 / 5) -> [['9', '+', '3'], '*', ['4', '/', '5']]
   

   否则，pyparsing只是把内容分成一个个小块，你需要逐个查看这些小块，才能找到嵌套的表达式。

2. 因为op只是定义为一个符号集合("+ - * /")，所以没有运算的优先级。你可以在pyparsing的代码库里找到一些示例，地址是 https://github.com/pyparsing/pyparsing/tree/master/examples，里面有手动定义运算优先级的例子（fourFn.py），还有最近使用infixNotation这个助手的方式（simpleArith.py）。再次强调，这样pyparsing的功能就不仅仅是分块了。

对提问者来说，请看看那些示例，我觉得它们会对你的项目有帮助。

-- Paul