LỜI NÓI ĐẦU
Xử lý ngôn ngữ tự nhiên nói chung và phân tích cú pháp ngôn ngữ tự nhiên nói
riêng là những vấn đề quan trọng của trí tuệ nhân tạo, được nhiều nhà khoa học trên
thế giới quan tâm nghiên cứu trong suốt 50 năm qua. Các ứng dụng trong lĩnh vực
này rất phong phú. Ta có thể điểm qua một số ứng dụng chính như dịch máy, kiểm
tra và chữa lỗi văn bản, chuyển giao diện người – máy sang ngôn ngữ tự nhiên,
nhận dạng chữ viế
t, thiết kế người máy có khả năng hiểu và nói được tiếng của con
người…
Bài toán phân tích cú pháp ngôn ngữ tự nhiên bằng máy tính là bài toán lớn và
phức tạp. Với tiếng Việt - một ngôn ngữ rất phức tạp thì dường như bài toán này lại
càng khó khăn hơn. Chúng ta đã có một số công trình nghiên cứu về xử lý tiếng
Việt và đã đạt được một số thành công nhất định. Tuy nhiên, cho đến nay bài toán
phân tích cú pháp tiếng Việt v
ẫn chưa được giải quyết triệt để. Một trong những lý
do chính là vì chúng ta chưa nghiên cứu một cách có hệ thống ngữ pháp tiếng Việt
và cơ sở lý thuyết về xây dựng những trình phân tích cú pháp cho tiếng Việt còn
tương đối ít và chưa hoàn chỉnh.
Các mô hình văn phạm phi ngữ cảnh và mạng chuyển được sử dụng rộng rãi
trong mô tả cú pháp không chỉ của các ngôn ngữ lập trình mà cả các ngôn ngữ tự
nhiên. Trong khoá luậ
n này, em sẽ tập trung nghiên cứu việc vận dụng các mô hình
này cho bài toán cụ thể là phân tích cú pháp tiếng Việt. Ngôn ngữ Việt có nhiều
điểm khác so với các ngôn ngữ phổ biến, đã được nghiên cứu nhiều như tiếng Anh
hay tiếng Pháp. Do đó, chúng ta không thể áp dụng hoàn toàn những kết quả đã đạt
được đối với các ngôn ngữ này vào tiếng Việt.
Khoá luận trình bày các vấn đề sau:
• Khái quát vấn đề phân tích văn bản
• Vận dụng các mô hình văn phạm phi ngữ cảnh và mạng chuyển đệ quy để
mô tả ngôn ngữ tự nhiên

nghệ Thông tin, Trung tâm Khoa học Tự nhiên và Công nghệ Quốc gia, nơi em thực
tập trong thời gian qua. Em xin chân thành cảm ơn.
Em xin chân thành cảm ơn các thầy cô giáo trong và ngoài Khoa Toán-Cơ-Tin
học đã truyền đạt cho em những kiến thức, trang bị cho em những hành trang quý
giá trước khi em ra trường. Em xin chân thành cảm ơn các thầy cô giáo trong Bộ
môn Tin học đã tạo điều kiện cho em được thực hiện một số xêmina khoa học liên
quan đến đề tài, và đóng góp nhiều ý kiến quý báu, kịp thời. Xin cảm ơn các bạn
sinh viên đã động viên, giúp đỡ tôi thực hiện đề tài này.
Hà Nội, ngày 10 tháng 5 năm 2002
Sinh viên
Lê Hồng Phươ
ng
Khoá luận tốt nghiệp
2

Mục lục
LỜI NÓI ĐẦU ..................................................................1

Danh mục hình .............................................................................................5

Danh mục bảng.............................................................................................5

Chương 1. Mở đầu...........................................................7

1.1. Tổng quan về vấn đề phân tích văn bản........................................... 7

1.2. Bài toán phân tích cú pháp............................................................... 7

1.3. Nội dung khoá luận .......................................................................... 8


4.2. Xây dựng văn phạm tiếng Việt ...................................................... 38

Khoá luận tốt nghiệp
3

4.2.1. Danh ngữ..........................................................................................39

