SLR 文法项目集构造详解：完整代码及优化建议

SLR 文法项目集构造是构建 SLR 解析器的关键步骤。本文将深入讲解 SLR 文法的项目集构造过程，并提供完整代码示例，帮助您深入理解 SLR 解析器的构建原理。

1. SLR 文法的项目集构造原理

SLR 文法的项目集构造与 LR0 文法的项目集构造基本相同，只需要在求闭包时进行一些修改即可。具体来说，SLR 文法需要考虑终结符的 Follow 集，因此在求闭包时需要将终结符的 Follow 集加入到闭包中。

2. 完整代码示例

以下是 SLR 文法的项目集构造代码，其中修改部分已经标注：

public void Buildprod(string str)
{
    LRNode Lr;
    int i = 0;
    string left = '';
    string right = '';
    left += 'S'';
    right += str[0];
    Lr = new LRNode(left, right);//拓广文法开始
    LRproNum.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 LRNode(left, right);
                LRproNum.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 LRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
            LRproNum.Add(Lr);
        }
    }//while
    Echar.Add('#');

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

//求项目集
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);//求闭包，加入终结符的Follow集
                    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  本身
                        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

3. 代码优化建议

为了提升代码可读性和搜索引擎友好度，以下是一些优化建议：

代码注释: 添加详细的代码注释，解释每个部分的功能和逻辑，方便读者理解代码。
变量命名: 使用清晰、易懂的变量名，例如将 lr2_club 改为 nextItemSet， lr_item 改为 currentItemSet。
代码格式: 使用规范的代码格式，例如缩进、空格，提高代码可读性。
函数分离: 将代码拆分成多个函数，提高代码可维护性。
代码重构: 对代码进行重构，使其更简洁、易于理解和维护。

4. 结论

本文详细讲解了 SLR 文法项目集构造过程，并提供了完整代码示例，希望能帮助您理解 SLR 解析器的构建原理。代码优化建议可以帮助您提升代码质量，提高代码的可读性和搜索引擎友好度。