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

đầu, f là trạng thái kết thúc. 
 Start  
 i f 
 Hình 2.17. Automat đoán nhận biểu thức r=  
 b) Xây dựng Automat đoán nhận ký tự a . 
 Start a 
 i f 
 Hình 2.18. Automat đoán nhận biểu thức r = a 
 Hình 2.18 là sơ đồ biểu diễn Automat đoán nhận a, với i là trạng thái bắt 
đầu, f là trạng thái kết thúc. 
 2) Phương pháp xây dựng các automat tổng hợp từ các automat 
 a) Giả sử s và t là hai biểu thức chính quy và N(s), N(t) là hai Automat đoán 
nhận s và t tƣơng ứng khi đó Automat đoán nhận biểu thức chính quy s + t có dạng 
nhƣ hình 2.19. 
 N(s) 
   
 Start 
 i f 
  N(t)  
 Hình 2.19. Automat đoán nhận biểu thức r = s+t 
 61 
Chƣơng 2. Phân tích từ vựng 
 Ở đây i, f là các trạng thái mới chƣa có trong N(s), N(t), từ trạng thái bắt đầu 
i Automat nhìn thấy từ rỗng; nó có thể chuyển sang trạng thái bắt đầu của N(r) hoặc 
trạng thái bắt đầu của N(t). Ngƣợc lại từ trạng thái cuối của N(s) hoặc N(t) nó có thể 
chuyển sang trạng thái kết thúc f khi gặp từ rỗng. 
 b) Xây dựng Automat đoán nhận biểu thức chính quy st. Giả sử N(s), N(t) là 
hai Automat đoán nhận svà t tƣơng ứng khi đó Automat đoán nhận biểu thức chính 
quy st có dạng nhƣ hình 2.20. 
 Start 
 i N(s) N(t) f 
 Hình 2.20. Automat đoán nhận biểu thức r=st 
 Ở đây i là trạng thái mới chƣa có trong N(s) và N(t), khi gặp từ rỗng 
Automat chuyển đến trạng thái đầu của N(s), trạng thái kết thúc của N(s) và trạng 
thái bắt đầu của N(t) đƣợc kết hợp thành một trạng thái, trạng thái kết thúc của N(t) 
trở thành trạng thái kết thúc của Automat hợp thành. 
 c) Giả sử s là biểu thức chính quy, và N(s) là Automat đoán nhận nó, ta xây 
dựng Automat đoán nhận s* và s+. Hình 2.21a mô tả Automat N(s*), Hình 2.21 b 
 +
mô tả Automat N(s )  
 Start   
 i N(s) f 
  
 Hình 2.21a. Automat đoán nhận biểu thức r = s* 
  
 Start   
 i N(s) f 
 Hình 2.21b. Automat đoán nhận biểu thức r = s+ 
 Ở đây i, f là trạng thái mới tƣơng ứng là trạng thái bắt đầu và trạng thái cuối 
cùng của Automat. 
 62 
 Chƣơng 2. Phân tích từ vựng 
 3) Giải thuật Thomson 
 Input: r – biểu thức chính quy; 
 Output: NFA  M ; N(M) = N(r). 
 Process: 
 Bước 1: Phân tích r thành các biểu thức chính quy đơn giản 
 - Tìm trong biểu thức chính quy phép toán có thứ tự ƣu tiên thấp nhất 
 - Nếu có thì phân tích biểu thức chính quy thành các toán hạng theo phép 
toán đó. Mỗi toán hàng – một biểu thức chính quy đơn giản hơn. 
 - Quay lại bƣớc 1 cho đến khi đã phân tích tất cả các biểu thức chính quy 
thánh các biểu thức chính quy đơn giản dạng r = a. 
 Bước 2: Xây dựng 
 - Xây dựng các automat đơn giản đoán nhận các biểu thức chính quy đơn giản. 
 - Xây dựng các automat tổng hợp theo thứ tự ngƣợc lại cho đến khi xây dựng 
