LR(0)分析器代码解析：从项目集到分析表

本文将详细解析LR(0)分析器的核心代码，并以此为基础，给出完整的SLR分析器代码。

LR(0)分析器代码

以下代码实现了LR(0)分析器的核心功能，包括构建项目集、生成DFA以及构造LR(0)分析表。

class LR
{
    // ... (其他类成员)

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

        LRitemsets LR_C = new LRitemsets();
        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 < LRobjNum[index].Right.Length - 1; pi++)//length-1是避免匹配到.在最后的规约项目
                {
                    if (LRobjNum[index].Right[pi] == '.')
                    {
                        List<int> lr2_club = new List<int>(100);//记录项目的序号
                        char symbol = LRobjNum[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 < LRobjNum[index2].Right.Length - 1; m2++)
                            {
                                if (LRobjNum[index2].Right[m2] == '.' && LRobjNum[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);
                                }
                            }
                            LRitemsets LR_C2 = new LRitemsets();
                            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
    }//end-Cre_club

    //分析表
    public void LRAnaly()
    {
        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
            for (int j = 0; j < Echar.Count; j++)
            {
                LRAna[Gy_itemset[i]][j] = 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;
            }
        }
    }
    // ... (其他类方法)
}

SLR分析器代码

基于上述LR(0)分析器代码，可以实现完整的SLR分析器。SLR分析器与LR(0)分析器的主要区别在于如何处理移进-归约冲突。SLR分析器使用 Follow 集来解决冲突，而LR(0)分析器则无法处理此类冲突。

以下是一个简单的SLR分析器代码示例：

class SLR
{
    // ... (类成员与LR(0)分析器类似)

    //分析表
    public void SLRAnaly()
    {
        // ... (代码与LR(0)分析器类似，除了处理移进-归约冲突的部分)

        for (int i = 0; i < Gy_itemset.Count; i++)
        {
            int proNum = Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]); // 获取产生式序号
            char leftSymbol = LRproNum[proNum].Left; // 获取产生式左部非终结符

            foreach (char symbol in Follow(leftSymbol)) // 遍历非终结符的 Follow 集
            {
                int CID = FindID(Echar, symbol);
                if (LRAna[Gy_itemset[i]][CID].error) // 如果该位置为空，则添加归约状态
                {
                    tnode = new Table('r', proNum);
                    LRAna[Gy_itemset[i]][CID] = tnode;
                }
                else // 否则，存在移进-归约冲突，需要进行处理
                {
                    // ... (处理移进-归约冲突的代码，例如根据优先级或其他规则选择移进或归约)
                }
            }
        }
        // ... (剩余代码与LR(0)分析器类似)
    }

    // ... (其他类方法)
}

总结

本文详细解析了LR(0)分析器的核心代码，并基于此代码给出了完整的SLR分析器代码。通过学习这些代码，读者可以深入理解LR(0)和SLR分析器的原理和实现过程。