Python NLTK：使用联合结构解析句子，进入无限递归

Question

我被要求为以下句子创建 two 不同的解析树：

foo while bar and baz

基于这两个结构：

S-> S while S
S-> S and S

我拥有的两棵不同的树如下：

树 A)

     S
   / | \
  P  U  S
  |    /|\
  W   P U P  
      |   |
      W   W

这是 A 的代码：

import nltk

groucho_grammar = nltk.CFG.fromstring ("""
S -> P U S | P U P
P -> W
U -> 'while' | 'and'
W -> 'foo'|'bar'|'baz'
""")

print(groucho_grammar)

sentence = "foo while bar and baz"

rd_parser = nltk.RecursiveDescentParser(groucho_grammar)
for tree in rd_parser.parse(sentence.split()):
    print(tree)

A 的结果：

(S (P (W foo)) (U while) (S (P (W bar)) (U and) (P (W baz))))

树 B)

       S
     / | \
    S  U  P
  / | \    \
 P  U  P    W
 |     |
 W     W

现在对于 B 部分，我只是将语法修改为以下内容：

groucho_grammar = nltk.CFG.fromstring ("""
S -> S U P | P U P
P -> W
U -> 'while' | 'and'
W -> 'foo'|'bar'|'baz'
""")

但是我遇到了无限递归错误：

    if isinstance(index, (int, slice)):
RuntimeError: maximum recursion depth exceeded in __instancecheck__

如有任何帮助，我们将不胜感激。

谢谢。

Answer 1

你的问题是这条规则：S -> S U P | P U P

通过允许 S 以 S 的实例开始，您允许这种无限递归：

S -> S U P
S -> (S U P) U P
S -> ((S U P) U P) U P
S -> (((S U P) U P) U P) U P

这称为左递归，它是由一个符号扩展到自身引起的，在本例中是 S 扩展到 S。

来自NLTK book, chapter 8：

Recursive descent parsing has three key shortcomings. First, left-recursive productions like NP -> NP PP send it into an infinite loop.

一个解决方案

幸运的是，您可以简单地将您使用的解析器更改为不共享左递归阿喀琉斯之踵的解析器。简单的改变这个：

rd_parser = nltk.RecursiveDescentParser(groucho_grammar)

对此：

rd_parser = nltk.parse.chart.BottomUpLeftCornerChartParser(groucho_grammar)

这样你就可以利用左递归抵抗BottomUpLeftCornerChartParser

进一步阅读

左递归问题在自动机理论中是众所周知的。有一些方法可以使您的语法非递归，如这些链接中所述：

Python NLTK：使用联合结构解析句子，进入无限递归

Python NLTK: parse sentence using conjoint structure, getting into infinite recursion

python

nltk

context-free-grammar