Slide T08: Phân tích văn phạm bằng thuật toán top-down

1 bình luận cho Slide T08: Phân tích văn phạm bằng thuật toán top-down

• 

  11/08/2016 - 07:16

  admin  says:

  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 PTTD { public List<Rule> rules = new List<Rule>(); // bộ luật public List<Step> 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("<bo luat van pham>"); foreach (Rule r in rules) Console.WriteLine("  " + r.ToFineString()); } public void PrintSteps() { Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count); string w = "S"; foreach (Step s in steps) { string w0 = DoStep(w, s); Console.WriteLine("  {0} => {1} (o vi tri {3}, dung luat {2})", w, w0, rules[s.ruleNumber].ToFineString(), s.position + 1); 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; } public bool Process(string x) { steps = new List<Step>(); 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 < s.Length; i++) { if (i >= w.Length) return i; if (s[i] != w[i]) return i; } return -1; } // 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; } } 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.AddRule("E", "a"); parser.AddRule("E", "b"); parser.AddRule("E", "(E+E)"); parser.PrintAllRules(); if (parser.Process("(a=(b+a))")) 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

  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 PTTD {     public List<Rule> rules = new List<Rule>();   // bộ luật     public List<Step> 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("<bo luat van pham>");         foreach (Rule r in rules)             Console.WriteLine("  " + r.ToFineString());     }     public void PrintSteps() {         Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count);         string w = "S";         foreach (Step s in steps) {             string w0 = DoStep(w, s);             Console.WriteLine("  {0} => {1} (o vi tri {3}, dung luat {2})", w, w0, rules[s.ruleNumber].ToFineString(), s.position + 1);             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;     }     public bool Process(string x) {         steps = new List<Step>();         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 < s.Length; i++) {             if (i >= w.Length) return i;             if (s[i] != w[i]) return i;         }         return -1;     }     // 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;     } } 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.AddRule("E", "a");         parser.AddRule("E", "b");         parser.AddRule("E", "(E+E)");         parser.PrintAllRules();         if (parser.Process("(a=(b+a))"))             parser.PrintSteps();     } }

  Trả lời