Giáo trình môn học Chương trình dịch

2. 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 Bà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)

pdf268 trang | Chia sẻ: nguyenlam99 | Ngày: 05/01/2019 | Lượt xem: 95 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Giáo trình môn học Chương trình dịch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
C BÁCH KHOA ĐÀ NẴNG 1. Phươ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 < b b < c a >$. . . . . a < c. (Không có T/c bắc cầu) Giáo trình Kiến trúc máy tính và Hệ điều hành 133 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 1. Phươ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ử  Thuật toán Sử dụng: 1 stack và 1 Buffer Khở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 Giáo trình Kiến trúc máy tính và Hệ điều hành 134 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 1. Phươ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ử  Thuật toán Else {giả sử k/h kết thúc gần đỉnh stack nhất là a và buffer là b} If (a>b) Then - Tìm cán  ở đỉnh stack(vị trí mở cán <) - Lấy cán  ra khỏi stack - Đẩy A vào stack với A . . Giáo trình Kiến trúc máy tính và Hệ điều hành 135 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 1. Phươ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ử  Thuật toán Else If (a<b) or (a=b)Then D/c b từ Buffer Stack Else - Báo lỗi x không đúng cú pháp G - Dừng vòng lặp . . Giáo trình Kiến trúc máy tính và Hệ điều hành 136 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 1. Phươ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ụ: 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? Giáo trình Kiến trúc máy tính và Hệ điều hành 137 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 1. Phươ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ệ Xét vế phải của từng sản xuất - Phân tích Giáo trình Kiến trúc máy tính và Hệ điều hành 138 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 1. Phươ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;  if = then (qt1) Sif DK then L; DK true | false  if < true | false (qt2) S if DK then L; DK true | false  true | false > then(qt3) . .  a C b   a B  B b  b   A b  A  a  a . Giáo trình Kiến trúc máy tính và Hệ điều hành 139 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 1. Phươ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 < write | read (qt2) ) > ; (qt3) . a C b  . . Giáo trình Kiến trúc máy tính và Hệ điều hành 140 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 1. Phươ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) ( < a | b (qt2) a |b > ) (qt3) . . . . Giáo trình Kiến trúc máy tính và Hệ điều hành 141 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 1. Phươ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) . Giáo trình Kiến trúc máy tính và Hệ điều hành 142 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 Stt Stack Buffer Q/hệ H/động (0) $ if true then read(a);$ < D/c (1) $if true then read(a);$ < D/c (2) $if true then read(a);$ > R/g DKtrue (3) $if DK then read(a);$ = D/c 1. Phươ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ụ: . . . . < . Giáo trình Kiến trúc máy tính và Hệ điều hành 143 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 Stt Stack Buffer Q/hệ H/động (4) $if DK then read(a);$ < D/c (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 1. Phươ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ụ: . . . . < . Giáo trình Kiến trúc máy tính và Hệ điều hành 144 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 Stt Stack Buffer Q/hệ H/động (8) $if DK then read(ID );$ = D/c (9) $ if DK then read(ID) ;$ > 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ận 1. Phươ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ụ: . . . . < . < . Giáo trình Kiến trúc máy tính và Hệ điều hành 145 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 1. Phươ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ử Bài tập: (1)Cho văn phạm G: S C ; H H type ID=A;B Cconst ID = N A  byte | real IDa | b | c B var ID : A; N  5 Xâu x: const a=5; type b=byte; var c:real; Giáo trình Kiến trúc máy tính và Hệ điều hành 146 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 1. Phươ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ử Bài tập: (2)Cho văn phạm G: S C ; H H type ID=A var B Cconst ID = N A  byte; | real; IDa | b | c B ID : A N  5 Xâu x: const a=5; type b=byte; var c:real; Giáo trình Kiến trúc máy tính và Hệ điều hành 147 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 1. Phươ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ử Bài tập: (2) Các mối quan hệ: 5 | = > ; ; $ const= = const = =<5 type= = type< a|b|c = = var a|b|c> = =var var< :|a|b|c byte|real=; a|b|c> : :< byte|real . . .. . . . . . .. . . . . . . Giáo trình Kiến trúc máy tính và Hệ điều hành 148 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Cấu tạo: Stack $ x1 x2 xi $y1y2yi Buffer Kết quảBộ phân tích Bảng S_R Giáo trình Kiến trúc máy tính và Hệ điều hành 149 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Cấu tạo: - Xi  (ΣΔ) - yi  Σ - S_R: ma trận có: • Chỉ số hàng xi  (ΣΔ) • Chỉ số cột yi  Σ Giáo trình Kiến trúc máy tính và Hệ điều hành 150 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Cấu tạo: • S_R[xi,yi]: có các giá trị  S_R[xi,yi]=S  S_R[xi,yi]=R  S_R[xi,yi]=R*  S_R[xi,yi]=rỗng Giáo trình Kiến trúc máy tính và Hệ điều hành 151 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Hoạt động: - Tại một thời điểm nào đó k/h ở đỉnh của stack là Xi(ΣΔ), ở đỉnh buffer là yiΣ. Bộ phân tích sẽ xác định hành động thông qua bảng S_R: Giáo trình Kiến trúc máy tính và Hệ điều hành 152 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Hoạt động: • S_R[xi,yi]: xác định hành động  S_R[xi,yi]=S: dịch chuyển k/h đỉnh buffer  stack  S_R[xi,yi]=R: rút gọn  S_R[xi,yi]=R*: chấp nhận x đúng cp G  S_R[xi,yi]=rỗng: báo lỗi x k0 đúng cp G Giáo trình Kiến trúc máy tính và Hệ điều hành 153 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Thuật toán Sử dụng: 1 stack và 1 Buffer Khởi tạo: - stack: $ - Buffer: x$ Lặp: {g/sử k/h ở đỉnh stack là x, ở đỉnh buffer là y} Giáo trình Kiến trúc máy tính và Hệ điều hành 154 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 1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp thứ tự yếu  Thuật toán If (S_R[x,y]=R*) Then - x đúng cú pháp của vp G - Dừng vòng lặp Else If (S_R[x,y]=rỗng) Then Báo lỗi và dừng vòng lặp Giáo trình Kiến trúc máy tính và Hệ điều hành 155 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 1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp thứ tự yếu  Thuật toán Else If (S_R[x,y]=S) then D/c y từ buffer stack Else {S_R[x,y]=R} If (Có vế phải  dài nhất ở đỉnh stack) then - Lấy  ra khỏi stack - Đẩy A vào stack với A Giáo trình Kiến trúc máy tính và Hệ điều hành 156 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Thuật toán Else - Báo lỗi và dừng vòng lặp Giáo trình Kiến trúc máy tính và Hệ điều hành 157 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Ví dụ: Cho G : Sid=A AA+B | B BB*C | C Cid | (A) Xâu x: id=id+id*id Giáo trình Kiến trúc máy tính và Hệ điều hành 158 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 Bảng S_R id * + ( ) = $ S R* A S S R B S R R R C R R R R id R R R S R * S S + S S ( S S ) R R R R = S S $ S Giáo trình Kiến trúc máy tính và Hệ điều hành 159 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 1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp thứ tự yếu  Qui tắc xác định mối quan hệ (1) Sx mà vế phải có dạng xy - Nếu yΣ thì: x = y - Nếu yΔ thì: x < y Với x(ΣΔ); ,(ΣΔ)* . . Giáo trình Kiến trúc máy tính và Hệ điều hành 160 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 1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp thứ tự yếu  Qui tắc xác định mối quan hệ (2) Sx mà vế phải có dạng xA mà A+ y thì: x < y Với x,y(ΣΔ); AΔ; ,,(ΣΔ)* (3) Sx mà vế phải có dạng AB mà A+ x và B+ y thì: x > y Với x,y,B(ΣΔ); AΔ; ,,,(ΣΔ)* (Nếu BΣ thì y chính là B) . . Giáo trình Kiến trúc máy tính và Hệ điều hành 161 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 1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp thứ tự yếu  Qui tắc xác định mối quan hệ (4)S+x hay S+x thì x > $ Với x (ΣΔ) ;   (ΣΔ)* . Giáo trình Kiến trúc máy tính và Hệ điều hành 162 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Xây dựng bảng S_R - X < Y hay X=Y thì: S_R[X,Y]=S - X > Y thì: S_R[X,Y]=R - Stack 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 . . . Giáo trình Kiến trúc máy tính và Hệ điều hành 163 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Ví 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|real Xâu x: const a=5;var b:byte;begin read(b) end. Giáo trình Kiến trúc máy tính và Hệ điều hành 164 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu Các mối quan hệ: beginend A var C < D C $ const|A>$ ; > begin var < ID ID = : : < K K = ; var : :; write|read = ( ( < ID ID = ) ( ) const <ID ID= = = < N N=; const = = < 5 5 > ; begin<L L=end end=. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Giáo trình Kiến trúc máy tính và Hệ điều hành 165 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Văn phạm thứ tự yếu 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ải - Không có vế phải là  - Không có phần tử S_R[x,y] có cả trị S và R - Nếu Ax1x2xn và Bxixi+1xn thì không  xi-1<=B Giáo trình Kiến trúc máy tính và Hệ điều hành 166 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 1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu  Văn phạm thứ tự yếu Nếu  xi-1<=B thì có nghĩa  Cx1x2xi- 1B và như vậy để thu gọn x1x2xn, thì sẽ thu gọn xixi+1xn về B rồi mới thu gọn x1x2xi-1B về C. Như vậy mâu thuẫn với tính chất luôn luôn thay thế vế phải dài nhất. Giáo trình Kiến trúc máy tính và Hệ điều hành 167 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Cấu tạo: Kết quả $a0a1ai Buffer Bộ phân tích Stack $ S0 x0 Si Si-1 Xi-1 Bảng SLR Action Goto Giáo trình Kiến trúc máy tính và Hệ điều hành 168 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Cấu tạo: - Stack: $s0x0 s1x1si-1xi-1si st: trạng thái; xt(ΣΔ) - Buffer: aiai-1a0$ ; với at Σ - Bảng SLR gồm 2 phần: action và goto • Chỉ số hàng: trạ g thái St Giáo trình Kiến trúc máy tính và Hệ điều hành 169 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Cấu tạo: • Chỉ số cột Phần action: aiΣ Phần goto: XΔ • Action[Si,ai]=Shift j (Sj) • Action[Si,ai]=Reduce A (RJ) Giáo trình Kiến trúc máy tính và Hệ điều hành 170 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Cấu tạo: • Action[Si,ai]=Accept • Action[Si,ai]=rỗng • Goto[Si,X]=j Giáo trình Kiến trúc máy tính và Hệ điều hành 171 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Hoạt động: Tại một thời điểm bộ phân tích đọc trạng thái Si ở đỉnh stack và ký hiệu vào ai ở đỉnh buffer và tra trong bảng SLR ở phần Action một giá trị. Nếu: - Action[Si,ai]=Shift j (Sj)  D/c ai từ Buffer Stack  Đẩy j vào stack Giáo trình Kiến trúc máy tính và Hệ điều hành 172 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Hoạt động: - Action[Si,ai]=Reduce A (RJ)  Lấy 2*r phần tử ra khỏi stack. Với r=||  Đẩy A vào stack  Đẩy j vào stack với j=goto[Si-r,A] Giáo trình Kiến trúc máy tính và Hệ điều hành 173 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Hoạt động: - Action[Si,ai]=Accept  Xâu x đúng cp của vpG - Action[Si,ai]=rỗng  Báo lỗi x không cú pháp của vpG Giáo trình Kiến trúc máy tính và Hệ điều hành 174 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Thuật toán: Sử dụng: 1 stack, 1 buffer, bảng SLR Khởi tạo: - stack: $0 - Buffer: x$ Lặp: {g/sử ở đỉnh stack là Si, đỉnh buffer là a} If (Action[Si,a]=accept) then - x đúng cp và dừng vòng lặp Giáo trình Kiến trúc máy tính và Hệ điều hành 175 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Thuật toán: Else If (Action[Si,a]=Sj) then - D/c a từ buffer  stack - Đẩy j vào stack Else IF (Action[Si,a]=Reduce A) then - Lấy 2*r phần tử ra khỏi stack Giáo trình Kiến trúc máy tính và Hệ điều hành 176 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Thuật toán: - Đẩy A vào stack - Đẩy j vào stack. Với j=goto[Si-r,A] Else {Action[Si,a]=rỗng} - Báo lỗi x không đúng cp của G - Dừng vòng lặp Giáo trình Kiến trúc máy tính và Hệ điều hành 177 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 1. Phươ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âu x: id*(id+id) (1) (2) (3) (4) (5) (6) Giáo trình Kiến trúc máy tính và Hệ điều hành 178 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR) T/ thái Action Goto id + * ( ) $ E T F 0 S5 S4 1 2 3 1 S6 Accept 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S5 S4 8 2 3 5 R6 R6 R6 R6 6 S5 S4 9 3 Giáo trình Kiến trúc máy tính và Hệ điều hành 179 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR) T/ thái Action Goto id + * ( ) $ E T F 7 S5 S4 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 Giáo trình Kiến trúc máy tính và Hệ điều hành 180 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 1. Phươ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ụ: Stt Stack Buffer Hành động 0 $0 id*(id+id)$ S5 1 $0 id 5 *(id+id)$ R6(Fid) 2 $0 F 3 *(id+id)$ R4(TF) 3 $0 T 2 *(id+id)$ S7 4 $0 T 2 * 7 (id+id)$ S4 5 $0 T 2 * 7 ( 4 id+id)$ S5 Giáo trình Kiến trúc máy tính và Hệ điều hành 181 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 1. Phươ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ụ: Stt Stack Buffer Hành động 6 $0 T 2 * 7 ( 4 id 5 +id)$ R6(Fid) 7 $0 T 2 * 7 ( 4 F 3 +id)$ R4(TF) 8 $0 T 2 * 7 ( 4 T 2 +id)$ R2(ET) 9 $0 T 2 * 7 ( 4 E 8 +id)$ S6 10 $0 T 2 * 7 ( 4 E 8 + 6 id)$ S5 11 $0 T 2 * 7 ( 4 E 8 + 6 id 5 )$ R6(Fid) Giáo trình Kiến trúc máy tính và Hệ điều hành 182 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 1. Phươ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ụ: Stt Stack Buffer Hành động 12 $0 T 2 * 7 ( 4 E 8 + 6 F 3 )$ R4(TF) 13 $0 T 2 * 7 ( 4 E 8 + 6 T 9 )$ R1(EE+T) 14 $0 T 2 * 7 ( 4 E 8 )$ S11 15 $0 T 2 * 7 ( 4 E 8 ) 11 $ R5(F(E)) 16 $0 T 2 * 7 F 10 $ R3(TT*F) 17 $0 T 2 $ R2(ET) Giáo trình Kiến trúc máy tính và Hệ điều hành 183 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 1. Phươ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ụ: Stt Stack Buffer Hành động 18 $0 E 1 $ Accept Giáo trình Kiến trúc máy tính và Hệ điều hành 184 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Văn phạm gia tố G’ G’=G  {S’S} Ví dụ: G: S  0S | 1S|0|1 G’: S’  S S 0S | 1S|0|1 Giáo trình Kiến trúc máy tính và Hệ điều hành 185 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Thực thể: Sx thêm dấu chấm ở bất kỳ vị trí của vế phải. Ví dụ: A xyz thì A .xyz Ax.yz Axy.z A  xyz. là các thực thể Giáo trình Kiến trúc máy tính và Hệ điều hành 186 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Hàm tính bao đóng Closure(Ii): 2 qui tắc (1) Đưa tất cả các thực thể trong Ii vào closure(Ii) (2) Cứ mỗi thực thể có dạng A.Bclosure(Ii) mà B thì thêm B. vào closure(Ii) với B.  closure(Ii) Giáo trình Kiến trúc máy tính và Hệ điều hành 187 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 1. Phươ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 tập closure(I) của VP G’ E’ E E  E + T | T T  T * F | F F  (E) | id I={E’.E} Giáo trình Kiến trúc máy tính và Hệ điều hành 188 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Hàm tính goto Goto(Ii,x)=closure({Ax.}) với {A.x}  Ii ; x(ΣΔ) Giáo trình Kiến trúc máy tính và Hệ điều hành 189 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 1. Phươ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ìm tất cả các tập goto(I,X) có thể của VP G I={ E’.E E.E+T E.T T.T*F } X: E, T Goto(I,E) và Goto(I,T) E’ E E  E + T | T T  T * F | F F  (E) | id Goto(I,E)=closure({E’E. ; EE.+T}) Goto(I,T)=closure({ET. ; TT.*F}) Giáo trình Kiến trúc máy tính và Hệ điều hành 190 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Tập thực thể LR(0) I0=closure({S’.S}) - Tính tất cả các goto(Ii,x) của tất cả các tập thực thể ta sẽ được tập LR(0). - Tính hết goto(Ii,x) mà không sinh được Ii+1 thì dừng. Giáo trình Kiến trúc máy tính và Hệ điều hành 191 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Qui tắc xác định hành động (1)A.a  Ii và goto(Ii,a)=Ij với a Σ thì: Action[i,a]= Sj (2)A.X  Ii và goto(Ii,X)=Ij với X Δ thì: goto[i,X]= j Giáo trình Kiến trúc máy tính và Hệ điều hành 192 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 1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)  Xây dựng bảng SLR - Qui tắc xác định hành động (3) S’S.  Ii thì: Action[i,$]= accept (4)A.  Ii thì Action[i,a]= Reduce A với a Follow(A); AS’ - Qui tắc xác định Follow Follow(A)={(tΣ|S+At)(t=$|S+ A)} Giáo trình Kiến trúc máy tính và Hệ điều hành 193 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 1. Phươ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 Giáo trình Kiến trúc máy tính và Hệ điều hành 194 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 1. Phươ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 động Giáo trình Kiến trúc máy tính và Hệ điều hành 195 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 1. Phươ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 Giáo trình Kiến trúc máy tính và Hệ điều hành 196 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 1. Phươ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’.E E.E+T E.T T.T*F T.F F.(E) F.id I1=goto(I0,E) E’E. EE.+T Giáo trình Kiến trúc máy tính và Hệ điều hành 197 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 1. Phươ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 động Giáo trình Kiến trúc máy tính và Hệ điều hành 198 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 1. Phươ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: (1)cho VPG: A A or B | B B  B and C | C C  not C | (A) | true | false Hỏi xâu x: true and false or (not true) có được sinh ra từ VPG? c/m bằng PP SLR Giáo trình Kiến trúc máy tính và Hệ điều hành 199 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 1. Phươ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: (2)Cho VPG: S AS| b A  SA| a Xây dựng bảng SLR cho VP G? Giáo trình Kiến trúc máy tính và Hệ điều hành 200 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 1. Phươ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 LR Giáo trình Kiến trúc máy tính và Hệ điều hành 201 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 1. Phươ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ư SLR  Hoạt động: như SLR  Thuật toán: như SLR  Xây dựng bảng Canonical LR Giáo trình Kiến trúc máy tính và Hệ điều hành 202 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 1. Phươ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 LR - Văn phạm gia tố: như SLR - Thự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, a Giáo trình Kiến trúc máy tính và Hệ điều hành 203 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 1. Phươ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 LR - Hàm tính bao đóng closure(Ii): 2 qui tắc (1)Đưa tất cả các thực thể trong Ii vào closure(Ii) (2)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) Giáo trình Kiến trúc máy tính và Hệ điều hành 204 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 1. Phươ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 LR - Qui 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, $}) Giáo trình Kiến trúc máy tính và Hệ điều hành 205 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 1. Phươ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 LR cho I={S’.S,$} và Tính Closure(I)=? G’: S’S SAA A aA | d Closure(I)={ S’.S, $ S.AA, $ A.aA, a|d A.d, a|d } A  .B, a B  , b Giáo trình Kiến trúc máy tính và Hệ điều hành 206 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 1. Phươ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 LR G’: S’S SAA A aA | d I={ S’.S, $ S.AA, $ A.aA, a|d A.d, a|d } X:{S, A, a, d} Goto(I,S)=closure({S’S.,$}) Goto(I,A)=closure({SA.A,$}) Goto(I,a)=closure({Aa.A,a|d}) Goto(I,d)=closure({Ad., a|d}) Giáo trình Kiến trúc máy tính và Hệ điều hành 207 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 1. Phươ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 LR - Qui tắc xác định hành động (1) [A.a,b] Ii và goto(Ii,a)=Ij với a Σ thì: Action[i,a]= Sj (2) [A.X,b]  Ii và goto(Ii,X)=Ij với X Δ thì: goto[i,X]= j Giáo trình Kiến trúc máy tính và Hệ điều hành 208 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 1. Phươ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 LR - Qui tắc xác định hành động (3) [S’S.,$]  Ii thì: Action[i,$]= accept (4) [A.,a]Ii thì Action[i,a]= Reduce A với AS’ Giáo trình Kiến trúc máy tính và Hệ điều hành 209 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 1. Phươ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 LR - Trộ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ước Giáo trình Kiến trúc máy tính và Hệ điều hành 210 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 1. Phươ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 LR Ví dụ: SAA A aA | d - Xây dựng văn phạm gia tố G’ - Tính I0=closure({S’.S, $} và tất cả các Ii - Xác định hành động Giáo trình Kiến trúc máy tính và Hệ điều hành 211 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 1. Phươ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 LR Ví dụ: SAA A aA | d I0=closure({S’.S, $} Giáo trình Kiến trúc máy tính và Hệ điều hành 212 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 1. Phương pháp phân tích cú pháp dưới lên 1.4. Phương pháp Canonical LR (LR(1)) Action Goto a d $ S A 0 S36 S47 1 2 1 Accept 2 S36 S47 5 36 S36 S47 89 47 R3 R3 R3 89 R2 R2 R2 5 R1 Giáo trình Kiến trúc máy tính và Hệ điều hành 213 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 1. Phương pháp phân tích cú pháp dưới lên 1.4. Phương pháp Canonical LR (LR(1)) Stt Stack Buffer Hành động 0 $0 aadad$ S36 1 $0 a 36 adad$ S36 2 $0 a 36 a 36 dad$ S47 3 $0 a 36 a 36 d 47 ad$ R3(Ad) 4 $0 a 36 a 36 A 89 ad$ R2(AaA) 5 $0 a 36 A 89 ad$ R2(AaA) Giáo trình Kiến trúc máy tính và Hệ điều hành 214 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 1. Phương pháp phân tích cú pháp dưới lên 1.4. Phương pháp Canonical LR (LR(1)) Stt Stack Buffer Hành động 6 $0 A 2 ad$ S36 7 $0 A 2 a 36 d$ S47 8 $0 A 2 a 36 d 47 $ R3(Ad) 9 $0 A 2 a 36 A 89 $ R2(AaA) 10 $0 A 2 A 5 $ R1(SAA) 11 $0 S 1 $ Accept Giáo trình Kiến trúc máy tính và Hệ điều hành 215 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 1. Phươ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 | a (I0I10) trộn I2 và I10, I3 và I7, I8 và I9 Giáo trình Kiến trúc máy tính và Hệ điều hành 216 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 2. Phương pháp phân tích cú pháp trên xuống - PTCP 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ác - Hạn chế văn phạm. Giáo trình Kiến trúc máy tính và Hệ điều hành 217 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 2. Phươ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ải - Nhìn trước 1 ký hiệu Giáo trình Kiến trúc máy tính và Hệ điều hành 218 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 2. Phươ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: (1)sx có dạng A1 | 2 | 3 | | n thì phải có first(i)  first(j) =  với ij (2)AΔ mà A+  thì phải có: first(A)  follow(A)= Giáo trình Kiến trúc máy tính và Hệ điều hành 219 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 2. Phương pháp phân tích cú pháp trên xuống 2.1. Văn phạm LL(1)  Ví dụ: (1) SA | B AaA | b BaB | c Xét: SA | B First(A)={a,b} First(B)={a,c} First(A)  firs (B)={a} (vi phạm ĐK1) nên vp trên không phải là LL(1) Giáo trình Kiến trúc máy tính và Hệ điều hành 220 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 2. Phương pháp phân tích cú pháp trên xuống 2.1. Văn phạm LL(1)  Ví dụ: (2) 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) Giáo trình Kiến trúc máy tính và Hệ điều hành 221 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 2. 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)  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) Giáo trình Kiến trúc máy tính và Hệ điều hành 222 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 2. 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)  Khử đệ qui trái: Dạng (1): AA |  Dạng (2): AA |  Xét (2): AΔ mà A+  có: first(A)=first(A)=first(), follow(A)=first() nên first(A)follow(A)=first() (vi pham đk2) VP đệ qui trái không phải là LL(1) Giáo trình Kiến trúc máy tính và Hệ điều hành 223 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 2. 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)  Khử đệ qui trái: Dạng (1): AA |  Thay bởi: AA’ A’A’| A A A    A A’ A’    A’  Giáo trình Kiến trúc máy tính và Hệ điều hành 224 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 2. 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)  Khử đệ qui trái: Dạng (2): AA |  Thay bởi: AA |  A A A    A A A    Giáo trình Kiến trúc máy tính và Hệ điều hành 225 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 2. 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) Giáo trình Kiến trúc máy tính và Hệ điều hành 226 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 2. 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’ |  Giáo trình Kiến trúc máy tính và Hệ điều hành 227 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 2. 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) (1) E  E + T | T T  T * F | F F  (E) | id (2) A A T | T T 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Giáo trình Kiến trúc máy tính và Hệ điều hành 228 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 2. 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) (3) AA S | A C | C C a S  0 (4)Xây dựng VP LL(1) sản sinh ra danh định của một ngôn ngữ. Giáo trình Kiến trúc máy tính và Hệ điều hành 229 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 2. 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 (1) E TE’ E’+TE’ |  T  FT’ T’*FT’ |  F(E) | id Giáo trình Kiến trúc máy tính và Hệ điều hành 230 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 2. 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 (2) A TA | T ATA’ T 0 | .. | 9 A’A | T 0|..|9 Giáo trình Kiến trúc máy tính và Hệ điều hành 231 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 2. 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 (3)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 Giáo trình Kiến trúc máy tính và Hệ điều hành 232 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 2. 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 (4) ID ID CC | ID CS |ID_ | CC| _ID| CC a | b CS  0 | 1 Giáo trình Kiến trúc máy tính và Hệ điều hành 233 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 2. 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 (4) ACC A’ | _B BCCA’ | CS A’| _B A’CCA’| CSA’ | _A’|  CCa CS0 Giáo trình Kiến trúc máy tính và Hệ điều hành 234 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 235 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 2. 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: 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ỗng Giáo trình Kiến trúc máy tính và Hệ điều hành 236 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 2. 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ỗ g: xâu x không đúng CP VPG Giáo trình Kiến trúc máy tính và Hệ điều hành 237 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 238 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 239 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 2. 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 ? Giáo trình Kiến trúc máy tính và Hệ điều hành 240 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 241 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 242 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 243 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 2. 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 (1) sx A thì M[A,a]=A với afirst()    (2) sx A thì M[A,a]=A với a follow(A) Giáo trình Kiến trúc máy tính và Hệ điều hành 244 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 2. 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) Giáo trình Kiến trúc máy tính và Hệ điều hành 245 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 2. 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: - 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’ Giáo trình Kiến trúc máy tính và Hệ điều hành 246 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 2. 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: - 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id Giáo trình Kiến trúc máy tính và Hệ điều hành 247 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 2. 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: - 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’ Giáo trình Kiến trúc máy tính và Hệ điều hành 248 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 2. 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: + * 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) Giáo trình Kiến trúc máy tính và Hệ điều hành 249 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 2. 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: 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án Giáo trình Kiến trúc máy tính và Hệ điều hành 250 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 251 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 2. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 252 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 2. 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: (1)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) Giáo trình Kiến trúc máy tính và Hệ điều hành 253 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 2. 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: (2)Sự rẽ nhánh tạo thành cấu trúc chọn 1 2 3 If 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; Giáo trình Kiến trúc máy tính và Hệ điều hành 254 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 2. 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: (3) Lặp kiểm tra đk sau (4)Lặp kiểm tra đk trước While k/htiepfirst() do t()   Repeat t() Until k/htiepfirst() Giáo trình Kiến trúc máy tính và Hệ điều hành 255 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 2. 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: (5) (6) a If k/htiep=a Then k/htiep=k/htieptheo trong xâu x Else baoloi; B goi B //t(B); Giáo trình Kiến trúc máy tính và Hệ điều hành 256 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 2. 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, dừng} Procedure I;{các Ctcon biểu diễn AΔ} Giáo trình Kiến trúc máy tính và Hệ điều hành 257 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 2. 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. Giáo trình Kiến trúc máy tính và Hệ điều hành 258 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 2. 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ụ: E TE’ E’+TE’ |  T  FT’ T’*FT’ |  F(E) | id Giáo trình Kiến trúc máy tính và Hệ điều hành 259 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 2. 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ụ: Biểu đồ cú pháp T E’E: T E’+E’: F T’T: F T’*T’: F: E( ) id Giáo trình Kiến trúc máy tính và Hệ điều hành 260 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 2. 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ụ: giải thuật các ctcon tương ứng 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} Giáo trình Kiến trúc máy tính và Hệ điều hành 261 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 2. 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ụ: giải thuật các ctcon tương ứng Procedure E; Begin T; Ephay; End; Giáo trình Kiến trúc máy tính và Hệ điều hành 262 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 2. 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ụ: giải thuật các ctcon tương ứng Procedure Ephay; Begin If k/htiep=+ Then Begin k/htiep:=Dockh; T; Ephay; End; End; Giáo trình Kiến trúc máy tính và Hệ điều hành 263 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 2. 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ụ: giải thuật các ctcon tương ứng Procedure T; Begin F; Tphay; End; Giáo trình Kiến trúc máy tính và Hệ điều hành 264 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 2. 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ụ: giải thuật các ctcon tương ứng Procedure Tphay; Begin If k/htiep=* Then Begin k/htiep:=Dockh; F; Tphay; End; End; Giáo trình Kiến trúc máy tính và Hệ điều hành 265 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 2. 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 Procedure 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; E d Else baoloi; End; Giáo trình Kiến trúc máy tính và Hệ điều hành 266 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 2. 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; E; if k/htiep=$ then x đúng CP else baoloi; End. Giáo trình Kiến trúc máy tính và Hệ điều hành 267 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 2. 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 Bà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) Giáo trình Kiến trúc máy tính và Hệ điều hành 268 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 Bài tập: Cho G sau: EE and T| T TT or F | F F not F | (E) | true| false Xâu x: true and not false Ch/m x đúng cp VPG bằng pp SLR

Các file đính kèm theo tài liệu này:

  • pdfchuong_trinh_dich_364.pdf
Tài liệu liên quan