4.2.2. Động ngữ ..........................................................................................41

4.2.3. Tính ngữ............................................................................................44

4.2.4. Câu đơn hai thành phần ...................................................................45

4.2.5. Văn phạm tiếng Việt .........................................................................47

Chương 5. Cài đặt chương trình ....................................49

5.1. Cấu trúc dữ liệu.............................................................................. 49

5.2. Cài đặt thuật toán ........................................................................... 51

5.3. Thể hiện kết quả phân tích ............................................................. 52

5.4. Đánh giá kết quả............................................................................. 57

Phụ lục .........................................................................58

Bài toán tách từ vựng tiếng Việt ...........................................................58

1. Đặt bài toán............................................................................................58

Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên .................................25

Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại .....................................25

Hình 12. Cấu trúc của câu cần phân tích...................................................................26

Hình 13. Mạng chuyển đệ quy làm ví dụ trong phân tích từ trên xuống..................35

Hình 14. Giao diện chương trình phân tích cú pháp tiếng Anh................................53

Hình 15. Phương pháp xây dựng ôtômát âm tiết ......................................................59

Hình 16. Phương pháp xây dựng ôtômát từ vựng.....................................................59

Hình 17. Một tình huống nhập nhằng .......................................................................60

Hình 18. Các phương án phân tích cho một câu tiếng Việt nhập nhằng ..................62

Hình 19. Cây phân tích ứng với cách tách từ đúng...................................................62Danh mục bảng
Bảng 1. Phân tích từ trên xuống, ưu tiên chiều sâu cho văn phạm phi ngữ cảnh.....15

Bảng 2. Một văn phạm phi ngữ cảnh đơn giản.........................................................20

Bảng 3. Quá trình phân tích từ trên xuống................................................................35

Bảng 4. Phân tích từ trên xuống kết hợp quay lui cho mạng chuyển đệ quy............36


dựa trên mối liên hệ của câu với hiện thực. Ý nghĩa thực tế của câu phụ thuộc
rất nhiều vào ngữ cảnh diễn ra lời nói. Do vậy, quá trình phân tích này rất khó
thực hiện được bằng máy tính. Thường thì việc phân tích câu chỉ dừng ở phân
tích ngữ nghĩa, còn việc phân tích thực chứng do người dùng tự quyết định.
1.2. Bài toán phân tích cú pháp
Phân tích cú pháp đưa ra mô tả về quan hệ và vai trò ngữ pháp của các từ, các
cụm từ (hoặc ngữ) trong câu, đồng thời đưa ra hình thái của câu. Đầu vào của giai
đoạn này là câu đã được phân tách từ, trong đó mỗi từ có đặc điểm hình thái xác định.
Quá trình kiểm tra cú pháp tiến hành phân tích và tổ hợp các từ ở đầu vào, dựa trên
các luật cú pháp để loại bỏ các trường hợp bất quy tắc và từng bước dựng lên cấ
u trúc
cú pháp (cây phân tích) của câu. Kết quả cần đạt được là hình thái của câu.
Cú pháp là chủ đề nghiên cứu của hai cộng đồng gồm những người làm ngôn ngữ
và những người làm tin học. Với những người làm ngôn ngữ thì ngôn ngữ là đối
tượng nghiên cứu, cú pháp là một trong các cấp độ phải mô tả. Với những người làm
tin học thì cần làm cho máy tính phân tích được cú pháp với hai mục tiêu là xây dựng
các ứng dụng, qua đó phục vụ vi
ệc nghiên cứu ngôn ngữ; đối tượng nghiên cứu của họ
là các hệ hình thức và các thuật toán.
Chương 1. Mở đầu
Khoá luận tốt nghiệp
8
Khi xét về cấu trúc cú pháp có hai khía cạnh, một là thứ tự của các từ, trong đó có
những ràng buộc về cấu tạo câu đúng và chức năng của các thành phần trong câu (chủ
ngữ, vị ngữ...); hai là những biến tố (về hình thái, ví dụ các thì, số ít, số nhiều,
giống...) quy định ràng buộc về cấu tạo và chức năng ngữ pháp. Với tiếng Việt, không
có khía cạnh thứ hai.
Để phân tích cấu trúc của một câu ta cần đến hai thứ: Thứ nhất là ngữ pháp của
ngôn ngữ, là đặc tả hình thức cấu trúc của ngôn ngữ và thứ hai là các kỹ thuật phân
tích, là các phương thức phân tích để tìm ra cấu trúc ngữ pháp của câu, hoặc kết luận

