Bài toán phân tích cú pháp Phương pháp phân tích cú pháp quay lui Phương pháp phân tích cú pháp tất định Xây dựng bộ phân tích cú pháp cho KPL Kiểm tra xâu phân tích từ trái qua phải Kiểm tra ký hiệu trái nhất của xâu cần phân tích Tới ký hiệu tiếp, Cho tới ký hiệu cuối cùng Phương pháp xây dựng cây phân tích | Xây dựng CHƯƠNG TRÌNH DỊCH Phạm Đăng Hải haipd@ Chương 3: Phân tích cú pháp Bài toán phân tích cú pháp Phương pháp phân tích cú pháp quay lui Phương pháp phân tích cú pháp tất định Xây dựng bộ phân tích cú pháp cho KPL Bài toán đặt ra Cho Văn phạm phi ngữ cảnh G G = (VT, VN, P, S) Xâu V*T Hỏi L(G)? Nếu L(G) Chỉ ra các sản xuất đã sử dụng để sinh ra Cấu trúc nên cây suy dẫn 1. Bài toán phân tích cú pháp Trong chương trình dịch, xâu là chuỗi các token thu được từ giai đoạn trước – phân tích từ vựng Phương pháp phân tích Kiểm tra xâu phân tích từ trái qua phải Kiểm tra ký hiệu trái nhất của xâu cần phân tích Tới ký hiệu tiếp, Cho tới ký hiệu cuối cùng Phương pháp xây dựng cây phân tích Trên xuống (Top-down): S * ? Dưới lên (Bottom-up): * S? Phương pháp lựa chọn sản xuất (A α1| |αn) Quay lui (backtracking) Thử lần lượt các sản xuất Tất định (deterministic) Xác định được duy nhất một sản xuất thích hợp 1. Bài toán phân tích cú pháp Phân tích | Xây dựng CHƯƠNG TRÌNH DỊCH Phạm Đăng Hải haipd@ Chương 3: Phân tích cú pháp Bài toán phân tích cú pháp Phương pháp phân tích cú pháp quay lui Phương pháp phân tích cú pháp tất định Xây dựng bộ phân tích cú pháp cho KPL Bài toán đặt ra Cho Văn phạm phi ngữ cảnh G G = (VT, VN, P, S) Xâu V*T Hỏi L(G)? Nếu L(G) Chỉ ra các sản xuất đã sử dụng để sinh ra Cấu trúc nên cây suy dẫn 1. Bài toán phân tích cú pháp Trong chương trình dịch, xâu là chuỗi các token thu được từ giai đoạn trước – phân tích từ vựng Phương pháp phân tích Kiểm tra xâu phân tích từ trái qua phải Kiểm tra ký hiệu trái nhất của xâu cần phân tích Tới ký hiệu tiếp, Cho tới ký hiệu cuối cùng Phương pháp xây dựng cây phân tích Trên xuống (Top-down): S * ? Dưới lên (Bottom-up): * S? Phương pháp lựa chọn sản xuất (A α1| |αn) Quay lui (backtracking) Thử lần lượt các sản xuất Tất định (deterministic) Xác định được duy nhất một sản xuất thích hợp 1. Bài toán phân tích cú pháp Phân tích trái Phân tích trái của xâu a là dãy các sản xuất được sử dụng trong suy dẫn trái từ S ra a Các sản xuất được đánh số thứ tự 1,p Phân tích là danh sách các số từ 1 đến p Ví dụ cho văn phạm E T+E E T T F* T T F F (E) F a Phân tích trái của xâu a*(a+a) là 23645146246 1. Bài toán phân tích cú pháp Xét xâu a*(a+a) E 2 T 3 F*T 6 a*T 4 a*F 5a*(E) 1 a*(T+E) 4 a*(F+E) 6 a*(a+E) 2 a*(a+T) 4 a*(a+F) 6 a*(a+a) Chương 3: Phân tích cú pháp Giới thiệu Phương pháp phân tích cú pháp quay lui Phương pháp phân tích cú pháp tất định Xây dựng bộ phân tích cú pháp cho KPL Giới thiệu Tư tưởng chủ yếu của giải thuật Xây dựng cây phân tích cú pháp (cây suy dẫn) cho xâu Thuật toán Top-down Đi từ nút gốc tới nút lá Thuật toán Bottom –up Quá trình phân tích gạt thu gọn 2. Phương pháp phân tích quay lui Thuật toán Top-down Cho VPPNC G = (VT, VN, P, S) sản xuất A α1| |αn được đánh số 1, 2, Xây dựng cây phân tích cho xâu : 1. Khởi tạo Xây dựng cây chỉ có một nút gốc S S .