IT4073: NGÔN NGỮ và PHƯƠNG PHÁP DỊCH

Chương 3: Phân tích cú pháp1. Bài toán phân tích cú pháp 2. Phương pháp phân tích cú pháp quay lui 3. Phương pháp phân tích bảng4. Phương pháp phân tích cú pháp tất định5. Phân tích cú pháp cho PL/0.1. Bài toán phân tích cú phápBài toán đặt raCho– Văn phạm phi ngữ cảnh G G = (VT, VN, P, S) Trong chương trình dịch, xâu  là chuỗi các token – Xâu V*T thu được từ giai đoạnHỏi
Nội dung trích xuất từ tài liệu:
IT4073:NGÔN NGỮ và PHƯƠNG PHÁP DỊCHIT4073:NGÔN NGỮ vàPHƢƠNG PHÁP DỊCH Phạm Đăng Hải haipd@soict.hut.edu.vn Chương 3: Phân tích cú pháp1. Bài toán phân tích cú pháp2. Phương pháp phân tích cú pháp quay lui3. Phương pháp phân tích bảng4. Phương pháp phân tích cú pháp tất định5. Phân tích cú pháp cho PL/010/24/2012 21. Bài toán phân tích cú pháp Bài toán đặt ra Cho – Văn phạm phi ngữ cảnh G G = (VT, VN, P, S) Trong chương trình dịch, xâu  là chuỗi các token – Xâu  V*T thu được từ giai đoạn Hỏi Program Vidu; trước – phân tích từ vựng Begin PROGRAM IDENT –  L(G)? SEMICOLON BEGIN IDENT X := 10 ASSIGN NUMBER END Nếu   L(G) End. PERIOD – Chỉ ra các sản xuất đã sử dụng để sinh ra  – Cấu trúc nên cây suy dẫn 10/24/2012 31. Bài toán phân tích cú pháp 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) 10/24/2012 • Xác định được duy nhất một sản xuất thích hợp 41. 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 1. E  T+E Xét xâu a*(a+a) 2. E  T E 2 T 3 F*T 6 a*T 3. T  F* T 4 a*F 5a*(E) 4. T  F 1 a*(T+E) 4 a*(F+E) 5. F  (E) 6 a*(a+E) 2 a*(a+T) 6. F  a 4 a*(a+F) 6 a*(a+a) 10/24/2012 Phân tích trái của xâu a*(a+a) là 23645146246 5 Chương 3: Phân tích cú pháp1. Bài toán phân tích cú pháp2. Phương pháp phân tích cú pháp quay lui3. Phương pháp phân tích bảng4. Phương pháp phân tích cú pháp tất định5. Phân tích cú pháp cho PL/010/24/2012 62. Phương pháp phân tích quay lui 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 10/24/2012 72. Phương pháp phân tích quay lui Phân tích 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 (Start symbol): Ký hiệu khởi đầu - Gọi ký hiệu cần phân tích là ký hiệu đầu tiên của xâu  - Gọi S là nút hoạt động, 10/24/2012 82. Phương pháp phân tích quay lui Phân tích Top-down 2. Tạo các nút con của cây (một cách đệ quy)  Nút hoạt động là ký hiệu không kết thúc A – Chọn sản xuất đầu tiên của A chưa được áp dụng: A X1X2. . . .Xk (k 0) – Tạo k con trực tiếp của A với nhãn X1, X2, ...Xk – Nếu k > 0, Lấy X1 làm nút hoạt động – Nếu k = 0, (sản xuất A  e), lấy nút bên phải (ngay sau) A là nút hoạt động Tiếp tục thực hiện bước 2 10/24/2012 92. Phương pháp phân tích quay lui Phân tích Top-down 2. Tạo các nút con của cây (một cách đệ quy)  Nút hoạt động là ký hiệu kết thúc a - So sánh a với ký hiệu cần phân tích hiện tại – Nếu trùng nhau • Nút hoạt động là nút bên phải của a • Ký hiệu cần phân tích là ký hiệu tiếp theo trên xâu vào – Nếu không trùng nhau • Quay lại bước đã sử dụng một sản xuất và thử sản xuất tiếp. – Nếu đã hết khả năng, quay lại bước trước 10/24/2012 102. Phương pháp phân tích quay lui Phân tích Top-down 3. Điều kiện dừng - Đã áp dụng hết khả năng mà không tạo được cây Xâu không được đoán nhận - Tạo ra cây suy dẫn cho xâu vào 10/24/2012 112. Phương pháp phân tích quay lui Phân tích Top-down  Điều kiện áp dụng thuật toán - Văn phạm không đệ quy trái  Chi phí (n = l( ...