Mỗi dãy ký hiệu các phần tử của Χ: α = a
i1
a
i2
...a
it
, a
ij
∈ Χ, 1 ≤ j ≤ t được gọi là
một từ hay một xâu trên bảng chữ cái Χ. Ví dụ ba, ca, con,... Tổng số vị trí của tất cả
các ký hiệu xuất hiện trong từ α được gọi là độ dài của α, ký hiệu là |α|. Từ có độ dài
bằng 0 được gọi là từ rỗng (trống), được ký hiệu là ε.
Gọi Σ* là tập hợp gồ
m tất cả các từ trên bảng chữ cái Σ, kể cả từ rỗng. Mỗi một
tập con của tập Σ* được gọi là một ngôn ngữ trên bảng chữ cái Σ. Tập rỗng cũng là
một ngôn ngữ trên bảng chữ cái tuỳ ý, được ký hiệu bằng φ.
Giả sử có bảng chữ cái Σ, một văn phạm là một bộ bốn G = (Σ, V,
σ, P), trong đó:
¾ Σ là bảng chữ cái chính hay bảng chữ cái từ hay tập ký hiệu kết
¾ V là bảng chữ cái phụ hay bảng chữ cái làm việc hay tập ký hiệu không kết
¾ σ ∈ V là một ký hiệu phụ, gọi là tiền đề hay ký hiệu xuất phát hay ký hiệu
khởi đầu
¾ P = {ϕ → ψ⎪ϕ∈(
Σ ∪V)*\{e}, ψ ∈(Σ ∪V)*, → ∉ (Σ ∪V)} gọi là tập quy
tắc sinh hay tập quy tắc thế của văn phạm G. r = ϕ → ψ là một quy tắc
sinh hay quy tắc thế của văn phạm G, ϕ, ψ theo thứ tự được gọi là vế trái
và vế phải của quy tắc r.
Ví dụ, G = ({a, b, c},
{S, A, B}, S, P), trong đó P là
S

