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

có nhãn là id và ( 
đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token 
đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là 
+, tức là ký tự đầu tiên của xâu + id$. Quá trình duyệt chuyển sang nút có nhãn là 17. 
 Vì 17 là nút kết thúc của F nên quá trình duyệt chuyến sang nút có nhãn là 8 
trong sơ đồ chuyển của T. 
 Trên sơ đồ chuyển của T đang ở nút 8 và có 2 cung đi ra có nhãn là + và  
đang nối với nút có nhãn là 7 và 13. Chọn cung đi ra có nhãn là +, trùng với ký tự 
đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo 
là id, tức là ký tự đầu tiên của xâu id$. Quá trình duyệt chuyển sang nút có nhãn là 7 
của sơ đồ chuyển của T. 
 Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với 
nút có nhãn là 8. 
 Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong 
sơ đồ chuyển của F là 14 . 
 Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( 
đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token 
đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo 
là $, tức là ký tự kết thúc xâu. Quá trình duyệt chuyển sang nút có nhãn là 17. 
 Vì 17 là nút kết thúc trong sơ đồ chuyển của F và đã duyệt hết xâu vào nên 
quá trình duyệt kết thúc và thông báo thành công. 
 - w = id + + id * id$ 
 Xuất phát từ trạng thái 0 của ký hiệu khởi đầu E của văn phạm. Con trỏ trỏ 
vào ký tự đầu tiên của xâu vào id + + id * id$ là id. Trên sơ đồ chuyển của E đang ở 
nút 0 và cung đi ra có nhãn là T đang nối với nút có nhãn là 3. 
 Vì T là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong 
sơ đồ chuyển của T là 7 . 
 Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với 
nút có nhãn là 8. 
 Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong 
sơ đồ chuyển của F là 14 . 
 204 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( 
đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token 
đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo 
là +, tức là ký tự đầu tiên của xâu + + id * id$. Quá trình duyệt chuyển sang nút có 
nhãn là 17 của sơ đồ F. 
 Vì 17 là nút kết thúc của F nên quá trình duyệt chuyến sang nút có nhãn là 8 
trong sơ đồ chuyển của T. 
 Trên sơ đồ chuyển của T đang ở nút 8 và có 2 cung đi ra có nhãn là + và  
đang nối với nút có nhãn là 7 và 13. Chọn cung đi ra có nhãn là +, trùng với token 
đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo 
là +, tức là ký tự đầu tiên của xâu + id * id$. Quá trình duyệt chuyển sang nút có 
nhãn là 7. 
 Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với 
nút có nhãn là 8 trong sơ đồ chuyển của T. 
 Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong 
sơ đồ chuyển của F là 14 . 
 Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( 
đang nối với nút có nhãn là 17 và 15. Các nhãn này là token id và ký tự kết thúc ( 
đều không trùng với ký hiệu kết thúc + đang đƣợc trỏ bởi con trỏ trên xâu vào. 
 Vì đã xét hết các cung đi ra khỏi các nút 14, 7 và 0 và quá trình duyệt không 
đến đƣợc trạng thái kết thúc của một sơ đồ chuyển nào nên quá trình duyệt dừng để 
thông báo lỗi. 
 - Các xâu còn lại phân tích tƣơng tự. 
3.39. Lời giải tóm tắt 
a) Loại bỏ đệ quy trái trực tiếp 
 - expr (expr) expr1 | id expr1 | digits expr1 
 - expr1 matop expr expr1 |  
 - digit 0 | 1 |...| 9 ; 
 * 
 - digits digit digit ; 
 - letter A | B | ...| Z | a | b |...| z ; 
 * 
 - id (letter| _ ) (letter | digit | _ ) ; 
 - matop → + | - | * | / ; 
 205 
Lời giải tóm tắt hoặc hƣớng dẫn 
b) Sơ đồ chuyển của văn phạm. 
 digits 
 Start ( expr ) expr 
 expr: 0 1 2 3 1 4 
 1 
 id 
 Start mato expr expr1 
 expr1: 6 7 8 
 5 p 
  
 0,1,2,3,4,5,6,7,8,9 
 Digit: Start 
 9 A,, Z, a, , z 10 
 digit
 Digits: 
 Start digit
 11 12 
 Letter: Start A,,Z, a, ,z 
 13 14 
 letter, digit 
 id: Start letter
 15 16 
 + , - , *, / 
 Matop: Start 
 17 18 
 Hình BT 3.39b. Sơ đồ chuyển 
 206 
 Lời giải tóm tắt hoặc hƣớng dẫn 
c) Tự làm, tƣơng tự bài 3.38 
3.40. Lời giải tóm tắt 
 a) Khử đệ quy trái trực tiếp, thu đƣợc: 
 E TE1 ; 
 E1 * TE1| ; 
 T FT1 ; 
 T1 +FT1 | ; 
 F GF1 ; 
 F1 /GF1 | ; 
 G BG1 ; 
 G1 -BG1 | ; 
 B (E) | id. 
 T E 
 b) Start 1
 E: 0 1 2 
 E : Start * T E1 
 1 3 4 5 6 
  
 Start F T1 
 T: 7 8 9 
 Start + F T1 
 T1 10 11 12 13 
 : ‟: : : 
  
 Start G F1 
 F: 14 15 16 
 Start / G F1 
 F1 17 18 19 20 
 :  
 Start B G 
 G: 21 22 1 23 
 207 
