我如何在CFG解析器中求解左递归

Question

如何解决此左递归？我已经花了很长时间找到解决方案，但我为之奋斗。句子：鲍勃给最大汽车。我想在这里显示的要点是发生的左递归。哪个是np-> np，我该如何解决这个问题？如果我现在在Python3中运行此代码，它将崩溃。

import nltk.grammar
grammar = nltk.CFG.fromstring(""" 
S -> NP VP
VP -> V NP 
NP -> "cars" | "Bob" | NP | "Max" 
V -> "gives"
""") 
sent = "Bob gives Max cars".split() 
rd_parser = nltk.RecursiveDescentParser(grammar)
for tree in rd_parser.parse(sent):
    print(tree)

Answer 1

通过不编写递归规则来解决问题。如果您甚至不能想出需要它的句子，就不需要它。

递归规则在CFG中是合法的；这就是他们可以产生无限数量的句子的方式。借助左获取语法，递归下降解析器 Will 将与某些输入永远运行。这就是它的作用，这就是为什么有更聪明的解析算法。

Answer 2

的确， NP -> NP是左记录规则。但是，这也是一个毫无意义的规则，因为它不会改变语法产生的语言，而只是使语法模棱两可。

因此，如果您认为将NP -> NP添加到语法中可以使您可以解析" Bob Max Max Car"，则不会。这与解析器无关，而只是该句子不是语法产生的语言的事实。

尝试绘制您希望为该句子获得的解析树。您会发现没有一个符合该语法的人。但是，如果您发现不符合语法，那应该告诉您如何更改语法来处理这种句子。(请注意，可能有各种此类树，反映了可以生成该句子的各种不同语法。>