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 (Phần 2)

1Bài 4. 
PHÂN TÍCH CÚ PHÁP
Hoàng Anh Việt 
Viện CNTT&TT - ĐHBKHN
2Nộ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
4. Phương pháp phân tích từ dưới lên
• Thí dụ 4.6. Cho văn phạm G.
S ->aABe 
A ->Abc|b 
B ->d
Phân tích câu w = abbcde.
3
4. Phương pháp phân tích từ dưới lên
4
4. Phương pháp phân tích từ dưới lên
5
Phân tích từ dưới lên 
(bottom-up parsing)
• Kỹ thuật phân tích mạnh hơn
• Văn phạm lớp LR có khả năng mô tả mạnh hơn văn 
phạm lớp LL, có thể mô tả văn phạm đệ quy trái (có 
trong hầu hết các ngôn ngữ lập trình)
• Dễ dàng mô tả các ngôn ngữ lập trình thông thường
• Bộ phân tích cú pháp gạt – thu gọn (Shift-Reduce parsing) 
– Xây dựng cây suy dẫn phải
– Tự động xây dựng bộ phân tích cú pháp 
VD: yacc, CUP
– Phát hiện lỗi ngay khi xuất hiện
– Cho phép phục hồi khi lỗi xảy ra
Phân tích trên xuống
• Suy dẫn trái
• Toàn bộ cây phía trên 
một kí hiệu được sinh ra
• Phải có khả năng đoán 
trước được sản xuất
S
S + E
E
( S )
S + E
S + E
E
1
2
( S )
S + E
E
3
4
5
Phân tích dưới lên (1)
• Suy dẫn phải
• Cây suy dẫn được xây dựng ngược lại
– Bắt đầu từ kí hiệu kết thúc
– Kết thúc tại kí hiệu bắt đầu
• Ví dụ
(1+2+(3+4))+5 (E+2+(3+4))+5 
(S+2+(3+4))+5 (S+E+(3+4))+5 
(S+(3+4))+5 (S+(E+4))+5 (S+(S+4))+5 
(S+(S+E))+5 (S+(S))+5 (S+E)+5 
(S)+5 E+5 S+5 S+E S
S S+E | E
E số | (S)
Phân tích dưới lên (2)
(1+2+(3+4))+5 (1+2+(3+4))+5
(E+2+(3+4))+5 (1 +2+(3+4))+5
(S+2+(3+4))+5 (1 +2+(3+4))+5
(S+E+(3+4))+5 (1+2 +(3+4))+5
(S+(3+4))+5 (1+2+(3 +4))+5
(S+(E+4))+5 (1+2+(3 +4))+5
(S+(S+4))+5 (1+2+(3 +4))+5
(S+(S+E))+5 (1+2+(3+4 ))+5
(S+(S))+5 (1+2+(3+4 ))+5
(S+E)+5 (1+2+(3+4) )+5
(S)+5 (1+2+(3+4) )+5
E+5 (1+2+(3+4)) +5
S+E (1+2+(3+4))+5
S (1+2+(3+4))+5
S
u
y
 d