automat tổng hợp đoán nhận biểu thức chính quy r. 
Nhận xét: 
 - Với biểu thức chính quy r, Automat N(r) đoán nhận nó sẽ có số trạng thái 
nhiều nhất không vƣợt quá hai lần số ký tự có trong r và số phép toán có trong nó. 
Điều nhận xét này có đƣợc là do trong giải thuật Thomson với mỗi ký hiệu hoặc 
phép toán trong r ta thêm vào không quá hai trạng thái. 
 - Mỗi Automat N(r) xây dựng theo giải thuật Thomson chỉ có một trạng thái 
đầu và một trạng thái kết thúc, và trạng thái kết thúc không bao giờ chuyển sang 
một trạng thái nào khác. 
 - Mỗi trạng thái của Automat N(r) chỉ có một trạng thái chuyển đi theo ký 
hiệu của tập  và tối đa hai trạng thái chuyển đi theo ký hiệu rỗng , vì vậy nói 
chung Automat xây dựng theo giải thuật Thomson là Automat không đơn định. 
 - Do mỗi lần xây dựng một Automat mới ta thêm vào trạng thái bắt đầu và 
kết thúc mới, cho nên Automat xây dựng theo giải thuật Thomson không có hai 
trạng thái trùng nhau. 
 63 
Chƣơng 2. Phân tích từ vựng 
Ví dụ 2.22: 
 Cho r = (a b)*abb. Hãy xây dựng NFA đoán nhận biểu thức chính quy r 
theo giải thuật Thomson. 
 Bước 1: Phân tích r = (a + b)*abb 
 - r = r1r2; 
 *
 r1 = (a + b) ab; r2 = b; 
 - r1 = r3r4; 
 *
 r3 = (a + b) a; r4 = b; 
 - r3 = r5r6; 
 *
 r5 = (a + b) ; r6 = a; 
 * 
 - r5 = (r7) ;
 r7 = a + b; 
 - r7 = r8r9; 
 R8 = a ; r9 = b; 
 Bước 2: Xây dựng 
 - Xây dựng Automat đoán nhận r8= a; r9 = b 
 Start a 
 2 3 
 Start b 
 4 5 
 Hình 2.22. Các automat đoán nhận a, b 
 - Xây dựng Automat đoán nhận r7 = r8 + r9 
 a 
  2 3  
 Start 
 1 6 
   
 b 
 4 5 
 Hình 2.23. Automat đoán nhận r7 = a+b 
 64 
 Chƣơng 2. Phân tích từ vựng 
 *
 - Xây dựng Automat đoán nhận r5 =(r7) 
  
 a 
  2 3  
 Start   
 0 1 6 7 
   
 b 
 4 5 
  
 * 
 Hình 2.24. Automat đoán nhận r5 = (a+b)
 Thực hiện tƣơng tự với r6 = a; r3 = r5 r6; r4 = b; r1 = r3 r4; r2 = b; r = r1 r2. Thu 
 đƣợc kết quả nhƣ hình sau: 
  
 a 
  2 3  
Start  
 0 1  a b b 
 6 7 8 9 10 
   
 b 
 4 5 
  
 Hình 2.25. Automat đoán nhận r=(a b)*abb 
 65 
Chƣơng 2. Phân tích từ vựng 
 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 
2.1. - Nêu các khái niệm: thẻ từ, trị từ vựng, mẫu từ vựng; cho ví dụ. 
 - Nêu các phƣơng pháp biểu diễn thẻ từ; cho ví dụ minh họa. 
2.2. Nêu vị trí, chức năng, nhiệm vụ của giai đoạn phân tích từ vựng. 
2.3. Nêu các kỹ thuật đọc chƣơng trình nguồn sử dụng buffer. 
2.4. Nêu giải thuật nhận biết từ vị bằng automat đơn định DFA. Chạy ví dụ minh họa 
2.5. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ 
 minh họa. 
