Luận Tốt Nghiệp KS2-K7
LỜI NÓI ĐẦU
Môn học ngôn ngữ hình thức và automata có rất nhiều ứng dụng trong lĩnh vực khoa học
máy tính như xây dựng các trình biên dịch, nhận dạng và chuyển đổi giữa các ngôn ngữ khác
nhau… Do đó mà môn học này là một môn học bắt buộc cho các sinh viên ngành CNTT trong các
trường đại học.
Để giúp cho các sinh viên có điều kiện học tốt và thực hành các bài tập của môn học này, luận văn
này đi sâu vào việc mô phỏng lại hoạt động của các giải thuật trong phần ngôn ngữ phi ngữ cảnh
đặc biệt là các giải thuật phân tích cú pháp Earley và CYK.
Sinh viên có thể khai thác cơ sở lý thuyết của môn học thông qua hệ thống Help của chương trình.
Xin cám ơn thầy Hồ Văn Quân đã tận tình hướng dẫn và giúp đỡ tôi hoàn thành bản luận văn tốt
nghiệp như yêu cầu của đề bài.
Sinh Viên Thực Hiện
Thái Thuần Thạch
PHẦN 1
Trang 1
Luận Tốt Nghiệp KS2-K7
GIỚI THIỆU
1. GIỚI THIỆU ĐỀ TÀI
Yêu cầu của đề tài là :
“Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và
Automata.” Ngoài các giải thuật biến đổi văn phạm, tập trung vào nghiên cứu và hiện thực hai giải
thuật phân tích cú pháp CYK và Earley, Đánh giá số bước phân tích của mỗi giải thuật.
Aùp dụng nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh)
2. MỤC ĐÍCH & Ý NGHĨA
Hiện nay, ở nước ta việc áp dụng giảng dạy các môn học thông qua các mô hình giảng dạy
thiết kế trên máy tính còn gặp nhiều khó khăn, một trong những nguyên nhân là thiếu các phần
mềm hỗ trợ việc học và giảng dạy.
Luận văn này ra đời không nằm ngoài mục đích giúp sinh viên nghành CNTT có một công
cụ để hỗ trợ thêm cho việc học môn học “Ngôn Ngữ Hình Thức & Automata” . Bộ công cụ này
cho phép sinh thấy rõ cách thức hoạt động của một số giải thuật của phần ngôn ngữ phi ngữ cảnh,

