Bài giảng Chương trình dịch: Bài giảng 5 - Nguyễn Phương Thái

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:41

Thêm vào BST

Báo xấu

67
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng 5 trình bày các phương pháp phân tích hiệu quả. Thông qua bài giảng này, người học có thể biết được các ưu và nhược điểm của phân tích Top-Down, Bottom-up; biết được các ưu và nhược điểm của phân tích tất định; nắm bắt được đặc điểm phân tích tất định;... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Chương trình dịch: Bài giảng 5 - Nguyễn Phương Thái

Bài giảng 5 – Các phương pháp phân tích hiệu quả Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/ 1
Phân tích TopDown, Bottomup Ưu điểm:  Đơn giản  Phân tích được cho toàn bộ lớp VPPNC  Phân tích được ngôn ngữ nhập nhằng Nhược điểm:  Quá chậm (cn) do phải quay lui 2
HaìGiang Cao Bàò ng Lai Cháu Thaïi Nguyãn Tìm đường Sån La Laû ng Sån Haìnäüi Haíi Phoìng NamÂënh Thanh Hoaï Vinh Âäö ng Håïi Huãú ÂaìNàô ng Quaíng Ngaîi Qui Nhån NhaTrang Phan Rang Phan Thiãú t Tp HCM 3
Phân tích hiệu quả (tất định) Hi sinh (nhược điểm):  Lớp ngôn ngữ bé hơn PNC  Bắt buộc không nhập nhằng Ưu điểm:  Rất nhanh (cn) 4
Đặc điểm phân tích tất định  Quét xâu vào từ phải sang trái  Quá trình phân tích là hoàn toàn xác định  Không dùng quay lui  Dựa vào trạng thái hiện tại và ký hiệu kết thúc để xác định luật duy nhất  Các luật phải được thiết kế đặc biệt 5
Các lớp văn phạm  Văn phạm LL(k) văn phạm cho phép xây dựng các bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k ký hiệu vào nằm ngay ở bên phải của vị trí vào hiện thời.  Văn phạm LR(k) văn phạm cho phép xây dựng các bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k ký hiệu vào nằm vượt quá vị trí vào hiện thời. 6
Phân tích LL Xáu vaìo c a + b $ Ngàn xãú p Âáöu ra Chæång trçnh phán X têch táú t âënh Y Z Baíng phán têch M[A, a] $ Mä hçnh cuía bäü phán têch táút âënh 7
Chương trình điều khiển X ký hiệu đỉnh ngăn xếp, a ký hiệu vào hiện tại  Nếu X = a = $: dừng và tuyên bố thành công (cả xâu vào lẫn ngăn xếp đều rỗng).  Nếu X = a $: lấy X khỏi ngăn xếp, dịch con trỏ vào sang ký hiệu vào tiếp theo (đã khai triển đến lá khớp với xâu vào).  Nếu X là một biến: xét ô M [X, a]. Nếu:  Nếu M[X, a] = {X UVW} thay X đang nằm trên đỉnh ngăn xếp bằng WVU (U sẽ nằm trên đỉnh) (thực hiện một phép mở rộng cây)  Nếu M[X, a] = lỗi (vị trí lỗi), gọi hàm khôi phục lỗi. 8
Thuật toán Đặt con trỏ ip chỉ đến ký tự đầu tiên của xâu w$ repeat Giả sử X là ký hiệu đỉnh của ngăn xếp và a là ký hiệu vào tiếp theo; if X là một ký hiệu kết thúc hoặc $ then if X = a then pop X từ đỉnh ngăn xếp và loại bỏ a khỏi xâu vào else ERROR( ); else { X không phải là ký hiệu kết thúc } if M[X, a] = X Y1Y2 ...Yk then begin pop X từ ngăn xếp; push Yk,Yk1,...Y1 vào ngăn xếp, với Y1 ở đỉnh; đưa ra sản xuất X Y1Y2 ...Yk end else ERROR( ); until X = $; { ngăn xếp rỗng } 9
HaìGiang Cao Bàò ng Lai Cháu Thaïi Nguyãn Sån La Laû ng Sån Tìm đường Haìnäüi Haíi Phoìng NamÂënh Thanh Hoaï Xuáút phaït Âiãøm âãún Vinh HCM Haíi Phoìng Nam Âënh ... Âäö ng Håïi Haì näüi Haìnäü i Nam âënh Haìnäü i Haíi dæång Haìnäü i Nam âënh ... Huãú Nam âënh Nam âënh Nam âënh Haìnäü i ... ÂaìNàô ng Thanh hoaï Quaíng Ngaîi Thanh hoaï Thanh hoaï Vinh Thanh hoaï Nam âënh Thanh hoaï Nam âënh ... Qui Nhån ... ... ... ... ... NhaTrang Phan Thiãút Phan thiãú t HCM Phan thiãú t Phan rang Phan thiãú t Phan rang ... Phan Rang Phan Thiãú t HCM HCM Phan thiãú t HCM Phan thiãú t Tp HCM... 10
Ví dụ Kyï hiãûu Kyï hiãûu vaìo cuï phaïp a + * ( ) $ E E TE’ E TE’ E’ E’ +TE’ E’ E’ T T FT’ T FT’ T’ T’ T’ *FT’ T’ T’ F F a F (E) Baíng phán têch M 11
Ví dụ phân tích: a+a*a a + + a ** a $ E E’ T’ +* F a $ T E E’ T’ T F E T E’E’ $ E’ T’ $ F T’ + T E’E’ E’ $ F T’ a $ a * F T’ 12 a
Ngàn Âáöu Âáö u ra xãú p vaìo $E a+a*a$ Ví dụ $E’T $E’T’F a+a*a$ E TE’ a+a*a$ T FT’ $E’T’a a+a*a$ F a $E’T’ +a*a$ $E’ +a*a$ T' $E’T+ +a*a$ E’ +TE’ $E’T a*a$ $E’T’F a*a$ T FT’ $E’T’a a*a$ F a $E’T’ *a$ $E’T’F* *a$ T’ *FT’ $E’T’F a$ $E’T’a a$ F a $E’T’ $ $E’ $ T’ 13 $ $ E’
Nhận xét  M[A, a] đóng vai trò “cẩm nang” tìm đường  Chương trình đơn giản  Hoạt động nhanh Cần xây dựng M[A, a]?  First, Follow 14
Tính First và Follow  Tính dựa vào bộ luật P  Từ First và Follow có thể xây dựng được bảng M[A, a] 15
Định nghĩa  FIRST( ): là tập các ký hiệu kết thúc bắt đầu các xâu được suy dẫn từ .  FOLLOW(A): là tập các ký hiệu kết thúc a mà chúng có thể xuất hiện ngay bên phải của A ở trong một số dạng câu, tức là tập các ký hiệu kết thúc a sao cho tồn tại một suy dẫn dạng E + Aa đối với , bất kỳ. Nếu A là ký hiệu bên phải nhất trong một số dạng câu thì ta thêm $ vào FOLLOW(A). 16
 Hàm FIRST( ) cho biết một xâu hiện tại S có thể suy dẫn đến tận cùng thành một xâu bắt đầu bằng các A kí hiệu kết thúc nào.  Hàm FOLLOW(A) cho biết các kí hiệu kết x yi zi thúc ở đầu phần câu do các phần tử sau A tạo ra. w 17
