Slide T09: Phân tích văn phạm bằng thuật toán bottom-up

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

• 

  11/08/2016 - 07:17

  admin  says:

  C#

  using System; using System.Collections.Generic; 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; } } 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("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}, thu gon bang luat {3})", w, x, s.position + 1, 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); } // á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) { 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); String b = DoBackStep(w, st); Console.WriteLine("{0} <= {1}", w, b); if (BottomUp(b)) return true; steps.RemoveAt(steps.Count - 1); } Console.WriteLine("<<<"); return false; } } 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(); } }

  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

  using System; using System.Collections.Generic;   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;     } }   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("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}, thu gon bang luat {3})", w, x, s.position + 1, 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);     }     // á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) {         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);                     String b = DoBackStep(w, st);                     Console.WriteLine("{0} <= {1}", w, b);                     if (BottomUp(b)) return true;                     steps.RemoveAt(steps.Count - 1);                 }         Console.WriteLine("<<<");         return false;     } } 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ả lời