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

哇，我想 pyparsing 真的很受欢迎！感谢亚历克斯和约翰介入解决这个问题。你们的回答都切中要害。但让我添加一两条评论：

1. 如果我们抑制左括号和右括号符号，并使用 Group 对括号表达式进行分组，pyparsing 将得到一个更接近 AST 的结构化结果。

   from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf,Group
   
   def 语法():
       op = oneOf('+ -')
       lpar = Literal( '(' ).suppress()
       rpar = Literal( ')' ).suppress()
       数字=字（数字）
       expr = 转发()
       原子=数字|组(lpar + expr + rpar)
       表达式 <<原子 + ZeroOrMore(操作 + 原子)
       返回表达式
   
   如果 __name__ == "__main__":
       expr = 语法()
       定义测试：
           结果 = expr.parseString(s)
           print s,'->', 结果
   
       测试（“（9 + 3）”）
       测试（“（9 + 3）*（4 / 5）”）
   

   给予：

   <前><代码>(9 + 3) -> [[‘9’、‘+’、‘3’]]
   (9 + 3) * (4 / 5) -> [['9', '+', '3'], '*', ['4', '/', '5']]

   否则，pyparsing 只是标记化，您必须遍历已解析标记的列表来查找嵌套表达式。

2. 由于 op 被定义为 oneOf("+ - * /")，因此操作没有优先级。 pyparsing 存储库上有示例 https://github.com/pyparsing/pyparsing/ tree/master/examples 手动定义此方法 (fourFn.py)，或者使用 infixNotation 帮助程序 (simpleArith.py) 的最新方法。同样，这使 pyparsing 比仅仅标记化添加了更多价值。

对于OP，请查看这些示例，我认为它们将帮助您推进项目。

——保罗

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

像这样的语法

expr :: expr op expr

很难使用，因为递归总是向左潜入。

正常的算术语法看起来像这样：

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

基本上，你永远不会得到 S :: S;每当非终结符出现在语法中一行的左侧和右侧时，中间必须有一些文字供解析器使用。

Answer 4

使用 operatorPrecedence 构建表达式。它将构建正确的表达式，并在执行时处理运算符优先级：

num = Word(nums)
plusop = oneOf( '+ -')
multop = oneOf('/ *')
expr = operatorPrecedence(num,
                          [(multop, 2, opAssoc.LEFT),(plusop, 2, opAssoc.LEFT)])

示例：

>> print parsetime.expr.parseString("1+(2 * 3-(4*(5+6)-(7)))")
[['1', '+', [['2', '*', '3'], '-', [['4', '*', ['5', '+', '6']], '-', '7']]]]