Chương trình dịch - Bài 14: Phân tích cú pháp bằng thuật toán LR

Nội dung text: Chương trình dịch - Bài 14: Phân tích cú pháp bằng thuật toán LR

1. CHƯƠNG TRÌNH DỊCH Bài 14: Phân tích cú pháp bằng thuật toán LR
2. Nội dung 1. Bộ phân tích kiểu gạt-thu (shift-reduce) 2. Máy phân tích cú pháp LR 3. Văn phạm họ LR . CLOSURE và GOTO . Đồ thị LR(0) . SLR 4. Đánh giá về phân tích LR 5. Bài tập TRƯƠNG XUÂN NAM 2
3. Phần 1 Bộ phân tích kiểu gạt-thu (shift-reduce) TRƯƠNG XUÂN NAM 3
4. Bộ phân tích kiểu gạt-thu . Cách làm việc xuất phát từ việc quan sát hoạt động của phân tích bottom-up . Bắt đầu từ nút lá phải nhất . Thu gọn dần về nút gốc . Chỉ 2 kiểu hoạt động chính: . Gạt (shift) . Thu (reduce) . Shift: lấy kí hiệu tiếp theo . Reduce: thu gọn nhánh thành một kí hiệu trung gian TRƯƠNG XUÂN NAM 4
5. Bộ phân tích kiểu gạt-thu . Là một dạng automat làm việc theo bảng phương án (đã được đề cập tới trong bài trước) . Vấn đề: xây dựng bảng phương án như thế nào . Khi nào thì shift . Khi nào thì reduce . Còn hoạt động nào khác? . Có trạng thái bị tranh chấp? . Hoạt động của stack ra sao? . Ý nghĩa các trạng thái của máy TRƯƠNG XUÂN NAM 5
6. Ví dụ về bộ phân tích gạt-thu TRƯƠNG XUÂN NAM 6
7. Ví dụ về bộ phân tích gạt-thu TRƯƠNG XUÂN NAM 7
8. Ví dụ về bộ phân tích gạt-thu TRƯƠNG XUÂN NAM 8
9. Phần 2 Máy phân tích cú pháp LR TRƯƠNG XUÂN NAM 9
10. Cấu trúc của máy phân tích LR TRƯƠNG XUÂN NAM 10
11. Cấu trúc của máy phân tích LR . Máy phân tích LR là một cặp (STACK, INPUT) . Trạng thái ban đầu (s0, a1a2 an$) . Trạng thái trung gian (s0X1s1 Xmsm, aiai+1 an$) . Trạng thái kết thúc thành công (s0Ss1, $) . Bảng phương án gồm 2 phần . Bảng action: ACTION[s, a] với s là một trạng thái và a là một kí hiệu kết thúc (terminal), giá trị trong bảng chỉ có thể là 1 trong 4 hành động gạt (shift), thu (reduce), nhận (accept), lỗi (error) . Bảng goto: GOTO[s, A] với s là một trạng thái và A là một non-terminal, chỉ ra cách dịch chuyển trạng thái TRƯƠNG XUÂN NAM 11
12. Bảng ACTION 1. Shift s: đẩy kí hiệu input và trạng thái s vào stack (s0X1s1 Xmsm,aiai+1 an$) (s0X1s1 Xmsmais,ai+1 an$) 2. Reduce k: thu gọn bởi luật thứ k (A β), r = | β | . Lấy 2r kí hiệu ra khỏi stack: (s0X1s1 Xmsm,aiai+1 an$) (s0X1s1 Xm-rsm-r,ai+1 an$) . Đẩy vào stack A và s = GOTO[sm-r, A]: (s0X1s1 Xm-rsm-r,aiai+1 an$) (s0X1s1 XmsmAs,ai+1 an$) . Ghi nhận phát sinh luật A β 3. Accept: phân tích thành công 4. Error: phân tích phát hiện lỗi TRƯƠNG XUÂN NAM 12
13. Ví dụ hoạt động của máy LR TRƯƠNG XUÂN NAM 13
14. Ví dụ hoạt động của máy LR TRƯƠNG XUÂN NAM 14
15. Phần 3 Văn phạm họ LR TRƯƠNG XUÂN NAM 15
16. Văn phạm họ LR . Việc chính là làm thế nào để xây dựng bảng phương án? Có nhiều thuật toán làm việc này . LR(0): thuật toán cơ bản, mọi thuật toán LR đều dựa trên nó . SLR (Simple LR): cải tiến một chút từ LR(0), mạnh hơn, dễ cài đặt . LR(1): còn gọi là LR chính tắc ~ Canonical LR, sử dụng cho nhiều loại văn phạm, kích cỡ bảng rất lớn . LALR(1): cân bằng giữa SLR và LR, đủ dùng cho hầu hết các văn phạm nhân tạo TRƯƠNG XUÂN NAM 16
17. Khái niệm cơ sở . Để dễ dàng cho việc thực thi automat, ta bổ sung thêm luật S’ S vào tập luật . Khái niệm LR(0) item: một luật đang được phân tích dở, sử dụng dấu chấm (.) để ngăn giữa phần trước và phần sau (tương tự như thuật toán earley) . Luật S ABC sẽ có 4 item: 1. S .ABC 2. S A.BC 3. S AB.C 4. S ABC. TRƯƠNG XUÂN NAM 17
18. Closure(I) – bao đóng của I TRƯƠNG XUÂN NAM 18
19. GOTO(I, X) – hàm chuyển TRƯƠNG XUÂN NAM 19
20. Xây dựng đồ thị LR(0) . Có cạnh I đến J là X . X là terminal: (I, X) = shift J . X là non-terminal: (I, X) = goto J . Nếu X = $: accept . Nếu state chứa A β. thì điền reduce vào mọi ô trên dòng TRƯƠNG XUÂN NAM 20
21. Ví dụ S’ S $ S ( L ) S x L S L L , S TRƯƠNG XUÂN NAM 21
22. Ví dụ TRƯƠNG XUÂN NAM 22
23. SLR S’ E $ E T + E E T T x TRƯƠNG XUÂN NAM 23
24. SLR . SLR sửa đổi lại cách tính reduce, chỉ sử dụng reduce cho những tình huống X thuộc FOLLOW(A) . Chú ý: có nhiều loại xung đột, phương pháp SLR chỉ sửa được một phần rất nhỏ . Xung đột giữa shift và reduce . Xung đột giữa reduce và reduce TRƯƠNG XUÂN NAM 24
25. Phần 4 Đánh giá về phân tích LR TRƯƠNG XUÂN NAM 25
26. Đánh giá về phân tích LR . Phân tích LR không đủ mạnh cho văn phạm CFG . Nhưng đủ mạnh cho hầu hết ngôn ngữ nhân tạo . LR(0): là hạt nhân . SLR: đơn giản, yếu . LALR(1): tạm đủ dùng . LR(1): bảng quá to . LR(k): quá phức tạp . Nhanh ~ tuyến tính . Rất nhiều biến thể . GLR ~ Earley TRƯƠNG XUÂN NAM 26
27. Phần 5 Bài tập TRƯƠNG XUÂN NAM 27
28. Bài tập 1. Cho văn phạm G: S AS | b A SA | a . Xây dựng bộ các tập item LR(0) cho văn phạm này . Xây dựng bảng phân tích cú pháp bằng thuật toán SLR 2. Cho văn phạm G: E E + T | T T T F | F F F * | a | b . Xây dựng bộ các tập item LR(0) cho văn phạm này . Xây dựng bảng phân tích cú pháp bằng thuật toán SLR TRƯƠNG XUÂN NAM 28