Bài giảng Nhập môn chương trình dịch - Bài 4: Phân tích cú pháp - Hoàng Anh Việt

1Bài 4. 
PHÂN TÍCH CÚ PHÁP
Hoàng Anh Việt 
Viện CNTT&TT - ĐHBKHN
2Mục đích
• Sau khi học xong chương này, sinh viên sẽ 
nắm được:
– Các phương pháp phân tích cú pháp
– Cách cài đặt một bộ PTCP từ một Văn phạm phi 
ngữ cảnh
– Các khái niệm và sử dụng công cụ sinh bộ PTCP: 
Yacc.
Điều kiện
• Kiến thức cần có:
– Kiến thức cơ bản về Automat.
– Kiến thức về văn phạm phi ngữ cảnh CFG.
3
Tài liệu tham khảo
[1] Slide bài giảng
[2] Compilers : Principles, Technique and Tools - Alfred 
V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing 
Company, 1986.
[3] Automata and Formal Language, An Introduction- Dean 
Kelley- Prentice Hall, Englewood Cliffs, New Jersey 
07632
[4] Compilers course, CS 143 summer 2010, Standford 
University.
[5] Compiler Design – Reinhard Wilhelm, Dieter Maurer -
Addison – Wesley Publishing Company, 1996. 4
5Nội dung
1. Vai trò của bộ phân tích cú pháp (PTCP)
2. Văn phạm của ngôn ngữ lập trình
3. Phân tích cú pháp từ trên xuống
4. Phân tích cú pháp từ dưới lên
5. Bộ sinh bộ PTCP
6Nội dung
1. Vai trò của bộ phân tích cú pháp (PTCP)
2. Văn phạm của ngôn ngữ lập trình
3. Phân tích cú pháp từ trên xuống
4. Phân tích cú pháp từ dưới lên
5. Bộ sinh bộ PTCP
1. Vai trò của bộ phân tích cú pháp
• Bộ phân tích cú pháp nhận chuổi các token từ 
bộ phân tích từ vựng để tạo ra cấu trúc cú pháp 
của chương trình nguồn.
• Tồn tại ba loại bộ phân tích cú pháp:
• Phương pháp tổng quát: 
• Cocke-Younger-Kasami. 
• Earley.
• Phương pháp thông dụng: Phân tích từ trên 
xuống hay phân tích từ dưới lên.
7
1. Vai trò của bộ phân tích cú pháp
Mã nguồn (dãy các kí tự)
If (a == 0) min = a; Phân tích từ 
vựng
Phân tích cú 
pháp
Phân tích ngữ 
nghĩa
Cây cú pháp if
== = ;
a 0 min a
Dãy các từ tố (token)
If ( Id:a == 0 ) Id:min = Id:a ;
1. Vai trò của bộ phân tích cú pháp
• Mã nguồn
• Cây cú pháp
{
if (b == (0)) a = b;
while (a != 1) {
stdio.print(a);
a = a - 1;
}
}
block
if_stmt while_stmt
bin_op
== variable const
b 0
bin_op
!= variable const
b 1
block
expr_stmt
call
•
stdio print
variable
a
1. Vai trò của bộ phân tích cú pháp
• Kiểm tra tính đúng đắn về cú pháp của chương 
trình nguồn
• Xác định chức năng của các thành phần trong 
chương trình nguồn
I gave him the book
câu
chủ ngữ vị ngữ bổ ngữ trực tiếp bổ ngữ gián tiếp
cụm danh từ
quán từ danh từ
I gave him
the book
1. Vai trò của bộ phân tích cú pháp
• Input: Dãy các từ tố
• Output: Cây cú pháp
• Cài đặt: 
– Duyệt qua dãy các từ tố
– Xây dựng cây cú pháp
– Loại bỏ các cú pháp thừa trong cây cú pháp
VD: a+b (a)+(b) ((a)+((b))) bin_op
+ a b
1. Vai trò của bộ phân tích cú pháp
• Phân tích cú pháp không làm tất cả mọi công 
đoạn của chương trình dịch. Ví dụ: kiểm tra 
kiểu, khai báo biến, khởi tạo biến =>Để lại 
cho phần phân tích ngữ nghĩa.
• Bộ PTCP có cơ chế ghi nhận và xử lý các lỗi 
cú pháp thường gặp.
13
Nội dung
1. Vai trò của bộ phân tích cú pháp (PTCP)
2. Văn phạm của ngôn ngữ lập trình
3. Phân tích cú pháp từ trên xuống
4. Phân tích cú pháp từ dưới lên
5. Bộ sinh bộ PTCP
2. Văn phạm của ngôn ngữ lập trình
2.1 Đặc tả cú pháp của ngôn ngữ
2.2 Văn phạm nhập nhằng
2.3 Loại bỏ nhập nhằng
14
2.1. Đặc tả cú pháp của ngôn ngữ
• Vấn đề: Làm thế nào để mô tả chính xác và dễ 
dàng cú pháp của ngôn ngữ tạo nên mã nguồn?
• Giống như từ tố được mô tả bằng REs
• REs dễ cài đặt (bằng NFA hoặc DFA)
• Có thể dùng REs để mô tả cú pháp của ngôn 
ngữ lập trình được không?
15
2.1. Đặc tả cú pháp của ngôn ngữ
• Cú pháp của ngôn ngữ lập trình không thuộc 
lớp ngôn ngữ chính quy không thể mô tả 
bằng REs được
• Ví dụ: L { (, ) }* sao cho L là tập các cách 
viết () đúng.
• Nếu dùng RE để biểu diễn L phải đếm số 
lượng dấu “(“ chưa có dấu “)” tương ứng số 
đếm không bị giới hạn
16
2.1. Đặc tả cú pháp của ngôn ngữ
• Ta biết: RE DFA
• Số đếm không giới hạn số trạng thái không 
giới hạn mâu thuẫn với cấu trúc của DFA 
(hữu hạn)
17
( ( ( ( (
)))))
=6
2.1. Đặc tả cú pháp của ngôn ngữ
• Nhiều NNLT có cấu trúc đệ quy mà nó có thể 
được định nghĩa bằng các VP PNC (context-
free grammar) G với 4 thành phần G (V, T, P, 
S), trong đó:
– V : là tập hữu hạn các ký hiệu chưa kết thúc hay 
các biến (variables) 
– T : là tập hữu hạn các ký hiệu kết thúc (terminals). 
– P : là tập luật sinh của văn phạm (productions). 
– S ∈ V: là ký hiệu bắt đầu của văn phạm (start 
symbol). 
18
2.1. Đặc tả cú pháp của ngôn ngữ
• Ví dụ: mô tả ngôn ngữ L
S (S)S
S 
• CFG sử dụng định nghĩa đệ quy
• CFG trực quan hơn REs
S (S)S ((S)S)S (( )S)S  (())
• Một xâu nằm trong ngôn ngữ của CFG nếu có 
một dãy suy dẫn sử dụng các sản xuất của 
CFG tạo nên xâu đó
19
2.1. Đặc tả cú pháp của ngôn ngữ
• Cây PTCP có thể được xem như một dạng biểu 
diễn hình ảnh của một dẫn xuất.
• αAβ dẫn xuất ra αγβ (ký hiệu: αAβ ⇒ αγβ) nếu 
A → γ là một luật sinh, α và β là các chuỗi tùy ý 
các ký hiệu văn phạm.
• Nếu α1 ⇒ α2 ⇒ .. .. ⇒ αn ta nói α1 dẫn xuất ra 
(suy ra) αn
• Ký hiệu: ⇒ : dẫn xuất ra qua 1 bước 
⇒*: dẫn xuất ra qua 0 hoặc nhiều bước. 
⇒+ : dẫn xuất ra qua 1 hoặc nhiều bước.20
2.1. Đặc tả cú pháp của ngôn ngữ
• Tính chất của Dẫn xuất:
1. α ⇒* α với ∀α 
2. 2. α ⇒* β và β ⇒* γ thì α ⇒* γ 
• Ví dụ 4.1: xét xâu (1 + 2 + (3 + 4)) + 5, và bộ
luật sinh:
S E + S
S E
E số
E (S)
21
2.1. Đặc tả cú pháp của ngôn ngữ
S E + S | E
E số | (S)
• Xâu (1 + 2 + (3 + 4)) + 5
S E + S (S) + S (E + S) + S
(1 + S) + S (1 + E + S) + S
(1 + 2 + S) + S (1 + 2 + E) + S
(1 + 2 + (S)) + S (1 + 2 + (E + S)) + S
(1 + 2 + (3 + S)) + S (1 + 2 + (3 + E)) + 
S 
(1 + 2 + (3 + 4)) + S (1 + 2 + (3 + 4)) + 
E
(1 + 2 + (3 + 4)) + 5 
22
kí hiệu không kết thúc – vế trái
vế phải của sản xuất
2.1. Đặc tả cú pháp của ngôn ngữ
• Cây suy dẫn:
– Một dãy dẫn xuất bắt đầu từ S 
có thể mô tả dưới dạng cây 
suy dẫn
• Lá của cây là kí hiệu kết thúc; 
theo thứ tự duyệt sẽ tạo thành 
xâu vào
• Nút trong của cây là các kí hiệu 
không kết thúc
• Cây không chỉ rõ thứ tự của các 
dẫn xuất
23
S
E + S
E
4
( S )
E + S
E + S
E
( S )
E + S
2
1
3
E
5
2.1. Đặc tả cú pháp của ngôn ngữ
• Cây cú pháp:
– Giản lược các thông tin thừa 
khỏi cây suy dẫn
24
+
5+
+1
+2
43
S
E + S
E
4
( S )
E + S
E + S
E
( S )
E + S
2
1
3
E
5
2.1. Đặc tả cú pháp của ngôn ngữ
• Thứ tự dẫn xuất tùy ý, có thể chọn bất cứ một 
kí hiệu không kết thúc nào để áp dụng sản xuất
• Hai thứ tự dẫn xuất thường dùng: 
– Suy dẫn trái: chọn kí hiệu bên trái nhất
– Suy dẫn phải: chọn kí hiệu bên phải nhất
• Được sử dụng trong nhiều kiểu phân tích cú 
pháp tự động (automatic parsing)
25
2.1. Đặc tả cú pháp của ngôn ngữ
• Suy dẫn trái
S E+S (S) + S (E + S )+ S (1 + S)+S 
(1+E+S)+S (1+2+S)+S (1+2+E)+S 
(1+2+(S))+S (1+2+(E+S))+S (1+2+(3+S))+S 
(1+2+(3+E))+S (1+2+(3+4))+S (1+2+(3+4))+E
(1+2+(3+4))+5
• Suy dẫn phải
S E+S E+E E+5 (S)+5 (E+S)+5 
(E+E+S)+5 (E+E+E)+5 (E+E+(S))+5 
(E+E+(E+S))+5 (E+E+(E+E))+5 
(E+E+(E+4))+5 (E+E+(3+4))+5
(E+2+(3+4))+5 (1+2+(3+4))+5
• Cùng một cây suy dẫn, cùng sử dụng các dẫn xuất nhưng theo 
thứ tự khác nhau
26
2.2 Văn phạm nhập nhằng
• Xét văn phạm sau
S → S + S | S * S | number
• Sử dụng dẫn xuất khác nhau cho ra các cây suy 
dẫn khác nhau => Văn phạm nhập nhằng
28
2.2 Văn phạm nhập nhằng
S → S + S | S * S | number
• Nếu xâu vào là 1 + 2 * 3
• Suy dẫn 1:
S S + S 1 + S 1 + S * S 
1 + 2 * S 1 + 2 * 3
• Suy dẫn 2:
S S * S S + S * S 1 + S * S 
1 + 2 * S 1 + 2 * 3
29
*
3+
1 2
+
1 *
2 3
2.2 Văn phạm nhập nhằng
• Cây suy dẫn khác nhau cho kết quả tính toán 
khác nhau
• Văn phạm nhập nhằng 
 Có nhiều cách hiểu chương trình nguồn
