|
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 105 106 107 108 |
using System; using System.Collections.Generic; class Rule { public char left; public string right; public Rule(char 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 PTTD { public List rules = new List(); public List steps; string w = null; // thêm luật left --> right vào tập luật public void AddRule(char left, string right) { rules.Add(new Rule(left, right)); } public void PrintAllRules() { Console.WriteLine(""); foreach (Rule r in rules) Console.WriteLine(" " + r.ToFineString()); Console.WriteLine(); } public void PrintSteps2() { string w = "S"; Console.Write("S"); foreach (Step s in steps) { string w0 = DoStep(w, s); Console.Write(" => {0}", w0); w = w0; } Console.WriteLine(); } 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; } // tìm kí hiệu không kết thúc đầu tiên trong s 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; } 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 == s[n]) { Step st = new Step(i, n); steps.Add(st); PrintSteps2(); if (Try(DoStep(s, st))) return true; steps.RemoveAt(steps.Count - 1); PrintSteps2(); } return false; } public bool Process(string x) { steps = new List(); w = x; return Try("S"); } } class Program { public static void Main() { PTTD parser = new PTTD(); parser.AddRule('S', "E"); parser.AddRule('E', "Te"); parser.AddRule('e', "&Te"); parser.AddRule('e', ""); parser.AddRule('T', "Ft"); parser.AddRule('t', "|Ft"); parser.AddRule('t', ""); parser.AddRule('F', "~F"); parser.AddRule('F', "(E)"); parser.AddRule('F', "d"); parser.AddRule('F', "s"); parser.PrintAllRules(); if (parser.Process("d&~s")) Console.WriteLine("\nThuat toan ket thuc thanh cong"); else Console.WriteLine("\nThuat toan ket thuc that bai"); } } |
Mã nguồn: thuật toán phân tích top-down bằng C#
14/04/2015 mã nguồn Chưa có bình luận
Bình luận mới