2
, β = α
1
ψα
2
, ϕ → ψ ∈ P thì ta nói rằng xâu α
dẫn trực tiếp ra xâu β hoặc xâu β được dẫn trực tiếp từ xâu α.
Một dãy từ ω
0
, ω
1
, ..., ω
i
, ω
i+1
, ..., ω
m
được gọi là một dẫn xuất trong văn phạm G
nếu ∀i, ω
i
⇒ ω
i+1
.
Ta nói rằng xâu α dẫn gián tiếp ra xâu β hay xâu β được dẫn gián tiếp từ α trong
văn phạm G, và viết là α
β nếu hoặc α = β hoặc tồn tại một dẫn xuất ω mà từ đầu
tiên là α và từ cuối cùng là β.
*
⇒
Tập {x ∈ Σ* | σ


Khoá luận tốt nghiệp
11

Hình 1. Phân loại văn phạm của Chomsky
Các quy tắc sinh của văn phạm phi ngữ cảnh G có thể được chuẩn hoá theo hai
cách mà không làm thay đổi khả năng sinh của nó, gồm dạng chuẩn Chomsky và dạng
chuẩn Greibach. Trong dạng chuẩn Chomsky, các quy tắc có dạng A → BC hoặc A →
a. Với dạng chuẩn Greibach, các qui tắc có dạng A → aα.
Cây dẫn xuất của văn phạm là một cây được đánh dấu bởi các ký hiệu kết thúc
hoặc không kết thúc sao cho mỗ
i nút mẹ là vế trái của một qui tắc sinh mà vế trái của
qui tắc đó lập nên bởi dãy các kí hiệu của các nút con.
Hầu hết các ngôn ngữ lập trình đều được mô tả bằng văn phạm phi ngữ cảnh.
Chẳng hạn, câu lệnh lặp while được mô tả bởi các quy tắc phi ngữ cảnh sau:
WhileStatement → while Condition do StatementList end
StatementList → Statement
StatementList → Statement ; StatementListVăn phạm phi ngữ cảnh cũng được lựa chọn để biểu diễn cấu trúc cú pháp của các
ngôn ngữ tự nhiên bởi hai lý do:
¾ Nó đủ mạnh để mô tả hầu hết những cấu trúc của ngôn ngữ tự nhiên
¾ Nó vừa đủ hạn chế để xây dựng những trình phân tích câu hiệu quả
Sau đây ta đi vào tìm hiểu việc vận dụng các văn phạm phi ngữ c
ảnh và các thuật
toán phân tích để biểu diễn ngôn ngữ tự nhiên và xây dựng các trình phân tích cú
pháp.
2.3. Biểu diễn cấu trúc câu
Văn phạm phi ngữ cảnh khi được sử dụng để biểu diễn cấu trúc cú pháp thì các ký

Có hai phương pháp điển hình dùng để phân tích văn phạm phi ngữ cảnh, là phân
tích từ trên xuống và phân tích từ
dưới lên.
¾
Phân tích từ trên xuống: Xuất phát từ ký hiệu đầu S, áp dụng các suy dẫn
tiến hành từ trái qua phải thử tạo ra câu cần phân tích
¾ Phân tích từ dưới lên: Xuất phát từ chính câu vào, áp dụng thu gọn các suy
dẫn phải, tiến hành từ phải qua trái để đi tới ký hiệu đầu.
Ví dụ, xét câu "John ate the cat". Phân tích từ trên xuống như sau
S
→
NP VP

→
NAME VP

→
John VP

→
John VERB NP

→
John ate NP

→
John ate ART NOUN

→
John ate the NOUN

VERB NP NP
8. VP
→
VERB PP

Trong đó, các ký hiệu và từ loại tương ứng được cho trong bảng sau:
Ký hiệu Từ loại tương ứng
S Câu
NP cụm danh từ
VP cụm động từ
PP cụm giới từ
NOUN danh từ
ART mạo từ
VERB động từ
NAME tên riêng

Theo văn phạm này thì một số câu như
¾ John saw the cat by the pond
¾ The dog barked in the house
là chấp nhận được, nhưng nó cũng chấp nhận những câu không có nghĩa như
¾ The dog allows the house
¾ John barked the cat by the pond
Với câu John ate the cat, ta có cây phân tích như Hình 2.
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
14

Hình 2. Cây biểu diễn câu John ate the cat


VERB PP

Ta có phân tích từ trên xuống của câu
1
The
2
dogs
3
cried
4
như trên Bảng 1.
Bước Trạng thái hiện tại Trạng thái lưu Vị trí Nhận xét
1. (S) 1 vị trí khởi tạo
2. (NP VP) 1 viết lại S theo quy tắc 1
3. (ART NOUN VP) 1 viết lại NP theo các quy tắc 2, 3
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
15
(NAME VP) 1
4. (NOUN VP) 2
so khớp ART với the
(NAME VP) 1
5. (VP) 3
so khớp NOUN với dogs
(NAME VP) 1
6. (VERB) 3 viết lại VP theo các quy tắc 5-8
(VERB NP) 3
(VERB NP PP) 3
(VERB PP) 3

4. NP
→
ADJ NOUN
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
16
5. VP
→
AUX VERB NP
6. VP
→
VERB NP

Nếu ta bắt đầu bằng khoá ART thì các quy tắc 2 và 3 là khớp. Ta ghi lại điều này
cho bước xử lý tiếp theo, các quy tắc 2, 3 có thể đi tiếp được ở sau điểm ART. Ta biểu
diễn điều này bằng cách viết lại các quy tắc đó cùng với dấu chấm tròn (ο) chỉ rằng ta
đã đi đến đâu:
2'. NP
→
ART ο ADJ NOUN
3'. NP
→
ART ο NOUN
Nếu khoá sau đó là ADJ thì có thể có quy tắc 4 và quy t
ắc 2' được thác triển tiếp
như sau:
2''. NP
→
ART ADJ ο NOUN

2
trên biểu đồ gồm các bước
sau:
1. đưa C vào giữa p
1
và p
2
;
2. nếu C bắt đầu một quy tắc r của văn phạm thì thêm một cung biểu diễn quy tắc
r từ p
1
đến p
2
;
3. với mỗi cung A đi từ p
0
đến p
1
(điểm bắt đầu của C), nếu C là thành phần con
kế tiếp của A thì thêm một cung từ p
0
đến p
2
biểu diễn quy tắc A đã cập nhật.
4. nếu một cung nào đó trong số các cung được thêm vào tại các bước 2, 3 là một
quy tắc đã hoàn chỉnh thì thêm vào danh sách khoá một thành phần mới có tên
là vế trái của quy tắc đó.
Ví dụ, xét thuật toán này với câu cần phân tích là
The large can can hold the water,
với từ điển sau:

dạng như Hình 4.

Hình 4. Sau khi phân tích can là NOUN
Bây giờ xét tới các từ loại khác của can.
• Vào AUX1: (can từ 3 đến 4). Thêm cung VP → AUX ο VERB NP từ 3 tới 4.
• Vào VERB1: (can từ 3 đến 4). Thêm cung VP → VERB ο NP từ 3 tới 4.
Từ tiếp theo lại là can và NOUN2, AUX2, VERB2 được tạo ra.
• Vào NOUN2: (can từ 4 đến 5). Không cung nào được thêm vào.
• Vào AUX2: (can từ 4 đến 5). Thêm cung VP → AUX ο VERB NP từ 4 tới 5.
• Vào VERB2: (can từ 4 đến 5). Thêm cung VP → VERB ο NP từ 4 tới 5, thêm
cung VP
→ AUX VERB ο NP từ 3 tới 5.
Từ tiếp theo là hold và NOUN3, VERB3 được tạo ra.
• Vào NOUN3: (hold từ 5 đến 6). Không cung nào được thêm vào.
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
19
• Vào VERB3: (hold từ 5 đến 6). Thêm cung VP → VERB ο NP từ 5 tới 6,
thêm cung VP → AUX VERB ο NP từ 4 tới 6. Ta được biểu đồ như Hình 5.

Hình 5. Biểu đồ sau khi thêm hold
• Vào ART2: (the từ 6 đến 7). Thêm cung NP → ART ο ADJ NOUN từ 6 tới 7,
thêm cung NP → ART ο NOUN từ 6 tới 7.
• Vào NOUN4: (water từ 7 đến 8). Không có cung nào được thêm vào trong
bước 2, một NP, NP3 từ 6 tới 8 được đẩy vào danh sách khoá do hoàn thành cung NP
→ ART ο NOUN từ 6 tới 7.
• Vào NP3: (the water từ 6 đến 8). Một VP, VP1 từ 4 tới 8 được đẩy vào danh
sách khoá do hoàn thành quy tắc VP → AUX VERB ο NP từ 4 tới 6; một VP, VP2 từ
5 tới 8 được đẩy vào danh sách khoá do hoàn thành quy tắc VP →

2. S
→
NP AUX VERB 6. NP
→
ADJ NOUN
3. S
→
NP VERB 7. VP
→
AUX VERB NP
4. NP
→
ART NOUN 8. VP
→
VERB NP
Bảng 2. Một văn phạm phi ngữ cảnh đơn giản
thì trình phân tích từ trên xuống của câu The can fall sẽ cho rằng câu S bắt đầu
bằng một NP, NP bắt đầu bằng ART, sau đó là ADJ hoặc NOUN. Vì can là NOUN,
nên nó tìm thấy một NP và do đó các nghĩa AUX hoặc VERB của can không bao giờ
được xét.
Nhưng phân tích từ trên xuống lại có thể tốn nhiều thời gian bởi những công việc
tương tự nhau có khi phải lặp lại nhiều lần. Giả sử ta cần phân tích câu The bird
sang cũ
ng với văn phạm trên. Ban đầu, trình phân tích sử dụng quy tắc 1 tìm ra một
NP the bird, sau đó sử dụng quy tắc 8 cho VP, nó tìm thấy VERB, nhưng sau đó
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
21
phải là NP thì không thoả mãn. Do đó nó quay lại và thử tìm một phân tích khác của

4
evaporated
5
,
trong đó green có thể là ADJ hoặc NOUN, water là NOUN hoặc VERB. Trạng
thái khởi đầu như sau
Trạng thái hiện tại Trạng thái lưu Vị trí
(S) nil 1

Sử dụng văn phạm ở Bảng 2, viết lại S theo các quy tắc 1, 2 và 3, ta có tình huống
sau
Trạng thái hiện tại Trạng thái lưu Vị trí
(NP VP) 1
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
22
(NP AUX VERB) 1
(NP VERB) 1

Sử dụng các quy tắc 4, 5 và 6 để viết lại NP của trạng thái hiện tại sinh ra
Trạng thái hiện tại Trạng thái lưu Vị trí
(ART NOUN VP) 1
(ART ADJ NOUN VP) 1
(ADJ NOUN VP) 1
(NP AUX VERB) 1
(NP VERB) 1

Câu cần phân tích được kiểm tra xem có bắt đầu bằng một ART và sau đó là một
NOUN hay không, việc này thành công, trình phân tích xây dựng được một NP trên

hạn, cho vị trí hiện tại của trạng thái ([NP2] VP) là 5, ta sẽ thêm một NP vào
biểu đồ từ vị trí 2 tới vị trí 5.
3. Ngược lại, nếu ký hiệu đó là một ký hiệu kết, thì thêm m
ột cờ dựng vào vị trí
đó và viết lại ký hiệu này theo các quy tắc của văn phạm. Ví dụ, cho trạng thái
(NP VP) tại vị trí 1 và một biểu đồ trống, theo văn phạm ở trên, ta sẽ sinh ra ba
trạng thái mới là: (ART NOUN [NP1] VP), (ART ADJ NOUN [NP1] VP), và
(ADJ NOUN [NP1] VP), tất cả đều ở vị trí 1.
4. Nếu không xảy ra các trường hợp trên thì trạng thái này không thoả, một trạng
thái lưu được lấy ra làm trạng thái hiện tại.
Bây giờ, s
ử dụng thuật toán này, ta xét lại quá trình phân tích câu The green
water evaporated. Nếu ta bắt đầu bằng ký hiệu S và vị trí 1, viết lại ký hiệu này,
ta được
Trạng thái hiện tại Trạng thái lưu Vị trí
(NP VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1

Viết lại NP theo bước 4 trong thuật toán, ta được
Trạng thái hiện tại Trạng thái lưu Vị trí
(ART NOUN [NP1] VP [S1]) 1
(ART ADJ NOUN [NP1] VP [S1]) 1
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1

Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp

Trạng thái hiện tại Trạng thái lưu Vị trí
(VP [S1]) 4
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
25
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1 Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên
Viết lại VP ở vị trí 4 trong trạng thái hiện tại sinh ra tình huống mới sau
Trạng thái hiện tại Trạng thái lưu Vị trí
(AUX VERB NP [VP3] [S1]) 4
(VERB NP [VP3] [S1]) 4
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1

Vì không có AUX ở vị trí 4 nên trạng thái hiện tại không được chấp nhận. Trạng
thái lưu thứ nhất cũng không thoả mãn, vì tuy có một VERB ở vị trí 4 nhưng sau đó
lại không có NP. Trạng thái tiếp theo (ADJ NOUN [NP1] VP [S1]) cũng bị loại do
the không phải là một ADJ. Chỉ còn lại hai trạng thái và biểu đồ như sau:
Trạng thái hiện tại Trạng thái lưu Vị trí
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1

Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại
Bây giờ ta đã kết thúc mọi phân tích có thể từ việc bắt đầu bằng S, viết lại nó theo