2.6. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ 
 minh họa. 
2.7. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định 
 DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa. 
2.8. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định 
 DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa. 
2.9. Nêu giải thuật Thomson để xây dựng một automat đoán nhận một biểu thức 
 chính quy. Cho ví dụ minh họa. 
2.10. Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chƣơng trình 
 Pascal sau: 
 function max2 (i, j : integer) : integer; 
 { Trả về số nguyên lớn hơn trong 2 số i và j } 
 begin 
 If i > j then max2 : = i 
 else max2 : = j; 
 end; 
2.11. 
 Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chƣơng trình 
 Pascal sau: 
 PROGRAM GPTB2; 
 VAR a,b,c,x1,x2: real; 
 FUNCTION Delta: real; 
 66 
 Chƣơng 2. Phân tích từ vựng 
 Begin 
 Delta:= Sqr(b) - 4*a*c; 
 End; 
 PROCEDURE Ptb2; 
 VAR r: real; {r la bien cuc bo} 
 BEGIN 
 BEGIN 
 r := Sqrt (delta); 
 x1 := (-b-r)/(2*a); 
 x2 := (-b+r)/(2*a); 
 END; 
 END; 
 (* than chuong trinh *) 
 BEGIN 
 REPEAT 
 Write(„a=‟); readln(a); 
 UNTIL a0 ; 
 Write(„b=‟); readln(b); 
 Write(„c=‟); readln(c); 
 If (delta < 0) Then 
 Writeln ( „PT vo nghiem‟); 
 If delta = 0 Then 
 Writeln ( „PT co nghiem kep x1 = x2 =‟,x1:1:2); 
 If delta > 0 Then 
 Begin 
 Ptb2; 
 Writeln ( „PT co 2 nghiem: x1=‟,x1:1:2,‟x2=‟,x2:1:2); 
 Writeln ( „x2 = ‟, x2:1:2); 
 End; 
 Readln; 
END. 
 67 
Chƣơng 2. Phân tích từ vựng 
 2.12. Trong ngôn ngữ lập trình bậc cao Pascal, cho một số thẻ từ đƣợc phát biểu 
 bằng lời nhƣ sau: 
 1) Số nguyên không dấu là một xâu bắt đầu bằng một số, sau đó là không, một 
 hoặc nhiều các chữ số. 
 2) Số nguyên là một xâu bắt đầu bằng phần dấu, sau đó là một số nguyên 
 không dấu; phần dấu là dấu + hoặc dấu - hoặc không có ký tự nào. 
 3) Số thực dấu phảy tĩnh là một xâu bắt đầu bằng phần dấu; sau đó là phần 
 nguyên rồi đến phần thập phân; phần thập phân có thể có, có thể không; nếu 
 có phần thập phân thì hai phần này phân cách nhau bởi dấu chấm. Phần 
 nguyên và phần thập phân là một số nguyên không dấu 
 4) Số thực dấu phảy động là một xâu bắt đầu bằng một số nguyên, tiếp đến là 
 dấu chấm, sau đó là một số nguyên không dấu, tiếp theo là phấn mũ. Phần 
 mũ bắt đầu bằng ký tự E, tiếp đến là một số nguyên. 
 5) Các toán tử số học là một trong các phép toán +, -, *, / , ** 
 6) Khoảng trắng là một hoặc nhiều ký tự trống hoặc dấu tab hoặc dấu xuống 
 dòng. 
 7) Tên là một xâu các ký tự, bắt đầu bằng một chữ cái; sau đó là không, một 
 hoặc nhiều các chữ cái hoặc chữ số. Có thể thay chữ cái hoặc chữ số bằng 
 dấu gạch dƣới. 
 a) Hãy biểu diễn mỗi thẻ từ trên bằng biểu thức chính quy và chỉ ra thẻ từ, 
 mẫu từ vựng, trị từ vựng của mỗi từ đó. 
 b) Xây dựng sơ đồ chuyển để nhận biết mỗi token trên. 
