Bài giảng Chương trình dịch - Bài 12: Phân tích văn phạm bằng thuật toán LL - Trương Xuân Nam

CHƯƠNG TRÌNH DỊCH
Bài 12: Phân tích văn phạm bằng 
thuật toán LL
Nội dung
1. Bộ phân tích cú pháp tất định
2. Tiếp cận top-down
3. Phân tích LL(1)
 FIRST
 FOLLOW
 Bảng phân tích LL(1)
 Ví dụ
4. Bài tập
TRƯƠNG XUÂN NAM 2
Bộ phân tích cú pháp tất định
Phần 1
TRƯƠNG XUÂN NAM 3
Ràng buộc về thời gian tính toán
 Các thuật toán phân tích vạn năng (CYK, Earley)
 Phân tích mọi văn phạm phi ngữ cảnh
 Tốc độ chấp nhận được: O(n3) với n là độ dài chuỗi vào
 Đối với những mã nguồn các ngôn ngữ lập trình, 
giá trị của n có thể lên tới vài triệu, bài toán phân 
tích văn phạm trở nên rất đặc biệt
 Tốc độ chấp nhận được nếu là gần tuyến tính O(n)
 Văn phạm đơn giản, chặt chẽ, đơn nghĩa
 Hệ quả là nảy sinh nhu cầu xây dựng các bộ phân 
tích văn phạm tất định (deterministic)
TRƯƠNG XUÂN NAM 4
Chiến lược tất định
 Thế nào là “tất định” – do ràng buộc độ phức tạp 
tính toán là O(n), hệ quả là:
 Khi nhận một kí hiệu đầu vào, bộ phân tích văn phạm 
cần ngay lập tức quyết định sẽ sử dụng luật sinh nào cho 
trường hợp này
 Quyết định chọn luật sinh nào cần phải đủ tốt để không 
phải thử lại phương án khác
 Tính chất “tất định” ~ không có quay lui
 Cái giá phải trả cho sự “tất định”: các bộ phân tích 
văn phạm sẽ không còn vạn năng nữa, nhưng đủ tốt 
để dùng trong thực tế
TRƯƠNG XUÂN NAM 5
Kiến trúc chung: bảng phương án
 Việc lựa chọn ngay lập tức phương án suy dẫn dẫn 
tới yêu cầu cần nghiên cứu trước bộ luật văn phạm 
và có các phương án phù hợp trong các tình huống 
có thể xảy ra
 Các thuật toán phân tích tất định đều sử dụng kĩ 
thuật xây dựng trước bảng phương án
 Có nhiều kĩ thuật xây dựng bảng phương án khác 
nhau ứng với các phương pháp tiếp cận khác nhau
 Với các loại bảng phương án, thuật toán phân tích 
cũng có sự khác biệt khi thực hiện đoán nhận
TRƯƠNG XUÂN NAM 6
Kiến trúc chung: bảng phương án
TRƯƠNG XUÂN NAM 7
Tiếp cận top-down
Phần 2
TRƯƠNG XUÂN NAM 8
Tiếp cận top-down
 Hãy quan sát quá trình thực hiện phân tích top-
down chuỗi w = ( ) ( ) của văn phạm:
S → ( S ) S | 
 Cần tìm quá trình suy dẫn S ⇒* w = ( ) ( )
 Ở đây chúng ta chỉ có 1 non-terminal duy nhất S
 Có 2 terminal “(” và “)”
 Bước suy dẫn đầu tiên, S⇒ ( S ) S ⇒* ( ) ( )
 Vậy ở bước 2, cần tìm quá trình S ) S ⇒* ) ( )
 Rõ ràng trong tình huống này, ta không thể áp dụng 
luật sinh S → ( S ) S mà phải sử dụng S → 
TRƯƠNG XUÂN NAM 9
Tiếp cận top-down
Quan sát quá trình suy dẫn từ α ⇒* w, dễ thấy:
 Nếu α bắt đầu bởi terminal, thì terminal đó nhất thiết 
phải trùng với kí hiệu bắt đầu của w, trong tình huống 
này ta gạt bỏ kí hiệu này ở cả 2 chuỗi
 Nếu α bắt đầu bởi non-terminal A, thì A nhất thiết 
phải suy dẫn (trực tiếp hoặc gián tiếp) ra kí hiệu bắt đầu 
của w (w1) hoặc ra 
 Ta có thể dựa trên văn phạm G để tính được A có suy ra 
w1 được hay không?
 Lập một bảng phương án 2 chiều, 1 chiều gồm các non-
