Trang 2
Nội dung 1. Vai trò của bộ phân tích cú pháp (PTCP) 2. Văn phạm của ngôn ngữ lập trình 3. Phân tích cú pháp từ trên xuống 4. Phân tích cú pháp từ dưới lên 5. Bộ sinh bộ PTCP 2 goupee.com fb.com/groups/goupee
Nội dung tài liệu
Trang 3
4. Phương pháp phân tích từ dưới lên • Thí dụ 4.6. Cho văn phạm G. S ->aABe A ->Abc|b B ->d Phân tích câu w = abbcde. 3 goupee.com fb.com/groups/goupee
Trang 6
Phân tích từ dưới lên (bottom-up parsing) • Kỹ thuật phân tích mạnh hơn • Văn phạm lớp LR có khả năng mô tả mạnh hơn văn phạm lớp LL, có thể mô tả văn phạm đệ quy trái (có trong hầu hết các ngôn ngữ lập trình) • Dễ dàng mô tả các ngôn ngữ lập trình thông thường • Bộ phân tích cú pháp gạt – thu gọn (Shift-Reduce parsing) – Xây dựng cây suy dẫn phải – Tự động xây dựng bộ phân tích cú pháp VD: yacc, CUP – Phát hiện lỗi ngay khi xuất hiện – Cho phép phục hồi khi lỗi xảy ra goupee.com fb.com/groups/goupee
Trang 7
Phân tích trên xuống S S + E • Suy dẫn trái E 5 • Toàn bộ cây phía trên ( S ) một kí hiệu được sinh ra • Phải có khả năng đoán S + E trước được sản xuất S + E ( S ) E 2 S + E 1 E 4 3 goupee.com fb.com/groups/goupee
Trang 8
Phân tích dưới lên (1) S S+E | E • Suy dẫn phải E số | (S) • Cây suy dẫn được xây dựng ngược lại – Bắt đầu từ kí hiệu kết thúc – Kết thúc tại kí hiệu bắt đầu • Ví dụ (1+2+(3+4))+5 (E+2+(3+4))+5 (S+2+(3+4))+5 (S+E+(3+4))+5 (S+(3+4))+5 (S+(E+4))+5 (S+(S+4))+5 (S+(S+E))+5 (S+(S))+5 (S+E)+5 (S)+5 E+5 S+5 S+E S goupee.com fb.com/groups/goupee
Trang 9
Phân tích dưới lên (2) (1+2+(3+4))+5 (1+2+(3+4))+5 (E+2+(3+4))+5 (1 +2+(3+4))+5 (S+2+(3+4))+5 (1 +2+(3+4))+5 (S+E+(3+4))+5 (1+2 +(3+4))+5 (S+(3+4))+5 (1+2+(3 +4))+5 (S+(E+4))+5 (1+2+(3 +4))+5 (S+(S+4))+5 (1+2+(3 +4))+5 Suy dẫn(S+(S+phảiE))+5 (1+2+(3+4 ))+5 (S+(S))+5 (1+2+(3+4 ))+5 (S+E)+5 (1+2+(3+4) )+5 (S)+5 (1+2+(3+4) )+5 E+5 (1+2+(3+4)) +5 S+E (1+2+(3+4))+5 S (1+2+(3+4))+5 goupee.com fb.com/groups/goupee
Trang 10
Phân tích dưới lên (3) (1+2+(3+4))+5 S (E+2+(3+4))+5 S + E E 5 (S+2+(3+4))+5 ( S ) (S+E+(3+4))+5 … S + E S + E ( S ) • Phân tích dưới lên có nhiều thông tin hơn khi E 2 S + E phân tích 1 E 4 3 goupee.com fb.com/groups/goupee
Trang 11
Phân tích dưới lên và phân tích trên xuống • Phân tích dưới lên không cần sinh ra toàn bộ cây suy dẫn trong quá trình phân tích Phân tích trên xuống Phân tích dưới lên Đã đọc Chưa đọc Đã đọc Chưa đọc goupee.com fb.com/groups/goupee
Trang 12
4.1 Phân tích gạt – thu gọn (1) • Phân tích bằng một dãy thao tác: gạt và thu gọn • Mỗi thời điểm, trạng thái của bộ phân tích là ngăn xếp các kí hiệu kết thúc và không kết thúc • Cấu hình tại mỗi thời điểm gồm: ngăn xếp + xâu các kí hiệu chưa đọc Suy dẫn Ngăn xếp Chưa đọc (1+2+(3+4))+5 (1+2+(3+4))+5 (E+2+(3+4))+5 (E +2+(3+4))+5 (S+2+(3+4))+5 (S +2+(3+4))+5 (S+E+(3+4))+5 (S+E +(3+4))+5 goupee.com fb.com/groups/goupee
Trang 13
4.1 Phân tích gạt – thu gọn (2) • Gạt: Đọc và đưa một kí hiệu kết thúc của xâu vào stack Ngăn xếp Chưa đọc Thao tác ( 1+2+(3+4))+5 Gạt 1 (1 +2+(3+4))+5 • Thu gọn: Thay thế một xâu ở đỉnh của ngăn xếp bằng kí hiệu không kết thúc X với X (pop , push X) Ngăn xếp Chưa đọc Thao tác (S+E +(3+4))+5 Thu gọn: S S+E (S +(3+4))+5 goupee.com fb.com/groups/goupee
Trang 14
4.1 Phân tích gạt – thu gọn (3) Suy dẫn Ngăn xếp Chưa đọc Thao tác (1+2+(3+4))+5 (1+2+(3+4))+5 gạt ( (1+2+(3+4))+5 ( 1+2+(3+4))+5 gạt 1 (1+2+(3+4))+5 (1 +2+(3+4))+5 thu gọn E1 (E+2+(3+4))+5 (E +2+(3+4))+5 thu gọn SE (S+2+(3+4))+5 (S +2+(3+4))+5 gạt + (S+2+(3+4))+5 (S+ 2+(3+4))+5 gạt 2 (S+2+(3+4))+5 (S+2 +(3+4))+5 thu gọn E2 (S+E+(3+4))+5 (S+E +(3+4))+5 thu gọn SS+E (S+(3+4))+5 (S +(3+4))+5 gạt + (S+(3+4))+5 (S+ (3+4))+5 gạt ( (S+(3+4))+5 (S+( 3+4))+5 gạt 3 (S+(3+4))+5 (S+(3 +4))+5 thu gọn E3 (S+(E+4))+5 (S+(E +4))+5 thu gọn SE (S+(S+4))+5 (S+(S +4))+5 gạt + (S+(S+4))+5 (S+(S+ 4))+5 gạt 4 goupee.com ... ... ... fb.com/groups/goupee...
Trang 15
Các vấn đề nảy sinh • Cần xác định khi nào gạt hoặc thu gọn hoặc thu gọn với sản xuất nào? • Thu gọn sản xuất rỗng X → ε • Có nhiều cách thu gọn S E hay S S+E goupee.com fb.com/groups/goupee
Trang 16
Lựa chọn thao tác • Tại mỗi thời điểm, từ cấu hình <S – ngăn xếp, a – từ tố nhìn trước> • Xác định – Gạt a, ngăn xếp trở thành <Sa> – Thu gọn X , nếu S = , ngăn xếp trở thành < X> • Nếu S = , cần lựa chọn gạt a hoặc thu gọn X dựa vào tiền tố – Với mỗi khả năng thu gọn X có một – Cần tìm cách đánh dấu các khả năng thu gọn goupee.com fb.com/groups/goupee
Trang 17
Trạng thái của bộ phân tích gạt – thu gọn • Mục tiêu: Xác định khả năng thu gọn hợp lệ tại từng thời điểm • Ý tưởng: gộp các khả năng có thể có của tiền tố thành trạng thái của bộ phân tích • Các vấn đề nảy sinh: – Tính toán các trạng thái của bộ phân tích – Tính toán các trạng thái kết thúc – Phân tích tất định (loại văn phạm nào) – Kích cỡ của bộ phân tích (số lượng trạng thái) goupee.com fb.com/groups/goupee
Trang 18
4.2 Bộ phân tích cú pháp LR Phân tích cú pháp LR(k): • L (left - to - right): Duyệt chuỗi nhập từ trái sang phải. • R (rightmost derivation): Xây dựng chuỗi dẫn xuất phải nhất đảo ngược. • k : Số lượng ký hiệu nhập được xét tại mỗi thời điểm dùng để đưa ra quyết định phân tích. Khi không đề cập đến k, hiểu ngầm là k = 1. 18 goupee.com fb.com/groups/goupee
Trang 19
4.2 Bộ phân tích cú pháp LR Các tính chất của phương pháp phân tích LR(k): • Bộ phân tích LR có thể nhận dạng được cấu trúc cú pháp của các ngôn ngữ lập trình do văn phạm phi ngữ cảnh tạo ra. • Phương pháp LR là phương pháp tổng quát nhất của phương pháp phân tích gạt và thu gọn, không bị quay lui. • Lớp văn phạm có thể dùng phương pháp LR là một lớp rộng lớn hơn lớp văn phạm có thể sử dụng phương pháp dự đoán. • Bộ phân tích cú pháp LR cũng có thể xác định lỗi cú pháp nhanh ngay trong khi duyệt dòng nhập từ trái sang phải. Nhược điểm? 19 goupee.com fb.com/groups/goupee
Hiển thị 19 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!