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 | 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 PTCYK { public List<Rule> rules = new List<Rule>(); string[,] table = null; string w = null; int n = 0; // 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("<bo luat van pham>"); foreach (Rule r in rules) Console.WriteLine(" " + r.ToFineString()); Console.WriteLine(); } void InitData(string x) { w = x; n = x.Length; table = new string[n+1, n+1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) table[i,j] = ""; } void FirstProcess() { for (int i = 1; i <= n; i++) foreach (Rule r in rules) if (r.right.Length == 1) if (w[i-1] == r.right[0]) table[i,1] += r.left; } bool IsIn(char x, string w) { return w.IndexOf(x) != -1; } bool CanGen(int j, int i, Rule r) { for (int k = 1; k <= j-1; k++) if (IsIn(r.right[0], table[i,k])) if (IsIn(r.right[1], table[i+k, j-k])) return true; return false; } void GenTable() { for (int j = 2; j <= n; j++) for (int i = 1; i <= n-j+1; i++) foreach (Rule r in rules) if (r.right.Length == 2) if (!IsIn(r.left, table[i,j])) if (CanGen(j, i, r)) table[i,j] += r.left; } public void Process(string x) { InitData(x); FirstProcess(); GenTable(); } public void PrintResult() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) Console.Write("[{0,5}]", table[j,n+1-i]); Console.WriteLine(); } } } class Program { public static void Main() { PTCYK parser = new PTCYK(); // nạp bộ luật vào bộ phân tích parser.AddRule('S', "AB"); parser.AddRule('S', "XB"); parser.AddRule('T', "AB"); parser.AddRule('T', "XB"); parser.AddRule('X', "AT"); parser.AddRule('A', "a"); parser.AddRule('B', "b"); parser.PrintAllRules(); // phân tích thử parser.Process("aaabbb"); // in ra bảng CYK parser.PrintResult(); } } |
Mã nguồn: thuật toán CYK bằng C#
07/05/2015 mã nguồn Chưa có bình luận
Bình luận mới