Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Chương 4: Phân tích cú pháp - Lê Thanh Hương

Phân tích cú pháp
1
Lê Thanh Hương
Bộ môn Hệ thống Thông tin
Viện CNTT &TT – Trường ĐHBKHN
Email: huonglt-fit@mail.hut.edu.vn
Bài toán PTCP
P
T
C
cây PTCP mẫu
độ chính xác
tính
điể
2
P
Văn phạm
câu 
Các bộ PTCP 
hiện nay có độ 
chính xác cao
(Eisner, Collins, 
Charniak, etc.)
cây cú pháp
m
Khái niệm về văn phạm
z Phân tích câu “Bò vàng gặm cỏ non”
z Cây cú pháp:
z Tập luật
z C Æ CN VN
z CN Æ DN
z VN Æ ĐgN
z ĐgN Æ ĐgT DN
z DN Æ DT TT
3
Văn phạm
z Một văn phạm sản sinh là một hệ thống
z G = ( T, N, S, R ), trong đó
z T (terminal) – tập ký hiệu kết thúc
z N (non terminal) – tập ký hiệu không kết thúc
z S (start) – ký hiệu khởi đầu
z R (rule) – tập luật
z R = { αÆ β | α, β ∈ (T∪N) } 
z αÆ β gọi là luật sản xuất
4
Dạng chuẩn Chomsky
z Mọi NNPNC không chứa ε đều có thể sinh từ 
một văn phạm tnđó mọi sản xuất đều có 
dạng A Æ BC hoặc A Æ a, với A,B,C∈N và a 
∈T
z Ví dụ: Tìm dạng chuẩn Chomsky cho văn 
phạm G với T = {a,b}, N ={S,A,B}, R như sau:
z S Æ bA|aB
z A ÆbAA|aS|a
z B Æ aBB|bS|b
5
Nhắc lại về văn phạm
z Văn phạm: 1 tập luật viết lại
z Ký hiệu kết thúc: các ký hiệu không thể phân rã được 
nữa.
z Ký hiệu không kết thúc: các ký hiệu có thể phân rã 
được.
Xét ă h G
6
z v n p ạm :
S → NP VP
NP → John, garbage
VP → laughed, walks
G có thể sinh ra các câu sau:
John laughed. John walks.
Garbage laughed. Garbage walks.
Cấu trúc ngữ pháp
Cây cú pháp biểu diễn cấu trúc ngữ pháp của một câu. 
Bò vàng gặm cỏ non.
C
CN VN
7
DT
Bò
ĐgT
gặm
DT
cỏ
TT
non
TT
vàng
DN ĐgN
DN
Các ứng dụng của PTCP
ƒ Dịch máy (Alshawi 1996, Wu 1997, ...)
tiếng Anh tiếng Việt
các thao tác 
với cây
8
ƒ Nhận dạng tiếng nói sử dụng PTCP (Chelba et al 1998)
Put the file in the folder. 
Put the file and the folder.
Các ứng dụng của PTCP
ƒ Kiểm tra ngữ pháp (Microsoft)
ƒ Trích rút thông tin (Hobbs 1996)
9
Kho văn bản
NY Times
CSDL
câu truy vấn
Văn phạm phi ngữ cảnh 
(Context-Free Grammar)
 còn gọi là văn phạm cấu trúc đoạn
z G = 
z T – tập các ký hiệu kết thúc (terminals)
z N - tập các ký hiệu không kết thúc (non-terminals)
z P – ký hiệu tiền kết thúc (preterminals), khi viết lại trở 
thành ký hiệu kết thúc P ⊂ N
10
 , 