2.13. Cho Automat M: 
 1 0, 1 
 Start 0 0 1 
 q1 q2 q3 q4 
 0 
 1 
 Hình BT 2.13 
 68 
 Chƣơng 2. Phân tích từ vựng 
 a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? 
tại sao? 
 b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra 
xem M có nhận biết đƣợc các từ vị sau không? 
 1) 1010101100$ 
 2) 110011101$ 
 3) 000000000$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
2.14. Cho Automat M 
 1 0 1 
 0 0 
 Start 1 0 1 
 A B C D 
 Hình bt 2.14 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 + w = 1110011$ 
 + w = 100001110$ 
 + w = 111100000$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.15. Cho Automat M 
 a 
 a 
 b 1 2 b 
 Start b 
 0 5 6 
 a b 
 a 
 3 4 
 b b 
 Hình BT 2.15 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 + w = baaaabb$ 
 69 
Chƣơng 2. Phân tích từ vựng 
 + w = aabbbab$ 
 + w = aababbbb$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.16. Cho Automat M. 
  
  1 
 0 0 1 
 Start q q q q
 0 1 2 3 
  
 0 
 Hình BT 2.16 
 a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? 
 tại sao? 
 b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra 
xem M có nhận biết đƣợc các từ vị sau không? 
 1) 00011111$ 
 2) 01111110$ 
 3) 000000001$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
  
2.17. Cho Automat M. 
 1 
 Start 0 0 1 
 q0 q1 q2 q3 
  
  
 0 0 
 Hình BT 2.17 
 a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại 
sao? 
 b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra 
xem M có nhận biết đƣợc các từ vị sau không? 
 1) 000101001$ 
 70 
 Chƣơng 2. Phân tích từ vựng 
 2) 01010100$ 
 3) 0000000010$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.18. Cho Automat M 
 b a 
 1 a 2
  
 b 
 Start 
 0 b 
  
 b 
 3 4 
 Hình BT 2.18 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 1) w = bbbaaa$ 
 2) w = bbaaab$ 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.19. Cho Automat M 
 a 
 1 a 
  2  
 Start b 
 0 5 6 
  a 
  
 3 4 
 b 
 b 
 Hình BT 2.19 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 + w = aaaaab 
 + w = bbbbab 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 71 
Chƣơng 2. Phân tích từ vựng 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.20. Cho Automat M 
 1 1 
   
 Start 1 0 1 
 A B C D 
  
  
 Hình BT 2.20 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 + w = 111110 
 + w = 111111 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
2.21. Cho Automat M 
 a  
 b 
 1 2
 a 
 b 
 Start 
 0 
  a 4 a 
 3 
 b 
 Hình BT 2.21 
 a) Nêu các thành phần của M 
 b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 
 + w = bbbaaaa 
 + w = aaaabba 
 c) Chỉ ra ngôn ngữ đoán nhận bởi M 
 d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 
 72 
 Chƣơng 2. Phân tích từ vựng 
2.22. Cho các biểu thức chính quy 
 a) 0(0 + 1)* 0+ 
 *
 b) ((0+ 1) 0(0 + 1))+ 
 c) (1+ 0)00 (0* + 1+) 
 *
 d) (a + ba + aab) (ε + a)+ 
 Hãy xây dựng các NFAε tƣơng đƣơng với mỗi biểu thức trên. 
2.23. Cho các biểu thức chính quy sau: 
 * + * 
 a) ( a + b ) 
 * + 
 b) ((ε + a) b ) 
 + * 
 c) (a + b) abb (a + b) 
 * *
 d) ab + (a + bb) a b 
 1) Xây dựng NFAε đoán nhận các biểu thức chính quy trên. 
 2) Hãy chuyển mỗi sang DFA tƣơng đƣơng. 
