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

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: xixi-1x0$ với xt  (ΣΔ)Buffer: aiai-1a0$ với at  ΣBảng tiên đoán M:Chỉ số hàng: A  ΔChỉ số cột: a  ΣM[A,a]: A hoặc rỗng235CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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 stackM[A,a]=rỗng: xâu x không đúng CP VPG236CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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 bufferKhở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ặp237CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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à bufferElse 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ặp238CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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 ?239CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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 $SSaAAAbAAc240CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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ụ:	STTStackBufferHà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bA241CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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ụ:	STTStackBufferHà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 cp242CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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)243CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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)244CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: Xét sx: E  TE’ có First(TE’)={ (, id }	M[E,(]=M[E,id]=ETE’Xét sx: E’+TE’ có First(+TE’)={+}	M[E’,+]=E’+TE’Xét sx: TFT’ có First(FT’)={(, id}	M[T,(]=M[T,id]=TFT’245CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: Xét sx: T’*FT’ có First(*FT’)={*}	M[T’,*]=T’*FT’Xét sx: F(E) có First((E))={(}	M[F,(]=F(E)Xét sx: Fid có First(id)={id}	M[F,id]=Fid246CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: Xét sx: E’ có follow(E’)={), $}	M[E’,)]=M[E’,$]=E’Xét sx: T’ có follow(T’)={),$,+}	M[T’,)]=M[T’,$]=M[T’,+]=T’	ETE’TFT’ F(E)(TE’)(T)(FT’)	E  TE’  T+TE’  FT’+TE’247CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: 	+*id()$EETE’ETE’E’E’+TE’E’ εE’εTTFT’TFT’T’T’ εT’*FT’T’ εT’ εFFidF(E)248CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhươ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: 	Bài tập: 	xây dựng bảng tiên đoán M cho các vp LL(1) trong phần vài phép biến đổi về LL(1). Tự cho xâu vào và phân tích theo PP tiên đoán249CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVề 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ápMột biểu đồ cú pháp: bdiễn bằng 1 CT con250CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiBiể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’T251CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiCT 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 CT tương ứng.	ví dụ:  có đoạn ct t()12 t(1) ; t(2)252CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiCT con biểu diễn cho biểu đồ cú pháp:Sự rẽ nhánh tạo thành cấu trúc chọn123If k/htiepfirst(1) Then t(1)Elseif k/htiepfirst(2) Then t(2)Elseif k/htiepfirst(3) Then t(3)Else baoloi;253CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiCT 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ướcWhile k/htiepfirst() do t()Repeat t()Until k/htiepfirst() 254CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiCT con biểu diễn cho biểu đồ cú pháp: aIf k/htiep=a Then k/htiep=k/htieptheo trong xâu xElse baoloi;B goi B //t(B);255CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiThuậ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, dừng}Procedure I;{các Ctcon biểu diễn AΔ}	256CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiThuật toán:Procedure PTCP;	Begin	k/htiep:=Dockh;	S;	if k/htiep=$ then x đúng CP	else baoloi;	End.	257CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ:	E  TE’	E’+TE’ | 	T  FT’	T’*FT’ | 	F(E) | id258CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: Biểu đồ cú phápTE’E:TE’+E’:FT’T:FT’*T’:F:E()id259CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: giải thuật các ctcon tương ứngk/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, dừng}260CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: giải thuật các ctcon tương ứngProcedure E; 	Begin	T; Ephay;	End;261CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: giải thuật các ctcon tương ứngProcedure Ephay; 	Begin	If k/htiep=+ Then	 	 	Begin	k/htiep:=Dockh;	T;	Ephay;	 	 End;	 End;262CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: giải thuật các ctcon tương ứngProcedure T; 	Begin	F; 	Tphay;	End;263CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiVí dụ: giải thuật các ctcon tương ứngProcedure Tphay; 	Begin	If k/htiep=* Then	 	 	 Begin	k/htiep:=Dockh;	F;	Tphay;	 	 End;	 End;264CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiProcedure F;	 Begin	If k/htiep=id Then k/htiep:=Dockh	 	Else If k/htiep=( Then 	 	 Begin	k/htiep:=Dockh;	E;	if k/htiep=) Then k/htiep:=Dock	Else baoloi;	 	 	 End 	 Else baoloi;	 End;265CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiThuật toán:Procedure PTCP;	Begin	k/htiep:=Dockh;	E;	if k/htiep=$ then x đúng CP	else baoloi;	End.	266CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGPhương pháp phân tích cú pháp trên xuống	2.4. Phương pháp đệ qui không quay luiBài tập: 	Xây dựng giải thuật đệ qui không quay lui cho các VP LL(1) trong phần bài tập vài phép biến đổi về VP LL(1)267CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG	07Tnh12 	(1) Nguyen Tien Thanh 07t1(2) Nguyen Bon 07t1(3) La thi my le 07t1(4) Dinh Hong Thanh 07t2(5) Phan Duy 07t2(6) Nguyen Ngoc Nhan 07t1268CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG	07Tnh13 	(1) Mai Trần Trung Hiếu 07t1(2) Trần Hồ Minh Châu 07t4(3) Trương Thị Tâm 07t3(4) Huỳnh Tấn Lợi 07t4269CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG	Ctd he 2010 	Đỗ Thiên Hoàng 08t1 Hoàng Tiến sơn 07t4270