30
*
3+
1 2
+
1 *
2 3
= 7 = 9
2.3 Loại bỏ nhập nhằng
• Loại bỏ đệ quy trái
• Tạo yếu tố trái
32
2.3.1 Loại bỏ đệ quy trái
• Đệ quy trái:
oMột văn phạm là đệ qui trái (left recursive) nếu nó 
có một ký hiệu chưa kết thúc A sao cho có một dẫn 
xuất , với α là một chuỗi nào đó. 
o Các phương pháp phân tích từ trên xuống không
thể nào xử lý văn phạm đệ qui trái, do đó cần phải 
dùng một cơ chế biến đổi tương đương để loại bỏ 
các đệ qui trái. 
o Có 2 loại:
oTrực tiếp: Dạng A -> A α
oGián tiếp: A =>i Aα với i>=2 33
2.3.1 Loại bỏ đệ quy trái
• Với đệ quy trái trực tiếp: Luật sinh có dạng
Sẽ thay thế bởi: 
• Với đệ quy trái gián tiếp: áp dụng giải thuật 
loại bỏ đệ quy (áp dụng cho đệ quy trái nói 
chung).
34
2.3.1 Loại bỏ đệ quy trái
Giải thuật 3.1: Loại bỏ đệ quy trái.
– Input: VP không tuần hoàn (không có luật sinh 
A=> +A) và không có luật sinh ε ( không có luật 
sinh A-> ε )
– Output: VP tương đương không đệ quy trái.
– Các Bước:
B1. Sắp xếp các ký hiệu không kết thúc theo thứ tự A1 , 
A2, , An
35
2.3.1 Loại bỏ đệ quy trái
Giải thuật 4.1: Loại bỏ đệ quy trái (tiếp)
B2:
36
2.3.1 Loại bỏ đệ quy trái
• Ví dụ: xét VP đệ quy
37
2.3.2 Tạo yếu tố trái
• Là phép biến đổi văn phạm thuận tiện cho việc 
phân tích dự đoán (phân tích dự đoán?)
• Thí dụ: Ta có hai luật sinh:
stmt -> if exp then stmt else stmt
| if exp then stmt
• Cả hai luật sinh đều có if dẫn đầu nên ta sẽ 
không biết chọn luật sinh nào để triển khai. Vì 
thế để làm chậm lại quyết định lựa chọn chúng 
ta sẽ tạo ra thừa số trái.
38
2.3.2 Tạo yếu tố trái
• Một cách tổng quát: khi có luật 
thì biến đổi thành:
• Giải thuật 4.2: Tạo yếu tố trái cho văn phạm
– Input: văn phạm G
– Output: văn phạm tương đương với yếu tố trái.
– Phương pháp: Tìm chuỗi α dẫn đầu chung của các vế phải 
luật sinh, thí dụ
là chuỗi không bắt đầu bởi . Ta thay các luật trên bằng 
các luật: 
39
A -> A’ | 
A’-> 1 | 2 | 3  | n
2.3.2 Tạo yếu tố trái
• Ví dụ: Áp dụng thuật toán 3.2 cho văn phạm 
sau: 
S -> iEtS | iEtSeS | a
E -> b
40
=> Văn phạm yếu tố trái tương đương:
41
Nội dung
1. Vai trò của bộ phân tích cú pháp (PTCP)
2. Văn phạm của ngôn ngữ lập trình
3. Phân tích cú pháp từ trên xuống
4. Phân tích cú pháp từ dưới lên
5. Bộ sinh bộ PTCP
3. Phân tích cú pháp từ trên xuống
3.1 Phân tích cú pháp đệ quy đi xuống
3.2 Phân tích cú pháp dự đoán
42
3.1 Phân tích cú pháp đệ quy đi xuống
• Mục tiêu: xây dựng cây suy dẫn trái trong khi 
đọc dãy từ tố
43
Suy dẫn
Từ tố 
nhìn trước
Dãy từ tố
Đã đọc / Chưa đọc
S
E+S
(S)+S
(E+S)+S
(1+S)+S
(1+E+S)+S
(1+2+S)+S
(1+2+E)+S
(1+2+(S))+S
(
(
1
1
2
2
(
(
3
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
(1+2+(3+4))+5
3.1 Phân tích cú pháp đệ quy đi xuống
• Ta muốn lựa chọn sản xuất dựa vào từ tố nhìn 
trước
(1) S E (S) (E) (1)
(1)+2 S E + S (S) + S (E) + S
(1)+E (1)+2
• Có thể quay lui để quét lại chuỗi nhập???
44
S E + S | E
E num | (S)
3.2 Phân tích cú pháp dự đoán 
(Predictive Parser)
• Với bộ văn phạm đã tinh chỉnh (loại bỏ đệ quy, 
thêm yếu tố trái) => có thể sử dụng PTCP đệ 
quy đi xuống, nhưng không cần quay lui, gọi 
là phân tích cú pháp dự đoán.
45
3.2.1 Xây dựng sơ đồ dịch cho PTDD
• Các bước xây dựng sơ đồ dịch cho mỗi ký tự 
chưa kết thúc A:
– B1: Loại bỏ đệ quy trái, tạo yếu tố trái cho văn 
phạm.
– B2: Tạo một trạng thái khởi đầu và một trạng thái 
kết thúc. 
– B3: Với mỗi luật sinh A → X1X2 ... Xn , tạo một 
đường đi từ trạng thái khởi đầu đến trạng thái kết 
thúc bằng các cạnh có nhãn X1X2 ... Xn 
46
3.2.1 Xây dựng sơ đồ dịch cho PTDD
• Luật sinh có dạng thì tương ứng 
sơ đồ dịch có dạng:
• Luật sinh có dạng thì tương ứng 
sơ đồ dịch có dạng:
47
3.2.1 Xây dựng sơ đồ dịch cho PTDD
• Ví dụ 4.2: Xét văn phạm cho bởi:
E -> E + T |T
T -> T*F|F
F -> (E)|id
• Loại bỏ đệ quy trái trong văn phạm, ta được 
văn phạm tương đương:
48
3.2.1 Xây dựng sơ đồ dịch cho PTDD
• Các sơ đồ dịch tương ứng:
49
3.2.1 Xây dựng sơ đồ dịch cho PTDD
• Một chương trình PTCP dự đoán xây dựng dựa 
trên các sơ đồ dịch cho các ký hiệu chưa kết 
thúc.
• Duyệt chuỗi token:
– So sánh ký hiệu chưa kết thúc với chuỗi token đầu 
vào.
– Đưa ra lời gọi đệ quy mỗi khi đi theo cạnh có nhãn 
là ký hiệu chưa kết thúc.
50
3.2.2 Phân tích dự đoán không đệ quy
• Mục đích chính: xác định luật sinh được áp 
dụng cho bước tiếp theo.
• Giải pháp: Sử dụng một stack để thực hiện 
phân tích thay vì lời gọi đệ quy
51
3.2.2 Phân tích dự đoán không đệ quy
• Cấu tạo bộ phân tích dự đoán
52
3.2.2 Phân tích dự đoán không đệ quy
• Input: là bộ đệm chứa chuỗi token cần phân 
tích, kết thúc bởi ký hiệu $. 
• STACK chứa một chuỗi các ký hiệu văn phạm 
với ký hiệu $ nằm ở đáy Stack. 
• Bảng phân tích M là một mảng hai chiều 
dạng M[A,a], trong đó A là ký hiệu chưa kết 
thúc, a là ký hiệu kết thúc hoặc $. (Mỗi văn 
phạm có một bảng phân tích M tương ứng)
53
3.2.2 Phân tích dự đoán không đệ quy
• Hoạt động: Chương trình xét ký hiệu X trên đỉnh 
Stack và ký hiệu nhập hiện hành a:
1. Nếu X = a = $ bộ phân tích dừng và báo thành công.
2. Nếu X = a $ bộ phân tích sẽ đẩy X ra khỏi Stack và 
dịch đầu đọc đến ký hiệu nhập kế tiếp.
3. Nếu X là ký hiệu không kết thúc bộ phân tích sẽ xét bảng 
ma trận tại M[X,a] để tìm luật sinh hoặt lỗi:
a) Nếu M[X,a] là một luật sinh có dạng X → UVW thì Pop 
X ra khỏi đỉnh Stack và Push W, V, U vào Stack (với U trên 
đỉnh Stack), đồng thời bộ xuất sinh ra luật sinh X → UVW. 
b) Nếu M[X,a] = error, gọi chương trình phục hồi lỗi.
54
3.2.2 Phân tích dự đoán không đệ quy
Giải thuật 4.3:
• Nhập: Chuỗi nhập w và bảng phân tích M cho 
văn phạm G.
• Xuất: Nếu w thuộc L(G), sẽ tạo ra dẫn xuất 
trái của w, ngược lại sẽ báo lỗi.
• Phương pháp: Lúc đầu cấu hình của bộ phân 
tích là ($S, w$) với S là ký hiệu mục tiêu của 
G. Đặt ip (là con trỏ hoặc còn gọi là đầu đọc 
của bộ phân tích) vào ký hiệu nhập đầu tiên 
của w$.
55
3.2.2 Phân tích dự đoán không đệ quy
Giải thuật 4.3:
56
3.2.2 Phân tích dự đoán không đệ quy
Ví dụ 4.3: Giả sử chúng ta có văn phạm G:
E -> E + T | T
T -> T *F | F
F -> (E) | id
Chúng ta sẽ thực hiện loại bỏ đệ quy trái, nhận được G’:
E -> TE’
E’-> +TE’ | ε
T -> FT’
T’ ->*FT’| ε
F -> (E) | id 57
3.2.2 Phân tích dự đoán không đệ quy
• Bây giờ chúng ta sẽ phân tích cú pháp cho câu 
nhập w = id + id * id bằng bảng phân tích M 
cho trước (cách xây dựng bảng ở phần sau)
58
3.2.2 Phân tích dự đoán không đệ quy
=> Các bước phân tích cú pháp cho w:
59
3.2.2 Phân tích dự đoán không đệ quy
=> Cây suy dẫn được xây dựng:
60
3.2.3 Xây dựng bảng phân tích M
• Xây dựng bảng M: dựa vào tập hợp First và Follow.
• Trong đó:
– Ðịnh nghĩa FIRST(α): Giả sử α là một chuỗi các ký hiệu văn 
phạm (bao gồm cả kết thúc và không kết thúc), FIRST(α) là tập 
hợp các ký hiệu kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ 
α. Nếu α ⇒* ε thì ε ∈ FIRST(α).
– Ðịnh nghĩa FOLLOW(A): (với A là một ký hiệu chưa kết 
thúc) là tập hợp các ký hiệu kết thúc a mà nó xuất hiện ngay 
sau A (bên phía phải của A) trong một dạng câu nào đó. Tức là 
tập hợp các ký hiệu kết thúc a, sao cho tồn tại một dẫn xuất 
dạng S ⇒* αAaβ. Chú ý rằng nếu A là ký hiệu phải nhất trong 
một dạng câu nào đó thì $ ∈ FOLLOW(A) ($ là ký hiệu kết 
thúc chuỗi nhập ). 61
3.2.3 Xây dựng bảng phân tích M
Các quy tắc tính First(X) với X là ký hiệu văn 
phạm (Thực hiện cho đến khi không còn có ký hiệu kết thúc nào 
hoặc ε có thể thêm vào tập FIRST(X)):
• Nếu X là ký hiệu kết thúc thì first(X) = {X}
• Nếu X-> ε là luật sinh thì ta thêm ε vào first(X)
• Nếu X là ký hiệu không kết thúc và X ->Y1Y2Y3 ...Yk là một 
luật sinh thì:
• Thêm tất cả các ký hiệu kết thúc khác ε của FIRST(Y1) vào 
FIRST(X). 
• Nếu ε ∈ FIRST(Y1) thì tiếp tục thêm vào FIRST(X) tất cả các ký hiệu 
kết thúc khác ε của FIRST(Y2). 
• Nếu ε ∈ FIRST(Y1) ∩ FIRST(Y2) thì thêm tất cả các ký hiệu kết thúc 
khác ε ∈ FIRST(Y3) ... 
• Cuối cùng thêm ε vào FIRST(X) nếu ε ∈ ∩ki=1 FIRST(Yi)
62
3.2.3 Xây dựng bảng phân tích M
• Ví dụ 4.4 xét văn phạm:
E -> TE’
E’-> +TE’ | ε
T -> FT’
T’ ->*FT’| ε
F -> (E) | id
• Vì E' → ε ⇒ ε ∈ FIRST(E').
Do E' → + TE' mà FIRST(+) = 
{+} ⇒ FIRST(E') = {+, ε } 
• Tương tự FIRST(T') = {*, ε }
• Vì F ⇒ (E) | id ⇒ FIRST(F) = { (, id } 
• Từ T → F T' và ε ∉ FIRST(F) ⇒
FIRST(T) = FIRST(F)= { (, id } 
• Từ E → T E' và ε ∉ FIRST(T) ⇒
FIRST(E) = FIRST(T)= { (, id } 
63
3.2.3 Xây dựng bảng phân tích M
• Tính FIRST(γ)? (γ là một chuỗi)
– FIRST(X) FIRST(γ) nếu X γ
– FIRST(a ) = {a}
– FIRST(X ) FIRST(X)
– FIRST(X ) FIRST( ) nếu X-> ε
• Thuật toán: Giả sử với mọi γ, FIRST(γ) rỗng, 
áp dụng các luật trên liên tục để xây dựng các 
tập FIRST.
64
3.2.3 Xây dựng bảng phân tích M
Các quy tắc tính follow(A) cho tất cả các ký 
hiệu không kết thúc A (Áp dụng các quy tắc sau cho 
đến khi không thể thêm gì vào mọi tập FOLLOW được nữa).
1. Cho ký hiệu $ vào follow(S), S là ký hiệu bắt đầu 
văn phạm, $ là ký hiệu kết thúc chuỗi nhập.
2. Tồn tại luật A-> B , tất cả các ký hiệu thuộc 
first( ) sẽ cho vào follow(B) trừ ε.
3. Tồn tại luật A-> B hoặc A-> B mà first( ) = 
{ε} thì tất cả các ký hiệu follow(A) sẽ cho vào 
follow(B).
65
FOLLOW(B) FIRST( ) 
FOLLOW(B) FOLLOW(A) nếu 
3.2.3 Xây dựng bảng phân tích M
• Với văn phạm ở ví dụ 4.4:
66
3.2.3 Xây dựng bảng phân tích M
• Thuật toán xây dựng bảng M:
• Nhập: Văn phạm G.
• Xuất: Bảng phân tích M.
• Phương pháp:
1. Với mỗi luật sinh A -> hãy thực thi bước 2 và 3.
2. Với mỗi ký hiệu kết thúc a thuộc first( ), thêm A -> 
vào M[A, a].
3. Nếu ký hiệu ε thuộc first( ), thêm A -> ε vào M[A, b] 
sao cho b thuộc follow(A). Nếu $ thuộc follow(A) thì 
thêm A -> ε vào M [A, $]. 
4. Những phần tử của bảng M trống, hãy đánh dấu lỗi.
67
Đặt A α:
- Dòng A, các cột FIRST(α)
- Dòng A, các cột FOLLOW(A) nếu 
α->ε
3.2.3 Xây dựng bảng phân tích M
• Ví dụ xây dựng bảng M trong ví dụ 4.3:
68
3.2.3 Xây dựng bảng phân tích M
• Bài tập: Cho G:
Xây dựng bảng phân tích M?
69
S ES’
S’ + S 
S’ 
E số 
E (S)
Ví dụ
• Triệt tiêu được
– Chỉ có S’ triệt tiêu được
• FIRST
– FIRST(E S’ ) = {số, ( }
– FIRST(+S) = { + }
– FIRST(số) = {số}
– FIRST( (S) ) = { ( } 
– FIRST(S’) = { + }
• FOLLOW
– FOLLOW(S) = { $, ) }
– FOLLOW(S’) = {$, )}
– FOLLOW(E) = { +, ), $}
S ES’
S’ + S 
S’ 
E số 
E (S)
số + ( ) $
S ES’ ES’
S’ +S 
E số (S)
3.2.3 Văn phạm LL(1)
• Giải thuật tạo bảng M có thể áp dụng cho văn 
phạm G bất kỳ.
• Nếu G mơ hồ hoặc đệ quy trái => trong M có 
đa trị (nhiều luật sinh trong một ô)
• Ví dụ 4.5: cho văn phạm G
S -> iEtSS’ | a
S’-> eS’ | €
E -> b
first(S) = {i,a}, first(S’) = {e,€}, first(E) = {b}
follow(S) = {e,$}, follow(S’) = {e,$}, follow(E) = {t} 
71
3.2.3 Văn phạm LL(1)
=> Bảng phân tích M cho ví dụ 4.5
72
3.2.3 Văn phạm LL(1)
• Ví dụ 4.5 (tiếp) Ðây là một văn phạm mơ hồ và sự mơ 
hồ này được thể hiện qua việc chọn luật sinh khi gặp ký 
hiệu e. Ô tại vị trí M [S', e] được gọi là ô đa trị.
• Văn phạm không có phần tử nào của bảng phân tích M có 
nhiều hơn một trị thì được gọi là văn phạm LL(1):
– L: Left-to-right parse (mô tả hành động quét chuỗi nhập từ 
trái sang phải) 
– L: Leftmost-derivation (biểu thị việc sinh ra một dẫn xuất 
trái cho chuỗi nhập)
– 1: 1-symbol lookahead (tại mỗi một bước, đầu đọc chỉ đọc 
trước được một token để thực hiện các quyết định phân tích 
cú pháp) 
73
3.2.3 Văn phạm LL(1)
• Tính chất của VP LL(1):
– Không là VP đệ quy trái hay mơ hồ
– Với các 2 luật sinh phân biệt: A ->α|β :
1. Không có một ký hiệu kết thúc a nào mà cả α và β đều 
dẫn xuất ra các chuỗi bắt đầu bằng a.
2. Tối đa chỉ có α hoặc chỉ có β có thể dẫn xuất ra chuỗi 
rỗng. 
3. Nếu β ⇒* ε thì α không dẫn xuất được chuỗi nào bắt đầu 
bằng một ký hiệu kết thúc thuộc tập FOLLOW(A). 
74
Biến Văn phạm mơ hồ/đệ quy => LL(1) ?
3.2.4 Khắc phục lỗi
• Lỗi xuất hiện trong các trường hợp sau: 
• Một là ký hiệu kết thúc trên stack không trùng với 
ký hiệu nhập đang được đọc. 
• Hai là A là ký hiệu không kết thúc trên đỉnh stack, 
a trên chuỗi nhập được đọc, mà M[A, a] là trống.
• Một số heuristics được áp dụng cho việc khắc 
phục lỗi.
• Ta cho tất cả các ký hiệu trong follow(A) vào 
tập token đồng bộ của A (synch). Chúng ta làm 
như vậy cho mỗi ký hiệu không kết thúc A. 75
3.2.4 Khắc phục lỗi
• Ví dụ 4.5: Xét VP G:
E -> TE’
E’-> +TE’ | ε
T -> FT’
T’ ->*FT’| ε
F -> (E) | id
=>FOLLOW(E) = FOLLOW(E') = { $, )} 
FOLLOW(T) = FOLLOW(T') = { +,$, )} 
FOLLOW(F) = {*,+, $, )} 
76
3.2.4 Khắc phục lỗi
77
Bảng phân tích cú pháp M phục hồi lỗi 
3.2.4 Khắc phục lỗi
• Bảng này được sử dụng như sau: 
– Nếu M[A,a] là rỗng thì bỏ qua token a. 
– Nếu M[A,a] là "synch" thì lấy A ra khỏi Stack 
nhằm tái hoạt dộng quá trình phân tích. 
– Nếu một token trên đỉnh Stack không phù hợp 
với token trong dòng nhập thì lấy token ra khỏi 
Stack. 
• Với chuỗi nhập: + id * + id, bộ phân tích cú 
pháp và cơ chế phục hồi lỗi thực hiện:
78
3.2.4 Khắc phục lỗi
79
3.2.4 Khắc phục lỗi
• Bài tập: Phân tích và khắc phục lỗi cho chuỗi 
nhập:
W = )id*+id
80
Kiểm tra
Bài 1
• Cho văn phạm G chứa các 
luật sinh sau: 
S → xAB 
A → Ayz | y
B → t
1. Khử đệ quy trái
2. Xây dựng bảng phân tích M
3. Sử dụng bộ phân tích cú pháp
trên để xây dựng cây suy dẫn
(chỉ rõ các bước): 
xyyzt
Bài 2
• Cho Văn phạm G chứa các
luật sinh:
E E op E | (E) | num
op + | * | ^
1. Khử đệ quy trái
2. Xây dựng bảng phân tích M
3. Sử dụng bộ phân tích cú pháp
trên để xây dựng cây suy dẫn
(chỉ rõ các bước): 
2 ^ 3 + 4 * 5 
81
Kiểm tra (2)
Bài 3:
Xét ngôn ngữ sử dụng các thẻ (tags) được mô tả như sau:
• Ký hiệu kết thúc: { , / , = , word }
• Mỗi thẻ bắt đầu bằng 
• Có hai loại thẻ: thẻ mở và thẻ đóng
• Thẻ mở có dạng , tức là bắt đầu bằng word, tiếp theo là các cặp word
được nối với nhau bằng dấu =, thể hiện các thuộc tính của thẻ.
• Thẻ đóng có dạng 
• Mỗi thẻ mở phải có một thẻ đóng tương ứng phía sau. Giữa cặp thẻ mở và đóng đó có thể có dãy 
các word dài tuỳ ý.
• Ví dụ: xâu word word word
thuộc ngôn ngữ trên.
a, Hãy viết văn phạm phi ngữ cảnh cho ngôn ngữ trên .
b, Tìm các kí hiệu có thể triệt tiêu được.
c, Tính các tập FIRST, FOLLOW cho văn phạm trên.
d, Lập bảng phân tích M, chỉ ra những vị trí xung đột trên bảng.
e, Hãy chỉ ra nguyên nhân khiến văn phạm này không phải là LL(1).
82
Xây dựng bộ PTCP trên xuống
Viết văn phạm của ngôn ngữ
Viết văn phạm LL(1)
Bảng phân tích LL(1)
Phân tích đệ quy xuống
Phân tích đệ quy xuống 
kết hợp xây dựng cây cú 
pháp
84
Nội dung
1. Vai trò của bộ phân tích cú pháp (PTCP)
2. Văn phạm của ngôn ngữ lập trình
3. Phân tích cú pháp từ trên xuống
4. Phân tích cú pháp từ dưới lên
5. Bộ sinh bộ PTCP
Tổng kết Bài 4
• Các kiến thức cần nhớ:
• Về nhà đọc thêm:
85
Bài học phần sau
Bài 5
86
Thảo luận
87