CTD Bài 10: Phân tích cú pháp bằng thuật toán bottom-up

1 bình luận cho CTD Bài 10: Phân tích cú pháp bằng thuật toán bottom-up

• 

  14/11/2016 - 17:16

  admin  says:

  Mã đầy đủ hơn của thuật toán bottom-up

  C#

  using System; using System.Collections.Generic; // 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;     } } // 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;     } } class PTBU {     public List<Rule> rules = new List<Rule>();     public List<Step> steps;     string word = null;     public void AddRule(string left, string right) {         rules.Add(new Rule(left, right));     }     public void PrintAllRules() {         Console.WriteLine("<bo luat van pham>");         foreach (Rule r in rules)             Console.WriteLine("  " + r.ToFineString());     }     public void PrintSteps() { Console.WriteLine();         Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count);         string w = word;         foreach (Step s in steps) {             string x = DoBackStep(w, s); Console.WriteLine(" {0} <== {1} (o vi tri {2} ap dung luat {3})", w, x, s.position, rules[s.ruleNumber].ToFineString()); w = x;         }     }     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;     } public bool Process(string x) {     steps = new List<Step>();     word = x;     return BottomUp(x, 0); } // á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); } public bool BottomUp(string w, int deep) { // in ra thong tin thu sai for (int i = 0; i < deep; i++) Console.Write("+--"); Console.WriteLine(w); if ("E" == 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), deep+1)) return true; steps.RemoveAt(steps.Count - 1); } return false; } } class Program {     public static void Main() {         PTBU parser = new PTBU();         parser.AddRule("E", "E&T");         parser.AddRule("E", "T");         parser.AddRule("T", "T|F");         parser.AddRule("T", "F");         parser.AddRule("F", "!F");         parser.AddRule("F", "(E)");         parser.AddRule("F", "d");         parser.AddRule("F", "s");         parser.PrintAllRules(); Console.WriteLine();         if (parser.Process("d&!s")) parser.PrintSteps();     } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

  using System; using System.Collections.Generic;   // 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;     } }   // 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;     } }   class PTBU {     public List<Rule> rules = new List<Rule>();     public List<Step> steps;     string word = null;     public void AddRule(string left, string right) {         rules.Add(new Rule(left, right));     }     public void PrintAllRules() {         Console.WriteLine("<bo luat van pham>");         foreach (Rule r in rules)             Console.WriteLine("  " + r.ToFineString());     }     public void PrintSteps() { Console.WriteLine();         Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count);         string w = word;         foreach (Step s in steps) {             string x = DoBackStep(w, s);             Console.WriteLine("  {0} <== {1} (o vi tri {2} ap dung luat {3})", w, x, s.position, rules[s.ruleNumber].ToFineString()); w = x;         }     }     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;     } public bool Process(string x) {     steps = new List<Step>();     word = x;     return BottomUp(x, 0); } // á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); } public bool BottomUp(string w, int deep) { // in ra thong tin thu sai for (int i = 0; i < deep; i++) Console.Write("+--"); Console.WriteLine(w); if ("E" == 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), deep+1)) return true; steps.RemoveAt(steps.Count - 1); } return false; } }   class Program {     public static void Main() {         PTBU parser = new PTBU();         parser.AddRule("E", "E&T");         parser.AddRule("E", "T");         parser.AddRule("T", "T|F");         parser.AddRule("T", "F");         parser.AddRule("F", "!F");         parser.AddRule("F", "(E)");         parser.AddRule("F", "d");         parser.AddRule("F", "s");         parser.PrintAllRules(); Console.WriteLine();         if (parser.Process("d&!s"))             parser.PrintSteps();     } }

  Trả lời