SLR1 分析器实现

{ 'SLR': { 'SLRNode': { 'Left': 'string', 'Right': 'string', 'constructor': [ 'string', 'string' ] }, 'SLRitemsets': { 'Container': 'List' }, 'DFA': { 'from': 'int', 'symbol': 'char', 'to': 'int', 'constructor': [ 'int', 'char', 'int' ] }, 'Table': { 'error': 'bool', 'type': 'char', 'id': 'int', 'constructor': [] }, 'dfa': 'DFA[]', 'Pindex': 'int', 'LRAna': 'Table[][]', 'Jz': 'Analyze', 'Success': 'bool', 'SLRproNum': 'List', 'SLRobjNum': 'List', 'proitemset': 'List', 'Gy_obj': 'List', 'Gy_itemset': 'List', 'Nchar': 'List', 'Echar': 'List', 'RStr': 'string', 'RStr_obitemset': 'string', 'RStr_DFA': 'string', 'RStr_ANA': 'string', 'Buildprod': [ 'string' ], 'GET_ANA': [], 'Creteitemsets': [], 'Closure': [ 'List' ] } }

// 产生式结点类 public class SLRNode { public string Left; public string Right; public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; } }

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

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

// 分析表 结点 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; } } public DFA[] dfa = new DFA[100]; public int Pindex = 0; // dfa 数组指针 public Table[][] LRAna; // 分析表 public Analyze Jz; public bool Success = false;

public List SLRproNum = new List(50); // 产生式 列表 public List SLRobjNum = new List(50); // 项目 列表 public List proitemset = new List(100); // 项目集合 public List Gy_obj = new List(50); // 归约项目序号集合 public List Gy_itemset = new List(50); // 含有归约项目的集合的序号 的集合 public List Nchar = new List(50); // 非终结符集合 public List Echar = new List(50); // 终结符集合

public string RStr = ''; public string RStr_obitemset = ''; // 输出返回 public string RStr_DFA = ''; public string RStr_ANA = '';

public void Buildprod(string str) { SLRNode Lr; int i = 0; string left = ''; string right = ''; left += 'S'; right += str[0]; Lr = new SLRNode(left, right); // 拓广文法开始 SLRproNum.Add(Lr); while (i < str.Length) { left = right = ''; // 还原 int j = i; while (i < str.Length && str[i] != '\r' && str[i] != '\n') // 换行符 ‘\r\n’ { if (str[i] == ' ') { i++; continue; } if (str[i] == '|') // 遇到 ‘|’ 可构造一条产生式 { Lr = new SLRNode(left, right); SLRproNum.Add(Lr); right = ''; // 产生式左边相同 右边重新积累 i++; // 跳过 ‘|’ continue; } if ((i - j) == 0) { if (!exist(Nchar, str[i])) // 如果非终结符集合中不存在 str[i], 加入 Nchar 产生式左边 只有非终结符 不必判断终结符 Nchar.Add(str[i]); left += str[i++]; } else if (i - j <= 2) i++; else { if (isFinalsymbol(str[i]) && !exist(Nchar, str[i])) // 如果非终结符集合中不存在 str[i], 加入 Nchar isfinalsymbol 非终结符返回 T 终结符返回 F Nchar.Add(str[i]); else if (!isFinalsymbol(str[i]) && !exist(Echar, str[i])) // 产生式右边 需要判断终结符 Echar.Add(str[i]); right += str[i++]; } } // while

i++; // 跳过换行符
if (left != '' && right != '')
{
  Lr = new SLRNode(left, right); // 构造每一行最后一个产生式，不存在 '|' 时就是该行产生式本身
  SLRproNum.Add(Lr);
}

} // while Echar.Add('#');

// 构造项目 对产生式集合 SLRproNum 中的所有产生式都循环插 ‘.’ SLRNode Lobj; for (i = 0; i < SLRproNum.Count; i++) { left = ''; right = ''; for (int j = 0; j <= SLRproNum[i].Right.Length; j++) // j 可以等于 length 项目共 length+1 个 { left = SLRproNum[i].Left; right = CreObj(SLRproNum[i].Right, j); // 在第 j 个位置插入 ‘.’ if (j == SLRproNum[i].Right.Length && SLRobjNum.Count != 1) { // 在产生式最后的位置插入 . 即为归约项目 项目集中 1 号位置为接受项目 Gy_obj.Add(SLRobjNum.Count); // 归约项目在项目集中的序号 不用 +1 本身就是从 0 开始的 } Lobj = new SLRNode(left, right); SLRobjNum.Add(Lobj); left = ''; // 还原 right = ''; } } Creteitemsets(); // 项目集 RStr_obitemset += '\r\n项目集构建：\r\n'; for (int j = 0; j < proitemset.Count; j++) { RStr_obitemset += 'I' + j.ToString() + ':' + '\r\n'; for (i = 0; i < proitemset[j].Container.Count; i++) { RStr_obitemset += SLRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + SLRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n'; } } // return RStr_obitemset; }