z S – ký hiệu bắt đầu
z R: X → γ , X là ký hiệu không kết thúc; γ là chuỗi các 
ký hiệu kết thúc và không kết thúc (có thể rỗng)
z Văn phạm G sinh ra ngôn ngữ L
z Bộ nhận dạng: trả về yes hoặc no
z Bộ PTCP: trả về tập các cây cú pháp
So với văn phạm cảm ngữ cảnh 
R: αAγ ⇒ αβγ
z Văn phạm ngữ cấu:
z α→β, với α ∈ V+ , β ∈ V*
z Văn phạm cảm ngữ cảnh:
z r = α→β, với α ∈ V+ , β ∈ V* , ⏐α⏐≤⏐β⏐
z và α1Aα2→α1β’α2 với β’≠ε
z Văn phạm phi ngữ cảnh:
z A → θ, A ∈ N,
ới θ V* ( T N )*
11
z v ∈ = ∪ 
z Văn phạm chính qui:
z A → aB, 
z A → Ba, 
z A → a, 
với A, B ∈ N, a ∈ T. 
VPCQ
VPPNC
VPCNC
VPNC
Văn phạm phi ngữ cảnh
12
Áp dụng tập luật ngữ pháp
z S
→ NP VP
→ DT NNS VBD
→ The children slept
13
z S
→ NP VP
→ DT NNS VBD NP
→ DT NNS VBD DT NN
→ The children ate the cake
Cấu trúc đoạn đệ qui
14
Văn phạm cho ngôn ngữ tự nhiên 
có nhập nhằng
S
NP VP
Nhập nhằng - PP
có thể gắn tại 2 điểm (với VP 
hoặc với NP)
John saw snow on the campus
15
0 John PP
NP
1 saw NP
2 snow
3 on
4 the 5 campus 6
PTCP kiểu trên xuống
z Hướng đích
z Khởi đầu với 1 danh sách các ký hiệu cần triển khai (S, 
NP,VP,) 
z Viết lại các đích trong tập đích bằng cách:
S
NP VP
.
16
z tìm luật có vế trái trùng với đích cần triển khai
z triểu khai nó với vế phải luật, tìm cách khớp với câu đầu vào
z Nếu 1 đích có nhiều cách viết lại Æ chọn 1 luật để áp 
dụng (bài toán tìm kiếm)
z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc 
tìm kiếm sâu (depth-first search)
Khó khăn với PTCP trên xuống
z Các luật đệ qui trái
z PTCP trên xuống rất bất lợi khi có nhiều luật có cùng vế trái
S→NP X1 S→NP X2 S→NP X600 S→VP Y1
17
z Nhiều thao tác thừa: triển khai tất cả các nút có thể phân tích trên 
xuống 
z PTCP trên xuống sẽ làm việc tốt khi có chiến lược điều khiển ngữ 
pháp phù hợp
z PTCP trên xuống không thể triển khai các ký hiệu tiền kết thúc 
thành các ký hiệu kết thúc. Trên thực tế, người ta thường sử dụng 
phương pháp dưới lên để làm việc này. 
z Lặp lại công việc: bất cứ chỗ nào có cấu trúc giống nhau
PTCP dưới lên
z Hướng dữ liệu
z Khởi tạo với xâu cần phân tích
z Nếu chuỗi trong tập đích phù hợp với vế phải của 1 luật 
→ thay nó bằng vế trái của luật
.
S
NP VP
18
 .
