5

我试图Forward()从 pyparsing 中理解元素。假设我有这个简单的 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工作的？

4

1 回答 1

14

问题不在于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，因为递归定义已经允许您的子表达式匹配多次。正如我所建议的不过，在我的评论中，在没有递归的情况下定义这种语法要简单得多。）

于 2013-01-20T00:17:24.103 回答