Bài 4. PHÂN TÍCH CÚ PHÁP Hoàng Anh Việt Viện CNTT&TT - ĐHBKHN 1 fb.com/groups/ 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 fb.com/groups/ 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 fb.com/groups/ 4. Phương pháp phân tích từ dưới lên 4 fb.com/groups/ 4. Phương pháp phân tích từ dưới lên 5 fb.com/groups/ 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 fb.com/groups/ 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 + ( S S + + E E 5 ) E ( S ) 2 S + E E 4 3 fb.com/groups/ 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 fb.com/groups/ 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 (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