Đồ Án Môn Học Chương Trình Dịch Predictive Parser
1. 1.Giới thiệu 2
2. Phân tích cú pháp đệ quy xuống 3
3. Phân tích cú pháp dự đoán (Predictive Parser) 4
4. Sơ đồ chuyển vị cho thể phân cú pháp dự đoán 7
5. Xây dựng bảng phân tích cú pháp dự đoán 8
5.1.Tính FIRST 8
Để tính FIRST(X) cho mọi ký hiệu văn phạm X, chúng ta áp dụng các quy tắc bên
dưới cho đến khi không còn thêm được một tận hoặc ε nào vào mọi tập FIRST 8
1. Nếu X là một tận thì FIRST(X) là {X} 8
2. Nếu X→ε là một luật sinh thì thêm ε vào FIRST(X) 8
3. Nếu X là một chưa tận và X→Y1Y2 Yk là một luật sinh thì đặt a vào FIRST(X)
nếu với I nào đó, a thuộc FIRST(Y1) và ε thuộc tất cả FIRST(Y1),…, FIRST(Yi-1);
Nghĩa là Y1 Yi-1=>* ε. Nếu ε thuộc FIRST(Y1) với mọi j=1, 2,…,k thì thêm ε vào
FIRST(X). Chẳng hạn, mọi tận trong FIRST(Y1) đều thuộc FIRST(X). Nếu Y1 không
dẫn xuất ε thì chúng ta không thêm gì voà FIRST(X) nhưng nếu Y1=>*ε thì chúng ta
đưa FIRST(Y2) vào… 8
5.2.Tính FOLLOW 8
Để tính FOLLOW(A) cho các chưa tận A, chúng ta áp dụng các quy tắc sau đây cho
đến khi không thêm được gì nữa vào mọi tập FOLLOW 9
1. Đặt $ vào tập FOLLOW(S), trong đó S là ký hiệu khởi đầu và $ là dấu kết cuối
nguyên liệu 9
2. Nếu có một luật sinh A→αBβ thì mọi phần tử của tập FIRST(β) trừ ε đều được đặt
vào FOLLOW(B) 9
3. Nếu có một luật sinh A→α hoặc một luật sinh A→αBβ trong đó FIRST(β) chứa ε
(nghĩa là β=>*ε) thì mọi phần tử trong FOLLOW(A) đều thuộc FOLLOW(B) 9
5.3.Thuật Toán 9
6. Phân tích cú pháp dự đoán không đệ quy 10
7. Xây dựng chương trình mô phỏng 11
1
Đồ Án Môn Học Chương Trình Dịch Predictive Parser

Trở lại với câu hỏi thứ nhất ở trên, tại mỗi bước dẫn xuất, dạng câu thu được có
thể có nhiều chưa tận, khi đó chúng ta sẽ chọn khai triển theo chưa tận nào? Chúng ta
sẽ không chọn chưa tận để thay một cách ngẫu nhiên mà thực hiện một cách có hệ
thống. Khai triển theo chưa tận tận phải (tìm một dẫn xuất tận phải) hoặc triển khai
theo chưa tận tận trái (tìm một dẫn xuất tận trái)
Vì vậy phân tích cú pháp từ trên xuống có thể được xem như một nổ lực tìm
kiếm một dẫn xuất tận trái cho chuỗi nguyên liệu. Nó cũng có thể được xem như một
nỗ lực xây dựng cây phân tích cú pháp cho nguyên liệu, khởi đi từ gốc và tạo ra các nút
của cây theo lỗi phiên đầu (preorder), nghĩa là xây dựng nút cha trước rồi lần lượt xây
dựng các nút con theo thứ tự từ trái sang.
Bây giờ ta xét một dạng tổng quát của kỹ thuật phân tích từ trên xuống có tên là
phân tích cú pháp đệ quy xuống (recursive descent parsing). Trong phương pháp phân
tích cú pháp đệ quy xuống, chúng ta xây dựng cây phân tích cú pháp bằng cách mô
phỏng hành động khai triển mỗi ký hiệu chưa tận bằng một hàm, khi khai triển một
chưa tận A theo A → α, chúng ta xây dựng một hàm funcA() thực hiện lần lượt các
hành động mô phỏng các ký hiệu có trong α theo đúng thứ tự đó.
1. Nếu ký hiệu hiện đang cần phân tích trong α là một tận a, hành động
tương ứng là đọc ký hiệu tiếp theo từ nguyên liệu và so xem ký hiệu đó có
phải là α hay không. Nếu ký hiệu đọc được cũng là α, hành động tiếp theo
là hành động tương ứng vói ký hiệu nằm bên phải a trong α. Ngược lại,
phân tích cú pháp thất bại.
2. Nếu ký hiệu trong α là một chưa tận B (B có thể là A), gọi hàm funcB()
tương ứng.
Ở trường hợp (2), một hàm có thể gọi đệ quy trực tiếp hoặc gián tiếp đến chính
nó. Ngoài vấn đề phải thực hiện trở lui trong một số tình huống, một số văn phạm có
thể có một hoặc nhiều luật sinh có đệ quy trái và chúng có thể khiến cho một thể phân
3
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
cú pháp đệ quy xuống phải trở lui hoặc chạy vào một vòng luẩn quẩn vô tận. Nghĩa là
khi cố gắng khai triển A, cuối cùng chúng ta có thể lại phải tiếp tục khai triển A mà

