Bài 4. PHÂN TÍCH CÚ PHÁP Hoàng Anh Việt Viện CNTT&TT - ĐHBKHN 1 goupee.com fb.com/groups/goupee 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 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 4. Phương pháp phân tích từ dưới lên 4 goupee.com fb.com/groups/goupee 4. Phương pháp phân tích từ dưới lên 5 goupee.com fb.com/groups/goupee 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 Phân tích trên xuống Suy dẫn trái Toàn bộ cây phía trên một kí hiệu được sinh ra Phải có khả năng đoán trước được sản xuất S S E S E 1 goupee.com + ( S S + + E E 5 ) E ( S ) 2 S + E E 4 3 fb.com/groups/goupee Phân tích dưới lên (1) Suy dẫn phải Cây suy dẫn được xây dựng ngược lại S  S+E | E E  số | (S) 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 Phân tích dưới lên (2) Suy dẫn phải (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+E S goupee.com (1+2+(3+4))+5 (1 +2+(3+4))+5 (1 +2+(3+4))+5 (1+2 +(3+4))+5 (1+2+(3 +4))+5 (1+2+(3 +4))+5 (1+2+(3 +4))+5

… Tải file gốc để đọc toàn bộ tài liệu.