Lời giải tóm tắt hoặc hƣớng dẫn 
 Start - B G1 
 G1: 24 25 26 27 
  
 Start ( E ) 
 B: 28 29 30 31 
 id 
 Hình BT 3.40b. Sơ đồ chuyển 
 c) Tự làm, tƣơng tự bài 3.38 
3.41. Lời giải tóm tắt 
 id + * ( ) $ 
 E E TE‟ E TE‟ 
 E‟ E‟ +TE‟ E‟  E‟  
 T T FT‟ T FT‟ 
 T‟ T‟  T‟ *FT‟ T‟  T‟  
 F F id F (E) 
 Bảng BT 3.41 
 1) w = id * (id + id) 
 a) Áp dụng giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp, quá trình 
phân tích cú pháp cho xâu vào w = id * (id + id) đƣợc trình bày trong bảng sau: 
 Bƣớc STACK INPUT OUTPUT 
 Khởi tạo $ E id * (id + id)$ 
 1 $ E' T id * (id + id)$ E TE‟ 
 2 $ E' T‟F id * (id + id)$ T FT‟ 
 3 $ E' T‟id id * (id + id)$ F id 
 4 $ E' T‟ * (id + id)$ 
 5 $ E' T‟F* * (id + id)$ T‟ *FT‟ 
 6 $ E' T‟F (id + id)$ 
 7 $ E' T‟) E ( (id + id)$ F (E) 
 8 $ E' T‟) E id + id)$ 
 9 $ E' T‟) E‟T id + id)$ E TE‟ 
 10 $ E' T‟) E‟T‟F id + id)$ T FT‟ 
 11 $ E' T‟) E‟T‟id id + id)$ F id 
 208 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 12 $ E' T‟) E‟T‟ + id)$ 
 13 $ E' T‟) E‟ + id)$ T‟  
 14 $ E' T‟) E‟T+ + id)$ E‟ +TE‟ 
 15 $ E' T‟) E‟T id)$ 
 16 $ E' T‟) E‟T‟F id)$ T FT‟ 
 17 $ E' T‟) E‟T‟id id)$ F id 
 18 $ E' T‟) E‟T‟ )$ 
 19 $ E' T‟) E‟ )$ T‟  
 20 $ E' T‟) )$ E‟  
 21 $ E' T‟ $ 
 22 $ E' $ T‟  
 23 $ $ E‟  
 Bảng BT 3.41.1a Mô phỏng quá trình phân tích cú pháp dự đoán 
 X = a = $. Quá trình phân tích kết thúc thành công 
 b) Cây phân tích cú pháp đƣợc hình thành từ output : 
 E 
 T 
 E‟ 
 F T‟ + T E‟ 
 T‟  
 id * F F T‟ 
  T‟ 
 ( E ) id * F 
  
 T E‟ id 
 F T‟ 
 id 
Hình BT 3.41b. Cây phân tích cú pháp của xâu id * (id + id) được xây dựng 
 từ trên xuống theo phương pháp dự đoán dựa vào bảng phân tích 
 209 
