Chương trình dịch - Bài 9: Phân tích văn phạm bằng thuật toán bottom - Up

Nội dung text: Chương trình dịch - Bài 9: Phân tích văn phạm bằng thuật toán bottom - Up

1. CHƯƠNG TRÌNH DỊCH Bài 9: Phân tích văn phạm bằng thuật toán bottom-up
2. Nội dung 1. Ý tưởng & thuật toán 2. Ví dụ minh họa 3. Cài đặt bottom-up đơn giản . Cấu trúc một luật văn phạm . Cấu trúc một suy diễn trực tiếp . Máy phân tích: các hàm hỗ trợ . Máy phân tích: các hàm chính 4. Đánh giá về bottom-up 5. Bài tập TRƯƠNG XUÂN NAM 2
3. Phần 1 Ý tưởng & thuật toán TRƯƠNG XUÂN NAM 3
4. Bottom-up: ý tưởng . Cho văn phạm G với các luật sinh: S → E + S | E E → 1 | 2 | 3 | 4 | 5 | ( S ) . Xâu vào: W = (1 + 2 + (3 + 4)) + 5 . Thu gọn W thành S: ( 1 + 2 + ( 3 + 4 ) ) + 5  ( E + 2 + ( 3 + 4 ) ) + 5  ( E + E + ( 3 + 4 ) ) + 5  ( E + E + ( E + 4 ) ) + 5  ( E + E + ( E + E ) ) + 5  ( E + E + ( E + S ) ) + 5  ( E + E + ( S ) ) + 5  ( E + E + E ) + 5  ( E + E + S ) + 5  ( E + S ) + 5  ( S ) + 5  E + 5  E + E  E + S  S TRƯƠNG XUÂN NAM 4
5. Bottom-up: mục tiêu & ý tưởng . Mục tiêu: trong số nhiều suy dẫn dạng S * w, thuật toán sẽ tìm suy dẫn phải . Ý tưởng chính: . Thử sai và quay lui bằng năng lực tính toán của máy tính . Dò ngược quá trình suy dẫn w  wn-1   w1  S bằng kĩ thuật thu-gọn: tìm xem wi có chứa vế phải của luật hay không, nếu có thì thay thế phần vế phải đó bằng vế trái tương ứng . Nếu một wi S thì chắc chắn nó cần phải được thu-gọn, nếu wi không chứa vế phải của luật nào đó thì nhánh thử sai này cần quay lui, ngược lại thì thu-gọn và thử tiếp TRƯƠNG XUÂN NAM 5
6. Bottom-up: thuật toán 1. A = w 2. Với chuỗi A đạt được trong quá trình lần ngược: . Nếu A = “S”: • Kết luận: quá trình tìm kiếm thành công • Lưu lại kết quả (chuỗi biến đổi từ đầu để được A) • Kết thúc ngay lập tức quá trình tìm kiếm . * Duyệt tất cả các luật sinh dạng x → α, nếu α là một chuỗi con trong A thì: • Áp dụng thu-gọn: thế α trong A bằng x, ta được A’ • Thử bước 2 với chuỗi A = A’ . Nếu không có phương án thu gọn nào thì quay lui TRƯƠNG XUÂN NAM 6
7. Phần 2 Ví dụ minh họa TRƯƠNG XUÂN NAM 7
8. Bottom-up: ví dụ Cho tập luật S → AB, A → ab, B → aba Chỉ ra quá trình thu gọn chuỗi w = ababa . . Áp dụng luật A → ab, thu gọn ababa  Aaba . Chuỗi Aaba có 2 phương án thu gọn: Aaba  AAa và Aaba  AB TRƯƠNG XUÂN NAM 8
9. Bottom-up: ví dụ . Áp dụng luật A → ab, thu gọn Aaba  AAa . Đến đây nhánh này ngưng vì không thu gọn tiếp được nữa . Áp dụng luật B → aba, thu gọn Aaba  AB TRƯƠNG XUÂN NAM 9
10. Bottom-up: ví dụ . Áp dụng luật S → AB, thu gọn AB  S . Đến đây điều kiện A = “S” xảy ra: . Thuật toán dừng, kết luận thu gọn thành công . Lưu lại quá trình suy dẫn ngược TRƯƠNG XUÂN NAM 10
11. Phần 3 Cài đặt bottom-up đơn giản TRƯƠNG XUÂN NAM 11
12. Cấu trúc một luật văn phạm class Rule { public string left, right; public Rule(string l, string r) { left = l; right = r; } public string ToFineString() { string s = left + " >"; for (int i = 0; i < right.Length; i++) s += " " + right[i]; return s; } } TRƯƠNG XUÂN NAM 12
13. Cấu trúc một suy diễn trực tiếp class Step { public int ruleNumber, position; public Step(int r, int p) { ruleNumber = r; position = p; } } Giải thích: . Biến ruleNumber lưu số thứ tự của luật sẽ được dùng . Biến position lưu vị trí sẽ áp dụng luật đó TRƯƠNG XUÂN NAM 13
14. Máy phân tích: các hàm hỗ trợ class PTBU { public List rules = new List (); public List steps; string word = null; public void AddRule(string left, string right) { rules.Add(new Rule(left, right)); } public void PrintAllRules() { Console.WriteLine(" "); foreach (Rule r in rules) Console.WriteLine(" " + r.ToFineString()); } TRƯƠNG XUÂN NAM 14
15. Máy phân tích: các hàm hỗ trợ public void PrintSteps() { Console.WriteLine("Doan nhan thanh cong sau string w = word; foreach (Step s in steps) { string x = DoBackStep(w, s); } } string DoBackStep(string w, Step s) { string w1 = w.Substring(0, s.position); string w2 = w.Substring(s.position + rules[s.ruleNumber].right.Length); return w1 + rules[s.ruleNumber].left + w2; } TRƯƠNG XUÂN NAM 15
16. Máy phân tích: các hàm chính public bool Process(string x) { steps = new List (); word = x; return BottomUp(x); } // áp dụng được luật k ở vị trí i của chuỗi w? bool CanApplyHere(string w, int i, int k) { string s = w.Substring(i); if (s.Length > rules[k].right.Length) s = s.Substring(0, rules[k].right.Length); return (s == rules[k].right); } TRƯƠNG XUÂN NAM 16
17. Máy phân tích: các hàm chính public bool BottomUp(string w) { if ("S" == w) return true; for (int i = 0; i < w.Length; i++) for (int k = 0; k < rules.Count; k++) if (CanApplyHere(w, i, k)) { Step st = new Step(k, i); steps.Add(st); if (BottomUp(DoBackStep(w, st))) return true; steps.RemoveAt(steps.Count - 1); } return false; } TRƯƠNG XUÂN NAM 17
18. Thử nghiệm class Program { public static void Main() { PTBU parser = new PTBU(); parser.AddRule("S", "AB"); parser.AddRule("A", "ab"); parser.AddRule("B", "aba"); parser.PrintAllRules(); if (parser.Process("ababa")) parser.PrintSteps(); } } TRƯƠNG XUÂN NAM 18
19. Phần 4 Đánh giá về bottom-up TRƯƠNG XUÂN NAM 19
20. Đánh giá về bottom-up . Đặc trưng: . Dễ hiểu: cài đặt đơn giản . Chậm: duyệt toàn bộ, không có các bước cắt nhánh . Không vạn năng: không làm việc với văn phạm có suy dẫn rỗng (A → ) hoặc đệ quy (A + A) . Không dễ loại bỏ những kết quả trùng lặp (trường hợp muốn tìm mọi phương án suy dẫn) . Ý tưởng cải tiến: . * Quy hoạch động: sử dụng lại những kết quả duyệt cũ . * Cắt nhánh sớm: dựa trên đặc trưng của một số luật để loại bỏ các phương án không có tương lai TRƯƠNG XUÂN NAM 20
21. Phần 5 Bài tập TRƯƠNG XUÂN NAM 21
22. Bài tập 1. Chỉ ra quá trình thu gọn theo phân tích bottom-up của chuỗi raid thuộc văn phạm G sau: . S → r X d | r Z d . X → o a | e a . Z → a i 2. Chỉ ra quá trình thu gọn theo phân tích bottom-up của chuỗi (a=(b+a)) thuộc văn phạm G sau: . S → B . B → R | ( B ) . R → E = E . E → a | b | ( E + E ) TRƯƠNG XUÂN NAM 22
23. Bài tập 3. Chỉ ra quá trình thu gọn theo phân tích bottom-up cho chuỗi (5+7)*3 thuộc văn phạm G sau: . E → E + T | T . T → T * F | F . F → ( E ) | số 4. Chỉ ra quá trình thu gọn theo phân tích bottom-up của chuỗi true and not false với tập luật: . E → E and T | T . T → T or F | F . F → not F | ( E ) | true | false TRƯƠNG XUÂN NAM 23
24. Bài tập 5. Chỉ ra quá trình thu gọn theo phân tích bottom-up của chuỗi abbcbd thuộc văn phạm G có tập luật: . S → a A | b A . A → c A | b A | d 6. Có thể thực hiện phân tích bottom-up chuỗi aaab thuộc văn phạm G dưới đây hay không? Chỉ ra phương án xử lý nếu có. . S → A B . A → a A |  . B → b | b B TRƯƠNG XUÂN NAM 24
25. Bài tập (lập trình) 1. Hãy chỉnh sửa thuật toán top-down và bottom-up để chúng có thể chỉ ra mọi phương án suy dẫn từ kí hiệu bắt đầu S thành chuỗi đích w 2. * Mã nguồn minh họa cả hai thuật toán top-down và bottom-up đều dựa trên đệ quy, hãy chuyển đổi chúng thành dạng không đệ quy (gợi ý: sử dụng một stack lưu lại trạng thái của các chuỗi trung gian trong quá trình thử-sai các luật sinh) 3. Hãy xây dựng thuật toán chuyển đổi từ suy dẫn trả về bởi thuật toán top-down (bottom-up) thành cây phân tích cú pháp tương ứng TRƯƠNG XUÂN NAM 25
26. Bài tập (lập trình) 4. * Hãy điều chỉnh thuât toán top-down (bottom-up) để chúng trả về mọi cây phân tích cú pháp khác nhau (dùng cho văn phạm có nhập nhằng) 5. Nếu văn phạm G đệ quy phải, thì thuật toán top-down hay bottom-up sẽ trả về kết quả nhanh hơn trong các tính huống: . Chuỗi w không thuộc văn phạm G . Chuỗi w có nhiều cây phân tích cú pháp TRƯƠNG XUÂN NAM 26