public Table[][] GET_ANA() { LRAnaly(); RStr_ANA += '\r\nSLR1 分析表：\r\n '; int i; for (i = 0; i < Echar.Count; i++) { RStr_ANA += Echar[i].ToString() + ' '; } for (i = 0; i < Nchar.Count; i++) { RStr_ANA += Nchar[i].ToString() + ' '; } RStr_ANA += '\r\n'; for (i = 0; i < proitemset.Count; i++) { RStr_ANA += i.ToString() + ' '; for (int j = 0; j < Echar.Count + Nchar.Count; j++) { if (LRAna[i][j].error) { RStr_ANA += ' ' + ' '; } else if (i == 1 && j == Echar.Count - 1) { RStr_ANA += 'AC' + ' '; } else if (LRAna[i][j].type != 'N') { RStr_ANA += LRAna[i][j].type.ToString() + LRAna[i][j].id.ToString() + ' '; } else RStr_ANA += LRAna[i][j].id.ToString() + ' '; } RStr_ANA += '\r\n'; }

return LRAna; }

// 求项目集 public void Creteitemsets() { List lr_item = new List(100); // 记录项目的序号 lr_item.Add(0); lr_item = Closure(lr_item); // 构造初始项目集 求闭包

SLRitemsets LR_C = new SLRitemsets(); LR_C.Container = lr_item; // 集合----项目集序号的集合 proitemset.Add(LR_C); // 集合的集合----存放项目集序号集合 的集合

for (int i = 0; i < proitemset.Count; i++) // 整体集合中 第 i 个项目集 { proitemset[i].Container.Sort(); // 排序由小到大 后面用于判断是否存在的比较 int[] flag = new int[proitemset[i].Container.Count]; for (int fi = 0; fi < proitemset[i].Container.Count; fi++) // 标志位，用来判断该序号是否已经构造 { flag[fi] = 0; }

for (int j = 0; j < proitemset[i].Container.Count; j++) // 第 i 个项目集的第 j 个项目
{
  if (flag[j] == 1) // 如果已经访问过 就不再构造 找下一个项目
    continue;
  int index = proitemset[i].Container[j];
  for (int pi = 0; pi < SLRobjNum[index].Right.Length - 1; pi++) // length-1 是避免匹配到 . 在最后的规约项目
  {
    if (SLRobjNum[index].Right[pi] == '.')
    {
      List<int> lr2_club = new List<int>(100); // 记录项目的序号
      char symbol = SLRobjNum[index].Right[pi + 1]; // 记录 .a 转移状态 a. 的符号 a
      lr2_club.Add((index + 1)); // 如果遇到 .a 形式的项目序号为 index 那么项目 a. 的序号为 index+1
      for (int m1 = j + 1; m1 < proitemset[i].Container.Count; m1++)
      { // 在第 i 个项目集中找到了可以移动的 .：.a  重新遍历第 i 个项目集 j 项目之后的 找到同样可以移动 a 的项目集
        int index2 = proitemset[i].Container[m1];
        for (int m2 = 0; m2 < SLRobjNum[index2].Right.Length - 1; m2++)
        {
          if (SLRobjNum[index2].Right[m2] == '.' && SLRobjNum[index2].Right[m2 + 1] == symbol)
          {
            flag[m1] = 1; // 标记位置为 1 已经访问 之后不再访问
            lr2_club.Add(index2 + 1);
          }
        }
      }
      lr2_club = Closure(lr2_club); // 求闭包
      int value = isexist(lr2_club);
      if (value == -1) // -1 表示不存在相同的
      {
        for (int m3 = 0; m3 < Gy_obj.Count; m3++)
        {
          if (isnexist(lr2_club, Gy_obj[m3]))
          {
            Gy_itemset.Add(proitemset.Count);
          }
        }
        SLRitemsets LR_C2 = new SLRitemsets();
        dfa[Pindex++] = new DFA(i, symbol, proitemset.Count); // count 不用加 1  本身从 0 开始
        LR_C2.Container = lr2_club;
        proitemset.Add(LR_C2);
      }
      else
      {
        dfa[Pindex++] = new DFA(i, symbol, value);
      }
      break;
    }
  }
} // end-forj

} // end-fori }

