SLR(1) 分析表构建：高效实现方法及代码解析

public void SLRAnaly() { // 构造终结符集合、非终结符集合 List terminals = new List(); List nonterminal = new List(); foreach (var item in Echar) { terminals.Add(item); } terminals.Remove('#'); foreach (var item in Nchar) { nonterminal.Add(item); } nonterminal.Remove('S');

// 构造FIRST、FOLLOW集合
FIRST first = new FIRST(SLRproNum, Nchar, Echar);
first.buildFIRST();
FOLLOW follow = new FOLLOW(SLRproNum, first.getfirsts(), Nchar, Echar);
follow.buildFOLLOW();

// 构造LR(0)自动机
LR_0 lr_0 = new LR_0(SLRobjNum, proitemset, Nchar, Echar);
lr_0.buildLR_0();

// 构造SLR(1)自动机
SLR_1 slr_1 = new SLR_1(lr_0, Nchar, Echar);
slr_1.buildSLR_1();

// 构造分析表
Dictionary<int, List<string>> table = new Dictionary<int, List<string>>();
SLRTable slrtable = new SLRTable(table, SLRproNum, slr_1, terminals, nonterminal, follow);
slrtable.buildtable();
SLRAna = new Table[table.Count][];
for (int i = 0; i < table.Count; i++)
{
    SLRAna[i] = new Table[terminals.Count + nonterminal.Count];
    for (int j = 0; j < terminals.Count + nonterminal.Count; j++)
    {
        if (j < terminals.Count)
        {
            string str = table[i][j];
            if (str == "")
            {
                SLRAna[i][j] = new Table();
            }
            else if (str[0] == 'S')
            {
                SLRAna[i][j] = new Table('S', int.Parse(str.Substring(1)));
            }
            else if (str[0] == 'r')
            {
                SLRAna[i][j] = new Table('r', int.Parse(str.Substring(1)));
            }
            else if (str == "acc")
            {
                SLRAna[i][j] = new Table('a', 0);
            }
        }
        else
        {
            string str = table[i][j - terminals.Count];
            if (str == "")
            {
                SLRAna[i][j] = new Table();
            }
            else
            {
                SLRAna[i][j] = new Table('G', int.Parse(str.Substring(1)));
            }
        }
    }
}

}

public void buildtable() { for (int i = 0; i < states.Count; i++) { // 对每个状态经过终结符的情况进行判断 List strings = new List(); foreach (var symbol in terminals) { flag = 0; // 包含移进项的 if (transitions.ContainsKey(i)) { foreach (var item in transitions[i]) { if (item[0].ToString().Equals(symbol)) { strings.Add('S' + item.Substring(1)); flag = 1; break; } } foreach (var item in states[i].items) { if (item.dotIndex == item.RHS.Count && !item.LHS.Equals(production.Keys.First() + ''')) { if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol)) { flag = 1; int index = getproconut(item); strings.Add("r" + index); break; } } } if (flag == 0) { if (states[i].items.First().LHS.Equals(production.Keys.First() + ''') && i != 0) { if (symbol.Equals("#")) strings.Add("acc"); else strings.Add(""); } else strings.Add(""); } } // 只有归约项的 else { if (states[i].items.First().LHS.Equals(production.Keys.First() + ''')) { if (symbol.Equals("#")) strings.Add("acc"); else strings.Add(""); } else { flag = 0; foreach (var item in states[i].items) { // 如果该终结集在FOLLOW集中则加入分析表 if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol) || symbol.Equals('#')) { flag = 1; int index = getproconut(item); strings.Add("r" + index); break; } } if (flag == 0) strings.Add(""); } } } // 对每个状态经过非终结符的情况进行判断 foreach (var t in nonterminal) { flag = 0; if (transitions.ContainsKey(i)) { foreach (var item in transitions[i]) { if (item[0].ToString().Equals(t)) { strings.Add(item.Substring(1)); flag = 1; break; } } if (flag == 0) strings.Add(""); } else strings.Add(""); } table.Add(i, strings); } }