Bài giảng Tin học - Chương 1: Nhập môn chương trình dịch

ƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG Lập bộ phân tích từ vựng4.1. Phương pháp mô phỏng Mỗi trạng thái: tương ứng với một đoạn chương trình Nối tiếp các trạng thái: nối tiếp 2 đoạn chương trình tương ứng Lệnh rẽ nhánhLệnh lặp43Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 2. PHÂN TÍCH TỪ VỰNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGLập bộ phân tích từ vựng>01=3>khác24*5=7khác68*') s=1;	else if (c=='') s=3;	else s=4;	break;	case 5: 	if (c=='=') s=6;	else if (c=='01=3>khác24*5=7khác68*==(strlen(x)-1)) {	printf(“het xau vao, ko roi vao TT ket thuc”);	tk=“”; break;	}	 catchar_in_token(c,tk);	*i++;	s=cs;}while(1);return tk;}	71Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 2. PHÂN TÍCH TỪ VỰNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG Lập bộ phân tích từ vựngvoid create_table(int table[][MAX]){// tao bang chuyen trang thai table}void lexical_analysis(){	token tk; attri a;	create_table(table);	do {	tk=search_token(&i,a);	save_token_and_attribute(tk,a);	}while ((*tk!='\0')&&(i B => (B) => (R) => (E=E)	=> (E=(E+E)) => (E=(E+a))	=> (E=(b+a)) => (a=(b+a)) :xâu xVậy xâu x viết đúng cú pháp của G(1)(3)(2)(4)(7)(5)(5)(6)104Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.2. Phương pháp giải quyếtVí dụ:Phương pháp từ dưới lên	SttDạng câuCánSx dùng(0)(a=(b+a)) aEa(1)(E=(b+a)) bEb(2)(E=(E+a)) aEa(3)(E=(E+E))(E+E)E(E+E)105Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.2. Phương pháp giải quyếtVí dụ:Phương pháp từ dưới lên Vậy xâu x viết đúng cú pháp của G(4)(E=E)E=ERE=E(5)(R)RBR(6)(B) (B)B(B)(7)BBSB(8)S106Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênS A 0i-1ik=xiuii’ABiết i tìm i-1i = iui i(ΣΔ)*; uiΣ*i =i’k = x=uk; k=0 = S=0; u0=107Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênThuật toán: Sử dụng: 1 stack và 1 BufferKhởi tạo: - stack: $	 - Buffer: x$Lặp: If (Stack là $S) và (Buffer là $) Then	- x đúng cú pháp của vp G	- Dừng vòng lặp	 108Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênThuật toán: 	 Else	If (cán  xuất hiện ở đỉnh stack) Then	 - Lấy cán  ra khỏi stack	 - Đẩy A vào stack với A	 109Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênThuật toán: 	 Else	 If (Buffer$) Then	 D/c k/h ở đỉnh của Buffer Stack	 Else	 -Báo lỗi x không đúng cú pháp VP G	 -Dừng vòng lặp	110Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênVí dụ: 	Sif DK then L ;	DK  true | false	L  write(ID) | read(ID)	ID a | b	Xâu x: if true then read(a); có đúng cú pháp vp trên?111Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSttStackBufferHành động(0)$if true then read(a); $ D/c(1)$iftrue then read(a);$D/c(2)$if truethen read(a);$R/g DKtrue(3)$if DKthen read(a);$D/c(4)$if DK thenread(a);$D/cĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênVí dụ: 112Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSttStackBufferHành động(5)$if DK then read(a);$D/c(6)$if DK then read(a);$D/c(7)$if DK then read(a);$R/g IDa(8)$if DK then read(ID);$D/c(9)$if DK then read(ID);$R/g Lread(ID)Đại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênVí dụ: 113Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSttStackBufferHành động(10)$if DK then L;$D/c(11)$if DK then L;$R/g Sif DK then L;(12)$S$Chấp nhận x đúng cp GĐại cương về phân tích cú pháp3.3. Sơ đồ chung giải thuật PTCP từ dưới lênVí dụ: 114Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngBiết i tìm i+1i = uii i(ΣΔ)*; uiΣ*i =Ai’k = x=uk; k=0 = S=A=0; 0’=u0=AS 0ii+1k=x Aiuii’ i’115Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngThuật toán:Sử dụng: 1 stack và 1 bufferKhởi tạo: - stack: S$	 - Buffer: x$Lặp: If (Stack là $) và (Buffer là $) Then	- x đúng cú pháp của VP G	116Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngThuật toán:	- Dừng vòng lặp	 Else	If (AΔ) xuất hiện ở đỉnh Stack Then	 Chọn sx thích hợp A	 Triển khai A bằng  ở đỉnh Stack 	117Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngThuật toán:	Else	 If (aΣ) xuất hiện ở đỉnh Stack và Buffer Then 	Lấy a ra khỏi Stack và Buffer {đối sánh} 	 118Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngThuật toán: 	 Else	 - Báo lỗi x không đúng cú pháp của G	 - Dừng vòng lặp119Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngVí dụ: 	SaA	AbA | c	Xâu x: abbc có đúng cú pháp của VP trên ?120Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngVí 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ánh121Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp3.4. Sơ đồ chung giải thuật PTCP từ trên xuốngVí dụ: 	SttStackBufferHành động(4)A$bc$Triển khai AbA(5)bA$bc$Đối sánh(6)A$c$Triển khai Ac(7)c$c$Đối sánh(8)$$Chấp nhận122Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp	Bài tập:Cho văn phạm G:	S var ID:K;T	ID a | b | c	K byte | integer | real	T  begin L end.	L  read(ID) | write(ID)	Xâu x: var a : byte; begin read(a) end. 	Xâu x có đúng cp của G? ch/m?123Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGĐại cương về phân tích cú pháp	Bài tập:Cho văn phạm G:	S aA | bA	A cA | bA | d	Xâu x: abbcbd 	Xâu x có đúng cp của G? ch/m?124Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCác phương pháp phân tích cú pháp4.1. Từ trên xuốngPhương pháp tiên đoánPhương pháp đệ qui không quay lui125Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ 	PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCác phương pháp phân tích cú pháp	4.2. Từ dưới lênPhương pháp ưu tiên toán tửPhương pháp thứ tự yếuPhương pháp LR(k)126Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửVăn phạm ưu tiên toán tử	Văn phạm phi ngữ cảnh thỏa mãn các ĐK:Không có 2 sản xuất có cùng vế phảiKhông có vế phải là  Không có 2 ký hiệu chưa kết thúc đứng liền nhau127Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửMối quan hệ ưu tiên giữa các ký hiệu	Với a, b Σ có:a b: a ưu tiên hơn ba và b : không có quan hệ ưu tiên128Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửQui tắc xác định mối quan hệ (1)  Sx mà vế phải có dạng ab 	hay aCb (2)  Sx mà vế phải có dạng aB	mà B+ b hay B+Cb(3)  Sx mà vế phải có dạng Ab	mà A+ a hay A+ aCa=b.ab.129Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửQui tắc xác định mối quan hệ (4) 	S+a hay S+aC 	hay S+ a hay S+Ca	Với a, bΣ; A,B,CΔ; , ,   (ΣΔ)*Lưu ý:- Cán:	 -	a $.. ...a b) Then	 - Tìm cán  ở đỉnh stack(vị trí mở cán then(qt3).. a C b  a B B b  b   A b A  a  a.136Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:Xác định tất cả các mối quan hệSx(1):Sif DK then L;  then = ; (qt1)	Tương tự:	then ; (qt3) .  a C b ..137Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:Xác định tất cả các mối quan hệSx(4|5): Lwrite(ID) | read(ID) 	write | read = ( (qt1)	( = ) (qt1)	( ) (qt3)....138Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:Xác định tất cả các mối quan hệ	S  if DK then L ;  if | ; > $ a  a(1).139Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSttStackBufferQ/hệH/động(0)$if true then read(a);$R/g DKtrue(3)$if DKthen read(a);$=D/cPhương pháp phân tích cú pháp dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:....R/g IDaPhương pháp phân tích cú pháp dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:....R/g Lread(ID)(10)$ if DK then L;$=D/c(11)$ if DK then L;$>R/g Sif DK then L;(12)$S$Chấp nhậnPhương pháp phân tích cú pháp dưới lên	1.1. Phương pháp ưu tiên toán tửVí dụ:.... ; 	; $const= =	const =	= = 	=var	var :	: y	Với x,y,B(ΣΔ); AΔ; ,,,(ΣΔ)*	 (Nếu BΣ thì y chính là B)..158Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.1. Phương pháp thứ tự yếuQui tắc xác định mối quan hệ S+x hay S+x thì x > $	Với x (ΣΔ) ;   (ΣΔ)*.159Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.2. Phương pháp thứ tự yếuXây dựng bảng S_RX Y thì: S_R[X,Y]=RStack là $S và Buffer là $ thì: S_R[X,Y]=R*X và Y không có mối quan hệ thì: S_R[X,Y]=rỗng ...160Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.2. Phương pháp thứ tự yếuVí dụ: cho G như sau:	SA C D	A const ID=N;	C var ID: K; 	D begin L end.	L write(ID) |read(ID)	ID a|b	N5	Kbyte|realXâu x: const a=5;var b:byte;begin read(b) end.161Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.2. Phương pháp thứ tự yếuCác mối quan hệ:	beginendA var	C $	const|A>$	; > beginvar :	:;write|read = (	( )	const =	= ;	beginS’Qui tắc xác định Follow Follow(A)={(tΣ|S+At)(t=$|S+ A)}185Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Ví dụ: Cho vp G	E  E + T | T	T  T * F | F	F  (E) | id	Xây dựng bảng SLR cho VP G 186Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Ví dụ: Xác định G’Tạo tập thực thể LR(0)Xác định các hành động187Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Ví dụ: VP gia tố G’	E’  E	E  E + T | T	T  T * F | F	F  (E) | id	188Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Ví dụ: Tạo tập thực thể LR(0)I0=closure({E’.E})E’.EE.E+TE.TT.T*FT.FF.(E)F.idI1=goto(I0,E)E’E.EE.+T189Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Ví dụ: Xác định các hành động190Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Bài tập: cho VPG:	A A or B | B	B  B and C | C	C  not C | (A) | true | falseHỏi xâu x: true and false or (not true) có được sinh ra từ VPG? c/m bằng PP SLR	191Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Simple LR (SLR)Bài tập: Cho VPG:	S AS| b	A  SA| a	Xây dựng bảng SLR cho VP G?192Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Trong PP SLR xung đột chỉ xảy ra ở những thực thể A .Khi xảy ra xung đột ta có thể sử dụng PP Canonical LR193Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Cấu tạo: như SLRHoạt động: như SLRThuật toán: như SLRXây dựng bảng Canonical LR194Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRVăn phạm gia tố: như SLRThực thể: gồm có 2 phần+ Phần nhân: giống thực thể trong SLR+ Ký hiệu nhìn trước: aΣVí dụ: AX.YZ, a195Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRHàm tính bao đóng closure(Ii): 2 qui tắcĐưa tất cả các thực thể trong Ii vào closure(Ii)Cứ thực thể [A.B,a]closure(Ii) mà B thì thêm [B., b] vào closure(Ii) 	với [B., b]closure(Ii) và bfirst(a) 196Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRQui tắc xác định First()	First()={(aΣ|+a)(a=$|+ )}Hàm tính goto(Ii,X)	Goto(Ii,X)=Closure({AX., a}) với {A.X, a} Ii và X(ΣΔ)I0=closure({S’.S, $})197Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRQui tắc xác định hành động [A.a,b] Ii và goto(Ii,a)=Ij với a Σ thì: Action[i,a]= Sj [A.X,b]  Ii và goto(Ii,X)=Ij với X Δ thì: goto[i,X]= j198Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRQui tắc xác định hành động [S’S.,$]  Ii thì: Action[i,$]= accept [A.,a]Ii thì Action[i,a]= Reduce A với AS’199Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.3. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRTrộn các tập thực thể 	Với các tập thực thể có chung phần nhân, khác nhau phần ký hiệu nhìn trước, ta có thể trộn chúng lại với nhau để được một tập thực thể mới có:+ phần nhân: phần giống nhau + ký hiệu nhìn trước: hợp các k/h nhìn trước200Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Xây dựng bảng Canonical LRVí dụ: 	S CC	C cC | d201Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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 dưới lên	1.4. Phương pháp Canonical LR (LR(1))Bài tập: xây dựng bảng Canonical LR	SAS | b	A SA | a202Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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ốngPTCP từ trên xuống: thay vế trái bằng vế phải. Một vấn đề đặt ra khi có 2 sx có vế trái giống nhau thì chọn sx nào?Chọn một sx nếu không được thì quay lui, chọn sx khácHạn chế văn phạm.	203Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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.1. Văn phạm LL(1)VP cho phép PTCP bằng cách triển khai dần dần suy dẫn trái từ trên xuống.Thăm dò xâu vào từ trái sang phảiNhìn trước 1 ký hiệu204Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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.1. Văn phạm LL(1)Định nghĩa:	VP PNC G=(Σ, Δ, S, p) được gọi là LL(1) nếu nó thỏa mãn 2 điều kiện sau:sx có dạng A1 | 2 | 3 | | n thì phải có first(i)  first(j) =  với ijAΔ mà A+  thì phải có: 	first(A)  follow(A)=	205Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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.1. Văn phạm LL(1)Ví dụ: 	SA | B	AaA | b	BaB | c	Xét: SA | B	First(A)={a,b} First(B)={a,c}	First(A)  first(B)={a} (vi phạm ĐK1) nên vp trên không phải là LL(1)206Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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.1. Văn phạm LL(1)Ví dụ: 	AAa 	Aa | 	Xét: AΔ mà A+  có: 	 first(A)={a,$}, follow(A)={a} nên first(A)follow(A)={a} (vi pham đk2)VP trên không phải là LL(1) 	207Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠ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.2. Vài phép biến đổi về VP LL(1)Khử đệ qui trái:	Dạng (1): AA |  	Dạng (2): AA |  	Xét (1) có: first(A)=first() nên first(A)first()=first() (vi pham đk1)VP đệ qui trái không phải là LL(1) 	208Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁPTRƯỜNG ĐẠI HỌC