Lời giải tóm tắt hoặc hƣớng dẫn 
 2) w = id + id + id) 
 a) Quá trình phân tích cú pháp đƣợc trình bày trong bảng sau: 
 Bƣớc STACK INPUT OUTPUT 
 Khởi tạo $ E id + id + id) 
 1 $ E' T id + id + id)$ E TE‟ 
 2 $ E' T‟F id + id + id)$ T FT‟ 
 3 $ E' T‟id id + id + id)$ F id 
 4 $ E' T‟ + id + id)$ 
 5 $ E' + id + id)$ T‟  
 6 $ E' T+ + id + id)$ E‟ +TE‟ 
 7 $ E' T id + id)$ 
 8 $ E' T‟F id + id)$ T FT‟ 
 9 $ E' T‟id id + id)$ 
 10 $ E' T‟ + id)$ 
 11 $ E' + id)$ T‟  
 12 $ E' T+ + id)$ E‟ +TE‟ 
 13 $ E' T id)$ 
 14 $ E' T‟F id)$ T FT‟ 
 15 $ E' T‟id id)$ F id 
 16 $ E' T‟ )$ 
 17 $ E' )$ T‟  
 18 $ )$ E‟  
 Bảng BT 3.41.2a Mô phỏng quá trình phân tích cú pháp dự đoán 
 X = $ a = ). Quá trình phân tích báo lỗi. 
 b) Không có cây phân tích cú pháp. 
 3) w = id + * id + id. 
 210 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 a) Quá trình phân tích cú pháp đƣợc trình bày trong bảng sau: 
 Bƣớc STACK INPUT OUTPUT 
 Khởi tạo $ E id + * id + id$ 
 1 $ E' T id + * id + id$ E TE‟ 
 2 $ E' T‟F id + * id + id$ T FT‟ 
 3 $ E' T‟id id + * id + id$ F id 
 4 $ E' T‟ + * id + id$ 
 5 $ E' + * id + id$ T‟  
 6 $ E' T+ + * id + id$ E‟ +TE‟ 
 7 $ E' T * id + id$ 
 Bảng BT 3.41.3a Mô phỏng quá trình phân tích cú pháp dự đoán 
 Không tồn tại luật sinh tại ô M[T, *] của bảng phân tích cú pháp nên quá trình 
phân tích dừng để thông báo lỗi. 
 b) Không có cây phân tích cú pháp. 
 Các câu 4, 5, 6, 8) Tự làm, tƣơng tự nhƣ trên. 
3.42. Lời giải tóm tắt 
 a) Khử đệ quy trái, thu đƣợc văn phạm không đệ quy trái với các luật sinh: 
 E TE1 ; (1) 
 E1 * TE1; (2) 
 E1  (3) 
 T FT1 (4) 
 T1 +FT1; (5) 
 T1 ; (6) 
 F (E) (7) 
 F id (8) 
 b) FIRST và FOLLOW của các ký hiệu không kết thúc 
 1) FIRST 
 Tính FIRST(F): 
 211 
Lời giải tóm tắt hoặc hƣớng dẫn 
 - Từ luật sinh (7), theo quy tắc 3 ta thêm đƣợc FIRST(„(‟) = „(‟ (theo 
 quy tắc1) vào FIRST(F). 
 - Từ luật sinh (8), theo quy tắc 3 ta thêm đƣợc FIRST(id) = „id‟ (theo 
 quy tắc1) vào FIRST(F). 
 - Không còn luật sinh nào có vế trái là F nữa. Vì vậy, ta không thể 
 thêm ký hiệu nào vào FIRST(F) nữa FIRST(F) = { (, id }. 
 - Tính FIRST(E1): 
 - Từ luật sinh (2), theo quy tắc 3 ta thêm đƣợc FIRST(*) = * (theo quy 
 tắc1) vào FIRST(E1). 
 - Từ luật sinh (3), theo quy tắc 2 ta thêm đƣợc  vào FIRST(E1). 
 - Không còn luật sinh nào có vế trái là E1 nữa. Vì vậy, ta không thể 
 thêm ký hiệu nào vào FIRST(E1) nữa FIRST(E1) = { * , }. 
 Tƣơng tự FIRST(T1) = { +, }. 
 Từ luật sinh (4), theo quy tắc 3: T FT1 và  FIRST(F) FIRST(T) = 
FIRST(F) = { (, id } 
 Tƣơng tự từ E TE1 và  FIRST(T) FIRST(E) = FIRST(T) = { (, id } 
 Vậy ta có: 
 FIRST(E) = FIRST(T) = FIRST(F) = { (, id } 
 FIRST(E1) = {* ,  } 
 FIRST(T1) = {+ ,  } 
2) FOLLOW 
 Tính FOLLOW(E): 
 - Vì E là ký hiệu khởi đầu, theo quy tắc 1 ta thêm $ vào FOLLOW(E) . 
 - Áp dụng quy tắc 2 cho luật sinh (7): 
 F (E) ) FOLLOW(E) FOLLOW(E) ={$, )} 
 - Không còn áp dụng đƣợc quy tắc nào cho E nữa. Vậy FOLLOW(E) ={$, )} . 
 Tính FOLLOW(E1): 
 - Áp dụng quy tắc 3 cho luật sinh (1): E TE1 ta thêm mọi ký hiệu của 
FOLLOW(E) vào FOLLOW(E1) ), $ FOLLOW(E1) 
 - Không thêm đƣợc ký hiệu nào vào FOLLOW(E1) nữa 
 212 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 FOLLOW(E1) ={$, )} 
 - Áp dụng luật 2 cho luật sinh (1): E TE1 * FOLLOW(T). 
 - Áp dụng luật 3 cho luật sinh (2, 3): E1 *TE1 , E1  
 FOLLOW(E1)  FOLLOW(T) FOLLOW(T) = { * , ) , $ }. 
 - Áp dụng quy tắc 3 cho luật sinh (4): T FT1 thì FOLLOW(T1) = 
