Bài giảng Chương trình dịch - Bài 13: Phân tích LR & các bộ tự động sinh parser - Trương Xuân Nam

CHƯƠNG TRÌNH DỊCH
 Bài 13: Phân tích LR & các bộ tự 
 động sinh parser
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. Các bộ tự động sinh parser
6. Bài tập
 TRƯƠNG XUÂN NAM 2
Phần 1
Bộ phân tích kiểu gạt-thu 
(shift-reduce)
 TRƯƠNG XUÂN NAM 3
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
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
Ví dụ về bộ phân tích gạt-thu
 TRƯƠNG XUÂN NAM 6
Ví dụ về bộ phân tích gạt-thu
 TRƯƠNG XUÂN NAM 7
Ví dụ về bộ phân tích gạt-thu
 TRƯƠNG XUÂN NAM 8
Phần 2
Máy phân tích cú pháp LR
 TRƯƠNG XUÂN NAM 9
Cấu trúc của máy phân tích LR
 TRƯƠNG XUÂN NAM 10
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, a1a2an$)
 . Trạng thái trung gian (s0X1s1Xmsm, aiai+1an$)
 . 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 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
Bảng ACTION
1. Shift s: đẩy kí hiệu input và trạng thái s vào stack
 (s0X1s1Xmsm,aiai+1an$) (s0X1s1Xmsmais,ai+1an$)
2. Reduce k: thu gọn bởi luật thứ k (A β), r = | β |
 . Lấy 2r kí hiệu ra khỏi stack: (s0X1s1Xmsm,aiai+1an$) 
 (s0X1s1Xm-rsm-r,ai+1an$)
 . Đẩy vào stack A và s = GOTO[sm-r, A]:
 (s0X1s1Xm-rsm-r,aiai+1an$) 
 (s0X1s1XmsmAs,ai+1an$)
 . 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
Ví dụ hoạt động của máy LR
 TRƯƠNG XUÂN NAM 13
Ví dụ hoạt động của máy LR
 TRƯƠNG XUÂN NAM 14
Phần 3
Văn phạm họ LR
 TRƯƠNG XUÂN NAM 15
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
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
Closure(I) – bao đóng của I
 TRƯƠNG XUÂN NAM 18
GOTO(I, X) – hàm chuyển
 TRƯƠNG XUÂN NAM 19
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
Ví dụ
S’ S $ S ( L ) S x
L S L L , S
 TRƯƠNG XUÂN NAM 21
Ví dụ
 TRƯƠNG XUÂN NAM 22
SLR
S’ E $ E T + E
E T T x
 TRƯƠNG XUÂN NAM 23
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
Phần 4
Đánh giá về phân tích LR
 TRƯƠNG XUÂN NAM 25
Đá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
Phần 5
Các bộ tự động sinh parser
 TRƯƠNG XUÂN NAM 27
Các bộ tự động sinh parser
. Với cách tiếp cận xây dựng automat tất định: cho 
 trước văn phạm G, ta có thể tạo một bảng phân tích 
 riêng của G, bảng phân tích này chỉ cần tạo một lần 
 và cố định đối với văn phạm G
. Các bộ parser generator tự động hóa việc xây dựng 
 các bộ phân tích văn phạm:
 . Người dùng định nghĩa văn phạm G
 . Thiết lập các xử lý cần thực hiện khi hoàn thành câu
 . Phần mềm phân tích G, tự sinh bảng phương án
 . Phần mềm tự sinh mã bộ phân tích, chèn những đoạn xử 
 lý vào các vị trí thích hợp
 TRƯƠNG XUÂN NAM 28
Các bộ tự động sinh parser
. Hầu hết các parser generator sinh bảng LALR(1)
 . Bảng này đủ tốt để xử lý hầu hết các ngôn ngữ nhân tạo
 . Bảng kích thước không quá lớn (với ngôn ngữ C, bảng 
 LR(1) có khoảng 10000 trạng thái, bảng LALR chỉ có 
 khoảng 350 trạng thái)
. Parser generator đầu tiên là META II (1960)
. Nổi tiếng nhất: YACC (1975, mã C)
. Sinh mã Java: SableCC
. Sinh mã C#, giao diện trực quan: GOLD Parser 
 (yêu cầu tìm hiểu phần mềm này như là bài tập)
 TRƯƠNG XUÂN NAM 29
Phần 6
Bài tập
 TRƯƠNG XUÂN NAM 30
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 31