Nhập môn Chương trình dịch - Bài 7

Mỗi trạng thái thể hiện vàđánh dấu các khả năng cóthể xảy ra E số trạng thái LR(0) Mỗi trạng thái LR(0) là một Etập hợp các sản xuất đượcsản xuất được đánh dấuđánh dấu bằng các dấuchấm
Nội dung trích xuất từ tài liệu:
Nhập môn Chương trình dịch - Bài 7Nhập môn Chương trình dịch Học kì II 2006-2007 Bài 7: Phân tích LR Bộ phân tích LR(0) Left-to-right scanning Right-most derivation “zero” lookahead token Chưa đủ mạnh để nhận dạng các ngôn ngữ lập trình Dùng để hiểu các loại phân tích LR Các trạng thái LR(0) Mỗi trạng thái thể hiện và đánh dấu các khả năng có thể xảy ra E  số  trạng thái LR(0) Mỗi trạng thái LR(0) là một E  (S) tập hợp các sản xuất được sản xuất được đánh dấu đánh dấu bằng các dấu chấm Trước dấu  là các kí hiệu đã nằm trên ngăn xếp Sau dấu  là các kí hiệu có thể xuất hiện (các từ tố chưa đọc) Ví dụ: Danh sách (x, (y,z), w) Văn phạm của danh sách S S  (L) | id ( L ) L  S | L, S L , S L , Sw x (x,(y,z), w) S ( L ) (((x))) ((x,(y, z)), w) x L , S z S y Trạng thái LR(0) và bao đóng S  (L) | id S’  S$ bao đóng L  S | L, S S  (L) S’  S$ S  id Thêm sản xuất: S’  S$ Trạng thái ban đầu của ngăn xếp S’  S$ Bao đóng của trạng thái: – Với mỗi sản xuất dạng A  B, thêm vào trạng thái tất cả các sản xuất dạng B   – Ý nghĩa: • A  B: B chưa xuất hiện (hay có thể xuất hiện ở xâu vào) • B  : Chưa kí hiệu nào do B suy dẫn ra xuất hiện (hay  có thể xuất hiện ở xâu vào) Chuyển trạng thái – DFA (1) S  (L) | id S  (L) L  S | L, S L  S S’  S$ ( L  L, S S  (L) S  (L) S  id ( S  id id id S  id Sử dụng các kí hiệu kết thúc và không kết thúc để chuyển trạng thái Trạng thái mới bao gồm các sản xuất và bao đóng của chúng Chuyển trạng thái – DFA (2) S  (L) | id trạng thái kết thúc10 L  S | L, S 8 S’  S$  2 id L  L, S S9 S  id  L  L,S  S  (L) $ id S  id4 ( id S’  S  $ , 3 S  (L) S 5 L )6 S  (L ) S  (L)  L  S1 S’  S$ ( L  L , S L  L, S S S  (L) 7 S  (L) LS S  id ( S  id trạng thái có thể thu gọn 2, 6, 7, 9 Cài đặt DFA qua PDA (1) PDA: push-down automata – ôtômát đẩy xuống Khởi tạo ngăn xếp: push trạng thái 1 (bắt đầu) Tại mỗi thời điểm, ngăn xếp có dạng (s1 x1 s2 x2 … sn-r xn-r … sn-1 xn-1 sn) Trong đó: – si: là trạng thái của DFA – xi: là kí hiệu kết thúc hoặc không kết thúc (kí hiệu trước dấu ) – si+1 = (si, xi) – chuyển từ trạng thái si sang si+1 nhờ kí hiệu vào xi Cài đặt DFA qua PDA (2) (s1 x1 s2 x2 … sn-r xn-r … sn-1 xn-1 sn) Hoạt động: với a là kí hiệu vào – Gạt a, chuyển tới trạng thái s với s =  ...