FOLLOW(T) = {* , ) , $ } 
 Áp dụng quy tắc 2 cho luật sinh (4): T FT1 + FOLLOW(F) 
 Áp dụng quy tắc 3 cho luật sinh (5, 6): T1 +FT1 ; T1  
 FOLLOW(T1)  FOLLOW(F) FOLLOW(F) = {*, +, ), $ }. 
 Vậy ta có: FOLLOW(E) = FOLLOW(E1) = { $, ) } 
 FOLLOW(T) = FOLLOW(T1) = { * , ) , $ } 
 FOLLOW(F) = {*, +, ), $ } 
 c) Xây dựng bảng phân tích cú pháp 
 Áp dụng giải thuật xây dựng bảng phân tích cú pháp dự đoán cho văn phạm 
trong ví dụ trên: 
- Xét luật sinh E TE1: 
 Tính FIRST(TE1) = FIRST(T) = {( , id} 
 M[E, id] và M[E,( ] chứa luật sinh E TE1 
- Xét luật sinh E1 *TE1 : 
 Tính FIRST(*TE1) = FIRST(*) = {*} 
 M[E1, *] chứa E1 *TE1 
- Xét luật sinh E1 : Vì  FIRST(E1) và FOLLOW(E1) = { ) , $ } 
 E  nằm trong M[E1, )] và M[E1, $] 
- Xét luật sinh T1 + FT' : 
 Tính FIRST(+ FT') = {+ } 
 T1 + FT1 nằm trong M[T1, +] 
- Xét luật sinh T1 : Vì  FIRST(T1) và FOLLOW(T1) = {* , ) , $} 
 T'  nằm trong M[T1, *] , M[T1, )] và M[T1, $] 
- Xét luật sinh F (E) ; FIRST((E)) = { ( } 
 F ( E) nằm trong M[F, ( ] 
 213 
Lời giải tóm tắt hoặc hƣớng dẫn 
- Xét luật sinh F id ; FIRST(id) = {id} 
 F id nằm trong M[F, id] 
 Kết quả bảng phân tích cú pháp M của văn phạm đƣợc xây dựng nhƣ trong 
bảng sau: 
 id * + ( ) $ 
 E E TE1 E TE1 
 E1 E1 *TE1 E1  E1  
 T T FT1 T FT1 
 T1 T1  T1 +FT1 T1  T1  
 F F id F (E) 
 Bảng BT 3.42 Bảng phân tích cú pháp 
 d) Tự làm, tƣơng tự bài 3.41 
3.43. Lời giải tóm tắt 
 a) Khử đệ quy trái trực tiếp, thu đƣợc: 
 E TE1 ; (1) 
 E1 *TE1; (2) 
 E1  (3) 
 T FT1 (4) 
 T1 +FT1; (5) 
 T1 ; (6) 
 F GF1 ; (7) 
 F1 / GF1 ; (8) 
 F1 ; (9) 
 G BG1 ; (10) 
 G1 -BG1 ; (11) 
 G1 ; (12) 
 B (E) (13) 
 B id (14) 
 214 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 b) Tính FIRST và FOLLOW của các ký hiệu không kết thúc 
 Tự làm, tƣơng tự bài 4.43b. 
 c) Xây dựng bảng phân tích cú pháp 
 Tự làm, tƣơng tự bài 4.43c. 
 d) Tự làm, tƣơng tự bài 3.42 
3.44. Lời giải tóm tắt 
 1) w = id * (id + id) 
 - Áp dụng giải thuật phân tích cú pháp đẩy - thu, quá trình phân tích xâu 
