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

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

1. CHƯƠNG TRÌNH DỊCH Bài 8: Phân tích văn phạm bằng thuật toán top-down
2. Nội dung 1. Ý tưởng & thuật toán 2. Ví dụ minh họa 3. Cài đặt top-down đơ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 . Thử nghiệm 4. Đánh giá về top-down 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. Top-down: ý 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 . Tìm suy dẫn từ S thành W. S E + S ( S ) + S ( E + S ) + S ( 1 + S ) + S ( 1 + E + S ) + S ( 1 + 2 + S ) + S ( 1 + 2 + E ) + S ( 1 + 2 + ( S ) ) + S ( 1 + 2 + ( E + S ) ) + S ( 1 + 2 + ( 3 + S ) ) + S ( 1 + 2 + ( 3 + E ) ) + S ( 1 + 2 + ( 3 + 4 ) ) + S ( 1 + 2 + ( 3 + 4 ) ) + E ( 1 + 2 + ( 3 + 4 ) ) + 5 TRƯƠNG XUÂN NAM 4
5. Top-down: ý tưởng . Xét quá trình suy dẫn S W1 W2 W . Wi luôn chứa ít nhất một non-terminal . Xét X là non-terminal trái nhất của Wi: . W không chứa non-terminal nên X sẽ phải “biến mất” . Cách làm “biến mất” X chỉ có thể do sử dụng luật văn phạm mà vế trái là X . Nhận xét: trước sau gì X cũng sẽ “biến mất” bởi một luật văn phạm có dạng X → α . Top-down sử dụng năng lực tính toán của máy tính để tìm ra luật đó bằng phương pháp thử-sai-quay-lui TRƯƠNG XUÂN NAM 5
6. Top-down: ý tưởng . Dò tìm quá trình suy dẫn S W1 W: . Với Wi, tìm non-terminal X . Tìm mọi luật X → α, áp dụng luật đó biến đổi Wi thành Wi+1 . Dừng nếu Wi+1 = W (tìm được phương án suy dẫn) . Thử tiếp với Wi+1 hoặc quay lui nếu không phù hợp . Đặc điểm của Top-down: . Nếu Wi có chứa nhiều non-terminal thì chỉ cần thử với non-terminal trái nhất . Trong số nhiều suy dẫn dạng S * W, thuật toán sẽ tìm suy dẫn trái TRƯƠNG XUÂN NAM 6
7. Top-down: thuật toán 1. A = S 2. Với một chuỗi A đạt được trong quá trình suy dẫn: . Nếu A = W: • Kết luận: quá trình tìm kiếm thành công • Lưu lại quá trình biến đổi từ đầu để được A • Kết thúc ngay lập tức quá trình tìm kiếm . Nếu A ≠ W: tìm kí hiệu trung gian trái nhất X . Không tìm được X thì dừng, trở lại hàm gọi . Duyệt tất cả các luật sinh dạng X → α • Áp dụng luật đó trên A (ở vị trí X), ta được A’ • Thử bước 2 với chuỗi A = A’ TRƯƠNG XUÂN NAM 7
8. Phần 2 Ví dụ minh họa TRƯƠNG XUÂN NAM 8
9. Top-down: ví dụ Phân tích W = aacbc với tập luật S → aSbS | aS | c 1. Xét A = aSbS 2. Tìm được kí hiệu S thứ 2 trong A là non-terminal 3. Thử áp dụng luật S → aSbS được A’ = aaSbSbS TRƯƠNG XUÂN NAM 9
10. Top-down: ví dụ 1. Xét A = aaSbSbS 2. Tìm được kí hiệu S thứ 3 trong A là non-terminal 1. Thử áp dụng luật S → aSbS được A’ = aaaSbSbSbS 2. Thử áp dụng luật S → aS được A’ = aaaSbSbS 3. Thử áp dụng luật S → c được A’ = aacbSbS TRƯƠNG XUÂN NAM 10
11. Top-down: ví dụ . Quá trình thử sai kết luận rằng A = aSbS không thể áp dụng luật S → aSbS . Quay lui về đến tình huống ban đầu ở hình (a) . Thử phương án tiếp theo S → aS, được A’ = aaSbS TRƯƠNG XUÂN NAM 11
12. Top-down: ví dụ . Quá trình thử sai tiếp tục và cuối cùng dừng ở phương án được thể hiện ở hình (g) . Khi nhận được chuỗi A = W = aacbc, ngay lập tức thuật toán dừng và trả về quá trình áp dụng luật TRƯƠNG XUÂN NAM 12
13. Phần 3 Cài đặt top-down đơn giản TRƯƠNG XUÂN NAM 13
14. Cấu trúc một luật văn phạm // Lớp chứa luật văn phạm, dạng left -> right class Rule { public string left, right; public Rule(string l, string r) { left = l; right = r; } // chuyển đổi luật về dạng string (để in cho dễ nhìn) public string ToFineString() { string s = left + " >"; for (int i = 0; i < right.Length; i++) s += " " + right[i]; return s; } } TRƯƠNG XUÂN NAM 14
15. Cấu trúc một suy diễn trực tiếp // Lớp chứa một bước áp dụng luật suy diễn // + ruleNumber: số thứ tự của luật sẽ được dùng // + position: vị trí sẽ áp dụng luật đó class Step { public int ruleNumber, position; public Step(int r, int p) { ruleNumber = r; position = p; } } TRƯƠNG XUÂN NAM 15
16. Máy phân tích: các hàm hỗ trợ class PTTD { public List rules = new List (); // bộ luật public List steps; // các bước suy diễn string w = null; // chuỗi W đích // thêm luật left > right vào tập luật 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 16
17. Máy phân tích: các hàm hỗ trợ public void PrintSteps() { Console.WriteLine("Doan nhan thanh cong sau string w = "S"; foreach (Step s in steps) { string w0 = DoStep(w, s); Console.WriteLine(" {0} => {1} (vi tri w = w0; } } string DoStep(string w, Step s) { string w1 = w.Substring(0, s.position); string w2 = w.Substring(s.position + 1); return w1 + rules[s.ruleNumber].right + w2; } TRƯƠNG XUÂN NAM 17
18. Máy phân tích: các hàm chính public bool Process(string x) { steps = new List (); w = x; return Try("S"); } // tìm vị trí non-terminal trái nhất trong s // trả về -1 nếu không tìm được public int FindNonterminal(string s) { for (int i = 0; i = w.Length) return i; if (s[i] != w[i]) return i; } return -1; } TRƯƠNG XUÂN NAM 18
19. Máy phân tích: các hàm chính // hàm thử-sai-quay-lui với chuỗi s public bool Try(string s) { if (s == w) return true; int n = FindNonterminal(s); if (n != -1) for (int i = 0; i < rules.Count; i++) if (rules[i].left[0] == s[n]) { Step st = new Step(i, n); steps.Add(st); if (Try(DoStep(s, st))) return true; steps.RemoveAt(steps.Count - 1); } return false; } TRƯƠNG XUÂN NAM 19
20. Thử nghiệm class Program { public static void Main() { PTTD parser = new PTTD(); // nạp thử bộ luật parser.AddRule("S", "B"); parser.AddRule("B", "R"); parser.AddRule("B", "(B)"); parser.AddRule("R", "E=E"); parser.PrintAllRules(); if (parser.Process("(a=(b+a))")) parser.PrintSteps(); } } TRƯƠNG XUÂN NAM 20
21. Phần 4 Đánh giá về top-down TRƯƠNG XUÂN NAM 21
22. Đánh giá về top-down . Thuật toán đơn giản, sử dụng sức mạnh của máy tính để tìm kiếm lời giải . Thuật toán dạng thử-sai-quay-lui, không cắt nhánh, độ phức tạp tính toán là hàm mũ (~ chậm) . Thuật toán không vạn năng, không làm việc được với các văn phạm có đệ quy trái . Lý do: vì không có cắt nhánh phù hợp, dẫn đến việc đi mãi theo chiều sâu mà không quay lui Câu hỏi: có thể sửa đổi thuật toán như thế nào để làm việc được với văn phạm có đệ quy trái? TRƯƠNG XUÂN NAM 22
23. Cải tiến top-down thế nào? . Tăng tính vạn năng của thuật toán: . Xử lý tình huống đệ quy trái bằng ràng buộc phù hợp . Biến đổi văn phạm trước khi bắt đầu thử-sai-quay-lui . Tăng tốc độ tính toán: . Tập trung vào việc cài đặt cắt nhánh (nhiều ý tưởng) • Cắt nhánh khi trong A có terminal không có trong w • Cắt nhánh khi số terminal trong A nhiều hơn trong w . Tính trước các bước không có “cơ hội về đích” để loại bỏ bớt những tình huống thử-sai không cần thiết . Sử dụng lại những kết quả đã duyệt cũ TRƯƠNG XUÂN NAM 23
24. Phần 5 Bài tập TRƯƠNG XUÂN NAM 24
25. Bài tập 1. Chỉ ra quá trình thực hiện phân tích top-down của chuỗi raid thuộc văn phạm G có tập luật: . S → r X d | r Z d . X → o a | e a . Z → a i 2. Chỉ ra quá trình thực hiện phân tích top-down của chuỗi (a=(b+a)) thuộc văn phạm G có tập luật: . S → B . B → R | ( B ) . R → E = E . E → a | b | ( E + E ) TRƯƠNG XUÂN NAM 25
26. Bài tập 3. Có thể áp dụng thuật toán phân tích top-down cho chuỗi (5+7)*3 thuộc văn phạm G dưới đây hay không? Chỉ ra quá trình thực hiện nếu có thể . E → E + T | T . T → T * F | F . F → ( E ) | số 4. Tương tự câu trên, chỉ ra quá trình phân tích top-down 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 26
27. Bài tập 5. Chỉ ra quá trình thực hiện phân tích top-down 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. Chỉ ra quá trình thực hiện phân tích top-down của chuỗi aaab thuộc văn phạm G có tập luật: . S → A B . A → a A |  . B → b | b B TRƯƠNG XUÂN NAM 27