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真的在地图上!感谢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被定义为oneOf("+ - */"),因此没有优先级的操作.有关pyparsing repo的例子,请参阅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；每当非终结符出现在语法中一行的左侧和右侧时，中间必须有一些文字供解析器使用。