# 8\. 分析句子結構
前面的章節重點關注詞：如何識別它們，分析它們的結構，分配給他們詞匯類別，以及獲得它們的含義。我們還看到了如何識別詞序列或 n-grams 中的模式。然而，這些方法只觸碰到支配句子的復雜約束的表面。我們需要一種方法處理自然語言中顯著的歧義。我們還需要能夠應對這樣一個事實，句子有無限的可能，而我們只能寫有限的程序來分析其結構和發現它們的含義。
本章的目的是要回答下列問題：
1. 我們如何使用形式化語法來描述無限的句子集合的結構？
2. 我們如何使用句法樹來表示句子結構？
3. 語法分析器如何分析一個句子并自動構建句法樹？
一路上，我們將覆蓋英語句法的基礎，并看到句子含義有系統化的一面，只要我們確定了句子結構，將更容易捕捉。
## 1 一些語法困境
## 1.1 語言數據和無限可能性
前面的章節中已經為你講述了如何處理和分析的文本語料庫，我們一直強調處理大量的每天都在增加的電子語言數據是 NLP 的挑戰。讓我們更加細致的思考這些數據，做一個思想上的實驗，我們有一個巨大的語料庫，包括在過去 50 年中英文表達或寫成的一切。我們稱這個語料庫為“現代英語”合理嗎？有許多為什么我們的回答可能是否定的的原因。回想一下，在[3](./ch03.html#chap-words)中，我們讓你搜索網絡查找 the of 模式的實例。雖然很容易在網上找到包含這個詞序列的例子，例如 New man at the of IMG （見`http://www.telegraph.co.uk/sport/2387900/New-man-at-the-of-IMG.html`），說英語的人會說大多數這樣的例子是錯誤的，因此它們根本不是英語。
因此，我們可以說，“現代英語”并不等同于我們想象中的語料庫中的非常大的詞序列的集合。說英語的人可以判斷這些序列，并將拒絕其中一些不合語法的。
同樣，組成一個新的句子，并讓說話者認為它是非常好的英語是很容易的。例如，句子有一個有趣的屬性，它們可以嵌入更大的句子中。考慮下面的句子：
```py
>>> groucho_grammar = nltk.CFG.fromstring("""
... S -> NP VP
... PP -> P NP
... NP -> Det N | Det N PP | 'I'
... VP -> V NP | VP PP
... Det -> 'an' | 'my'
... N -> 'elephant' | 'pajamas'
... V -> 'shot'
... P -> 'in'
... """)
```
這個文法允許以兩種方式分析句子，取決于介詞短語 in my pajamas 是描述大象還是槍擊事件。
```py
>>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> parser = nltk.ChartParser(groucho_grammar)
>>> for tree in parser.parse(sent):
... print(tree)
...
(S
(NP I)
(VP
(VP (V shot) (NP (Det an) (N elephant)))
(PP (P in) (NP (Det my) (N pajamas)))))
(S
(NP I)
(VP
(V shot)
(NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))
```
程序產生兩個括號括起的結構，我們可以用樹來表示它們，如[(3b)](./ch08.html#ex-elephant)所示：
```py
grammar1 = nltk.CFG.fromstring("""
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> "saw" | "ate" | "walked"
NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
Det -> "a" | "an" | "the" | "my"
N -> "man" | "dog" | "cat" | "telescope" | "park"
P -> "in" | "on" | "by" | "with"
""")
```
在[3.1](./ch08.html#code-cfg1)中的語法包含涉及各種句法類型的產生式，如在[3.1](./ch08.html#tab-syncat)中所列出的。
表 3.1：
句法類型
```py
>>> grammar1 = nltk.data.load('file:mygrammar.cfg')
>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.parse(sent):
... print(tree)
```
確保你的文件名后綴為`.cfg`，并且字符串`'file:mygrammar.cfg'`中間沒有空格符。如果命令`print(tree)`沒有產生任何輸出，這可能是因為你的句子`sent`并不符合你的語法。在這種情況下，可以將分析器的跟蹤設置打開：`rd_parser = nltk.RecursiveDescentParser(grammar1, trace=2)`。你還可以查看當前使用的語法中的產生式，使用命令`for p in grammar1.productions(): print(p)`。
當你編寫 CFG 在 NLTK 中分析時，你不能將語法類型與詞匯項目一起寫在同一個產生式的右側。因此，產生式`PP -> 'of' NP`是不允許的。另外，你不得在產生式右側仿制多個詞的詞匯項。因此，不能寫成`NP -> 'New York'`，而要寫成類似`NP -> 'New_York'`這樣的。
## 3.3 句法結構中的遞歸
一個語法被認為是遞歸的，如果語法類型出現在產生式左側也出現在右側，如[3.3](./ch08.html#code-cfg2)所示。產生式`Nom -> Adj Nom`（其中`Nom`是名詞性的類別）包含`Nom`類型的直接遞歸，而`S`上的間接遞歸來自于兩個產生式的組合`S -> NP VP`和`VP -> V S`。
```py
grammar2 = nltk.CFG.fromstring("""
S -> NP VP
NP -> Det Nom | PropN
Nom -> Adj Nom | N
VP -> V Adj | V NP | V S | V NP PP
PP -> P NP
PropN -> 'Buster' | 'Chatterer' | 'Joe'
Det -> 'the' | 'a'
N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log'
Adj -> 'angry' | 'frightened' | 'little' | 'tall'
V -> 'chased' | 'saw' | 'said' | 'thought' | 'was' | 'put'
P -> 'on'
""")
```
要看遞歸如何從這個語法產生，思考下面的樹。[(10a)](./ch08.html#ex-recnominals)包括嵌套的名詞短語，而[(10b)](./ch08.html#ex-recsentences)包含嵌套的句子。
```py
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in rd_parser.parse(sent):
... print(tree)
(S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
```
注意
`RecursiveDescentParser()`接受一個可選的參數`trace`。如果`trace`大于零，則分析器將報告它解析一個文本的步驟。
遞歸下降分析有三個主要的缺點。首先，左遞歸產生式，如`NP -> NP PP`會進入死循環。第二，分析器浪費了很多時間處理不符合輸入句子的詞和結構。第三，回溯過程中可能會丟棄分析過的成分，它們將需要在之后再次重建。例如，從`VP -> V NP`上回溯將放棄為`NP`創建的子樹。如果分析器之后處理`VP -> V NP PP`，那么`NP`子樹必須重新創建。
遞歸下降分析是一種自上而下分析。自上而下分析器在檢查輸入之前先使用文法 _ 預測 _ 輸入將是什么！然而，由于輸入對分析器一直是可用的，從一開始就考慮輸入的句子會是更明智的做法。這種方法被稱為自下而上分析，在下一節中我們將看到一個例子。
## 4.2 移進-歸約分析
一種簡單的自下而上分析器是移進-歸約分析器。與所有自下而上的分析器一樣，移進-歸約分析器嘗試找到對應文法生產式 _ 右側 _ 的詞和短語的序列，用左側的替換它們，直到整個句子歸約為一個`S`。
移位-規約分析器反復將下一個輸入詞推到堆棧（[4.1](./ch04.html#sec-back-to-the-basics)）；這是移位操作。如果堆棧上的前 _n_ 項，匹配一些產生式的右側的 _n_ 個項目，那么就把它們彈出棧，并把產生式左邊的項目壓入棧。這種替換前 _n_ 項為一項的操作就是規約操作。此操作只適用于堆棧的頂部；規約棧中的項目必須在后面的項目被壓入棧之前做。當所有的輸入都使用過，堆棧中只剩余一個項目，也就是一顆分析樹作為它的根的`S`節點時，分析器完成。移位-規約分析器通過上述過程建立一顆分析樹。每次彈出堆棧 _n_ 個項目，它就將它們組合成部分的分析樹，然后將這壓回推棧。我們可以使用圖形化示范`nltk.app.srparser()`看到移位-規約分析算法步驟。執行此分析器的六個階段，如[4.2](./ch08.html#fig-srparser1-6)所示。
圖 4.2：移進-歸約分析器的六個階段：分析器一開始把輸入的第一個詞轉移到堆棧；一旦堆棧頂端的項目與一個文法產生式的右側匹配，就可以將它們用那個產生式的左側替換；當所有輸入都被使用過且堆棧中只有剩余一個項目`S`時，分析成功。
NLTK 中提供`ShiftReduceParser()`，移進-歸約分析器的一個簡單的實現。這個分析器不執行任何回溯，所以它不能保證一定能找到一個文本的解析，即使確實存在一個這樣的解析。此外，它最多只會找到一個解析，即使有多個解析存在。我們可以提供一個可選的`trace`參數，控制分析器報告它分析一個文本的步驟的繁瑣程度。
```py
>>> sr_parser = nltk.ShiftReduceParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in sr_parser.parse(sent):
... print(tree)
(S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
```
注意
**輪到你來：** 以跟蹤模式運行上述分析器，看看序列的移進和規約操作，使用`sr_parse = nltk.ShiftReduceParser(grammar1, trace=2)`。
移進-規約分析器可能會到達一個死胡同，而不能找到任何解析，即使輸入的句子是符合語法的。這種情況發生時，沒有剩余的輸入，而堆棧包含不能被規約到一個`S`的項目。問題出現的原因是較早前做出的選擇不能被分析器撤銷（雖然圖形演示中用戶可以撤消它們的選擇）。分析器可以做兩種選擇：（a）當有多種規約可能時選擇哪個規約（b）當移進和規約都可以時選擇哪個動作。
移進-規約分析器可以改進執行策略來解決這些沖突。例如，它可以通過只有在不能規約時才移進，解決移進-規約沖突；它可以通過優先執行規約操作，解決規約-規約沖突；它可以從堆棧移除更多的項目。（一個通用的移進-規約分析器，是一個“超前 LR 分析器”，普遍使用在編程語言編譯器中。）
移進-規約分析器相比遞歸下降分析器的好處是，它們只建立與輸入中的詞對應的結構。此外，每個結構它們只建立一次，例如`NP(Det(the), N(man))`只建立和壓入棧一次，不管以后`VP -> V NP PP`規約或者`NP -> NP PP`規約會不會用到。
## 4.3 左角落分析器
遞歸下降分析器的問題之一是當它遇到一個左遞歸產生式時，會進入無限循環。這是因為它盲目應用文法產生式而不考慮實際輸入的句子。左角落分析器是我們已經看到的自下而上與自上而下方法的混合體。
語法`grammar1`允許我們對 John saw Mary 生成下面的分析：
```py
>>> text = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> groucho_grammar.productions(rhs=text[1])
[V -> 'shot']
```
對于我們的 WFST，我們用 Python 中的列表的咧表創建一個(n-1) × (n-1)的矩陣，在[4.4](./ch08.html#code-wfst)中的函數`init_wfst()`中用每個標識符的詞匯類型初始化它。我們還定義一個實用的函數`display()`來為我們精美的輸出 WFST。正如預期的那樣，`V`在(1, 2)單元中。
```py
def init_wfst(tokens, grammar):
numtokens = len(tokens)
wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]
for i in range(numtokens):
productions = grammar.productions(rhs=tokens[i])
wfst[i][i+1] = productions[0].lhs()
return wfst
def complete_wfst(wfst, tokens, grammar, trace=False):
index = dict((p.rhs(), p.lhs()) for p in grammar.productions())
numtokens = len(tokens)
for span in range(2, numtokens+1):
for start in range(numtokens+1-span):
end = start + span
for mid in range(start+1, end):
nt1, nt2 = wfst[start][mid], wfst[mid][end]
if nt1 and nt2 and (nt1,nt2) in index:
wfst[start][end] = index[(nt1,nt2)]
if trace:
print("[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" % \
(start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end))
return wfst
def display(wfst, tokens):
print('\nWFST ' + ' '.join(("%-4d" % i) for i in range(1, len(wfst))))
for i in range(len(wfst)-1):
print("%d " % i, end=" ")
for j in range(1, len(wfst)):
print("%-4s" % (wfst[i][j] or '.'), end=" ")
print()
>>> tokens = "I shot an elephant in my pajamas".split()
>>> wfst0 = init_wfst(tokens, groucho_grammar)
>>> display(wfst0, tokens)
WFST 1 2 3 4 5 6 7
0 NP . . . . . .
1 . V . . . . .
2 . . Det . . . .
3 . . . N . . .
4 . . . . P . .
5 . . . . . Det .
6 . . . . . . N
>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar)
>>> display(wfst1, tokens)
WFST 1 2 3 4 5 6 7
0 NP . . S . . S
1 . V . VP . . VP
2 . . Det NP . . .
3 . . . N . . .
4 . . . . P . PP
5 . . . . . Det NP
6 . . . . . . N
```
回到我們的表格表示，假設對于詞 an 我們有`Det`在(2, 3)單元，對以詞 elephant 有`N`在(3, 4)單元，對于 an elephant 我們應該在(2, 4)放入什么？我們需要找到一個形如 _A_ → `Det N`的產生式。查詢了文法，我們知道我們可以輸入(0, 2)單元的`NP`。
更一般的，我們可以在(i, j)輸入 _A_，如果有一個產生式 _A_ → _B_ _C_，并且我們在(i, k)中找到非終結符 _B_，在(k, j)中找到非終結符 _C_。[4.4](./ch08.html#code-wfst)中的程序使用此規則完成 WFST。通過調用函數`complete_wfst()`時設置 `trace`為`True`，我們看到了顯示 WFST 正在被創建的跟蹤輸出：
```py
>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar, trace=True)
[2] Det [3] N [4] ==> [2] NP [4]
[5] Det [6] N [7] ==> [5] NP [7]
[1] V [2] NP [4] ==> [1] VP [4]
[4] P [5] NP [7] ==> [4] PP [7]
[0] NP [1] VP [4] ==> [0] S [4]
[1] VP [4] PP [7] ==> [1] VP [7]
[0] NP [1] VP [7] ==> [0] S [7]
```
例如，由于我們在`wfst[2][3]`找到`Det`，在`wfst[3][4]`找到`N`，我們可以添加`NP`到`wfst[2][4]`。
注意
為了幫助我們更簡便地通過產生式的右側檢索產生式，我們為語法創建一個索引。這是空間-時間權衡的一個例子：我們對語法做反向查找，每次我們想要通過右側查找產生式時不必遍歷整個產生式列表。
圖 4.5：圖數據結構：圖中額外的邊表示非終結符。
我們得出結論，只要我們已經在(0, 7)單元構建了一個`S`節點，表明我們已經找到了一個涵蓋了整個輸入的句子，我們就為整個輸入字符串找到了一個解析。最后的 WFST 狀態如[4.5](./ch08.html#fig-chart-positions2)所示。
請注意，在這里我們沒有使用任何內置的分析函數。我們已經從零開始實現了一個完整的初級圖表分析器！
WFST 有幾個缺點。首先，正如你可以看到的，WFST 本身不是一個分析樹，所以該技術嚴格地說是認識到一個句子被一個語法承認，而不是分析它。其次，它要求每個非詞匯語法生產式是二元的。雖然可以將任意的 CFG 轉換為這種形式，我們寧愿使用這種方法時沒有這樣的規定。第三，作為一個自下而上的語法，它潛在的存在浪費，它會在不符合文法的地方提出成分。
最后，WFST 并不能表示句子中的結構歧義（如兩個動詞短語的讀取）。(1, 7)單元中的`VP`實際上被輸入了兩次，一次是讀取`V NP`，一次是讀取`VP PP` 。這是不同的假設，第二個會覆蓋第一個（雖然如此，這并不重要，因為左側是相同的。）圖表分析器使用稍微更豐富的數據結構和一些有趣的算法來解決這些問題（詳細情況參見本章末尾的進一步閱讀一節）。
注意
**輪到你來：**嘗試交互式圖表分析器應用程序`nltk.app.chartparser()`。
## 5 依存關系和依存文法
短語結構文法是關于詞和詞序列如何結合起來形成句子成分的。一個獨特的和互補的方式，依存語法，集中關注的是詞與其他詞之間的關系。依存關系是一個中心詞與它的依賴之間的二元對稱關系。一個句子的中心詞通常是動詞，所有其他詞要么依賴于中心詞，要么依賴路徑與它聯通。
一個句子的中心詞通常是動詞，所有其他詞要么依賴于中心詞，要么依賴路徑與它聯通。[5.1](./ch08.html#fig-depgraph0)顯示一個依存關系圖，箭頭從中心詞指出它們的依賴。
圖 5.1：依存結構：箭頭從中心詞指向它們的依賴；標簽表示依賴的語法功能如：主語、賓語或修飾語。
[5.1](./ch08.html#fig-depgraph0)中的弧加了依賴與它的中心詞之間的語法功能標簽。例如，I 是 shot（這是整個句子的中心詞）的`SBJ`（主語），in 是一個`NMOD`（elephant 的名詞修飾語）。與短語結構語法相比，依存語法可以作為一種依存關系直接用來表示語法功能。
下面是 NLTK 為依存語法編碼的一種方式——注意它只能捕捉依存關系信息，不能指定依存關系類型：
```py
>>> groucho_dep_grammar = nltk.DependencyGrammar.fromstring("""
... 'shot' -> 'I' | 'elephant' | 'in'
... 'elephant' -> 'an' | 'in'
... 'in' -> 'pajamas'
... 'pajamas' -> 'my'
... """)
>>> print(groucho_dep_grammar)
Dependency grammar with 7 productions
'shot' -> 'I'
'shot' -> 'elephant'
'shot' -> 'in'
'elephant' -> 'an'
'elephant' -> 'in'
'in' -> 'pajamas'
'pajamas' -> 'my'
```
依存關系圖是一個投影，當所有的詞都按線性順序書寫，邊可以在詞上繪制而不會交叉。這等于是說一個詞及其所有后代依賴（依賴及其依賴的依賴，等等）在句子中形成一個連續的詞序列。[5.1](./ch08.html#fig-depgraph0)是一個投影，我們可以使用投影依存關系分析器分析很多英語句子。下面的例子演示`groucho_dep_grammar`如何提供了一種替代的方法來捕捉附著歧義，我們之前在研究短語結構語法中遇到的。
```py
>>> pdp = nltk.ProjectiveDependencyParser(groucho_dep_grammar)
>>> sent = 'I shot an elephant in my pajamas'.split()
>>> trees = pdp.parse(sent)
>>> for tree in trees:
... print(tree)
(shot I (elephant an (in (pajamas my))))
(shot I (elephant an) (in (pajamas my)))
```
這些括號括起來的依存關系結構也可以顯示為樹，依賴被作為它們的中心詞的孩子。
```py
VP -> TV NP
TV -> 'chased' | 'saw'
```
## 5.2 擴大規模
到目前為止，我們只考慮了“玩具語法”，演示分析的關鍵環節的少量的語法。但有一個明顯的問題就是這種做法是否可以擴大到覆蓋自然語言的大型語料庫。手工構建這樣的一套產生式有多么困難？一般情況下，答案是：_ 非常困難 _。即使我們允許自己使用各種形式化的工具，它們可以提供語法產生式更簡潔的表示，保持對覆蓋一種語言的主要成分所需要的眾多產生式之間的復雜的相互作用的控制，仍然是極其困難的。換句話說，很難將語法模塊化，每部分語法可以獨立開發。反過來這意味著，在一個語言學家團隊中分配編寫語法的任務是很困難的。另一個困難是當語法擴展到包括更加廣泛的成分時，適用于任何一個句子的分析的數量也相應增加。換句話說，歧義隨著覆蓋而增加。
盡管存在這些問題，一些大的合作項目在為幾種語言開發基于規則的語法上已取得了積極的和令人印象深刻的結果。例如，詞匯功能語法（LFG）Pargram 項目、中心詞驅動短語結構文法（HPSG）LinGO 矩陣框架和詞匯化樹鄰接語法 XTAG 項目。
## 6 語法開發
分析器根據短語結構語法在句子上建立樹。現在，我們上面給出的所有例子只涉及玩具語法包含少數的產生式。如果我們嘗試擴大這種方法的規模來處理現實的語言語料庫會發生什么？在本節中，我們將看到如何訪問樹庫，并看看開發廣泛覆蓋的語法的挑戰。
## 6.1 樹庫和語法
`corpus`模塊定義了`treebank`語料的閱讀器，其中包含了賓州樹庫語料的 10％的樣本。
```py
>>> from nltk.corpus import treebank
>>> t = treebank.parsed_sents('wsj_0001.mrg')[0]
>>> print(t)
(S
(NP-SBJ
(NP (NNP Pierre) (NNP Vinken))
(, ,)
(ADJP (NP (CD 61) (NNS years)) (JJ old))
(, ,))
(VP
(MD will)
(VP
(VB join)
(NP (DT the) (NN board))
(PP-CLR
(IN as)
(NP (DT a) (JJ nonexecutive) (NN director)))
(NP-TMP (NNP Nov.) (CD 29))))
(. .))
```
我們可以利用這些數據來幫助開發一個語法。例如，[6.1](./ch08.html#code-sentential-complement)中的程序使用一個簡單的過濾器找出帶句子補語的動詞。假設我們已經有一個形如`VP -> Vs S`的產生式，這個信息使我們能夠識別那些包括在`Vs`的擴張中的特別的動詞。
```py
def filter(tree):
child_nodes = [child.label() for child in tree
if isinstance(child, nltk.Tree)]
return (tree.label() == 'VP') and ('S' in child_nodes)
```
PP 附著語料庫`nltk.corpus.ppattach`是另一個有關特別動詞配價的信息源。在這里，我們演示挖掘這個語料庫的技術。它找出具有固定的介詞和名詞的介詞短語對，其中介詞短語附著到`VP`還是`NP`，由選擇的動詞決定。
```py
>>> from collections import defaultdict
>>> entries = nltk.corpus.ppattach.attachments('training')
>>> table = defaultdict(lambda: defaultdict(set))
>>> for entry in entries:
... key = entry.noun1 + '-' + entry.prep + '-' + entry.noun2
... table[key][entry.attachment].add(entry.verb)
...
>>> for key in sorted(table):
... if len(table[key]) > 1:
... print(key, 'N:', sorted(table[key]['N']), 'V:', sorted(table[key]['V']))
```
這個程序的輸出行中我們發現`offer-from-group N: ['rejected'] V: ['received']`，這表示 received 期望一個單獨的`PP`附著到`VP`而 rejected 不是的。和以前一樣，我們可以使用此信息來幫助構建語法。
NLTK 語料庫收集了來自 PE08 跨框架跨領域分析器評估共享任務的數據。一個更大的文法集合已準備好用于比較不同的分析器，它可以通過下載`large_grammars`包獲得（如`python -m nltk.downloader large_grammars`）。
NLTK 語料庫也收集了 _ 中央研究院樹庫語料 _，包括 10,000 句已分析的句子，來自 _ 現代漢語中央研究院平衡語料庫 _。讓我們加載并顯示這個語料庫中的一棵樹。
```py
>>> nltk.corpus.sinica_treebank.parsed_sents()[3450].draw()
```
## 6.2 有害的歧義
不幸的是，隨著文法覆蓋范圍的增加和輸入句子長度的增長，分析樹的數量也迅速增長。事實上，它以天文數字的速度增長。
讓我們在一個簡單的例子幫助下來探討這個問題。詞 fish 既是名詞又是動詞。我們可以造這樣的句子 fish fish fish，意思是 _fish like to fish for other fish_。（用 police 嘗試一下，如果你喜歡更有意思的東西。）下面是“fish”句子的玩具文法。
```py
>>> grammar = nltk.CFG.fromstring("""
... S -> NP V NP
... NP -> NP Sbar
... Sbar -> NP V
... NP -> 'fish'
... V -> 'fish'
... """)
```
現在，我們可以嘗試分析一個較長的句子，fish fish fish fish fish，其中一個意思是：“fish that other fish fish are in the habit of fishing fish themselves”。我們使用 NLTK 的圖表分析器，它在本章前面介紹過。這句話有兩種讀法。
```py
>>> tokens = ["fish"] * 5
>>> cp = nltk.ChartParser(grammar)
>>> for tree in cp.parse(tokens):
... print(tree)
(S (NP fish) (V fish) (NP (NP fish) (Sbar (NP fish) (V fish))))
(S (NP (NP fish) (Sbar (NP fish) (V fish))) (V fish) (NP fish))
```
隨著句子長度增加到（3，5，7，...），我們得到的分析樹的數量是：1; 2; 5; 14; 42; 132; 429; 1,430; 4,862; 16,796; 58,786; 208,012; ….（這是 Catalan 數，我們在[4](./ch04.html#chap-structured-programming)的練習中見過）。最后一個是句子長度為 23 的分析樹的數目，這是賓州樹庫 WSJ 部分的句子的平均長度。對于一個長度為 50 的句子有超過 10<sup>12</sup>的解析，這只是 Piglet 句子長度的一半（[1](./ch08.html#sec-dilemmas)），這些句子小孩可以毫不費力的處理。沒有實際的自然語言處理系統可以為一個句子構建數以百萬計的樹，并根據上下文選擇一個合適的。很顯然，人也不會這樣做！
請注意，這個問題不是只在我們選擇的例子中存在。[(Church & Patil, 1982)](./bibliography.html#church1982csa)指出`PP`附著句法歧義在像[(18)](./ch08.html#ex-pp)這樣的句子中也是按 Catalan 數的比例增長。
```py
def give(t):
return t.label() == 'VP' and len(t) > 2 and t[1].label() == 'NP'\
and (t[2].label() == 'PP-DTV' or t[2].label() == 'NP')\
and ('give' in t[0].leaves() or 'gave' in t[0].leaves())
def sent(t):
return ' '.join(token for token in t.leaves() if token[0] not in '*-0')
def print_node(t, width):
output = "%s %s: %s / %s: %s" %\
(sent(t[0]), t[1].label(), sent(t[1]), t[2].label(), sent(t[2]))
if len(output) > width:
output = output[:width] + "..."
print(output)
```
我們可以觀察到一種強烈的傾向就是最短的補語最先出現。然而，這并沒有解釋類似`give NP: federal judges / NP: a raise`的形式，其中有生性起了重要作用。事實上，根據[(Bresnan & Hay, 2006)](./bibliography.html#bresnan2006gg)的調查，存在大量的影響因素。這些偏好可以用加權語法來表示。
概率上下文無關語法（或 _PCFG_）是一種上下文無關語法，它的每一個產生式關聯一個概率。它會產生與相應的上下文無關語法相同的文本解析，并給每個解析分配一個概率。PCFG 產生的一個解析的概率僅僅是它用到的產生式的概率的乘積。
最簡單的方法定義一個 PCFG 是從一個加權產生式序列組成的特殊格式的字符串加載它，其中權值出現在括號里，如[6.4](./ch08.html#code-pcfg1)所示。
```py
grammar = nltk.PCFG.fromstring("""
S -> NP VP [1.0]
VP -> TV NP [0.4]
VP -> IV [0.3]
VP -> DatV NP NP [0.3]
TV -> 'saw' [1.0]
IV -> 'ate' [1.0]
DatV -> 'gave' [1.0]
NP -> 'telescopes' [0.8]
NP -> 'Jack' [0.2]
""")
```
有時可以很方便的將多個產生式組合成一行，如`VP -> TV NP [0.4] | IV [0.3] | DatV NP NP [0.3]`。為了確保由文法生成的樹能形成概率分布，PCFG 語法強加了約束，產生式所有給定的左側的概率之和必須為 1。[6.4](./ch08.html#code-pcfg1)中的語法符合這個約束：對`S`只有一個產生式，它的概率是 1.0；對于`VP`，0.4+0.3+0.3=1.0；對于`NP`，0.8+0.2=1.0。`parse()`返回的分析樹包含概率：
```py
>>> viterbi_parser = nltk.ViterbiParser(grammar)
>>> for tree in viterbi_parser.parse(['Jack', 'saw', 'telescopes']):
... print(tree)
(S (NP Jack) (VP (TV saw) (NP telescopes))) (p=0.064)
```
現在，分析樹被分配了概率，一個給定的句子可能有數量龐大的可能的解析就不再是問題。分析器將負責尋找最有可能的解析。
## 7 小結
* 句子都有內部組織結構，可以用一棵樹表示。組成結構的顯著特點是：遞歸、中心詞、補語和修飾語。
* 語法是一個潛在的無限的句子集合的一個緊湊的特性；我們說，一棵樹是符合語法規則的或語法樹授權一棵樹。
* 語法是用于描述一個給定的短語是否可以被分配一個特定的成分或依賴結構的一種形式化模型。
* 給定一組句法類別，上下文無關文法使用一組生產式表示某類型 _A_ 的短語如何能夠被分析成較小的序列α<sub>1</sub> ... α<sub>n</sub>。
* 依存語法使用產生式指定給定的中心詞的依賴是什么。
* 一個句子有一個以上的句法分析就產生句法歧義（如介詞短語附著歧義）。
* 分析器是一個過程，為符合語法規則的句子尋找一個或多個相應的樹。
* 一個簡單的自上而下分析器是遞歸下降分析器，在語法產生式的幫助下遞歸擴展開始符號（通常是`S`），嘗試匹配輸入的句子。這個分析器并不能處理左遞歸產生式（如`NP -> NP PP`）。它盲目擴充類別而不檢查它們是否與輸入字符串兼容的方式效率低下，而且會重復擴充同樣的非終結符然后丟棄結果。
* 一個簡單的自下而上的分析器是移位-規約分析器，它把輸入移到一個堆棧中，并嘗試匹配堆棧頂部的項目和語法產生式右邊的部分。這個分析器不能保證為輸入找到一個有效的解析，即使它確實存在，它建立子結構而不檢查它是否與全部語法一致。
## 8 深入閱讀
本章的附加材料發布在`http://nltk.org/`，包括網絡上免費提供的資源的鏈接。關于使用 NLTK 分析的更多的例子，請看在`http://nltk.org/howto`上的分析 HOWTO。
有許多關于句法的入門書籍。[(O'Grady et al, 2004)](./bibliography.html#ogrady2004)是一個語言學概論，而[(Radford, 1988)](./bibliography.html#radford1988tg)以容易接受的方式介紹轉換語法，推薦其中的無限制依賴結構的轉換文法。在形式語言學中最廣泛使用的術語是生成語法，雖然它與生成并沒有關系[(Chomsky, 1965)](./bibliography.html#chomsky1965)。X-bar 句法來自于[(Jacobs & Rosenbaum, 1970)](./bibliography.html#chomsky1970rn)，并在[(Jackendoff, 1977)](./bibliography.html#jackendoff1977xs)得到更深的拓展（The primes we use replace Chomsky's typographically more demanding horizontal bars）。
[(Burton-Roberts, 1997)](./bibliography.html#burtonroberts1997as)是一本面向實踐的關于如何分析英語成分的教科書，包含廣泛的例子和練習。[(Huddleston & Pullum, 2002)](./bibliography.html#huddleston2002cge)提供了一份最新的英語句法現象的綜合分析。
[(Jurafsky & Martin, 2008)](./bibliography.html#jurafskymartin2008)的第 12 章講述英語的形式文法；13.1-3 節講述簡單的分析算法和歧義處理技術；第 14 章講述統計分析；第 16 章講述喬姆斯基層次和自然語言的形式復雜性。[(Levin, 1993)](./bibliography.html#levin1993)根據它們的句法屬性，將英語動詞劃分成更細的類。
有幾個正在進行的建立大規模的基于規則的語法的項目，如 LFG Pargram 項目`http://www2.parc.com/istl/groups/nltt/pargram/`，HPSG LinGO 矩陣框架`http://www.delph-in.net/matrix/`以及 XTAG 項目`http://www.cis.upenn.edu/~xtag/`。
## 9 練習
1. ? 你能想出符合語法的卻可能之前從來沒有被說出的句子嗎？（與伙伴輪流進行。）這告訴你關于人類語言的什么？
2. ? 回想一下 Strunk 和 White 的禁止在句子開頭使用 however 表示“although”的意思。在網上搜索句子開頭使用的 however。這個成分使用的有多廣泛？
3. ? 思考句子<cite>Kim arrived or Dana left and everyone cheered</cite>。用括號的形式表示 and 和 or 的相對范圍。產生這兩種解釋對應的樹結構。
4. ? `Tree`類實現了各種其他有用的方法。請看`Tree`幫助文檔查閱更多細節（如導入 Tree 類，然后輸入`help(Tree)`）。
5. ? 在本練習中，你將手動構造一些分析樹。
1. 編寫代碼產生兩棵樹，對應短語 old men and women 的不同讀法
2. 將本章中表示的任一一顆樹編碼為加標簽的括號括起的形式，使用`nltk.Tree()`檢查它是否符合語法。使用`draw()`顯示樹。
3. 如(a) 中那樣，為 The woman saw a man last Thursday 畫一棵樹。
6. ? 寫一個遞歸函數，遍歷一顆樹，返回樹的深度，一顆只有一個節點的樹的深度應為 0。（提示：子樹的深度是其子女的最大深度加 1。）
7. ? 分析 A.A. Milne 關于 Piglet 的句子，為它包含的所有句子畫下劃線，然后用`S`替換這些（如第一句話變為`S` <cite>when</cite>:lx` `S`）。為這種“壓縮”的句子畫一個樹形結構。用于建立這樣一個長句的主要的句法結構是什么？
8. ? 在遞歸下降分析器的演示中，通過選擇 _Edit_ 菜單上的 _Edit Text_ 改變實驗句子。
9. ? `grammar1`中的語法能被用來描述長度超過 20 詞的句子嗎？
10. ? 使用圖形化圖表分析器接口，嘗試不同的規則調用策略做實驗。拿出你自己的可以使用圖形界面手動執行的策略。描述步驟，并報告它的任何效率的提高（例如用結果圖表示大小）。這些改進取決于語法結構嗎？你覺得一個更聰明的規則調用策略能顯著提升性能嗎？
11. ? 對于一個你已經見過的或一個你自己設計的 CFG，用筆和紙手動跟蹤遞歸下降分析器和移位-規約分析器的執行。
12. ? 我們已經看到圖表分析器增加邊而從來不從圖表中刪除的邊。為什么？
13. ? 思考詞序列：Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo。如`http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo`解釋的，這是一個語法正確的句子。思考此維基百科頁面上表示的樹形圖，寫一個合適的語法。正常情況下是小寫，模擬聽到這句話時聽者會遇到的問題。你能為這句話找到其他的解析嗎？當句子變長時分析樹的數量如何增長？（這些句子的更多的例子可以在`http://en.wikipedia.org/wiki/List_of_homophonous_phrases`找到。）
14. ? 你可以通過選擇 _Edit_ 菜單上的 _Edit Grammar_ 修改遞歸下降分析器演示程序。改變第二次擴充產生式，即`NP -> Det N PP`為`NP -> NP PP`。使用 _Step_ 按鈕，嘗試建立一個分析樹。發生了什么？
15. ? 擴展`grammar2`中的語法，將產生式中的介詞擴展為不及物的，及物的和需要`PP`補語的。基于這些產生式，使用前面練習中的方法為句子 Lee ran away home 畫一棵樹。
16. ? 挑選一些常用動詞，完成以下任務：
1. 寫一個程序在 PP 附著語料庫`nltk.corpus.ppattach`找到那些動詞。找出任何這樣的情況，相同的動詞有兩種不同的附著，其中第一個是名詞，或者第二個是名詞，或者介詞保持不變（正如我們在[2](./ch08.html#sec-whats-the-use-of-syntax)句法歧義中討論過的）。
2. 制定 CFG 語法產生式涵蓋其中一些情況。
17. ? 寫一個程序，比較自上而下的圖表分析器與遞歸下降分析器的效率（[4](./ch08.html#sec-parsing)）。使用相同的語法和輸入的句子。使用`timeit`模塊比較它們的性能（見[4.7](./ch04.html#sec-algorithm-design)，如何做到這一點的一個例子）。
18. 比較自上而下、自下而上和左角落分析器的性能，使用相同的語法和 3 個符合語法的測試句子。使用`timeit`記錄每個分析器在同一個句子上花費的時間。寫一個函數，在這三句話上運行這三個分析器，輸出 3×3 格的時間，以及行和列的總計。討論你的發現。
19. ? 閱讀“garden path”的句子。一個分析器的計算工作與人類處理這些句子的困難性有什么關系？`http://en.wikipedia.org/wiki/Garden_path_sentence`
20. ? 若要在一個窗口比較多個樹，我們可以使用`draw_trees()`方法。定義一些樹，嘗試一下：
```py
>>> from nltk.draw.tree import draw_trees
>>> draw_trees(tree1, tree2, tree3)
```
21. ? 使用樹中的位置，列出賓州樹庫前 100 個句子的主語；為了使結果更容易查看，限制從高度最高為 2 的子樹提取主語。
22. ? 查看 PP 附著語料庫，嘗試提出一些影響`PP`附著的因素。
23. ? 在本節中，我們說過簡單的用術語 n-grams 不能描述所有語言學規律。思考下面的句子，尤其是短語 in his turn 的位置。這是基于 n-grams 的方法的一個問題嗎？
> <cite>What was more, the in his turn somewhat youngish Nikolay Parfenovich also turned out to be the only person in the entire world to acquire a sincere liking to our "discriminated-against" public procurator.</cite> (Dostoevsky: The Brothers Karamazov)
24. ? 編寫一個遞歸函數產生嵌套的括號括起的形式的一棵樹，顯示去掉葉節點之后的子樹的非終結符。于是上面的關于 Pierre Vinken 的例子會產生：`[[[NNP NNP]NP , [ADJP [CD NNS]NP JJ]ADJP ,]NP-SBJ MD [VB [DT NN]NP [IN [DT JJ NN]NP]PP-CLR [NNP CD]NP-TMP]VP .]S`。連續的類別應用空格分隔。
25. ? 從古登堡工程下載一些電子圖書。寫一個程序掃描這些文本中任何極長的句子。你能找到的最長的句子是什么？這么長的句子的句法結構是什么？
26. ? 修改函數`init_wfst()`和`complete_wfst()`，使 WFST 中每個單元的內容是一組非終端符而不是一個單獨的非終結符。
27. ? 思考[4.4](./ch08.html#code-wfst)中的算法。你能解釋為什么分析上下文無關語法是與<cite>n</cite><sup>3</sup>成正比的，其中 _n_ 是輸入句子的長度。
28. ? 處理賓州樹庫語料庫樣本`nltk.corpus.treebank`中的每棵樹，在`Tree.productions()`的幫助下提取產生式。丟棄只出現一次的產生式。具有相同的左側和類似的右側的產生式可以被折疊，產生一個等價的卻更緊湊的規則集。編寫代碼輸出一個緊湊的語法。
29. ★ 英語中定義句子`S`的主語的一種常見的方法是作為`S` _ 的名詞短語孩子 _ 和`VP`的 _ 兄弟 _。寫一個函數，以一句話的樹為參數，返回句子主語對應的子樹。如果傳遞給這個函數的樹的根節點不是`S`或它缺少一個主語，應該怎么做？
30. ★ 寫一個函數，以一個語法（如[3.1](./ch08.html#code-cfg1)定義的語法）為參數，返回由這個語法隨機產生的一個句子。（使用`grammar.start()`找出語法的開始符號；`grammar.productions(lhs)`得到具有指定左側的語法的產生式的列表；`production.rhs()`得到一個產生式的右側。）
31. ★ 使用回溯實現移位-規約分析器的一個版本，使它找出一個句子所有可能的解析，它可以被稱為“遞歸上升分析器”。咨詢維基百科關于回溯的條目`http://en.wikipedia.org/wiki/Backtracking`
32. ★ 正如我們在[7.](./ch07.html#chap-chunk)中所看到的，可以將詞塊表示成它們的詞塊標簽。當我們為包含 gave 的句子做這個的時候，我們發現如以下模式：
```py
gave NP
gave up NP in NP
gave NP up
gave NP NP
gave NP to NP
```
