Skip to main content
 首页 » 编程设计

Python NLTK : parse sentence using conjoint structure, 进入无限递归

2025年05月04日14tintown

我被要求为以下句子创建两个不同的解析树:

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__ 

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

谢谢。

请您参考如下方法:

你的问题是这个规则: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

进一步阅读

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

  1. http://www.cs.engr.uky.edu/~lewis/essays/compilers/rec-des.html
  2. http://www.umsl.edu/~kjs9rc/CS4890/presentation.pdf
  3. http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf