的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 

下面是一個的代碼：

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)))) 

樹乙

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

現在對於部分B，I只是將語法修改爲以下內容：

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

進一步閱讀

左遞歸問題在自動機理論中是衆所周知的。有辦法讓你的語法非遞歸，因爲在這些鏈接解釋說：

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