S → Aα | b
A → Ac | Sd | ε
Chưa tận S là đệ quy trái bời vì S => Aa => Sda nhưng không phải đệ quy trực
tiếp.
Thuật toán được trinh bày sau đây sẽ khử bỏ một cách có hệ thống các đệ quy
trái ra khỏi một văn phạm. Nó bảo đảm hoạt động được nếu văn phạm không có chu
trình (là dẫn xuất có dạng A =>* A) hoặc các ε luật sinh ( là luật sinh có dạng A → ε).
Các chu trình có thể được loại bỏ một cách có hệ thống ra khỏi một văn phạm cũng
như các ε luật sinh.
Thuật toán khử đệ quy trái Một văn phạm
 Nguyên liệu: Văn phạm G không vòng và không có các ε luật sinh
 Thành phẩm: Một văn phạm tương đương không có đệ quy trái.
 Phương pháp: Áp dụng thuật toán sau cho văn phạm G (Chú ý
rằng văn phạm không có đệ quy trái thu được có thể có các ε luật
sinh).
1.Sắp các chưa tận theo một thứ tự nào đó như A1, A2, …, An
2.For i:=1 to n do begin
for j:=1 to i-1 do begin
Thay mỗi luật sinh dạng Ai → Ajγ bằng các luật sinh
Aj → δ1 | δ2 |…| δk là tất cả các Aj luật sinh hiện hành.
End
khử bỏ đệ quy trái trực tiếp trong số các Ai luật sinh
5
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
end.
Lý do thuật toán trên hoạt động được là vì sau lần lặp thứ i-1 của vòng for ngoài
(bước 2), mọi luật sinh dạng Ak→Alα vơi k<i phải có l>k. kết quả là ở lần lặp tiếp
theo, vòng lặp trong (trên j) tăng dần giới hạn dưới cho m trong mọi luật sinh
Ai→Amα cho đến khi chúng ta có m>=i. Như thế việc loại bỏ đệ quy trái cho Ai luật
sinh buộc m phải lớn hơn i.

còn hai khả triển nào cho một chưa tận có một tiền tố chung.
Như vậy, trong nhiều trường hợp, bằng cách viết văn phạm một cách cẩn thận,
loại bỏ đệ quy trái ra khỏi văn phạm rồi thừa số hoá trái văn phạm, chúng ta có thể thu
được một văn phạm mà một thể phân cú pháp đệ quy xuống phân tích được nhưng
không cần phải trở lui, nghĩa là một thể phân cú pháp dự đoán (Predictive parser). Để
xây dụng một thể phân cú pháp dự đoán, khi cho trước kí hiệu nguyên liệu hiện hành a
và một chưa tận A cần được khai triển, chúng ta phải biết khả triển nào trong số các
khả triển của luật sinh A → α1 | α2 | … | αn là khả triển duy nhất dẫn xuất ra một chuỗi
bắt đầu bằng a. Nghĩa là khả triển thích hợp phải có khả năng được phát hiện ra khi chỉ
cần xem ký hiệu đầu tiên mà nó dẫn xuất. Các kết cấu dòng điều khiển (flow of
control) trong phần lớn các ngôn ngữ lập trình với các từ khoá phân biệt thường được
nhận ra theo cách này.
4. Sơ đồ chuyển vị cho thể phân cú pháp dự đoán
Để xây dựng sơ đồ chuyển vị của một thể phân cú pháp dự đoán từ một văn
phạm, trước tiên cần loại bỏ đệ quy trái ra khỏi văn phạm rồi thừa số hoá trái văn
phạm. Sau đó thực hiện các bước sau cho mỗi chưa tận A:
 Tạo một khởi trạng và một kết trạng.
