›
›

Bài giảng Chương trình dịch

1.Các khái niệm cơ bản

1.2. Khái niệm chương trình dịch

   Chương trình dịch là chương trình dùng để dịch một chương trình (CT nguồn) viết trên NNLT nào đó (NN nguồn) sang một chương trình tương đương (CT đích) trên một NN khác (NN đích)

ppt 213 trang thamphan 27/12/2022 1400
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Chương trình dịch", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pptbai_giang_chuong_trinh_dich.ppt

Nội dung text: Bài giảng Chương trình dịch

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 <) Giáo trình Kiến trúc máy tính và Hệ 107 - Lấy cán điềura hành khỏi stack - Đẩy A vào stack với A→
  2. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 109 điều hành
  3. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ a C b  . Sx(1):S→if DK then L; if = then (qt1) a B  S→if DK then L; B b  b  DK true | false if then(qt3)
  4. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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) ( ) (qt3)điều hành
  5. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ụ: Stt Stack Buffer Q/hệ H/động (0) $ if true then read(a);$ R/g DK→true <. . (3) $if DKGiáo trình Kiến trúcthen máy read(a);$tính và Hệ = D/c 115 điều hành
  6. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ụ: Stt Stack Buffer Q/hệ H/động . (8) $if DK then read(ID );$ = D/c (9) $ if DK then ;$ .> R/g R/g S→if <. DK then L; Giáo trình Kiến trúc máy tính và Hệ 117 (12) $S điều hành $ Chấp nhận
  7. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 119 Xâu x: const a=5;điều hành type b=byte; var c:real;
  8. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Buffer $ x1 x2 xi yi y2 y1 $ Bộ phân Kết quả tích Giáo trình Kiến trúc máyBảng tính và HệS_R 121 điều hành
  9. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ỗngGiáo trình Kiến trúc máy tính và Hệ 123 điều hành
  10. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 125 ✓ S_R[xi,yi]=rỗng:điều hành báo lỗi x k0 đúng cp G
  11. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 GiáoBáo trình Kiến lỗi trúc vàmáy tínhdừng và Hệ vòng lặp 127 điều hành
  12. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 129 điều hành
  13. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 131 $ S điều hành
  14. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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,BGiáo trình ( KiếnΣ trúcΔ máy); Atính và ΔHệ; ,,, (ΣΔ)* 133 (Nếu B điềuΣ thìhành y chính là B)
  15. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 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ệ 135 điều hành
  16. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ: begin end. A var C $ const|A>$. ; .> begin . . var : : ;. . . write|read = ( ( ) const = = ; begin<Lđiều. hành L=end end=.
  17. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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→x1x2 xi- 1B và như vậy để thu gọn x1x2 xn, thì sẽ thu gọn xixi+1 xn về B rồi mới thu gọn x1x2 xi-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ệ 139 điều hành
  18. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 s1x1 si-1xi-1si st: trạng thái; xt (ΣΔ) - Buffer: aiai-1 a0$ ; với at Σ - Bảng SLR gồm 2 phần: action và goto Giáo trình Kiến trúc máy tính và Hệ • Chỉ số hàng: trạng thái St 141 điều hành
  19. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 143 điều hành
  20. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 145 điều hành
  21. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 147 - x đúng cp và điềudừng hành vòng lặp
  22. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ - Dừng vòng lặp 149 điều hành
  23. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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/ Action Goto thái 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 Giáo trình Kiến trúc máy tính và Hệ 6 S5 S4 9 151 3 điều hành
  24. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 G’: S’ → S Giáo trình Kiến trúc máy tính và Hệ S → 0S | 1S 153 điều hành
  25. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 155 điều hành
  26. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 157 thì dừng. điều hành
  27. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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); A<>S’ - Qui tắc xác định Follow Giáo trình Kiến trúc máy tính +và Hệ + Follow(A)={(t Σ|S At)(t=$|S 159 A)} điều hành
  28. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 161 điều hành
  29. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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) T→.F I =closure({E’→.E}) 0 F→.(E) E’→.E F→.id E→.E+T I1=goto(I0,E) E→.T E’→E. Giáo trình Kiến trúc máy tính và Hệ T→.T*F 163 điều hành E→E.+T
  30. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 165 điều hành
  31. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 167 điều hành
  32. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Σ Giáo trình Kiến trúc máy tính và Hệ Ví dụ: A→X.YZ, a 169 điều hành
  33. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 (ΣΔ) Giáo trình Kiến trúc máy tính và Hệ 171 điều hành - I0=closure({S’→.S, $})
  34. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 A<>S’ Giáo trình Kiến trúc máy tính và Hệ 173 điều hành
  35. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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→ CC C→ cC | d Giáo trình Kiến trúc máy tính và Hệ 175 điều hành
  36. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 177 điều hành
  37. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ó: Giáo trình Kiến trúc máy tính và Hệ first(A)  follow(A)= 179 điều hành
  38. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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) Giáo trình Kiến trúc máy tính và Hệ 181 VP trên không phảiđiều hành là LL(1)
  39. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ first(A)follow(A)=first( )  (vi pham183 đk2) VP đệ qui tráiđiều không hành phải là LL(1)
  40. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 185 điều hành 
  41. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 187 điều hành
  42. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 189 điều hành
  43. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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→ AT | 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ệ 191 điều hành
  44. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 193 điều hành
  45. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Buffer xi x2 x1 $ ai a2 a1 $ Bộ phân tích Kết quả Bảng tiên đoán M Giáo trình Kiến trúc máy tính và Hệ 195 điều hành
  46. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ • M[A,a]=rỗng: xâu x không đúng CP VPG197 điều hành
  47. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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 Giáo trình Kiến trúc máy tính và Hệ 199 Else x k0 đúngđiều hành CP VPG, dừng vòng lặp
  48. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 201 điều hành
  49. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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ệ 203 điều hành
  50. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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: (1) E → TE’ (2) (3) E’→+TE’ |  (4) T → FT’ (5) (6) T’→*FT’ |  Giáo trình Kiến trúc máy tính và Hệ (7) (8) 205 F→(E) | idđiều hành
  51. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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: T E’ Giáo trình Kiến trúc máy tính và Hệ 207 điều hành
  52. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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  (5) Nếu k/h tiếp=a thì Đọcký tự tiếp theo a Giáo trình Kiến trúc máy tính và Hệ 209 Ngược lại báođiều lỗi hành
  53. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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} Procedure I;{các Ctcon biểu diễn A Δ} Giáo trình Kiến trúc máy tính và Hệ 211 điều hành
  54. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP 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áo trình Kiến trúc máy tính và Hệ 213 điều hành