用pyparsing编写递归解析器

我试图从pyparsing中了解Forward()元素。假设我有这个简单的BNF：用pyparsing编写递归解析器

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占位符的工作？

来源

2013-01-19 Rafael T

为什么不只是'package_name = ZeroOrMore（identifier + dot）+ identifier'？我认为你正在做的事情的问题是它的复发*和*涉及ZeroOrMore，它允许它保持匹配零。您的原始BNF没有相当于ZeroOrMore。但是完全避免递归更简单。 – BrenBarn

我知道我可以做到另一种方式。像'delimitedList（标识符，delim =“。”）'但我想了解'前向'递归ParserElement。即使'package_name << definition'也不行 –

问题不在于Forward，而在于您的语法，它固有地或者限制得太早，或者以像Pyparsing这样天真的递归下降解析器不可判定的方式递归。

你有这样的：

package_name = identifier | (package_name "." identifier)

如果你匹配左到右，这将始终与一个标识符，然后停下来，而不会试图匹配下一个周期。如果切换顺序以匹配identifier最后一位：

package_name = (package_name "." identifier) | identifier

。。。那么它将无限递归，因为为了决定package_name是否匹配，它必须做的第一件事是决定package_name是否匹配。这是一个left-recursive文法，像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可以incremenetally与之匹敌。（你使用ZeroOrMore是一个红色的鲱鱼，如果你要有这样的递归语法，你不想使用ZeroOrMore，因为递归定义已经允许你的子表达式匹配多次。但是，正如我在我的评论中所建议的，无论如何定义这种类型的语法都是非常简单的。）

来源

2013-01-20 00:17:24 BrenBarn

用pyparsing编写递归解析器

回答

相关问题