SLR 分析器代码实现 - C# 示例

// SLR 分析器
public class SLR
{
    // 产生式结点类
    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<int> Container = new List<int>(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[][] SLRAna; // 分析表

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

    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('#');

        // 构造项目 对产生式集合 LRproNum 中的所有产生式都循环插 '.'
        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()
    {
        // ...
        return SLRAna;
    }

    // 求项目集
    public void Creteitemsets()
    {
        // ...
    }

    // 构造闭包
    public List<int> Closure(List<int> 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;
    }

    // ... 其他辅助函数 ...
}

详细注释：

• SLRNode 类： 表示一个产生式，包含左部和右部字符串。
• SLRitemsets 类： 表示一个项目集，包含一个列表，记录了该项目集中所有项目的序号。
• DFA 结构： 表示一个 DFA 状态转换，包含从状态、符号和目标状态。
• Table 类： 表示分析表中的一个单元格，包含错误标志、类型和数值。
• Buildprod 函数： 从文法规则字符串构建产生式列表和项目列表。
• GET_ANA 函数： 生成 SLR 分析表。
• Creteitemsets 函数： 构建所有项目集。
• Closure 函数： 构造项目集的闭包。

代码实现的步骤：

1. 构建产生式： 使用 Buildprod 函数从文法规则字符串构建产生式列表，并根据产生式构建项目列表。
2. 构建项目集： 使用 Creteitemsets 函数构建所有项目集，使用 Closure 函数构造每个项目集的闭包。
3. 生成分析表： 使用 GET_ANA 函数根据项目集构建分析表。
4. 分析过程： 使用分析表对输入字符串进行语法分析。

注意：

• 代码中的 // ... 部分需要根据具体情况进行实现。
• 具体实现细节可能需要根据文法规则进行调整。
• 代码仅供参考，可能需要进行进一步优化和完善。