đã tìm hiểu ở phần 2 và mô hình giảng dạy để đưa ra
• Lựa chọn ngôn ngữ lập trình
• Cấu trúc dữ liệu cho các giải thuật sử dụng trong chương trình
• Cách thức nhập liệu, cấu trúc file lưu trữ
• Cách trình bày dữ liệu xuất
• Các lưu đồ thuật toán, tính toán độ phức tạp…
• …
♦ Phần 5 : So sánh độ phức tạp giữa hai giải thuật phân tích cú pháp CYK và Earley, trong phần
này đưa ra các giả thiết để thực hiện tính độ phức tạp cho hai giải thuật trên bằng chương trình
cũng như đưa ra những minh họa bằng ví dụ thực tế (với các đồ thị minh họa)
♦ Phần 6 : Aùp dụng nhận dạng ngôn ngữ tự nhiên, trong phần này sẽ trình bày các vấn đề liên
quan đến việc nhận dạng một câu nhập (Tiếng Anh) và cách thức xây dựng bộ từ điển token.
♦ Phần 7 : Thiết kế Help : đây cũng là một phần quan trọng của một chương trình trợ giúp học
tập, trong phần này chú trọng tìm hiểu thiết kế một hệ thống Help. Đặc biệt là thiết kế hệ thống
Help cho chương trình thông qua công cụ Windows Help Designer Pro (down load từ
http://www.devgr.com)
♦ Phần 8 : Giới thiệu chuơng trình kết quả.
♦ Phần 9 : Phụ lục - Mã chương trình
♦ Phần 10 : Giới thiệu các tài liệu tham khảo
PHẦN 2 :
CƠ SỞ LÝ THUYẾT LIÊN QUAN
CHƯƠNG 1
MỘT SỐ KHÁI NIỆM CƠ BẢN
Trong chương này chúng ta sẽ tìm hiểu một số khái niệm và định nghĩa cơ bản liên quan
đến môn học như : bảng chữ cái, chuỗi, ngôn ngữ, văn phạm, cây dẫn xuất…, tuy nhiên sinh viên
có thể bỏ qua chương này nếu đã nắm bắt được các khái niệm trên.
1. BẢNG CHỮ CÁI
♦ Là một tập hữu hạn không trống các ký hiệu (symbol) tập này thường được ký hiệu bằng Σ
♦ Ví dụ :
Trang 3

chuỗi w với chính nó n lần, trường hợp đặc biệt
w
0
=λ
♦ Σ
*
: Nếu Σ là một bảng chữ cái thì tập tất cả các chuỗi trên Σ kể cả chuởi trống được gọi là Σ
*
♦ Σ
+
: Nếu Σ là một bảng chữ cái thì tập tất cả các chuỗi trên Σ không kể chuởi trống được gọi là
Σ
+
3. NGÔN NGỮ
♦ Bất kỳ một tập L nào trên bảng chữ cái Σ, hay tập con L của Σ
*
được gọi là một ngôn ngữ.
Ví dụ :
Cho Σ={a,b} thì Σ
*
={λ,a,b,aa,ab,ba,aaa,aab,...}
Tập {a,aa,aab} là một ngôn ngữ trên ∑
Tập L={a
n
b
n
: n≥0} cũng là một ngôn ngữ trên tập ∑
♦ Vì ngôn ngữ là một tập hợp các chuỗi nên hội (union), giao (intersection) và hiệu (diference)
của hai ngôn ngữ dễ dàng xác định ngay lập tức.
♦ Bù của một ngôn ngữ : Bù của một ngôn ngữ L trên bảng chữ cái ∑ được ký hiệu là

+ L
n
: Lũy thừa của một ngôn ngữ bao gồm L nối với chính n lần với trường hợp đặc biệt :
L
0
={λ}
L
n
=L
n-1
L với n≥0
♦ Bao đóng -sao của một ngôn ngữ L được ký hiệu là L
*
với :
L
*
=L
0
∪L
1
∪L
2
...
♦ Bao đóng -dương của một ngôn ngữ L được ký hiệu là L
+
với :
L
+
=L
1

thành một chuỗi khác, và thông qua cách này chúng (các luật sinh) định nghĩa một ngôn ngữ liên
kết với văn phạm.
♦ Chúng ta nói rằng w dẫn xuất ra z ký hiệu w=
*
>z hay z được dẫn xuất ra từ w. Các chuỗi lần
lượt được dẫn xuất bằng cách áp dụng các luật sinh của văn phạm trong một thứ tự tùy ý nếu :
w
1
=>w
2
=>...=>w
n
chúng ta nói w
1
dẫn xuất ra w
n
và viết w
1
=
*
> w
2.
Trang 5
Luận Tốt Nghiệp KS2-K7
♦ Dấu * chỉ ra rằng một số bước bất kỳ nào đó (kể cả không) có thể được áp dụng để dẫn xuất ra
w
n
từ w
1
♦ Để chỉ ra ít nhất một luật sinh áp dụng chúng ta phải viết : w

là những biểu thức chính qui, thì r
1
+r
2,
r
1.
r
2
, và(r
1
) cũng vậy.
+ Mộät chuỗi là một biểu thức chính quy nếu và chỉ nếu nó có thể được dẫn xuất từ các biểu thức
chính qui nguyên thủy bằng một số lần hữu hạn áp dụng các qui tắc trong (2).
♦ Ngôn ngữ L(r) được biểu thị bỡi biểu thức chính qui bất kỳ và được định nghĩa bởi các qui tắc
sau:
+ ∅ là một biểu thức chính qui biểu thị tập trống.
+ λ là một biểu thức chính qui biểu thị tập {λ}
+ Đối với mọi a ∈∑, a là biểu thức chính qui biểu thị cho ngôn ngữ {a}.
Nếu r
1
và r
2
những biểu thức chính qui thì :
+ L(r
1
+r
2
) = L(r
1
) ∪L(r

n
: n≥0}, chúng ta thay thế dấu ngoặc trái cho a và dấu ngoặc phải cho b
thì chuỗi các dấu ngoặc chẳng hạn như (( )) và ((( ))) là thuộc L nhưng (( ) thì không mà trong một
ngôn ngữ lập trình thì thường xuyên gặp những cấu trúc lồng nhau như vậy. Do đó ta thấy một vài
thuộc tính của ngôn ngữ lập trình yêu cầu một cái gì đó bên ngoài ngôn ngữ chính qui, để bao trùm
những vấn đề này ta phải mở rộng ngôn ngữ dẫn đến việc nguyên cứu ngôn ngữ và văn phạm
phi ngữ cảnh.
5.1- Văn Phạm Phi Ngữ Cảnh
Các luật sinh trong văn phạm chính qui thì bị giới hạn theo 2 cách : Vế phải là một biến
đơn, trong khi đó vế phải có một dạng đặc biệt. Để tạo ra văn phạm mạnh hơn, chúng ta phải nới
Trang 6
Luận Tốt Nghiệp KS2-K7
lỏng một vài giới hạn như vậy, bằng cách duy trì giới hạn trên vế trái nhưng cho phép bất kỳ cái gì
trên vế phải khi đó chúng ta nhận được một văn phạm phi ngữ cảnh.
♦ Định Nghĩa
Một văn phạm G =(V,T,S,P) được gọi là phi ngữ cảnh nếu mọi luật sinh trong P có dạng :
A-->x
trong đó A
∈
V còn x
∈
(V
∪
T)
*
.
Một ngôn ngữ được gọi là phi ngữ cảnh nếu và chỉ nếu có một văn phạm phi ngữ cảnh G sao cho
L= L(G).
5.2- Dẫn Xuất Trái Nhất Và Phải Nhất
Trong văn phạm phi ngữ cảnh mà không tuyến tính, một dẫn xuất có thể bao gồm nhiều

1
, a
2....
a
n
+ Một lá được gán nhãn
λ
không có anh chị e, tức là một nốt với một con được gán nhãn
λ
có thể
không có con nào khác.
Ngoài ra còn có một số khái niệm khác chưa được nêu ra ở đây, các bạn có thể tìm hiểu thêm trong
“An Introduction To Formal Languages And Automata” của Peter Linz
Trang 7
A
BA cb
a
Luận Tốt Nghiệp KS2-K7
CHUƠNG 2
MỘT SỐ GIẢI THUẬT BIẾN ĐỔI VĂN PHẠM PNC VÀ CÁC
DẠNG CHUẨN
Trong phần này, chúng ta đi sâu vào việc tìm hiểu một số giải thuật biến đổi văn phạm phi
ngữ cảnh như :
+ Loại bỏ các luật sinh rỗng
+ Loại bỏ các luật sinh vô dụng
+ Loại bỏ các luật sinh đơn vị
+ Chuyển văn phạm bất kỳ về dạng chuẩn Chomsky
+ Chuyển văn phạm bất kỳ về dạng chuẩn Greibach
Việc loại bỏ các luật sinh trên rất quang trọng làm tiền đề để có thể biến đổi tập văn phạm của
ngôn ngữ phi ngữ cảnh về các dạng chuẩn quan trọng như dạng chuẩn Chomsky, dạng chuẩn

3
... A
n
với A
1
A
2
A
3
... A
n
∈ Vn thì cho B vào Vn
Bước 3: Sau khi đã có tập Vn, xét mọi luật sinh trong P có dạng :
A---> x
1
x
2
... x
m
với m≥1 và x
i
∈ (V∪ T)
Đối với mỗi luật sinh như vậy của P, đặt vào P^ luật sinh đó cũng như những luật sinh bằng cách
thay thế các biến khả trống (∈ Vn) bằng λ trong mọi tổ hợp có thể có, ngoại trừ tất cả x
i
(i=1,2...)
là khả trống thì không đặt luật sinh A->λ vào trong P^
Ví dụ:
Cho văn phạm G =({S,A,B,C,D},{a, b,d,λ},{S},P) và các luật sinh trong P như sau :
Trang 8

Bước 2 : Đối với mỗi luật sinh trong P có dạng A---> B (A ≠ B), thì đối với mỗi biến A tìm tất cả
các biến B sao cho A--*> B Điều này có thể thực hiện được bằng cách vẽ đồ thị phụ thuộc cho G.
Bước 3 : Xét tất cả các biến A và B thỏa mãn ở bước 2 , chúng ta sẽ thêm vào P^ các luật sinh
sau :
A ---> y
1
| y
2
| y
3
| ...|y
n
Trong đó B ---> y
1
| y
2
| y
3
| ...|y
n
là các luật sinh không đơn vị của B. Hay nói cách khác đặt các vế
phải của các luật sinh không đơn vị của B ở trong P vào làm các vế phải của các luật sinh của A
trong p^
Kết quả G^ sẽ tương đương với G mà P^ không chứa các luật sinh đơn vị
Ghi chú :
Nếu muốn trong P^ không chứa luật sinh rỗng
λ
thì trước tiên ta phải loại bỏ luật sinh
λ
trước.

đóng góp gì trong bất kỳ dẫn xuất nào. Chẳng hạn trong văn phạm sau toàn bộ tập luật sinh của nó
là :
S ---> aSb | λ | A
A ---> aA
Luật sinh S ---> A rõ ràng không đóng một vai trò nào, vì A không thể được biến đổi thành
các ký hiệu kết thúc. Trong khi A có thể xuất hiện trong một chuỗi được dẫn xuất từ S, cái này có
thể không bao giờ dẫn đến câu. Việc loại bỏ luật sinh này không làm ảnh hưởng đến ngôn ngữ và
là một sự đơn giản hóa theo bất kỳ định nghĩa nào.
• Nhập :
- Một văn phạm phi ngữ cảnh G =(V,T,S,P) với :
+ V : Các kí hiệu không kết thúc.
+ T : Các kí hiệu kết thúc.
+ S : Biến khởi đầu
+ P : Tập các luật sinh
• Xuất :
- Một văn phạm G^=(V^,T^,S,P^) với tập luật sinh P^ không có tập luật sinh vô dụng.
Trang 10
B
A
S
Luận Tốt Nghiệp KS2-K7
• Giải Thuật
Bước 1 : Loại bỏ luật sinh vô dụng loại 1:
+ Khởi tạo V1={ }
+ Lặp lại các bước sau cho đến khi không còn biến nào được thêm vào V1.
Đối với mỗi A∈ V mà có luật sinh
A--> x
1
x
2

- Một văn phạm G^=( V^,T^,S^,P^) với tập luật sinh P^ thuộc dạng chuẩn Chomsky
• Giải Thuật
Bước 1: Loại bỏ các luật sinh:
- Rỗng
- Đơn Vị
- Vô dụng
Bước 2: Đặt các luật sinh A-->a vào trong P^
Bước 3: Đối với các luật sinh A-->x
1
x
2
...x
n
với n ≥ 2, x
i

∈
(V∪T) thì thay các kí hiệu kết thúc,
chẳng hạn x
k
=a, bằng các biến đại diện mới B
a
tạo thành các luật sinh trung gia A--> C
1
C
2
...C
n
.
Bước 4: Ưùng với mỗi biến B

n-2
---> C
n-1
C
n
Ví dụ : Hãy biến đổi văn phạm sau sang dạng chuẩn Chomsky
S a | Aba
Trang 11
Luận Tốt Nghiệp KS2-K7
A aab
B b | Ac
- Theo bước 1, ta đặt các luật sinh sau vào trong P^
S a,
B b
- Theo bước 2, ta đưa ra các biến mới và thay thế các luật sinh còn lại trở thành như sau:
S ABB
a
A B
a
B
a
B
b
B Ab
c
B
a
 a
B
b

 Bb
a
A B
a
D
2
D
2
 B
a
B
b
- Tóm lại ta được văn phạm ở dạng chuẩn Chomsky tương đương như sau:
S a | AD
1
D
1
 Bb
a
A B
a
D
2
D
2
 B
a
B
b
B b | Ab

Trang 12
Luận Tốt Nghiệp KS2-K7
+ Một văn phạm G^=( V^,T,S,P^) với tập luật sinh P^ thuộc dạng chuẩn Greibach
Giải Thuật
Bước 1: Loại bỏ các luật sinh:
- Rỗng
- Đơn Vị - Vô dụng
Bước 2: Đánh số thứ tự các biến chẳng hạn là A
1,
A
2
...
Bước 3:Viết lại văn phạm sao cho tất cả các luật sinh có một trong các dạng sau:
A
i
---> A
j
x
j
với j > i
Z
i
---> A
j
x
j
với j ≥ i
A
i
---> ax

n
và A
n-1
vào các xuất hiện của chúng ở vị trí đầu tiên trên
các vế phải của luật sinh A
n-2
bằng các vế phải tương ứng của chúng. Thực hiện lần lượt cho đến
A
1
Bước 5: Thay thế A
1
A
2
...A
n
trong các xuất hiện của nó ở vị trí đầu tiên các vế phải của các luật
sinh Z
n
(nếu có) bằng các vế phải tương ứng của chúng.
Bước 6: Thay thế các ký hiệu kết thúc, chẳng hạn a, nằm bên vế phải của các luật sinh mà không ở
vị trí đầu tiên bằng các biến đại diện, chẳng hạn B
a
đồng thời thêm vào các luật sinh mới B
a
---> a.
Ví dụ:
Biến đổi văn phạm sau thành dạng chuẩn Greibach
S SBb |Ab
A Sb | Ba
B Sa | b

1
b chưa thỏa mãn
bước 2. Loại bỏ đệ qui trái cho S
0
, ta có :
S
0
 S
0
B
2
b | A
1
b
 S
0
 A
1
b | A
1
bZ
1
(1)
Z
1
 B
2
b | B
2
bZ

1
b | B
2
a
- Đến đây xuất hiện đệ qui trái của A
1
, thực hiện việc loại bỏ đệ qui trái, ta có :
A
1
 A
1
bb | A
1
bZ
1
b | B
2
a
 A
1
 B
2
a | B
2
aZ
2
(3)
Z
2
 bb | bZ

ba | A
1
bZ
1
a | b (thay thế A
1
từ (3) )
 B
2
 B
2
aba | B
2
aZ
2
ba | B
2
abZ
1
a | B
2
aZ
2
bZ
1
a | b (loại bỏ đệ qui trái)
 B
2
 b | bZ
3

, A
1
, B
2
điều thỏa mãn bước 2, và các ký hiệu đi đầu các vế
phải của các luật sinh B
2
đều là ký tự kết thúc. Aùp dụng bước 3 thay ngược trở lại B
2
vào các luật
sinh của A
1
(nếu có) và thay B
2
, A
1
vào các luật sinh của S
0
(nếu có) ta có :
A
1
 B
2
a | B
2a
Z
2
(thay thế B
2
từ (5) )

3
aZ
2
b | babZ
1
| bZ
3
abZ
1
| baZ
2
bZ
1
|
bZ
3
aZ
2
bZ
1
(8)
Đến đây các ký hiệu đi đầu của các luật sinh của S
0
, A
1
, B
2
đều là ký tự kết thúc, vì thế các luật
sinh này đã gần có dạng chuẩn Greibach.
- Aùp dụng bước 4, thay thế S

Đến đây ta có văn phạm “gần” có dạng Greibach tương tương với văn phạm ban đầu như sau :
S
0
 bab | bZ
3
ab | baZ
2
b | bZ
3
aZ
2
b | babZ
1
| bZ
3
abZ
1
| baZ
2
bZ
1
|
bZ
3
aZ
2
bZ
1
(8)
Z

2
(4)
B
2
 b | bZ
3
(5)
Z
3
 aba | aZ
2
ba | abZ
1
a | aZ
2
bZ
1
a | abaZ
3
| aZ
2
baZ
3
| abZ
1
aZ
3
| aZ
2
bZ

YZ
1
Z
1
 bY | bZ
3
Y | bYZ
1
| bZ
3
YZ
1

A
1
 bX | bZ
3
X | bXZ
2
| bZ
3
XZ
2
Z
2
 bY | bZ
1
Y | bYZ
2
| bZ

2
YZ
1
XZ
3
X  a
Y  b
Trang 14
Luận Tốt Nghiệp KS2-K7
Đến đây để đơn giản ta có thể loại bỏ các chỉ số của các biến S
0
, A
1
, B
2
và sắp xếp lại thứ tự của
các luật sinh ta được văn phạm kết quả cuối cùng như sau :
S  bXY | bZ
3
XY | bXZ
2
Y | bZ
3
XZ
2
Y | bXYZ
1
| bZ
3
XYZ

| bZ
3
YZ
1

Z
2
 bY | bZ
1
Y | bYZ
2
| bZ
1
YZ
2

Z
3
 aYX | aZ
2
YX | aYZ
1
X | aZ
2
YZ
1
X | aYXZ
3
| aZ
2

1- Giải Thuật Phân Tích Cú Pháp LL
Giải thuật này là tiêu biểu cho phương pháp phân tích cú pháp từ trên xuống, giải thuật chỉ áp dụng
cho một tập các văn phạm hạn chế có tính chất đặt biệt gọi là LL. sau đây là cấu trúc dữ liệu chính
và hoạt động của giải thuật :
• Cấu trúc dữ liệu gồm :
+ Bộ đệm nhập chứa chuỗi nhập cần phân tích.
+ Parser : Điều khiển các hành vi của bộ phân tích.
+ Stack : Chứa các ký hiệu văn phạm trong quá trình phân tích.
+ Bảng phân tích LL
Trang 15
Luận Tốt Nghiệp KS2-K7
Hình 1 : Hoạt động của bộ phân tích cú pháp LL
Nhập :
- Văn phạm G
- Chuỗi nhập w
Xuất :
- Nếu G là văn phạm LL và w thuộc L(G) thì tạo ra dẫn xuất trái của w, ngược lại sẽ báo lỗi.
Giải Thuật :
Gọi S là ký hiệu mục tiêu của G, $ là ký hiệu kết thúc chuỗi nhập và đánh dấu stack rỗng.
Đầu tiên xây dựng bảng phân tích M cho văn phạm G, nó có dạng là một ma trận M. Trị của phần
tử M[A,a] có thể là một luật sinh mà A là vế trái, hoặc trị của phần tử này là error. Trong đó A là
ký hiệu không kết thúc, a là ký hiệu kết thúc hay ký hiệu đánh dấu kết thúc chuỗi nhập $.
Khi bộ phân tích bắt đầu hoạt động, stack chỉ chứa ký hiệu đánh dấu stack rỗng $ ở đáy stack và ký
hiệu mục tiêu S trên đỉnh.
Gọi X là ký hiệu trên đỉnh stack, a là ký hiệu trong chuỗi nhập được đọc hiện tại thi hành vi của bộ
phân tích hoạt động như sau:
• Nếu X=a=$, nghĩa là stack rỗng và chuỗi nhập được duyệt hết, thì giải thuật kết thúc và parser
thông báo quá trình phân tích chuỗi nhập thành công.
• Nếu X=a và a khác $ thì bộ phân tích sẽ đẩy X ra khỏi stack, dịch đầu đọc
đến ký hiệu nhập kế tiếp.

1
s
1
X
2
s
2
... X
m
s
m
với s
m
nằm trên đỉnh stack. X
i
được gọi là ký hiệu văn
phạm, s
i
là trạng thái.
• Bảng Action-Goto của giải thuật phân tích cú pháp LR, nó có dạng là một ma trận với hai phần
riêng biệt action và goto.
• Phần từ action[s
m
,a] có thể chứa một trong 4 giá trị sau :
+ Shift s, với s là trạng thái.
+ Reduce α, với α là vế phải của luật sinh A --> α
+ Accept
+ Error
• Phần tử goto[s
m

Chuỗi nhập
Xuất kết quảStack
Luận Tốt Nghiệp KS2-K7
Đối với một văn phạm phi ngữ cảnh tổng quát thì một phần tử của bảng action có thể là đa
trị . Giải thuật phân tích LR chỉ có thể áp dụng được với những tập văn phạm phi ngữ cảnh nào mà
một phần tử của bảng action-goto là đơn trị. Đó là văn phạm LR đã đề cập ở trên. Cách thức xây
dựng bảng action - goto xin xem thêm trong (Compilers - trang 221)
Về hiệu quả của giải thuật phân tích cú pháp LR : dễ dàng thấy độ phức tạp của giải thuật tuyến
tính theo kích thước chuỗi nhập.
Thông thường khó xác định giải thuật phân tích cú pháp LL hay LR áp dụng được với lớp văn
phạm lớn hơn, nhưng theo (Compilers-V. Aho) thì lớp văn phạm có thể phân tích bằng giải thuật
LR chứa lớp văn phạm có thể phân tích bằng giải thuật LL.
Ta cũng nhận xét tại một thời điểm trong quá trình phân tích thì giải thuật phân tích cú pháp LL chỉ
làm việc với một luật sinh mà thôi, còn giải thuật phân tích cú pháp LR có thể làm việc với nhiều
luật sinh cùng một lúc. Chính vì vậy mà giải thuật LR có khả năng phân tích tập văn phạm phức
tạp hơn giải thuật LL.
3- Giải Thuật Chart Pasing
Char pasing là một giải thuật phân tích cú pháp trên tập văn phạm phi ngữ cảnh tổng quát.
Nó có tính chất rất đặc biệt : trung hòa giữa phương pháp phân tích từ trên xuống và phương pháp
từ dưới lên. Điều đó có nghĩa là nó vừa có khả phân tích cú pháp từ trên xuống và vừa có khả năng
phân tích cú pháp từ dưới lên. sau đây là mô tả hoạt động của giải thuật:
Gọi chiều dài của chuỗi nhập là n, ta xét việc xây dựng cây dẫn xuất cho chuỗi nhập trên một sơ đồ
(chart)
Với chuỗi nhập có chiều dài n thì sơ đồ có n+1 đỉnh (vertex). Các đỉnh được đánh số từ 0 đến n.
Giữa hai đỉnh bất kỳ có thể có nhiều cung (edge), mỗi cung được biểu diễn bằng một bộ :
(<start-vertex>, <end-vertex>, <edge-lable>)
trong đó :
+ <start-vertex> : Một số tự nhiên chỉ ra đỉnh bắt đầu của cung.
+ <end-vertex> : Một số tự nhiên chỉ ra đỉnh kết thúc của cung.
+ <edge-vertex> : Đó là một luật có dấu chấm (dotted-rule). Luật có dấu chấm là luật sinh

là chuỗi các ký hiệu kết thúc và không kết thúc (cũng có thể là
rỗng) thì ta thêm cung (i,k, A--> w
1
B.w
2
) vào trong sơ đồ.
• Khởi tạo (Initialization)
Khởi tạo là quá trình tạo ra các cung mà luật sinh có dấu chấm dạng :
A--> a.
Trong đó A là ký hiệu không kết thúc còn a là ký hiệu kết thúc.
Với mọi i > 0 , i≤ n thì khi khỡi tạo ta phải tìm một cung có <start-vertex> =i-1, <end-
vertex>=i và luật sinh có dấu chấm là A --> a. với a là ký hiệu thứ i trong chuỗi nhập, ngược
lại chắc chắn chuỗi nhập không phải là một câu hợp lệ của văn phạm đang xét.
• Qui tắc từ dưới lên cho chart parsing (bottom-up rule)
Nếu thêm cung (i,j,C--> w
1
.) vào sơ đồ thì với mỗi luật sinh B --> Cw
2
ta phải thêm cung
(i,i, B-->.Cw
2
) vào sơ đồ.
• Qui tắc từ trên xuống cho chart parsing (top-down rule)
- Khi khỡi tạo : với mỗi luật sinh S --> α thêm cung (0,0,S-->.α) vào sơ đồ, trong đó S là
ký hiệu mục tiêu của văn phạm.
- Nếu thêm cung (i,j, C--> w
1
.Bw
2
) vào sơ đồ thì với mỗi luật sinh B --> w, phải thêm cung

P  on.
N  report.
IV  report.
N  her.
Det  her.
TV  see.
NP  they.
Luận Tốt Nghiệp KS2-K7
III- CÔNG CỤ PHÂN TÍCH CÚ PHÁP YACC
1- Tổng Quan
Trong phần này chúng ta sẽ trình bày một bộ sinh phân tích cú pháp LARL được gọi là
Yacc. Yacc sinh ra mã đích dưới dạng ngôn ngữ C từ đó xây dựng bảng phân tích LARL và phân
tích một chuỗi nhập theo văn phạm LR(1). Yacc thường được sử dụng để xây dựng các bộ phân
tích cú pháp cho các ngôn ngữ lập trình và hiện nay Yacc là một lệnh của hệ điều hành UNIX.
2- Mô Tả Bộ Phân Tích Cú Pháp Yacc
Dưới đây là sơ đồ mô tả quá trình xây dựng bộ phân tích cú pháp từ file đặc tả Yacc :
Tập tin nhập cho Yacc là translate.y là sự đặc tả văn phạm trong ngôn ngữ Yacc. Sau khi chúng ta
tạo ra tập tin translate.y, chúng ta sẽ dùng Yacc compiler để chuyển file translate.y sang tập tin
y.tab.c (đây là tập tin với mã nguồn là ngôn ngữ C). Đây chính là bộ phân tích cú pháp cùng với
một số hàm mà người sử dụng định nghĩa trong tập tin đặc tả.
Sau khi có tập tin y.tab.c sẽ được biên dịch để tạo ra file thực thi a.out.
3- Cấu Trúc File Đặc Tả Yacc
File đặc tả có dạng tổng quát như sau :
Declarations
%%
Translation rules
%%
C-routine codes
• Phần khai báo : Khai báo các ký hiệu để sử dụng trong phần thứ 2 và thứ 3, có hai dạng khai
báo

Đối với văn phạm không tường minh thì bộ phân tích sẽ tạo ra bảng phân tích với các ô có
nhiều giá trị (multiple entry). Do đó trong quá trình phân tích sẽ có sư đụng độ. Yacc sẽ báo cáo
các đụng độ này khi nó sảy ra. Ngoài ra, Yacc còn có khả năng giải quyết một số đụng độ bằng
cách sử dụng hai qui tắc sau :
+ Đụng độ do một phần tử trong bảng có 2 giá trị là reduce (reduce /reduce) được giải
quyết bằng cách thực hiện tác vụ reduce trên luật sinh được liệt kê trước trong file đặc
tả văn phạm.
+ Đụng độ do một phần tử trong bảng có hai giá trị, một là reduce và một là shift được giải
quyết bằng cách hực thi tác vụ shift. Quy tắc này xử lý tốt trong trường hợp không tường
minh trong cấu trúc if -then -else / if then :
if_stmt :
IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
Vì các qui tắc trên có thể không phải luôn luôn là điều mà người sử dụng mong muốn, cho
nên Yacc cung cấp một cơ chế tổng quát để giải quyết đụng độ shift/reduce bằng cách cho
phép người sử dụng có thể gán độ ưu tiên và kết hợp trái/phải hoặc không có kết hợp trong
phần khai báo.
4- Khắc Vụ Lỗi Trong Yacc
Khắc phục lỗi trong Yacc có thể được thực hiện bằng cách sử dụng các luật sinh khắc phục
lỗi. Trước tiên, người sử dụng phải chọn những ký hiệu không kết thúc chính yếu (major
nonterminal) nào sẽ có thủ tục khắc phục lỗi kèm theo. Sau đó người sử dụng phải thêm vào văn
phạm các luật sinh khắc phục lỗi, các luật sinh này có dạng A  error α với A là ký hiệu không
kết thúc chính yếu, error là một token được hỗ trợ sẵn trong Yacc và α là chuỗi các ký hiệu văn
phạm. Yacc sẽ sinh ra bộ phân tích cú pháp dưới dạng đặc tả như vậy và xử lý các luật sinh trên
như các luật sinh thông thường.

Trang 21
Luận Tốt Nghiệp KS2-K7
CHƯƠNG 4
GIẢI THUẬT PHÂN TÍCH CÚ PHÁP EARLEY VÀ CYK

. X
k+1
… X
m
, i]
Dấu chấm nằm giữa X
k
và X
k+1
là một ký hiệu không có trong N và ∑ và i đại diện cho tập thực thể
chứa luật trên
 Với mỗi số nguyên j (0 ≤ j ≤ n), chúng ta sẽ xây dựng một danh sách các tập thực thể I
j
mà mỗi
I
j
chứa các thực thể :
• [A α . β , i] là ở trong I
j
(0 ≤ i ≤ j) nếu và chỉ nếu tồn tại γ và δ sao cho chúng ta có
S =
*
> γAδ và γ =
*
> a
1
…a
i
và α =
*

, I
1
, … I
n
Giải Thuật :
• Đầu tiên chúng ta xây dựng tập I
0
như sau :
(1) Nếu S α là một luật sinh trong P thì ta cho [S.α , 0] vào trong I
0
, sau đó thực hiện
bước (2) và (3) cho đến khi nào không thể thêm tập thực thể mới vào trong I
0
được nữa.
(2) Nếu [B γ . , 0] thuộc I
0
(chú ý : γ có thể là ∈) thì cho vào I
0
[A αB . β , 0] cho tất cả
các thực thể có dạng [A α . Bβ , 0] có trong I
0
(3) Nếu [A α . Bβ ,0] là một thực thể trong I
0
thì ta cho vào I
0
tất cả các luật sinh trong P có
dạng B γ các thực thể [B .γ ,0]
• Xây giờ chúng ta xây dựng I
j
sau khi đã có I

từng tác vụ trong giải thuậtï như sau :
 (4) : Scan.
 (5) : Complete.
 (6) : Predict.
Và có thể mô tả sơ lượt giải thuật như sau, sau khi đã tạo được tập I
0
:
Giải thuật Earley chỉ dựa vào các thực thể trong tập trạng thái để quyết định tác vụ nào trong ba
tác vụ nói trên sẽ thực hiện.
• Nếu trạng thái là trạng thái không kết thúc và ký hiệu sau dấu chấm là ký hiệu không kết thúc
thì ta thực hiện tác vụ predict trên trạng thái đó bằng cách :
+ Tìm trên tập văn phạm P các luật sinh có ký hiệu vế trái trùng với kí hiệu nằm bên phải
dấu chấm của luật có dấu chấm đang xét sau đó thực hiện :
+ Thêm vào các thực thể mới vào cuối trạng thái I
i
, mỗi trạng thái mới gồm có :
- Luật sinh mà ta mới tìm được với dấu chấm nằm ở vị trí bắt đầu bên phải của luật
sinh
- Con trỏ (pointer) được đặt hàng i (trạng thái mới này sẽ không được thêm vào tập
trạng thái nếu nó đã có trong tập trạng thái)
• Nếu trạng thái là trạng thái không kết thúc, ký hiệu nằm sau dấu chấm là ký hiệu kết thúc trùng
với ký hiệu nhập đang xét thì ta thực hiện tác vụ Scan;
+ Scan đưa vào tập trạng thái I
i+1
một trạng thái giống với trạng thái cũ nhưng dấu chấm
trong luật tương ứng dịch qua phải một ký hiệu
• Nếu trạng thái là trạng thái kết thúc và chuỗi ký hiệu nhìn trước trùng với k ký hiệu nhập bắt
đầu từ vị trí i trong chuỗi nhập thì ta thực hiện tác vụ Complete:
+ Complete là tìm trong tập trạng thái I
f

0
rồi nên ta không thêm vào.
- Xéùt (03) áp dụng luật (3) của giải thuật ta thêm vào I
0
các thực thể :
[F . (E) , 0] (05)
[F . a , 0] (06)
- Xét (04) áp dụng luật (3) của giải thuật ta cũng có được hai thực thể (05) và (06) nhưng hai thực
thể này đã tồn tại trong I
0
rồi nên ta không thêm vào. Và bây giờ không có thực thể nào được thêm
vào I
0
nữa.
I
0
[E  .T+E , 0] (01)
[E .T, 0] (02)
[T .F*T, 0] (03)
[T .F , 0 ] (04)
[F . (E) , 0] (05)
[F . a , 0] (06)
• Xây dựng I
1
từ I
0
- Vì a
1
= ( nên ta theo luật (4) ta cho vào I
1

[E T . +E , 1] (24)
[E T . , 1] (25)
- Tương tự như trên ta thêm vào I
2
luật sinh
[F  (E . ) , 0] (26)
Bây giờ không còn tập luật sinh nào được thêm vào I
2
nữa.
• Tương tự ta tính các thực thể I
3
, I
4
, ... I
7
ta được kết quả :
I
0
I
1
I
2
Trang 25
[F  (. E ) , 0]
[E .T, 1]
[T .F*T, 1]
[T .F , 1]
[F . (E) , 1]
[F . a , 1]
[F  a ., 1]