使用pyparsing编写递归解析器

Question

我正在尝试理解pyparsing中的Forward()元素。假设我有一个简单的BNF（巴科斯-诺尔范式）：

identifier  =
  "a..z,$,_"  <  "a..z,$,_,0..9"  >

package_name = 
  identifier 
  /  ( package_name  "." identifier )

然后我尝试解析一个简单的包名，比如java.lang.String，结果要么只得到java，要么就一直在递归中卡住。

我这样尝试过：

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal

identifier=Word(alphas+"$_",alphanums+"$_")
dot=Literal(".")

package_name = Forward()
definition = package_name+dot+identifier
package_name << Group(identifier+ZeroOrMore(definition))

package_name.parseString("java.lang.String")

会打印出[['java']]

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal

identifier=Word(alphas+"$_",alphanums+"$_")
dot=Literal(".")

package_name = Forward()
definition = identifier^package_name+dot+identifier
package_name << definition

package_name.parseString("java.lang.String")

会达到递归限制

这个Forward占位符是怎么工作的呢？

Answer 1

问题不在于Forward，而在于你的语法本身。你的语法要么限制得太早，要么是递归的方式让人无法判断，这种情况用简单的递归下降解析器，比如Pyparsing，就无法处理。

你现在的写法是这样的：

package_name = identifier | (package_name "." identifier )

如果你从左到右匹配，这样总是只能匹配一个标识符，然后就停了，不会尝试匹配后面的句点。如果你把顺序改成最后匹配identifier：

package_name = (package_name "." identifier) | identifier

那么它就会无限递归，因为要判断package_name是否匹配，首先得判断package_name是否匹配。这就是一种左递归语法，简单的递归下降解析器像Pyparsing是处理不了的。Pyparsing不会提前查看匹配会如何影响后续的匹配，它只是从左到右尝试匹配。

你可以通过改变语法的递归方式，来简单了解Forward是如何工作的：

identifier  = pyp.Word(pyp.alphas+"$_", pyp.alphanums+"$_")
package_name = pyp.Forward()
package_name << ((identifier + '.' + package_name) | identifier)

>>> package_name.parseString("java.lang.String")
[u'java', u'.', u'lang', u'.', u'String'], {})

在这里，递归发生在右边，而不是左边，这样Pyparsing就可以逐步匹配了。

（你使用的ZeroOrMore其实是个误导。如果你的语法是递归的，就不应该使用ZeroOrMore，因为递归定义本身就允许你的子表达式匹配多次。不过，正如我在评论中提到的，定义这种语法时其实不使用递归会简单得多。）