đƣợc trình bày trong bảng sau: 
 Bƣớc Ngăn xếp Xâu vào Hành động Kết quả 
 12 $ id * (id + id)$ Đẩy 
 13 $id * (id + id)$ Thu gọn E id 
 14 $E * (id + id)$ Đẩy 
 15 $E* (id + id)$ Đẩy 
 16 $E*( id + id)$ Đẩy 
 17 $E*(id + id)$ Thu gọn E id 
 18 $E*(E id)$ Đẩy 
 19 $E*(E+id )$ Thu gọn E id 
 20 $E*(E+E )$ Thu gọn E E+E 
 21 $E*(E )$ Đẩy 
 22 $E*(E) $ Thu gọn E (E) 
 23 $E*E $ Thu gọn E E*E 
 24 $E $ Thành công 
 Bảng 3.44.1. Mô phỏng quá trình phân tích đẩy - thu 
- Xây dựng cây phân tích cú pháp 
 215 
Lời giải tóm tắt hoặc hƣớng dẫn 
 E 
 E 
 E 
 E 
 E E 
 id * ( id id ) 
 + 
 Hình BT 3.44a. Cây phân tích cú pháp của xâu id * (id + id) 
 được xây dựng từ dưới lên theo phương pháp đẩy - thu 
2) w = id + id + id) 
 - Quá trình phân tích cú pháp đẩy - thu xâu đƣợc trình bày trong bảng sau: 
 Bƣớc Ngăn xếp Xâu vào Hành động Kết quả 
 1 $ id + id + id)$ Đẩy 
 2 $id + id + id)$ Thu gọn E id 
 3 $E + id + id)$ Đẩy 
 4 $E+ id + id)$ Đẩy 
 5 $E+id + id)$ Thu gọn E id 
 6 $E+E + id)$ Thu gọn E E+E 
 7 $E + id)$ Đẩy 
 8 $E+ id)$ Đẩy 
 9 $E+id )$ Thu gọn E id 
 10 $E+E )$ Thu gọn E E+E 
 11 $E )$ Đẩy 
 12 $E) $ Báo lỗi 
 Bảng 3.44.2. Mô phỏng quá trình phân tích đẩy - thu 
 216 
 Lời giải tóm tắt hoặc hƣớng dẫn 
 - Quá trình phân tích gặp lỗi vì Stack không chỉ chứa duy nhất ký tự bắt đầu E 
nên không có cây phân tích cú pháp. 
3) w = id + * id + id 
 - Quá trình phân tích cú pháp đẩy - thu xâu đƣợc trình bày trong bảng sau: 
 Bƣớc Ngăn xếp Xâu vào Hành động Kết quả 
 1 $ id + * id + id$ Đẩy 
 2 $id + * id + id$ Thu gọn E id 
 3 $E + * id + id$ Đẩy 
 4 $E+ * id + id$ Đẩy 
 5 $E+* id + id$ Đẩy 
 6 $E+*id + id$ Thu gọn E id 
 7 $E+*E + id$ Đẩy 
 8 $E+*E+ id$ Đẩy 
 9 $E+*E+id $ Thu gọn E id 
 10 $E+*E+E $ Thu gọn E E+E 
 11 $E+*E $ Báo lỗi 
 Bảng 3.44.3. Mô phỏng quá trình phân tích đẩy - thu 
 - Quá trình phân tích gặp lỗi vì Stack không chỉ chứa duy nhất ký tự bắt đầu E 
nên không có cây phân tích cú pháp. 
 4, 5, 6, 7) Tự làm, tƣơng tự các câu trên. 
3.45. Hƣớng dẫn 
 Tự làm, tƣơng tự bài 3.44. 
3.46. Hƣớng dẫn 
 Xem lại và làm tƣơng tự ví dụ 3.34 
3.47. Hƣớng dẫn 
 1) Xem lại và làm tƣơng tự ví dụ 3.25 
 2) Xem lại và làm tƣơng tự ví dụ 3.26 
 3) Xem lại và làm tƣơng tự ví dụ 3.26 
 4) Xem lại và làm tƣơng tự ví dụ 3.24
 217 
Tài liệu tham khảo 
 TÀI LIỆU THAM KHẢO 
[1] Vũ Lục, Chương trình dịch, Nhà xuất bản Đại học Bách khoa Hà Nội, 1995. 
[2] Vũ Đình Hoà, Đỗ Bích Ngọc, Chương trình dịch, Nhà xuất bản Đai học Sƣ 
 phạm, 2007. 
[3] Phan Thị Tƣơi, Trình biên dịch, Nhà xuất bản Giáo dục, 1986. 
[4] Nguyễn Văn Xuất, Automat – Ngôn ngữ hình thức và nguyên lý chương trình 
 dịch, Nhà xuất bản khoa học kỹ thuật, 2006. 
[5] Alfred V.Aho, Jeffrey D.Ullman, Addison, Compilers: Principles, Technique 
 and Tools, Wesley Publishing Company, 1986. 
 218