z Kết thúc khi tập đích = {S}.
z Nếu vế phải của các luật khớp với nhiều luật trong tập 
đích, cần lựa chọn luật áp dụng (bài toán tìm kiếm)
z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc 
tìm kiếm sâu (depth-first search)
Khó khăn với PTCP dưới lên
z Không hiệu quả khi có nhiều nhập nhằng mức 
từ vựng
z Lặp lại công việc: bất cứ khi nào có cấu trúc con 
chung
19
z Cả PTCP TD (LL) và BU (LR) đều có độ phức 
tạp là hàm mũ của độ dài câu.
Thuật toán CKY (bộ nhận dạng)
ƒ Vào: xâu n từ
ƒ Ra: yes/no
ƒ Cấu trúc ngữ pháp: bảng n x n (chart table)
20
ƒ hàng đánh số 0 đến n-1
ƒ cột đánh số 1 đến n
ƒ cell [i,j] liệt kê tất cả các nhãn cú pháp giữa i và j
Thuật toán CKY (bottom-up)
ƒ for i := 1 to n
ƒ Thêm tất cả từ loại của từ thứ i vào ô [i-1,i]
ƒ for width := 2 to n
ƒ for start := 0 to n-width
end := start + width
21
ƒ 
ƒ for mid := start+1 to end-1
ƒ for mọi nhãn cú pháp X trong [start,mid]
ƒ for mọi nhãn cú pháp Y trong [mid,end]
ƒ for mọi cách kết hợp X và Y (nếu có)
ƒ Thêm nhãn kết quả vào [start,end] nếu chưa 
có nhãn này
Ví dụ
Bò vàng gặm cỏ non
1 2 3 4 5
0
DT
CN
DN
C
22
1
TT
2
ĐgT
VN
ĐgN
3
DT DN
4
TT
Văn phạm phi ngữ cảnh
1. Start→ S
2. S → NP VP
3. NP → Det Noun
4. NP → Name
9. V → ate
10. Name → John
11. Name → ice-cream, snow
12. Noun → ice-cream, pizza
23
5. NP → Name PP
6. PP → Prep NP
7. VP → V NP
8. VP → V NP PP
13. Noun → table, guy, campus
14. Det → the
15. Prep → on
Luật kết hợp
z Ô Cell[i,j] chứa nhãn X nếu
z Có luật X→YZ;
z Cell[i,k] chứa nhãn Y và ô Cell[k,j] chứa nhãn Z, 
ằ
24
với k n m giữa i và j;
z VD: NP → DT [0,1] NN[1,2]
CKY phải sử dụng luật nhị 
phân
z Chuyển VP→V NP PP thành:
8.a. VP→V Arguments
8 b Arguments → NP PP
25
. . 
CKY chart
1 2 3 4 5 6 7 8
0 DT
1 NN
2 VBD
“ The guy ate the ice-cream on the table”
26
3 DT
4 NN
5 IN
6 DT
7 NN
Áp dụng thao tác ‘dán’
1 2 3 4 5 6 7 8
0 DT NP
1 NN
27
2 VBD
3 DT
4 NN
5 IN
6 DT
7 NN
Nhập nhằng!
1 2 3 4 5 6 7 8
0 DT NP S
1 NN
2 VBD VP
5. NP → NN PP
8.a. VP→V Arguments
8.b. Arguments → NP PP
28
3 DT NP NP, 
Args
4 NN
5 IN PP
6 DT NP
7 NN
Thuật toán Earley (top-down)
z Tìm các nhãn và các nhãn thiếu (partial constituents) từ 
đầu vào
z A → B C . D E là nhãn thiếu:
A D+ =
A
29
z Tiến hành dần từ trái sang phải
B C D E
A → B C . D E
B C D E
A → B C D . E
Ví dụ
ROOT → S NP→ Papa
S → NP VP N → caviar
NP → Det N N → spoon 
30
NP → NP PP V → ate
VP → VP PP P → with
VP → V NP Det → the
PP → P NP Det → a
Recursive Descent (Đệ quy)
z 0 ROOT → . S 0
z 0 S → . NP VP 0
ROOT → S VP → VP PP NP → Papa V → ate
S → NP VP VP → V NP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
31
z 0 NP → . Papa 0 
z 0 NP → Papa . 1
z 0 S → NP . VP 1 
Root S VP
NP
VP
Papa
ROOT→ S S → NP VP NP → Papa
VP
Papa
Goal stack
Recursive Descent
z 0 S → NP . VP 1
z 1 VP → . VP PP 1 
ROOT → S VP → VP PP NP → Papa V → ate
S → NP VP VP → V NP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
32
ƒ 1 VP → . VP PP 1
ƒ 1 VP → . VP PP 1
1 VP → . VP PP 1 stack overflowed
VP→ VP PP VP→ VP PP
PP
VP
PP
VP
PP
PP
VP
PP
PP
VP→ VP PP
VP PP
PP
PP
VP→ VP PP
Recursive Descent
ROOT → S VP → V NP NP → Papa V → ate
S → NP VP VP → VP PP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
ƒ 0 ROOT → . S 0
ƒ 0 S → . NP VP 0
NP P 
33
z 1 VP → . V NP 1 sau . = nonterminal, lặp đi lặp lại việc tìm ký hiệu này (“predict”)
ƒ 1 V → . ate 1 sau . = terminal, tìm nó ở đầu vào (“scan”)
ƒ 1 V → ate . 2 sau . = rỗng, đích con của cha nó đã hoàn chỉnh (“attach”)
z 1 VP → V . NP 2 predict (đích con tiếp theo)
ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng 
ƒ 2 NP → ... . 7 we hoàn thành đích con NP của cha nó Æ attach
z 1 VP → V NP . 7 attach
z 0 S → NP VP . 7 attach 
ƒ 0 → . apa 0 
ƒ 0 NP → Papa . 1
ƒ 0 S → NP . VP 1
Recursive Descent
z 0 ROOT → . S 0
z 0 S → . NP VP 0
z 0 NP → . Papa 0
ROOT → S VP → V NP NP → Papa V → ate
S → NP VP VP → VP PP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
thực hiện bằng lời gọi hàm:
S() gọi NP() và VP(), VP được triển khai 1
34
z 0 NP → Papa . 1
z 0 S → NP . VP 1
z 1 VP → . V NP 1
ƒ 1 V → . ate 1
ƒ 1 V → ate . 2
z 1 VP → V . NP 2
ƒ 2 NP → . ... 2
ƒ 2 NP → ... . 7
z 1 VP → V NP . 7
z 0 S → NP VP . 7
cần quay lại để thử 1 luật VP khác
cách đệ qui
Recursive Descent
ROOT → S VP → V NP NP → Papa V → ate
S → NP VP VP → VP PP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
ƒ 0 ROOT → . S 0
ƒ 0 S → . NP VP 0
ƒ 0 NP → . Papa 0
35
ƒ 1 VP → . V NP 1
ƒ 1 V → . ate 1
ƒ 1 V → ate . 2
ƒ 1 VP → V . NP 2
ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng
ƒ 2 NP → ... . 4 ... đoạn NP đúng là từ 2 đến 4 
chỗ này cũng cần quay lại
ƒ 0 NP → Papa . 1
ƒ 0 S → NP . VP 1
ƒ 1 VP → . VP PP 1
Recursive Descent
ROOT → S VP → V NP NP → Papa V → ate
S → NP VP VP → VP PP N → caviar P → with
NP → Det N PP → P NP N → spoon Det → the
NP → NP PP Det → a
0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
ƒ 0 ROOT → . S 0
ƒ 0 S → . NP VP 0
NP P 
36
ƒ 1 VP → . VP PP 1
1 VP → . VP PP 1
1 VP → . VP PP 1
stack overflowed
không giải quyết được gì
– cần thay đổi tập luật để loại trừ đệ qui trái
ƒ 0 → . apa 0
ƒ 0 NP → Papa . 1
ƒ 0 S → NP . VP 1
ƒ 1 VP → . VP PP 1 
ƒ 1 VP → . VP PP 1
Thuật toán Earley
z Thuật toán Earley giống thuật toán đệ qui nói trên, nhưng giải 
quyết được vấn đề đệ qui trái. 
z Sử dụng bảng phân tích giống thuật toán CKY, nhằm lưu lại các 
thông tin đã tìm thấy Æ lập trình động “Dynamic programming.”
Các thao tác của thuật toán
37
z Xử lý phần đi sau dấu . theo kiểu đệ qui :
z Nếu là từ, quét (scan) đầu vào để xem có phù hợp không
z Nếu là ký hiệu không kết thúc, đoán (predict) các khả năng để 
khớp nó (giảm số phép tiên đoán bằng cách nhìn trước k ký 
hiệu từ đầu vào và chỉ sử dụng các luật phù hợp với k ký hiệu 
đó)
z Nếu rỗng, ta đã hoàn thành một thành phần ngữ pháp, gắn 
(attach) nó vào những chỗ liên quan
0
0 ROOT . S
khởi tạo
tương đương với (0, ROOT → . S)
38
0
0 ROOT . S
0 S . NP VP
predict luật có vế trái là S
(0, S → . NP VP)
39
0
0 ROOT . S
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
predict luật có VT = NP
(có 3 luật phù hợp)
40
0
0 ROOT . S
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
0 D t th
predict luật có VT = Det (2 luật)
41
e . e
0 Det . a
0
0 ROOT . S
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
0 D t th
predict luật có VT = NP
ta đã làm việc này ở bước trước, vì vậy không làm lại!
Chú ý: ta phải làm lại việc này với luật đệ qui trái
42
e . e
0 Det . a
0 Papa 1 
0 ROOT . S 0 NP Papa .
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
0 D t th
scan: từ phù hợp từ đầu vào
43
e . e
0 Det . a
0 Papa 1 
0 ROOT . S 0 NP Papa .
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
0 D t th khô hù hợ
44
e . e
0 Det . a
scan: ng p p
0 Papa 1 
0 ROOT . S 0 NP Papa .
0 S . NP VP
0 NP . Det N
0 NP . NP PP
0 NP . Papa
0 D t th
45
e . e
0 Det . a scan: không phù hợp
0 Papa 1
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP
0 NP . Papa
0 D t th
attach NP mới tạo (bắt đầu từ 0) với 
các phần liên quan (các phần chưa 
hoàn thành kết thúc tại 0 và có NP sau 
dấu . )
46
e . e
0 Det . a
0 Papa 1
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th
predict
47
e . e
0 Det . a
0 Papa 1
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
predict
48
e . e .
0 Det . a
0 Papa 1
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
predict
49
e . e .
0 Det . a 1 V . ate
0 Papa 1
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
predict
50
e . e .
0 Det . a 1 V . ate
0 Papa 1 
0 ROOT . S 0 NP Papa .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP predict
51
e . e .
0 Det . a 1 V . ate
1 P . with
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
52
e . e .
0 Det . a 1 V . ate
1 P . with
scan: thành công!
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
53
e . e .
0 Det . a 1 V . ate
1 P . with scan: không hợp
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP 1 VP V . NP
0 NP . Det N 0 NP NP . PP
0 NP . NP PP 1 VP . V NP
0 NP . Papa 1 VP . VP PP
0 D t th 1 PP P NP
attach
54
e . e .
0 Det . a 1 V . ate
1 P . with
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP 1 VP V . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa
0 D t th 1 PP P NP
predict
55
e . e .
0 Det . a 1 V . ate
1 P . with
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP 1 VP V . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa
0 D t th 1 PP P NP 2 D t th
predict (các bước sau tương tự)
56
e . e . e . e
0 Det . a 1 V . ate 2 Det . a
1 P . with
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP 1 VP V . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa
0 D t th 1 PP P NP 2 D t th
predict
57
e . e . e . e
0 Det . a 1 V . ate 2 Det . a
1 P . with
0 Papa 1 ate 2
0 ROOT . S 0 NP Papa . 1 V ate .
0 S . NP VP 0 S NP . VP 1 VP V . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa
0 D t th 1 PP P NP 2 D t th
scan (lúc này thất bại vì 
P khô hải là từ t ... OT S .
4 P . with
0 Papa 1 ate 2 the 3 caviar 4 with 5
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th
78
e . e . e . e . e . e
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a
1 P . with 0 ROOT S .
4 P . with
0 Papa 1 ate 2 the 3 caviar 4 with 5
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th
79
e . e . e . e . e . e
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a
1 P . with 0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
80
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
81
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
82
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
83
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 6 N spoon .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
84
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 6 N spoon .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N 5 NP Det N .
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
85
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
 ate 2 the 3 caviar 4 with 5 a 6 spoon 7
 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 6 N spoon .
P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N 5 NP Det N .
PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar 4 PP P NP .
P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon 5 NP NP . PP
PP 2 NP . Papa 0 S NP VP . 5 NP . Papa
P 2 D t th 1 VP VP PP 5 D t th
86
e . e . e . e
2 Det . a 4 PP . P NP 5 Det . a
0 ROOT S .
4 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
87
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP
1 P . with 0 ROOT S .
4 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
88
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S .
4 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
89
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
90
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
91
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
92
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
93
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
94
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 ROOT S .
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
95
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 ROOT S .
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
96
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 ROOT S .
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
97
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 ROOT S .
0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7
0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar .  6 N spoon .
0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N .
0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP .
0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP
0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP .
0 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 
98
e . e . e . e . .
0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP
1 P . with 0 ROOT S . 1 VP V NP .
4 P . with 2 NP NP . PP
0 S NP VP .
1 VP VP . PP
7 P . with
0 ROOT S .
Vấn đề với PTCP trên xuống: đệ qui 
trái
VP
VP PP
gắn liên tục các luật mới 
vào cây trước khi thấy 
PP
99
VP PP
VP PP
s
Æ cần đoán trước số PP 
cần ở đầu vào
 nhưng thuật toán Earley Ok!
VP
PPVP
1 VP → . VP PP
(cột 1)
100
attach
VP
V NP
VP
PP
ate the caviar
1 VP → VP . PP
(cột 4)
 nhưng thuật toán Earley Ok!
VP
VP
PPVP
1 VP → . VP PP
(cột1)
attach
có thể dùng lại
101
VP
V NP
VP
PP
PP
1 VP → VP . PP
ate the caviar
with a spoon
(cột 7)
 nhưng thuật toán Earley Ok!
VP
VP
PPVP
1 VP → . VP PP
có thể dùng lại
(cột1)
102
VP
V NP
VP
PP
PP
ate the caviar
with a spoon
in his bed
1 VP → VP PP .
(cột 10)
 nhưng thuật toán Earley Ok!
VP
PPVP
1 VP → . VP PP
có thể dùng lại
VP
VP
PP
1 VP → VP . PP(cột1) attach
103
VP
V NP
VP
PP
PP
ate the caviar
with a spoon
in his bed
(cột10)
Phục hồi cây cú pháp
Sử dụng thuật toán dùng queue đơn giản, 
dựa trên các thành phần có ích
• 1 thành phần ở trạng thái kết thúc là có ích 
• If s=[A →α•Β,i] trong tập đích k & có ích
• then q=[A →αΒ •,k] & item r= [B →γ •,j] là 
có ích
[s,itrong tập trạng thái j 
i k j
q r
α γ
104
Đánh dấu tất cả các thành phần trong tập trạng thái Sn ở dạng 
Start → αS•, 0
for j=n downto 0 do
for i=0 to j do
for mọi bộ đã đánh dấu [s,i] trong tập trạng thái j do
for k=i to j do 
if [q,i]∈Sk & [r,k] ∈Sj & s= q⊗r then
đánh dấu [q,i] và [r,k] 
[s,i] : một thành phần với luật s & trả về con trỏ i.
Ưu điểm
z Thuật toán Earley thực hiện một vài phép lọc 
top-down: bất cứ thành phần nào (state, or 
triple) được đưa vào tập trạng thái cần tương 
thích với phần đã được sinh ra ở bên trái Ví
105
 . 
dụ: S⇒ wi trong đó wi là phần của câu đã 
được duyệt qua
wi
S
*
Nhược điểm
z Biểu diễn luật: Explicit representation of 
rules: wastes time building them. 
z Thực hiện phép lọc bên trái nhưng không lọc 
106
bên phải
Phép lọc nhìn trước cho ký hiệu không kết thúc 
A:
FIRST(A)= {x|A ⇒ xδ }, x= 1 token
v.d., FIRST(S)= who, did, the, etc.
Các phương pháp khác
z Các phương pháp khác ứng với các cách khác nhau 
để tìm các đoạn
z Đoạn X[i, j] là đoạn có nhãn X phủ đầu vào từ I đến j
Example: 
John ate ice cream on the table
107
0 1 2 - 3 4 5 6
PP[3,6]; S[0,6]; 
z Biểu diễn không gian tìm kiếm như cây and-or
z Disjuncts (or) = các đường phân tích khác nhau
z Conjuncts (and) = vế phải của luật, ví dụ vế phải của 
S là NP VP 
PTCP là việc tìm kiếm
Det(0,1) Noun(1, 2)
S(0, 7)
0 the 1 guy 2 saw 3 ice-cream 4 on 5 the 6 hill 7
NP(0, 1) VP(1, 8) NP(0, 2)
V(1, 2)
VP(2, 7)
V(2, 3) NP(3,7) NP(3 4)
Name (0, 1)
108
NP(5, 7)
Det(5,6) Noun(6,7)
the hill
NP(5,7)
Name(5,6)
Name(3, 4) PP(4, 7)
the guy
saw
, 
Prep(4, 5)
on
ice-cream
PTCP góc trái (Left-corner parsing)
z Nhìn từ dưới lên để 
tìm ký hiệu đầu tiên 
(left-corner) của đoạn, 
sau đó phân tích phần 
còn lại theo kiểu trên 
ố
S
NP VP
S→ NP VP
NP→ the Noun
VP→ ate NP
109
xu ng
z Tìm cách kết hợp các 
đặc trưng tốt nhất của 
tìm phân tích trên 
xuống và dưới lên
the
Noun
1
2
tìm 
predict
ate
Phương pháp này làm việc tốt với ngôn ngữ với thành 
phần quan trọng đặt ở đầu như tiếng Anh. Các tiếng Đức, 
Hà Lan, Nhật là ngôn ngữ có phần quan trọng đặt cuối.