// 构造闭包 public List Closure(List I) { for (int index = 0; index < I.Count; index++) // 遍历该集合中的所有序号 初始序号就是拓广文法的 0 下面的 ADD 步骤中会扩大他的内容 for (int i = 0; i < SLRobjNum[I[index]].Right.Length - 1; i++) // 遍历第 index 序号项目右侧字符串 找到 .A 结构 { if (SLRobjNum[I[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[I[index]].Right[i + 1])) { for (int j = 0; j < SLRobjNum.Count; j++) // 遍历所有项目，找到以 A 开头的 .a { if (isnexist(I, j)) continue; if (SLRobjNum[j].Left == SLRobjNum[I[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.') I.Add(j); // ADD：在项目集（序号集合）中加入新成员 } } } return I; }

// SLR1 分析表构造函数 private void LRAnaly() { // 初始化分析表 LRAna = new Table[proitemset.Count][]; for (int i = 0; i < proitemset.Count; i++) { LRAna[i] = new Table[Echar.Count + Nchar.Count]; for (int j = 0; j < Echar.Count + Nchar.Count; j++) { LRAna[i][j] = new Table(); } }

// 处理项目集中的归约项目 for (int i = 0; i < Gy_itemset.Count; i++) { int itemsetIndex = Gy_itemset[i]; for (int j = 0; j < Gy_obj.Count; j++) { int objIndex = Gy_obj[j];

  // 找到项目集对应的产生式
  int prodIndex = SLRobjNum[objIndex].Right.IndexOf('.');
  string rightPart = SLRobjNum[objIndex].Right.Substring(0, prodIndex) + SLRobjNum[objIndex].Right.Substring(prodIndex + 1);
  string prod = SLRobjNum[objIndex].Left + '->' + rightPart;
  // 找到对应产生式的索引
  int prodNum = SLRproNum.FindIndex(x => x.Left == SLRobjNum[objIndex].Left && x.Right == rightPart);
  // 填充分析表
  for (int k = 0; k < Echar.Count; k++)
  {
    // 找到该项目对应的终结符
    char terminal = SLRobjNum[objIndex].Right[SLRobjNum[objIndex].Right.Length - 1];
    if (terminal == Echar[k])
    {
      LRAna[itemsetIndex][k] = new Table('R', prodNum + 1); // 'R' 表示规约
    }
  }
}

}

// 处理项目集中的转移项目 for (int i = 0; i < dfa.Length; i++) { if (dfa[i].to != -1) { int from = dfa[i].from; int to = dfa[i].to; int symbolIndex = Echar.FindIndex(x => x == dfa[i].symbol); if (symbolIndex != -1) { LRAna[from][symbolIndex] = new Table('S', to + 1); // 'S' 表示移进 } else { symbolIndex = Nchar.FindIndex(x => x == dfa[i].symbol); LRAna[from][symbolIndex + Echar.Count] = new Table('S', to + 1); } } }

// 填充接受状态 LRAna[1][Echar.Count - 1] = new Table('A', 0); }

// 判断项目集是否已经存在 private int isexist(List lr2_club) { int index = -1; for (int i = 0; i < proitemset.Count; i++) { if (lr2_club.Count != proitemset[i].Container.Count) continue; int j = 0; for (; j < proitemset[i].Container.Count; j++) { if (proitemset[i].Container[j] != lr2_club[j]) break; } if (j == proitemset[i].Container.Count) { index = i; break; } } return index; }

// 判断项目是否已经存在 private bool isnexist(List I, int j) { bool flag = false; foreach (int item in I) { if (item == j) { flag = true; break; } } return flag; }

// 判断是否为终结符 private bool isFinalsymbol(char ch) { bool flag = false; foreach (char item in Nchar) { if (item == ch) { flag = true; break; } } return flag; }

// 判断字符是否存在于集合中 private bool exist(List list, char ch) { bool flag = false; foreach (char item in list) { if (item == ch) { flag = true; break; } } return flag; }

// 在指定位置插入 ‘.’ private string CreObj(string right, int j) { string str = ''; for (int i = 0; i < right.Length; i++) { str += right[i]; if (i == j) { str += '.'; } } return str;