terminal, 1 chiều gồm các terminal, ta đưa ra các tình 
huống áp dụng luật sinh cho mỗi cặp (A, w1)
TRƯƠNG XUÂN NAM 10
Phân tích LL(1)
Phần 3
TRƯƠNG XUÂN NAM 11
Phân tích LL(1)
Bước Chuỗi nguồn Chuỗi đích Hành động
1 S$ ()()$ S → ( S ) S
2 (S)S$ ()()$ gạt bỏ
3 S)S$ )()$ S → 
4 )S$ )()$ gạt bỏ
5 S$ ()$ S → ( S ) S
6 (S)S$ ()$ gạt bỏ
7 S)S$ )$ S → 
8 )S$ )$ gạt bỏ
9 S$ $ S → 
TRƯƠNG XUÂN NAM 12
Phân tích LL(1)
 Như vậy bộ phân tích LL(1) hoạt động tương tự 
như phân tích top-down, nhưng không có bước 
quay lui (vì không có sự lựa chọn thử-sai)
 Vấn đề lớn nhất: làm sao xây dựng được bảng 
phương án?
 LL(1) nghĩa là gì? Viết tắt của “Left-to-right parse, 
Leftmost-derivation, 1-symbol lockahead”
 Kí hiệu k trong LL(k) nghĩa là bộ phân tích sẽ nhìn 
trước k kí hiệu khi ra quyết định
TRƯƠNG XUÂN NAM 13
FIRST(X)
 Nếu X là kí hiệu kết thúc thì FIRST(X) là {X}
 Nếu X → ε là một luật sinh thì thêm ε vào FIRST(X)
 Nếu 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)
 Tiếp tục như vậy cho tới Yk
 Thêm ε vào FIRST(X) nếu ε ∈ ∩i=1 k FIRST(Yi)
TRƯƠNG XUÂN NAM 14
FIRST(α)
Định nghĩa FIRST(α): giả sử α là một chuỗi các ký 
hiệu văn phạm, 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ừ α
 Giả sử α = X1X2Xn
 Thêm vào FIRST(α): FIRST(X1)-{ε}
 Với mọi i=2,3,,n; nếu FIRST(Xk) chứa ε với mọi 
k=1,2,i-1 thì thêm vào FIRST(α): FIRST(Xi)-{ε}
 Nếu với mọi i=1,2,n; nếu FIRST(Xi) chứa ε thì thêm ε 
vào FIRST(α)
TRƯƠNG XUÂN NAM 15
Tính FIRST: ví dụ
Xét văn phạm G:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id
 FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
 FIRST(E') = {+, ε }
 FIRST(T') = {*, ε }
TRƯƠNG XUÂN NAM 16
FOLLOW
Ðịnh nghĩa FOLLOW(A): 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ả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)
TRƯƠNG XUÂN NAM 17
Tính FOLLOW
Tính FOLLOW (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
 Ðặt $ vào follow(S), trong đó S là ký hiệu bắt đầu của 
văn phạm và $ là ký hiệu kết thúc chuỗi nhập
 Nếu có một luật sinh A→ αBβ thì thêm mọi phần tử 
khác ε của FIRST(β)vào trong FOLLOW(B) 
 Nếu có luật sinh A→ αB hoặc A→ αBβ mà ε ∈
FIRST(β) thì thêm tất cả các phần tử trong 
FOLLOW(A) vào FOLLOW(B)
TRƯƠNG XUÂN NAM 18
Tính FOLLOW: ví dụ
Xét văn phạm G:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id
 FOLLOW(E) = FOLLOW(E') = { $, ) } 
 FOLLOW(T) = FOLLOW(T') = { +, ), $ } 
 FOLLOW(F) = {*,+, ), $ } 
TRƯƠNG XUÂN NAM 19
Bảng phân tích LL(1)
1. Với mỗi luật sinh A→ α của văn phạm, thực hiện:
1. Với mỗi ký hiệu kết thúc a ∈ FIRST(α), thêm A→ α 
vào M[A,a]
2. Nếu ε ∈ FIRST(α) thì đưa luật sinh A→ α vào M[A,b] 
với mỗi ký hiệu kết thúc b ∈ FOLLOW(A)
3. Nếu ε ∈ FIRST(α) và $ ∈ FOLLOW(A) thì đưa luật 
sinh A→ α vào M[A,$]
2. Các ô trống trong bảng tương ứng với lỗi (error)
Chú ý: một ô trong bảng có thể chứa nhiều suy dẫn, 
tình huống này gọi là bảng có nhập nhằng
TRƯƠNG XUÂN NAM 20
Ví dụ
Xét văn phạm G:
E → T E' E' → + T E' | ε
T → F T' T' → * F T' | ε F → (E) | id
TRƯƠNG XUÂN NAM 21
Bài tập
Phần 4
TRƯƠNG XUÂN NAM 22
Bài tập
1. Tính First, Follow và tạo bảng phân tích LL(1) cho văn 
phạm sau:
S Ac | BBc A BC
C b | bCd B dBb | dDb | 
D bd | bDd
2. Tính First, Follow và tạo bảng phân tích LL(1) cho văn 
phạm sau:
S AD | abc A Bc
B dBc | CC D Dd | 
C DCb | CDb | 
TRƯƠNG XUÂN NAM 23