LR0文法分析器：SLR1分析表构建

{ "title": "LR0文法分析器：SLR1分析表构建", "description": "本文提供了一个LR0文法分析器，并实现了SLR1分析表构建功能。通过计算非终结符的Follow集，实现了SLR1分析表的构建，并输出结果。", "keywords": "LR0文法, SLR1分析表, Follow集, 分析器", "content": "//计算Follow集 public void Follow() { Dictionary<char, HashSet> follow = new Dictionary<char, HashSet>();//非终结符的Follow集 foreach (char c in Nchar) { follow[c] = new HashSet(); } follow[Nchar[0]].Add('#');//将开始符号的Follow集加入#

bool flag = true;
while (flag)
{
    flag = false;
    foreach (LRNode lr in LRproNum)//遍历每个产生式
    {
        string right = lr.Right;
        int len = right.Length;
        for (int i = 0; i < len; i++)
        {
            if (isFinalsymbol(right[i])) continue;//终结符不考虑
            HashSet<char> fset = follow[right[i]];
            if (i == len - 1)//如果是产生式右边的最后一个符号
            {
                HashSet<char> fset2 = follow[lr.Left];
                if (fset2.IsSupersetOf(fset)) continue;//如果已经包含了就不用再添加了
                fset2.UnionWith(fset);
                follow[lr.Left] = fset2;
                flag = true;
            }
            else
            {
                HashSet<char> fset2 = first(right.Substring(i + 1));
                if (fset2.Contains('#'))//如果后继符号可以为空
                {
                    fset2.Remove('#');
                    fset2.UnionWith(follow[lr.Left]);
                }
                if (fset2.IsSubsetOf(fset)) continue;//如果已经包含了就不用再添加了
                fset.UnionWith(fset2);
                follow[right[i]] = fset;
                flag = true;
            }
        }
    }
}

//输出Follow集
RStr += "\r\nFollow集:\r\n";
foreach (char c in Nchar)
{
    RStr += c + ": { ";
    foreach (char f in follow[c])
    {
        RStr += f + " ";
    }
    RStr += "}

\n"; } }

//计算一个字符串的First集 public HashSet first(string str) { HashSet fset = new HashSet(); if (str.Length == 0) return fset; if (isFinalsymbol(str[0])) { fset.Add(str[0]); } else { HashSet fset2 = first(str.Substring(1)); fset.UnionWith(fset2); if (fset2.Contains('#')) { fset.Remove('#'); fset.UnionWith(first(str.Substring(1))); } } return fset; }

//SLR1分析表 public void SLRAnaly() { Follow();//计算Follow集

Table tnode = new Table();

LRAna = new Table[proitemset.Count][];
for (int i = 0; i < proitemset.Count; i++)
    LRAna[i] = new Table[Echar.Count + Nchar.Count];

for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性
    for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态 
        LRAna[i][j] = tnode;

tnode = new Table('A', 0);
LRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目   构建[1][#]:acc的情况 先直接赋值好 dfa里没有

for (int i = 0; i < Gy_itemset.Count; i++)
{
    tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//归约项目 找到原产生式序号 添加状态r
    foreach (char c in follow[Nchar[Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]])]])//从follow集中读取状态r对应非终结符的follow集
    {
        int CID = FindID(Echar, c);
        LRAna[Gy_itemset[i]][CID] = tnode;
    }
}

for (int i = 0; i < Pindex; i++)
{
    if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N
    {
        int CID = FindID(Nchar, dfa[i].symbol);
        tnode = new Table('N', dfa[i].to);
        LRAna[dfa[i].from][CID + Echar.Count] = tnode;
    }
    else //不是归约项目 添加状态S
    {
        int CID = FindID(Echar, dfa[i].symbol);
        tnode = new Table('S', dfa[i].to);
        LRAna[dfa[i].from][CID] = tnode;
    }

}

}

//判断是否为终结符 public bool isFinalsymbol(char c) { if (Nchar.Contains(c)) return false; return true; }

//在数组中查找字符串 public int FindID(List arr, char c) { for (int i = 0; i < arr.Count; i++) { if (arr[i] == c) return i; } return -1; }

//查找产生式的序号 public int Find_pro(LRNode Lr) { for (int i = 0; i < LRproNum.Count; i++) { if (Lr.Left == LRproNum[i].Left && Lr.Right == LRproNum[i].Right) { return i; } } return -1; }

//在项目集中查找项目 public int isnexist(List lr_item, int value) { if (lr_item.Contains(value)) return 0; else return 1; }

//求项目集的闭包 public List Closure(List lr_item) { List lr_club = new List(lr_item); bool flag = true; while (flag) { flag = false; for (int i = 0; i < lr_club.Count; i++) { int index = lr_club[i]; for (int j = 0; j < LRobjNum[index].Right.Length - 1; j++) { if (LRobjNum[index].Right[j] == '.') { char symbol = LRobjNum[index].Right[j + 1]; if (!isFinalsymbol(symbol)) { for (int k = 0; k < LRobjNum.Count; k++) { if (LRobjNum[k].Left == symbol && LRobjNum[k].Right == ".") { if (!lr_club.Contains(k)) { lr_club.Add(k); flag = true; break; } } } } } } } } return lr_club; }

//判断项目集是否已经存在 public int isexist(List lr_item) { for (int i = 0; i < proitemset.Count; i++) { if (proitemset[i].Container.Count == lr_item.Count) { if (proitemset[i].Container.SequenceEqual(lr_item)) { return i; } } } return -1; }

//在产生式右边插入'.', 创建项目 public string CreObj(string right, int j) { string temp = ""; for (int i = 0; i < right.Length; i++) { temp += right[i]; if (i == j) temp += "."; } if (j == right.Length) { temp += "."; } return temp; }