7
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
 Với mỗi luật sinh A → X
1
X
2
X
n
, tạo một đường đi từ khởi trạng đến kết
trạng bằng các cạnh có nhãn là X
1
, X
2

1
),…, FIRST(Y
i-1
); Nghĩa là Y
1
Y
i-1
=>* ε. Nếu ε thuộc
FIRST(Y
1
) với mọi j=1, 2,…,k thì thêm ε vào FIRST(X). Chẳng hạn,
mọi tận trong FIRST(Y1) đều thuộc FIRST(X). Nếu Y
1
không dẫn xuất ε
thì chúng ta không thêm gì voà FIRST(X) nhưng nếu Y
1
=>*ε thì chúng
ta đưa FIRST(Y
2
) vào….
5.2.Tính FOLLOW
8
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
Để tính FOLLOW(A) cho các chưa tận A, chúng ta áp dụng các quy tắc sau đây
cho đến khi không thêm được gì nữa vào mọi tập FOLLOW.
1. Đặt $ vào tập FOLLOW(S), trong đó S là ký hiệu khởi đầu và $ là dấu
kết cuối nguyên liệu.
2. Nếu có một luật sinh A→αBβ thì mọi phần tử của tập FIRST(β) trừ ε
đều được đặt vào FOLLOW(B).
3. Nếu có một luật sinh A→α hoặc một luật sinh A→αBβ trong đó

nguyên liệu chứa chuỗi cần phân tích, theo sau là ký hiệu $ được dùng để đánh dấu đầu
phải, báo hiệu kết thúc chuỗi nguyên liệu. Chồng xếp chứa một loạt các ký hiệu văn
phạm với dấu $ chỉ ra đáy chồng xếp. Lúc ban đầu chồng xếp chứa ký hiệu khởi đầu
của văn phạm ở ngay bên trên $. Bảng phân tích cú pháp là một mảng hai chiều
M[A,a], trong đó A là một chưa tận. và a là một tận hoặc ký hiệu $.
10
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
Thể phân cú pháp được điều khiển bởi một chương trình hoạt động như sau.
Chương trình xét X, ký hiệu trên đỉnh chồng xếp, và a, ký hiệu nguyên liệu hiện hành.
Hai ký hiệu này xác định hành động của thể phân cú pháp có ba khả năng xảy ra.
1. Nếu X=a=$, thể phân cú pháp dừng, thông báo hoàn tất thành công.
2. Nếu X là một chưa tận, chương trình sẽ đọc mục ghi M[X,a] của bảng
M. Mục này sẽ là một X-luật sinh của văn phạm hoặc là mục báo lỗi.
Chẳng hạn nếu mục ghi M[X,a]={X→UVW}, thể phân cú pháp sẽ thay
X trên đỉnh chồng bằng WVU (với U ở đỉnh). Chúng ta giả thiết rằng thể
phân cú pháp chỉ in ra luật sinh được sử dụng làm thành phẩm; một đoạn
chương trình nào đó có thể cho thực hiện ở đây. Nếu M[X,a]=error, thể
phân cú pháp gọi một thủ tục khắc phục lỗi.
Hoạt động của thể phân cú pháp có thể được mô tả theo cấu hình của nó, là nội
dung chứa trong chồng xếp và phần nguyên liệu còn lại.
Thuật toán: Phân tích cú pháp dự đoán không đệ quy.
Nguyên liệu: Một chuỗi w và một bảng phân tích cú pháp M cho văn phạm G.
Thành phẩm: Nếu w thuộc L(G), cho ra một dẫn xuất tận trái của w, nếu không
thì báo lỗi.
Phương pháp: Khởi đầu, thể phân cú pháp có cấu hình với $S trong chồng xếp,
trong đó S, ký hiệu khởi đầu của G, nằm trên đỉnh chồng, và w$ trong vùng đệm
nguyên liệu. Chương trình sử dụng bảng phân tích cú pháp M để phân tích cú pháp cho
nguyên liệu được trình bày trong hình trên.
7. Xây dựng chương trình mô phỏng
Dựa vào những kiến thức tìm hiểu được trình bày trong phần trên, em đã xây

Sơ đồ luồng dữ liệu
13
Đồ Án Môn Học Chương Trình Dịch Predictive Parser
Qua một số bước tính toán các bước trung gian như tính FIRST, FOLLOW,
Xây dưng bảng phân tích cú pháp. Chương trình cho phép nhập vào một câu vào và
đoán nhận xem nó có thuộc văn phạm vừa nhập hay không.
Giao diện chức năng đoán nhận câu vào như sau:
14