SLR(1)分析表构造算法及代码实现

SLR(1)分析表是编译原理中一种重要的语法分析工具，用于判断输入符号串是否符合给定文法。本文将介绍SLR(1)分析表的构造算法，并提供C#代码实现。

1. 数据结构定义c#public class SLRNode{ public string Left; public string Right; public HashSet First; public HashSet Follow; public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; First = new HashSet(); Follow = new HashSet(); }}

//项目集类public class SLRitemsets{ public List Container = new List(100); //记录项目在项目集合中的序号 public HashSet LookAhead = new HashSet(); //记录展望符}

//DFA结点public struct DFA{ public int from; public char symbol; public int to; public HashSet LookAhead; public DFA(int from, char symbol, int to, HashSet LookAhead) { this.from = from; this.symbol = symbol; this.to = to; this.LookAhead = LookAhead; }}

//分析表结点public class Table{ public bool error;//是否为ERROR public char type;//结点类型 public int id;//数值 public Table() { this.error = true; } public Table(char type, int id) { this.type = type; this.id = id; this.error = false; }}

2. 核心函数实现

2.1 构造DFAc#//构造DFApublic void CreateDFA(){ SLRitemsets I0 = new SLRitemsets(); I0.Container.Add(0);//将拓广文法的0号项目加入 I0.LookAhead.Add('#');//将#加入展望符集合 proitemset.Add(I0);//将I0加入项目集合 int index = 0; while (index < proitemset.Count) { SLRitemsets I = proitemset[index]; //对于每个终结符或非终结符，计算它的Go(I,X)集合 for (int i = 0; i < Echar.Count + Nchar.Count; i++) { char symbol; if (i < Echar.Count) symbol = Echar[i]; else symbol = Nchar[i - Echar.Count]; SLRitemsets J = Goto(I, symbol); if (J.Container.Count == 0) continue; int k = IsExist(J); if (k == -1) { proitemset.Add(J); k = proitemset.Count - 1; } dfa[Pindex++] = new DFA(index, symbol, k, J.LookAhead); } index++; } // 打印DFA信息 RStr_DFA += '\r\nSLR1 DFA:\r\n'; for (int i = 0; i < Pindex; i++) { RStr_DFA += dfa[i].from.ToString() + ' ' + dfa[i].symbol.ToString() + ' ' + dfa[i].to.ToString() + ' '; foreach (char c in dfa[i].LookAhead) { RStr_DFA += c.ToString() + ','; } RStr_DFA += '\r\n'; }}

2.2 计算Go(I,X)集合c#//计算Go(I,X)集合public SLRitemsets Goto(SLRitemsets I, char X){ SLRitemsets J = new SLRitemsets(); for (int index = 0; index < I.Container.Count; index++) { int i = I.Container[index]; if (SLRobjNum[i].Right.Contains(X + '.')) { string right = SLRobjNum[i].Right.Replace(X + '.', '.' + X); int j = IsExist(new SLRNode(SLRobjNum[i].Left, right)); if (j == -1) { SLRNode node = new SLRNode(SLRobjNum[i].Left, right); SLRobjNum.Add(node); j = SLRobjNum.Count - 1; } J.Container.Add(j); J.LookAhead.UnionWith(FindLookAhead(I, SLRobjNum[i], X)); } } J.Container = Closure(J.Container); return J;}

2.3 计算展望符集合c#//计算展望符集合public HashSet FindLookAhead(SLRitemsets I, SLRNode node, char X){ HashSet set = new HashSet(); if (node.Right.Last() == '.' && I.Container.Contains(SLRproNum.IndexOf(node))) { set.Add(X); } else { for (int i = node.Right.IndexOf('.') + 1; i < node.Right.Length; i++) { if (isFinalsymbol(node.Right[i])) { set.Add(node.Right[i]); break; } else { HashSet temp = new HashSet(first[node.Right[i]]); if (temp.Contains('e')) { temp.Remove('e'); temp.UnionWith(FindLookAhead(I, node, X)); } set.UnionWith(temp); if (!follow.ContainsKey(node.Right[i])) continue; if (I.LookAhead.Contains(node.Right[i])) { set.UnionWith(follow[node.Right[i]]); } } } } return set;}

2.4 构造SLR(1)分析表c#//构造SLR1分析表public void CreateSLRTable(){ SLRAna = new Table[proitemset.Count][]; for (int i = 0; i < proitemset.Count; i++) { SLRAna[i] = new Table[Echar.Count + Nchar.Count]; for (int j = 0; j < Echar.Count + Nchar.Count; j++) { SLRAna[i][j] = new Table(); } } for (int i = 0; i < Pindex; i++) { int from = dfa[i].from; char symbol = dfa[i].symbol; int to = dfa[i].to; HashSet LookAhead = dfa[i].LookAhead; if (isFinalsymbol(symbol)) { SLRAna[from][Echar.IndexOf(symbol)] = new Table('S', to); } else { SLRAna[from][Nchar.IndexOf(symbol) + Echar.Count] = new Table('G', to); } if (Gy_obj.Contains(to)) { foreach (char c in LookAhead) { if (Echar.Contains(c)) { SLRAna[from][Echar.IndexOf(c)] = new Table('r', Gy_obj.IndexOf(to)); } } } else if (to == 1 && symbol == '#' && LookAhead.Contains('#')) { SLRAna[from][Echar.Count - 1] = new Table('A', 0); } } // 打印SLR(1)分析表 RStr_ANA += '\r\nSLR1分析表:\r\n '; int k; for (k = 0; k < Echar.Count; k++) { RStr_ANA += Echar[k].ToString() + ' '; } for (k = 0; k < Nchar.Count; k++) { RStr_ANA += Nchar[k].ToString() + ' '; } RStr_ANA += '\r\n'; for (k = 0; k < proitemset.Count; k++) { RStr_ANA += k.ToString() + ' '; for (int j = 0; j < Echar.Count + Nchar.Count; j++) { if (SLRAna[k][j].error) { RStr_ANA += ' ' + ' '; } else if (SLRAna[k][j].type != 'N') { RStr_ANA += SLRAna[k][j].type.ToString() + SLRAna[k][j].id.ToString() + ' '; } else RStr_ANA += SLRAna[k][j].id.ToString() + ' '; } RStr_ANA += '\r\n';