2.24. Quá trình phân tích từ vựng dựa vào sơ đồ chuyển có thể đƣợc tiến hành theo 
giải thuật sau: 
 Input: Sơ đồ chuyển của token và xâu vào w$ 
 Output: phân tích xâu vào có từ vị của token? 
 Process: 
 Bƣớc 1: Xuất phát từ trạng thái bắt đầu của ký tự khởi đầu của token, con 
 trỏ trỏ vào ký tự đầu tiên của xâu vào w. 
 Bƣớc 2: Nếu trên sơ đồ chuyển đang ở nút i và cung đi ra có nhãn là  đang 
 nối với nút j thì khi đó: 
 - Nếu  là ký tự kết thúc (Terminal) và ký tự mà con trỏ đang trỏ trong w 
cũng là  thì con trỏ trỏ đến ký tự tiếp theo của xâu w và quá trình duyệt chuyển 
sang nút j. 
 - Nếu  là token thì quá trình duyệt chuyển sang duyệt trạng thái bắt đầu 
trong sơ đồ chuyển của token . 
 + Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của biến  thì quá trình 
duyệt quay trở lại nút j. 
 73 
Chƣơng 2. Phân tích từ vựng 
 + Ngƣợc lại 
 * Nếu ở nút i còn cung đi ra thì chọn cung đi ra tiếp theo và quay lại 
bƣớc 2. 
 * Nếu đã xét hết các cung đi ra khỏi nút i và quá trình duyệt không đến 
đƣợc trạng thái kết thúc của token  thì báo lỗi. 
 - Nếu từ nút i đến nút j có cung mang nhãn , thì quá trình duyệt chuyển thẳng 
đến nút j và con trỏ trỏ vào ký tự trên xâu vào w đứng yên. 
 Bƣớc 3: Nếu quá trình duyệt đã duyệt hết xâu vào và: 
 - Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của sơ đồ chuyển của 
token thì thông báo thành công. 
 - Ngƣợc lại thì thông báo lỗi. 
Cho các sơ đồ chuyển: 
1) 0,1,2,3,4,5,6,7,8,9 
 Digit: Start 
 q0 A,, Z, a, , z q1 
 digit
 2) 
 Start digit
 Digits: q q3 
 2 
 3) 
 +, - 
 sign: Start 
 q4 q5 
  
 digit
 sign 
4) Start digit
 Digitsign: q
 6 q7 q8 
 digit digit
5) 
 number: +,- ,  digit digit
 Start q q q . 
 9 10 11 q12 q13 
 
 =, - 
 74 
 Chƣơng 2. Phân tích từ vựng 
 6) 
 digit digit digit
num s: 
 Start +,- , digit digit E +,- , digit
 q q q q19 q20 q21 
 14 15 16 . q17 q18 
 7) 
 Letter: Start A,,Z, a, ,z 
 q22 q23 
 letter, digit 
 id: Start letter
 q q25 
 24 
 8) 
 Hình BT 2.24 
 Và các xâu: 
 1) 123; -23467; 123.56; +123.789; - 001.34256; 123b 
 2) X1, a23b5; 1b34a; bien12, anpha1 
 3) 123. 01E02; -021E-03; +23. 098E+04 
 a) Sử dụng các giải thuật trên, kiểm tra các xâu trên là từ vị của token nào trong 
 các token sau: 
 1) Digits 
 2) Digitsign 
 3) Number 
 4) Nums 
 5) id 
 b) Hãy tổng hợp các sơ đồ trên để có đƣợc các sơ đồ chuyển dùng để nhận biết 
 các token: 
 1) Digits 
 2) Digitsign 
 3) Number 
 4) Nums 
 5) id 
 c) Sử dụng các sơ đồ đã tổng hợp đƣợc, kiểm tra các xâu trên là từ vị của token nào 
 trong các token trên. 
 75