Tính First( ) Hai bước:  Tính First(A)  Tính First( ) 18
Tính First(A) Lặp cho đến khi không còn thêm:  Nếu X là ký hiệu kết thúc thì FIRST(X) = {X};  Nếu X là một sản xuất thì thêm vào FIRST(X);  Nếu X Y Y ...Y là một sản xuất: 1 2 k  Nếu với một i nào đó thì có trong mọi FIRST(Y1), FIRST(Y2),... FIRST(Yi1) (nghĩa là Y1Y2 ...Yi1 * ) thì ta thêm mọi ký hiệu kết thúc có trong FIRST(Yi) vào FIRST(X).  Nếu i = k (tức là có trong mọi FIRST(Yi) với i = 1, 2, ..., k) thì thêm vào FIRST(X). 19
Tính First( ) Tính FIRST( ) với có dạng X1X2 ... Xn:  Thêm vào FIRST(X X ... X ) tất cả các ký 1 2 n hiệu không phải của FIRST(X1).  Thêm các ký hiệu không phải của FIRST(X2) nếu thuộc FIRST(X1)  Thêm các ký hiệu không phải của FIRST(X3) nếu thuộc cả FIRST(X1) và FIRST(X2)  ...  Thêm vào FIRST(X X ...X ) nếu với mọi i 1 2 n mà FIRST(Xi) có chứa , hoặc nếu n = 0. 20