Bài giảng Chương trình dịch - Đại học Bách khoa Đà Nẵng

	Thay bởi: 	A  A |  	 
A 
A 
A 
 
 
 
A 
A 
A 
 
 
 
185 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Đặt thừa số chung: 
	Dạng (3): A  |  
	Có: first(  )=first( )=first() nên first(  )  first( )= first( ) (vi phạm đk1) 
186 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Đặt thừa số chung: 
	Dạng (3): 	A  |  
	Thay bởi: 	A  A’ 
	A’   |  
187 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Bài tập: 	Biến đổi các VP sau thành LL(1) 
 	E  E + T | T 
	T  T * F | F 
	F  (E) | id 
 	A A T | T 
	T 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 	 
188 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
B ài tậ p: 	Biến đổi các VP sau thành LL(1) 
 	AA S | A C | C 
	C a 
	S  0 
Xây dựng VP LL(1) sản sinh ra danh định của một ngôn ngữ. 
189 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
B ài tậ p: 	giải 
 	E  TE’ 
	E’+TE’ |  
	T  FT’ 
	T’*FT’ |  
	F(E) | id 
190 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Bài tập: 	giải 
 	A  AT | T 	A TA’ 
	T  0 | .. | 9	 	A’ A |  
	T 0|..|9 	 
191 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Bài tập: 	giải 
Sx(1) và (2) biến đổi:	A AA’ 	A’S | C 
	A AA’|C	ACA”	ACA”	A’S | C	A”A’A”| 	A” SA”	C a	A’S|C	A”CA”|  	 S  0	Ca	Ca	S0	S0 
192 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Bài tập: 	giải 
 	ID  ID CC | ID CS |ID_ | CC| _ID| 
	CC  a | b 
	CS  0 | 1 
193 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.2. Vài phép biến đổi về VP LL(1) 
Bài tập: 	giải 
 ACC A’ | _B 
	BCCA’ | CS A’| _B 
	A’CCA’| CSA’ | _A’|  
	CCa 
	CS0 
194 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Cấu tạo: 
xi 
x2 
x1 
$ 
ai 
a2 
a1 
$ 
Bộ phân tích 
Bảng tiên đoán M 
Kết quả 
Stack 
Buffer 
195 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Cấu tạo: 
Stack: x i x i-1 x 0 $ với x t  ( ΣΔ ) 
Buffer: a i a i-1 a 0 $ với a t  Σ 
Bảng tiên đoán M: 
Chỉ số hàng: A  Δ 
Chỉ số cột: a  Σ 
M[A,a]: A   hoặc rỗng 
196 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Hoạt động: Tại một thời điểm nếu: 
Ở stack là $ và buffer là $: x đúng CP VPG 
Ở đỉnh stack và buffer a  Σ : đối sánh a 
Ở đỉnh stack là A  Δ thì nếu: 
M[A,a]=A   : triển khai A  ở đỉnh stack 
M[A,a]=rỗng: xâu x không đúng CP VPG 
197 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Giải thuật: 
Sử dụng: 1 stack và 1 buffer 
Khởi tạo: 	- stack là S$ 
	- Buffer là x$ 
Lặp: 
	If (stack là $) và (buffer là $) then 
	x đúng cp và dừng vòng lặp 
198 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Giải thuật: 
Else if (a  Σ ở đỉnh stack và buffer) then	đối sánh a ở đỉnh stack và buffer 
Else if (A  Δ ở đỉnh stack) 	và (a  Σ ở đỉnh buffer) then	if (M[A,a]=A  ) 	then	triển khai A ở đỉnh stack	Else x k0 đúng CP VPG, dừng vòng lặp 
199 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
 Ví dụ:	S aA 
	AbA | c 
	Xâu x: abbc có đúng CP của VP trên ? 
200 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
 Ví dụ:	 
 a 
 b 
 c 
 $ 
S 
SaA 
A 
A bA 
A c 
201 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
 Ví dụ:	 
STT 
Stack 
Buffer 
Hành động 
(0) 
S$ 
 abbc$ 
Triển khai S aA 
(1) 
 aA$ 
 abbc$ 
Đối sánh 
(2) 
A$ 
 bbc$ 
Triển khai A bA 
(3) 
 bA$ 
 bbc$ 
Đối sánh 
(4) 
A$ 
 bc$ 
Triển khai A bA 
202 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
 Ví dụ:	 
STT 
Stack 
Buffer 
Hành động 
(5) 
bA$ 
 bc$ 
Đối sánh 
(6) 
A$ 
 c$ 
Triển khai A c 
(7) 
 c$ 
 c$ 
Đối sánh 
(8) 
$ 
$ 
Chấp nhận x đúng cp 
203 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Xây dựng bảng tiên đoán M: 2 qui tắc 
 sx A   thì M[A,a]=A   với afirst() 
	   
 sx A   thì M[A,a]=A   với a follow(A) 
204 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.3. Phương pháp tiên đoán 
Xây dựng bảng tiên đoán M: 
	 Ví dụ: xây dựng bảng tiên đoán M cho vp: 
	 E  TE’ 
	E’+TE’ |  
	T  FT’ 
	T’*FT’ |  
	F(E) | id 
(1) 
(2) (3) 
(4) 
(5) (6) 
(7) (8) 
205 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
Về mặt nguyên lý giống pp tiên đoán. 
Khác về lập trình: không tra bảng tiên đoán M mà mô phỏng trực tiếp. 
Thay stack bằng sự đệ qui trong chương trình. 
Một k/h chưa kết thúc: bdiễn bằng 1 biểu đồ cú pháp 
Một biểu đồ cú pháp: bdiễn bằng 1 CT con 
206 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
Biểu đồ cú pháp: 
K/h kết thúc đặt: 
K/h chưa kết thúc đặt: 
Ví dụ: E  TE’ 
E: 
E’ 
T 
207 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
CT con biểu diễn cho biểu đồ cú pháp: 
Sự kết tiếp của các nút: sự kết tiếp của các đoạn ctcon 
Sự rẽ nhánh tạo thành cấu trúc chọn 
A: 
 1 
 2 
 3 
208 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
CT con biểu diễn cho biểu đồ cú pháp: 
 Lặp kiểm tra đk sau 
 Lặp kiểm tra đk trước 
 Nếu k/h tiếp=a thì 
	Đọcký tự tiếp theo 
 Ngược lại báo lỗi 
 
 
 a 
209 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
CT con biểu diễn cho biểu đồ cú pháp: 
 Gọi ctcon B 
 B 
210 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
Thuật toán: 
k/htiep: ký hiệu kết thúc; 
function Dockh:ký hiệu kết thúc; {đọc k/hiệu tiếp trong x} 
Procedure Baoloi; {đưa thông báo lỗi} 
Procedure  I ;{các Ctcon biểu diễn A Δ } 
211 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
Thuật toán: 
Procedure PTCP; 
	Begin	k/htiep:=Dockh; 
	S; 
	if k/htiep=$ then x đúng CP 
	else baoloi; 
	End.	 
212 
Giáo trình Kiến trúc máy tính và Hệ điều hành 
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG 
Phương pháp phân tích cú pháp trên xuống 
	2.4. Phương pháp đệ qui không quay lui 
Ví dụ: 
213 
Giáo trình Kiến trúc máy tính và Hệ điều hành