ẫ
n
p
h
ả
i
Phân tích dưới lên (3)
(1+2+(3+4))+5 
(E+2+(3+4))+5
(S+2+(3+4))+5 
(S+E+(3+4))+5 
• Phân tích dưới lên có 
nhiều thông tin hơn khi 
phân tích
S
S + E
E
( S )
S + E
S + E
E
1
2
( S )
S + E
E
3
4
5
Phân tích dưới lên và 
phân tích trên xuống
• Phân tích dưới lên không cần sinh ra toàn bộ 
cây suy dẫn trong quá trình phân tích
Đã đọc Chưa đọc
Phân tích trên xuống
Đã đọc Chưa đọc
Phân tích dưới lên
4.1 Phân tích gạt – thu gọn (1)
• Phân tích bằng một dãy thao tác: gạt và thu gọn
• Mỗi thời điểm, trạng thái của bộ phân tích là ngăn 
xếp các kí hiệu kết thúc và không kết thúc
• Cấu hình tại mỗi thời điểm gồm:
ngăn xếp + xâu các kí hiệu chưa đọc
Suy dẫn Ngăn xếp Chưa đọc
(1+2+(3+4))+5 
(E+2+(3+4))+5 
(S+2+(3+4))+5 
(S+E+(3+4))+5 
(E
(S 
(S+E
(1+2+(3+4))+5
+2+(3+4))+5
+2+(3+4))+5
+(3+4))+5
4.1 Phân tích gạt – thu gọn (2)
• Gạt: Đọc và đưa một kí hiệu kết thúc của xâu 
vào stack
• Thu gọn: Thay thế một xâu ở đỉnh của ngăn 
xếp bằng kí hiệu không kết thúc X với X 
(pop , push X)
Ngăn xếp Chưa đọc Thao tác
(
(1
1+2+(3+4))+5
+2+(3+4))+5
Gạt 1
Ngăn xếp Chưa đọc Thao tác
(S+E
(S
+(3+4))+5
+(3+4))+5
Thu gọn: S S+E
4.1 Phân tích gạt – thu gọn (3)
Suy dẫn Ngăn xếp Chưa đọc Thao tác
(1+2+(3+4))+5 
(1+2+(3+4))+5 
(1+2+(3+4))+5 
(E+2+(3+4))+5 
(S+2+(3+4))+5 
(S+2+(3+4))+5 
(S+2+(3+4))+5 
(S+E+(3+4))+5 
(S+(3+4))+5 
(S+(3+4))+5 
(S+(3+4))+5 
(S+(3+4))+5 
(S+(E+4))+5 
(S+(S+4))+5 
(S+(S+4))+5 
...
(
(1
(E 
(S
(S+
(S+2
(S+E
(S
(S+
(S+(
(S+(3
(S+(E
(S+(S
(S+(S+
...
(1+2+(3+4))+5
1+2+(3+4))+5
+2+(3+4))+5
+2+(3+4))+5
+2+(3+4))+5
2+(3+4))+5
+(3+4))+5
+(3+4))+5
+(3+4))+5
(3+4))+5
3+4))+5
+4))+5
+4))+5
+4))+5
4))+5
...
gạt (
gạt 1
thu gọn E 1
thu gọn S E
gạt +
gạt 2
thu gọn E 2
thu gọn S S+E
gạt +
gạt (
gạt 3
thu gọn E 3
thu gọn S E
gạt +
gạt 4
...
Các vấn đề nảy sinh
• Cần xác định khi nào gạt hoặc thu gọn hoặc 
thu gọn với sản xuất nào?
• Thu gọn sản xuất rỗng 
X → ε
• Có nhiều cách thu gọn
S E hay S S+E
Lựa chọn thao tác
• Tại mỗi thời điểm, từ cấu hình
• Xác định
– Gạt a, ngăn xếp trở thành 
– Thu gọn X , nếu S = , 
ngăn xếp trở thành 
• Nếu S = , cần lựa chọn gạt a hoặc 
thu gọn X dựa vào tiền tố 
– Với mỗi khả năng thu gọn X có một 
– Cần tìm cách đánh dấu các khả năng thu gọn
Trạng thái của 
bộ phân tích gạt – thu gọn
• Mục tiêu: Xác định khả năng thu gọn hợp lệ 
tại từng thời điểm
• Ý tưởng: gộp các khả năng có thể có của tiền 
tố thành trạng thái của bộ phân tích
• Các vấn đề nảy sinh:
– Tính toán các trạng thái của bộ phân tích
– Tính toán các trạng thái kết thúc
– Phân tích tất định (loại văn phạm nào)
– Kích cỡ của bộ phân tích (số lượng trạng thái)
4.2 Bộ phân tích cú pháp LR 
Phân tích cú pháp LR(k):
• L (left - to - right): Duyệt chuỗi nhập từ trái 
sang phải. 
• R (rightmost derivation): Xây dựng chuỗi dẫn 
xuất phải nhất đảo ngược. 
• k : Số lượng ký hiệu nhập được xét tại mỗi 
thời điểm dùng để đưa ra quyết định phân tích. 
Khi không đề cập đến k, hiểu ngầm là k = 1. 
18
4.2 Bộ phân tích cú pháp LR 
Các tính chất của phương pháp phân tích LR(k):
• Bộ phân tích LR có thể nhận dạng được cấu trúc cú pháp 
của các ngôn ngữ lập trình do văn phạm phi ngữ cảnh tạo 
ra.
• Phương pháp LR là phương pháp tổng quát nhất của 
phương pháp phân tích gạt và thu gọn, không bị quay lui.
• Lớp văn phạm có thể dùng phương pháp LR là một lớp 
rộng lớn hơn lớp văn phạm có thể sử dụng phương pháp 
dự đoán. 
• Bộ phân tích cú pháp LR cũng có thể xác định lỗi cú pháp 
nhanh ngay trong khi duyệt dòng nhập từ trái sang phải.
19
Nhược điểm?
Cấu tạo bộ phân tích LR
20
Mô hình bộ phân tích LR
Cấu tạo bộ phân tích LR
• Stack được dùng để chứa chuỗi ký hiệu có dạng 
s0X1s1X2Xmsm, với sm nằm trên đỉnh stack, Xi 
được gọi là ký hiệu văn phạm, si là trạng thái tóm tắt 
thông tin bên dưới stack. Cặp(si, Xi) sẽ xác định một 
trị được lưu chứa trong bảng phân tích.
• Cấu hình (configuration) của một bộ phân tích cú 
pháp LR là một cặp, trong đó thành phần đầu là nội 
dung của Stack, phần sau là chuỗi nhập chưa phân 
tích: 
(s0X1s1X2s2 ... Xmsm, aiai+1... an$) 
21
Cấu tạo bộ phân tích LR
• Bảng phân tích bao gồm 2 phần: hàm action 
và hàm goto:
– action[sm, ai] có thể có một trong 4 giá trị : 
1. shift s: đẩy s, trong đó s là một trạng thái. 
2. reduce A→ β: thu gọn bằng luật sinh A→ β. 
3. accept: Chấp nhận 
4. error: Báo lỗi 
– Goto lấy 2 tham số là một trạng thái và một ký 
hiệu văn phạm, nó sinh ra một trạng thái. 
22
Cấu hình
• Với sm là ký hiệu nằm trên đỉnh Stack, ai là ký hiệu 
nhập hiện tại thì cấu hình có được tại mỗi bước: 
– Nếu action[sm, ai] = Shift s : Thực hiện phép đẩy để được 
cấu hình mới: 
– Nếu action[sm, ai] = Reduce(A → β) thì thực hiện phép thu 
gọn để được cấu hình:
Trong đó: s = goto[sm-i, A]
– Nếu action[sm, ai] = accept: quá trình phân tích kết thúc.
– Nếu action[sm, ai] = error: gọi thủ tục phục hồi lỗi.
23
Giải thuật LR
• Nhập: chuỗi nhập w, bảng phân tích action 
goto của văn phạm G (giả sử đã có).
• Xuất: nếu w thuộc L (G), nó tạo ra sự phân 
tích từ dưới lên. Ngược lại, bộ phân tích sẽ báo 
lỗi.
• Phương pháp:
• Thời điểm ban đầu stack có trạng thái s0.
• Chuỗi w$ nằm trên bộ đệm nhập.
• Bộ phân tích đặt đầu đọc (con trỏ ip) vào ký hiệu 
nhập đầu tiên của w.
24
Giải thuật LR
25
Ví dụ
Cho văn phạmG
(1) E -> E + T 
(2) E -> T 
(3) T -> T * F
(4) T -> F
(5) F -> (E)
(6) F -> id
Phân tích câu w = id *id + id
26
Bảng phân tích cho 
văn phạm ví dụ
27
Trong đó:
si : chuyển trạng thái i 
ri : thu gọn bởi luật sinh i 
acc: accept (chấp nhận) 
error : khoảng trống 
Các bước chuyển trạng thái trên stack và 
nội dung bộ đệm nhập
28
w = id *id + id
Bài tập
• Xây dựng bước chuyển trạng thái trên stack và 
bộ đệm cho chuỗi nhập (với cùng văn phạm ở ví dụ trên): 
w= (id + id) * id + id
29
4.3 Xây dựng bảng phân tích SLR
• Định nghĩa: thực thể LR (0) gọi tắt là thực 
thể của văn phạm G là luật sinh của G với các 
điểm chấm ở các vị trí nào đó của vế phải.
• Thí dụ: G có luật sinh A -> XYZ, sẽ cho 
bốn thực thể:
A->•XYZ
A->X•YZ
A->XY•Z
A->XYZ•
Nếu A -> sẽ cho ta thực thể A ->•
30
31
Giải thuật tính bao đóng–Closure.
Function closure (I : item) : item;
begin J := I;
repeat
for với mỗi thực thể A -> a•Bß trong J và với mỗi luật 
sinh
B -> trong G sao cho
thực thể B -> • chưa có trong J do
thêm B -> • vào J;
until không thể thêm thực thể mới vào J;
closure := J;
end;
32
Ví dụ
• Xét văn phạm: 
E' → E 
E → E + T | T 
T → T * F | F 
F → (E) | id
33
Ví dụ
Nếu I là tập hợp chỉ gồm văn phạm { E'→ • E } 
thì closure(I) bao gồm: 
E' → • E 
E → • E + T
E → • T
T → • T * F
T → • F
F → • (E) 
F → • id
34
Giải thuật tính goto
• Goto(I, X), trong đó I là một tập các mục và X 
là một ký hiệu văn phạm, là bao đóng của tập 
hợp các mục A → αX•β sao cho A → α•Xβ € I. 
• Cách tính goto(I, X): 
1. Tạo một tập I' = ∅. 
2. Nếu A → α•Xβ € I thì đưa A→ αX•β vào I', tiếp tục 
quá trình này cho đến khi xét hết tập I. 
3. Goto(I, X) = closure(I') 
35
Ví dụ
• Giả sử I = { E' → E•, E → E • + T }. 
Tính goto (I, +) ? 
• Ta có I' = { E→ E + • T } 
( goto (I, +) = closure(I') bao gồm các mục : 
E → E + • T (Luật 1) 
T → • T * F (Luật 2) 
T → • F (Luật 2) 
F → • (E) (Luật 2) 
F → • id (Luật 2) 
36
Giải thuật tính tập tuyển các tập thực thể
Procedure items (G’);
begin
C := {closure ({S’->•S}}}
repeat
for với mỗi tập thực thể I trong C và với 
mỗi ký hiệu văn phạm X sao cho phép goto(I, 
X) không rỗng và không có trong C do
thêm goto(I, X) vào C;
until không thể thêm tập thực thể mới vào C;
end;
Ví dụ
• Xét văn phạm: 
E' → E 
E → E + T | T 
T → T * F | F 
F → (E) | id
• C:= Closure({E’->•E}): 
37
G
G’
Ví dụ(2)
38
Ví dụ (3)
39
40
Xây dựng bảng phân tích
 Nhập: văn phạm gia tố G’
 Xuất: bảng phân tích SLR với hàm action và goto cho văn 
phạm G’
 Phương pháp:
1. Xây dựng C = {Io, I1, In}.
2. i là trạng thái đại diện cho tập thực thể Ii.
2.1. Nếu A -> •aß là thực thể ở trong Ii và goto(Ii, a) = Ij thì 
phần tử action[i, a] = shift(j), với a phải là ký hiệu kết thúc.
2.2. Nếu A -> • ở trong Ii thì action[i, a] = reduce(A -> )
với a là tất cả các ký hiệu nằm trong follow(A). A không phải 
là S’(ký hiệu mục tiêu mới).
2.3. Nếu S’->S• ở trong Ii thì action [i, $] = accept.
41
Xây dựng bảng phân tích (2)
3. Cho tất cả các ký hiệu không kết thúc A. Nếu 
goto[Ii, A] = Ij thì hàm goto[i, A] = j.
4. Tất cả các phần tử của bảng phân tích không 
được xác định bằng quy tắc 2 và 3, chúng ta 
coi là lỗi.
5. Trạng thái bắt đầu của bộ phân tích là tập thực 
thể có chứa thực thể S’-> •S.
Ví dụ xây dựng bảng phân tích
• Xét văn phạm:
42
43
Ví dụ xây dựng bảng phân tích(1)
• Trước tiên xét tập mục I0 : Mục F → • (E) cho ra 
action[0, (] = "shift 4", và mục F → • id cho action[0, 
id] = "shift 5". Các mục khác trong I0 không sinh 
được hành động nào. 
• Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = 
"accept", mục E → E • + T cho action[1, +] = "shift 
6". 
44
Ví dụ xây dựng bảng phân tích(2)
• Kế đến xét I2 : E → T • 
T → T • * F 
• Vì FOLLOW(E) = {+, ), $}, làm cho action[2, $] = 
action[2,+] = action[2,)] = "reduce 2". Mục thứ hai 
làm cho action[2,*] = "shift 7". 
• Tiếp tục theo cách này, ta thu được bảng phân tích cú 
pháp SLR đã trình bày. 
Tổng kết Bài 4
• Các kiến thức cần nhớ:
– Phân tích từ trên xuống
– Phân tích dự đoán
– Phân tích từ dưới lên
45
Bài học phần sau
Bài 5: Phân tích ngữ nghĩa
46
Thảo luận
47