最簡單的grammar稱為context-free grammar(CFG)。CFG由許多規則組成，規則左邊的符號可以展開成右邊的一到多個符號。
In [2]:
import nltk
from nltk import CFG
In [3]:
# 也可以將grammar存在檔案中，透過
# nltk.data.load('file:mygrammar.cfg')
# 來讀取
grammar1 = 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"
""")
grammar1
Out[3]:
In [4]:
sent = "Mary saw Bob".split()
rd_parser = nltk.parse.RecursiveDescentParser(grammar1)
rd_parser.parse(sent).next()
Out[4]:
使用CFG來產生syntax tree，很容易遇到structurally ambiguous的問題，例如"the dog saw a man in the park"，就有兩種不同的tree。在下面的例子中，稱為PP attachment ambiguous，用CFG無法判斷"in the park"是要修飾"a man"還是修飾"saw"。
In [5]:
sent = "the dog saw a man in the park".split()
trees = rd_parser.parse(sent)
trees.next()
Out[5]:
In [6]:
trees.next()
Out[6]:
In [8]:
grammar2 = 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'
""")
這是一種top-down的方法，從最上層的S開始，recursive嘗試所有可能的展開規則，如果展開不下去，就會backtracking到上一個狀態。如果syntax tree不是唯一解，所有可能的展開規則都會被記錄下來。
缺點:
NP -> NP PP，會造成無窮迴圈這種方法的資料結構由一個stack及一個queue組成，stack包含已經處理的token，queue則包含未處理的token。
演算法的每個循環中，有兩種動作可以選擇：shift或reduce。
在設計演算法時，要考慮什麼時候用shift或reduce，其次是reduction要用那一種規則。例如「永遠先作reduce，不能reduce時才作shift」、「reduce時優先用最多token的規則」。
優點: 每個token只會用到一次，所以不會浪費時間
缺點: 因為無法回復上一動，如果一開始的parsing有問題，可能無法產生syntax tree。
Left-corner與recursive decent幾乎一樣，只差在展開時會查表，看下一個token是否符合table。
這種parser在開始前，會建一個表格，第一欄是所有的non-terminal，第二欄展開後的第一個non-terminal。例如S, NP表示所有規則都是S -> NP ...。例如NP, Det PropN表示規則有NP -> Det ...及NP -> PropN ...兩種。
chart parser用dynamic programming的技巧，也就是將計算的中間結果存下來給後面用。
演算法會建一個表格，稱為WFST(well-formed substring table)。WFST[0][2]代表第0和第1個字的可能結果。
一開始會先從WFST[0][1], WFST[1][2]...開始，先嘗試找一個token對應的non-terminal。接下來嘗試將第0和1個non-terminal結合，將結果存在WFST[0][2]。這樣一層層往上作，直到WFST[0][7]=S為止。
缺點:
In [14]:
groucho_grammar = 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 [17]:
sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
parser = nltk.ChartParser(groucho_grammar)
trees = parser.parse(sent)
trees.next()
Out[17]:
In [18]:
trees.next()
Out[18]:
In [ ]: