Giáo trình môn Chương trình dịch (Phần 1)

) E → T
 (3) T → T * F
 (4) T → F
 (5) F → (E)
 (6) F → id
 1. C = { I0, I1, ... I11 }
 2. FOLLOW(E) = {+, ), $}
 FOLLOW(T) = {*, +, ), $} 
 FOLLOW(F) = {*, +, ), $}
 Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 4.22, ta thấy:
 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".
 Kế đến xét I2: E → T • 
 T → T • * F
 Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] = "reduce 
(E → T)". 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ạng Action goto
 thái a + * ( ) $ E T F
 0 s5 S4 1 2 3
 1 s6 acc
 2 r2 s7 r2 r2
 3 r4 r4 r4 r4
 4 s5 S4 8 2 3
 5 r6 r6 r6 r6
 6 s5 S4 9 3
 7 s5 S4 10
 8 s6 s11
 9 r1 s7 r1 r1
 10 r3 r3 r3 r3
 11 r5 r5 r5 r5
 Bảng phân tích xác định bởi giải thuật 4.7 gọi là bảng SLR(1) của văn phạm G, bộ 
phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng 
SLR(1) gọi là văn phạm SLR(1).
 I : S' → • S
 0 Mọi văn phạm SLR(1) đều không mơ hồ, Tuy nhiên 
có S → • L = R những văn phạm không mơ hồ nhưng không phải là 
 S → • R SLR(1).
 L → • * R Ví dụ: Xét văn phạm G với tập luật sinh như sau:
 L → • id → → →
 S L = RI : LS → Rid • L * R 
L R → • L → id R → L 5
 Ðây là một văn phạm không mơ hồ nhưng không 
 I : S' → S •
 1 phải là văn phạm SLR(1).
 I : S → L = • R
 Họ tập hợp các mục C6 bao gồm:
 R → • L
 I : S → L • = R
 2 L → • * R
 R → L • L → • id
 I : S → R •
 3 I : L → * R•
 7
 I : L → * • R
 4 I : R → L•
 8
 R → • L
 L → • * R
 →• I : S → L = R•
 L id 9
 Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục 
đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = ∈ FOLLOW(R), 
nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" ⇒ Có sự đụng độ tại 
action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1).
 2.3.4.4. Xây dựng bảng phân tích LR chuẩn.
 * Mục LR(1) của văn phạm G là một cặp dạng [A → α• β , a], trong đó A → 
α β là luật sinh, a là một ký hiệu kết thúc hoặc $. 
 * Thuật toán xây dựng họ tập hợp mục LR(1)
  Giải thuật: Xây dựng họ tập hợp các mục LR(1)
 Input : Văn phạm tăng cường G’
 Output: Họ tập hợp các mục LR(1).
 Phương pháp: Các thủ tục closure, goto và thủ tục chính Items như sau:
 Function Closure (I);
 begin
 Repeat
 For Mỗi mục [A → α • Bβ ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi 
 ký hiệu kết thúc b ∈ FIRST (β a) sao cho [B → • γ , b] ∉ I do
 Thêm [ B → • γ , b] vào I;
 Until Không còn mục nào có thể thêm cho I được nữa;
 return I;
 end;
 Function goto (I, X);
 begin
 Gọi J là tập hợp các mục [A → α X•β , a] sao cho [A → α• Xβ , a]∈ I;
 return Closure(J);
 end;
 Procedure Items (G');
 begin
 C := Closure ({[S' → •S, $]})
 Repeat
 For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X
 sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do
 Thêm goto(I, X) vào C;
 Until Không còn tập các mục nào có thể thêm cho C;
 end;
Ví dụ: Xây dựng bảng LR chính tắc cho văn phạm gia tố G' có các luật sinh sau :
 S' S
 (1) S L = R3
 (2) S R
 (3) L * R
 (4) L id
 (5) R L
 Trong đó: tập ký hiệu chưa kết thúc ={S, L, R} và tập ký hiệu kết thúc {=, *, id, $}
 I0 : S' → • S, $ Goto (I4,R) I7 : L → * R•, = | $
 Closure (S' •S, $) S → • L = R, $ 
 S → • R, $ Goto (I4, L) I8 : R→ L•, = | $
 L → • * R, = | $ 
 → •
 L → • id, = | $ Goto (I6,R) I9 : S L = R , $
 R → • L, $ 
 → •
 Goto (I6,L) I10 :R L , $
 Goto (I0,S) I1 : S' → S •, $
 → •
 Goto (I6,*) I11 :L * R, $
 →•
 Goto (I0, L) I2 : S → L • = R, $ R L, $ 
 R → L •, $ L → • * R, $
 R → • id, $
 Goto (I 0,R) I3: S → R •, $ 
 Goto (I6, id) I12 :L → id •, $
 Goto (I0,*) I4: L → * • R, = | $ 
 → •
 R • L, = | $ Goto (I11,R) I13 :R * R , $
 L → • * R, = | $ 
 ≡
 R → • id, = | $ Goto (I11,L) I10
 Goto (I11,*) ≡ I11
 Goto (I0,id) I5 : L → id •, = | $
 ≡
 Goto (I2,=) I6 : S → L = • R, $ Goto (I11,id) I12
 R → • L, $
 L → • * R, $
 L → • id, $
* Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc 
 Giải thuật: Xây dựng bảng phân tích LR chính tắc
 Input: Văn phạm tăng cường G'
 Output: Bảng LR với các hàm action và goto
 Phương pháp:
 1. Xây dựng C = { I0, I1, .... In } là họ tập hợp mục LR(1)
 2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i 
 được xác định như sau:
 2.1. Nếu [A → α • aβ ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift 
 j". Ở đây a phải là ký hiệu kết thúc. 
 2.2. Nếu [A → α •, a] ∈ Ii , A ≠ S' thì action[i, a] = "reduce (A → α)
 2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept".
 Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không 
 phải là LR(1) và giải thuật sẽ thất bại.
 3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j
 4. Tất cả các ô không xác định được bởi 2 và 3 đều là "error"
 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các 
 mục chứa [S' → •S,$]
 Bảng phân tích xác định bởi giải thuật 4.9 gọi là bảng phân tích LR(1) chính tắc của văn 
phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm 
có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1).
 Ví dụ : Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên
 Trạng Action Goto
 thái = * id $ S L R
 0 s4 s5 1 2 3
 1 acc 
 2 s6 r5 
 3 r2 
 4 s4 s5 8 7
 5 r4 
 6 s11 s12 10 9
 7 r3 
 8 r5 
 9 r1 
 10 r5 
 11 s11 s12 10 13
 12 r4 
 13 r3 
 Hình 4.14 - Bảng phân tích cú pháp LR chính tắc
 Mỗi văn phạm SLR(1) là một văn phạm LR(1), nhưng với một văn phạm SLR(1), bộ 
phân tích cú pháp LR chính tắc có thể có nhiều trạng thái hơn so với bộ phân tích cú 
pháp SLR cho văn phạm đó. 
 2.3.4.5. Xây dựng bảng phân tích LALR.
 Phần này giới thiệu phương pháp cuối cùng để xây dựng bộ phân tích cú pháp LR - kỹ 
thuật LALR (Lookahead-LR), phương pháp này thường được sử dụng trong thực tế bởi vì những 
bảng LALR thu được nói chung là nhỏ hơn nhiều so với các bảng LR chính tắc và phần lớn các 
kết cấu cú pháp của ngôn ngữ lập trình đều có thể được diễn tả thuận lợi bằng văn phạm LALR.
 a. Hạt nhân (core) của một tập hợp mục LR(1)
 1. Một tập hợp mục LR(1) có dạng {[A → α• β , a]}, trong đó A → α β là một 
 luật sinh và a là ký hiệu kết thúc có hạt nhân (core) là tập hợp {A → α •β }.
 2. Trong họ tập hợp các mục LR(1) C = {I0, I1, ..., In} có thể có các tập hợp các 
 mục có chung một hạt nhân.
Ví dụ : Trong ví dụ 4.25, ta thấy trong họ tập hợp mục có một số các mục có chung hạt 
nhân là : 
 I4 và I11
 I5 và I12
 I7 và I13
 I8 và I10
 b. Thuật toán xây dựng bảng phân tích cú pháp LALR
 Giải thuậ: Xây dựng bảng phân tích LALR
 Input: Văn phạm tăng cường G'
 Output: Bảng phân tích LALR
 Phương pháp:
 1. Xây dựng họ tập hợp các mục LR(1) C = {I0, I1, ..., In } 
 2. Với mỗi hạt nhân tồn tại trong tập các mục LR(1) tìm trên tất cả các tập hợp 
 có cùng hạt nhân này và thay thế các tập hợp này bởi hợp của chúng.
 3. Ðặt C' = {I0, I1, ..., Im } là kết quả thu được từ C bằng cách hợp các tập 
 hợp có cùng hạt nhân. Action tương ứng với trạng thái i được xây dựng từ Ji 
 theo cách thức như giải thuật 4.9.
 Nếu có một sự đụng độ giữa các action thì giải thuật xem như thất bại và ta 
 nói văn phạm không phải là văn phạm LALR(1).
 4. Bảng goto được xây dựng như sau
 Giả sử J = I1 ∪ I2 ∪ ... ∪ Ik . Vì I1, I2, ... Ik có chung một hạt nhân nên goto 
 (I1,X), goto (I2,X), ..., goto (Ik,X) cũng có chung hạt nhân. Ðặt K bằng hợp tất 
 cả các tập hợp có chung hạt nhân với goto (I1,X) ( goto(J, X) = K.
Ví dụ : Với ví dụ trên, ta có họ tập hợp mục C' như sau
 C' = {I0, I1, I2, I3, I411, I512, I6, I713, I810, I9 }
 I0 : S' → • S, $ I512 = Goto (I0,id), Goto (I6,id) : 
 closure (S' •S, $) : S → • L = R, $ L → id •, = | $ 
 S → • R, $ 
 L → • * R, = I6 = Goto(I2,=) :
 → •
 L → • id, = S L = R,$ 
 →•
 R → • L, $ R L, $
 L → • * R, $
 →•
 I1 = Goto (I0,S) : S' → S •, $ L id, $
 I2 = Goto (I0, L) : S → L • = R, I713 = Goto(I411, R) : 
 $ L → * R•, = | $ 
 R → L •, $ 
 I810 = Goto(I411, L), Goto(I6, L): 
 → •
 I3 = Goto (I 0,R) : S → R • R L , = | $ 
 I411 = Goto (I0,*), Goto (I6,*) : I9 = Goto(I6, R) : 
 → •
 L → * • R, = | $ S L = R , $ 
 R → • L, = | $ 
 L → • * R, = | $ 
 R → • id, = | $
 Ta có thể xây dựng bảng phân tích cú pháp LALR cho văn phạm như sau :
 Action Goto
 State = * id $ S L R
 0 s411 s512 1 2 3
 1 acc 
 2 s6 
 3 r2 
 411 810 713
 512 r4 r4 
 6 s411 s512 810 9
 713 r3 r3 
 810 r5 r5 
 9 r1 
 Hình - Bảng phân tích cú pháp LALR
 Bảng phân tích được tạo ra bởi giải thuật 4.10 gọi là bảng phân tích LALR cho văn phạm G. 
Nếu trong bảng không có các action đụng độ thì văn phạm đã cho gọi là văn phạm LALR(1). Họ 
tập hợp mục C' được gọi là họ tập hợp mục LALR(1).
 2.4. Bắt lỗi.
 * Giai đoạn phân tích cú pháp phát hiện và khắc phục được khá nhiều 
 lỗi. Ví dụ lỗi do các từ tố từ bộ phân tích từ vựng không theo thứ tự của luật 
 văn phạm của ngôn ngữ.
 * Bộ bắt lỗi trong phần phân tích cú pháp có mục đích:
 + Phát hiện, chỉ ra vị trí và mô tả chính xác rõ rang các lỗi.
 + Phục hồi quá trìh phân tích sau khi gặp lỗi đủ nhanh để có thể phát 
 hiện ra các lỗi tiếp theo.
 + Không làm giảm đáng kể thời gian xử lý các chương trình viết đúng.
 * Các chiến lược phục hồi lỗi.
 - Có nhiều chiến lược mà bộ phân tích có thể dùng để phục hồi quá 
 trình phân tích sau khi gặp một lỗi cú pháp. Không có chiến lược nào tổng 
 quát và hoàn hảo, có một số phương pháp dùng rộng rãi.
 + Phục hồi kiểu trừng phạt: Phương pháp đơn giản nhất và được áp 
 dụng trong đa số các bộ phân tích. Mỗi khi phát hiện lỗi bộ phân tích sẽ bỏ 
 qua một hoặc một số kí hiệu vào mà không kiểm tra cho đến khi nó gặp một kí 
 hiệu trong tập từ tố đồng bộ. Các từ tố đồng bộ thường được xác định trước 
 ( VD: end, ; )
 Người thiết kế chương trình dịch phải tự chọn các từ tố đồng bộ. 
 Ưu điểm: Đơn giản, không sợ bj vòng lặp vô hạn, hiệu quả khi gặp câu 
 lệnh có nhiều lỗi.
 + Khôi phục cụm từ: Mỗi khi phát hienj lỗi, bộ phân tích cố gắng phân 
 tích phần còn lại của câu lệnh. Nó có thể thay thế phần đầu của phần còn lại 
 xâu này bằng một xâu nào đó cho phép bộ phân tích làm việc tiếp. Những việc 
 này do người thiết kế chương trình dịch nghĩ ra.
 + Sản xuất lỗi: Người thiết kế phải có hiểu biết về các lỗi hường gặp và 
 gia cố văn phạm của ngôn ngữ này tại các luật sinh ra cấu trúc lỗi. Dùng văn 
 phạm này để khôi phục bộ phân tích. Nếu bọ phân tích dùng một luật lỗi có 
 thể chỉ ra các cấu trúc lỗi phát hiện ở đầu vào.
 Ngoài ra ngừơi ta có cách bắt lỗi cụ thể hơn trong từng phương pháp phân 
 tích khác nhau.
 2.4.1. Khôi phục lỗi trong phân tích tất định LL.
 * Một lỗi được phát hiện trong phân tích LL khi:
 - Ký hiệu kết thúc nằm trên đỉnh ngăn xếp không đối sánh được với ký hiệu 
đầu vào hiện tại.
 - Mục M(A,a) trong bảng phân tích là lỗi (rỗng).
 * Khắc phục lỗi theo kiểu trừng phạt là bỏ qua các ký hiệu trên xâu vào cho 
đến khi xuất hiện một ký hiệu thuộc tập ký hiệu đã xác định trước gọi là tập ký hiệu 
đồng bộ. Xét một số cách chọn tập đồng bộ như sau:
 a) Đưa tất cả các ký hiệu trong Follow(A) vào tập đồng bộ hoá của ký 
hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp 
một phần tử của Follow(A) thì lấy A ra khỏi ngăn xếp và tiếp tục quá trình phân tích.
 b) Đưa tất cả các ký hiệu trong First(A) vào tập đồng bộ hoá của ký hiệu 
không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một 
phần tử thuộc First(A) thì quá trình phân tích được tiếp tục.
Ví dụ: với ví dụ trên, ta thử phân tích xâu vào có lỗi là “)id*+id” với tập đồng bộ 
hoá của các ký hiệu không kết thúc được xây dựng từ tập First và tập Follow của 
ký hiệu đó.
 Ngăn xếp Xâu vào Hành động
$E )id*+id$ M(E,)) = lỗi, bỏ qua ‘)’ để găp id ∈ First(E)
$E id*+id$ E->TE’
$E’T id*+id$ T->FT’
$E’T’F id*+id$ F->id
$E’T’id id*+id$ rút gọn id
$E’T’ *+id$ T’->*FT’
$E’T’F* *+id$ rút gọn *
$E’T’F +id$ M(F,+) = lỗi, bỏ qua. Tại đây xảy ra hai trường hợp(ta 
 chọn a): a).bỏ qua + vì id ∈ First(F) 
 b).bỏ qua F vì + ∈ Follow(F)
$E’T’F id$ F->id
$E’T’id id$ rút gọn id
$E’T’ $ T’->ε
$E’ $ E’->ε
$ $
 2.4.2. Khôi phục lỗi trong phân tích LR.
 Một bộ phân tích LR sẽ phát hiện ra lỗi khi nó gặp một mục báo lỗi trong 
bảng action (chú ý sẽ không bao giờ bộ phân tích gặp thông báo lỗi trong bảng 
goto). Chúng ta có thể thực hiện chiến lược khắc phục lỗi cố gắng cô lập đoạn câu 
chứa lỗi cú pháp: quét dọc xuống ngăn xếp cho đến khi tìm được một trạng thái s 
có một hành động goto trên một ký hiệu không kết thúc A ngay sau nó. Sau đó bỏ 
đi không hoặc nhiều ký hiệu đầu vào cho đến khi gặp một ký hiệu kết thúc a thuộc 
Follow(A), lúc này bộ phân tích sẽ đưa trạng thái goto(s,A) vào ngăn xếp và tiếp 
tục quá trình phân tích.
 Phương pháp phân tích bảng CYK (Cocke – Younger – Kasami)
 - Giải thuật làm việc với tất cả các VP PNC. Thời gian phân tích là: n3 (n là 
độ dài xâu vào cần phân tích), nếu văn phạm không nhập nhằng thì thờI gian phân 
tích là: n2.
 - Điều kiện của thuật toán là văn phạm PNC ở dạng chuẩn chômsky (CNF) 
và không có ε sản xuất (sản xuất A → ε ) và các kí hiệu vô ích.
 Giải thuật CYK:
 - Tạo một hình tam giác (mỗi chiều có độ dài là n , n là độ dài của xâu). 
Thực hiện giải thuật:
Begin
 1) For i:=1 to n do
 ∆ ij = { A | A → a là một sản xuất và a là kí hiệu thứ i trong w};
 2) For j:=2 to n do
 For i:=1 to (n – j +1) do
 Begin
 ∆ ij = ∅;
 For k:=1 to (j -1) do
 ∆ ij = ∆ ij ∪ { A | A → BC là một sản xuất; B ∈ ∆ ik C∈ ∆ i+k, j -k 
};
 end;
 end;
Ví dụ: Xét văn phạm chuẩn chômsky 
S → AB|BC; A → BA|a; B → CC|b; C → AB|a;
 (1) (2) (3) (4) (5) (6) (7) (8) 
Xâu vào w= baaba;
 i 
j
 b a a b a
 B A,C A,C B A,C
 S,A B S,C S,A
 ∅ B B
 ∅ S,A,C
 S,A,C
 b a a b a
 B A,C A,C B A,C
 S,A B S,C S,A
 ∅ B B
 ∅ S,A,C
 S,A,C
 - Quá trình tính ∆ ij . VD: tính ∆ 24 , Tính:
 ∆ 21 = {A,C}, ∆ 33 = {B}, ∆ 21∆ 33 = {AB,CB} Do (1), (7) nên đưa S,C vào 
∆ 24.
 ∆ 22 = {B}, ∆ 42 = {S,A}, ∆ 22∆ 42 = {BS,BA} Do (3) nên đưa A vào ∆ 24.
 ∆ 23 = {B}, ∆ 51 = {A,C}, ∆ 23∆ 51 = {BA,BC} (2),(3) nên đưa S,C vào ∆ 
24.
 Kết quả: ∆ 24 = {S,A,C}.
 - Nếu S ở ô cuối cùng thì ta kết luận: Xâu vào phân tích thành công và có 
thể dựng được cây phân tích cho nó. Số lượng cây phân tích = số lượng S có 
trong ô này.
 S
 b a a b a
 B A,C A,C B A,C A B
 S,A B S,C S,A
 BB A CC C
 ∅ B B
 ∅ S,A,C
 b a A B a
 S,A,C
 a b
 Bài tập
Luyện tập: 
cho văn phạm 
 E -> T + E | T
 T -> a
Hãy xây dựng bảng SLR(1) cho văn phạm trên
Thực hành: Thử nghiệm trên văn phạm biểu thức nêu trên
 1) xây dựng tập LR(0) tự động
 2) xây dựng bảng phân tích SLR(1) tự động
 3) phân tích xâu vào