SLR 分析表构造代码详解 - C# 实现

SLR 分析表构造代码详解 - C# 实现

本文将详细介绍使用 C# 代码构造 SLR 分析表的过程，并提供代码示例。

代码结构

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 class Analyze
    {
        public List<string> stack_state = new List<string>(100); // 记录状态栈
        public List<string> stack_symbol = new List<string>(100); // 记录符号栈
        public List<string> Input_str = new List<string>(100); // 记录输入串
        public List<string> Tran_pro = new List<string>(100); // 记录所用产生式
    }

    public DFA[] dfa = new DFA[100];
    public int Pindex = 0; // dfa 数组指针
    public Table[][] SLRAna; // 分析表
    public Analyze Jz;
    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); // 终结符集合

    Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>(); // 非终结符的 Follow 集

    public string RStr = "";
    public string RStr_obitemset = ""; // 输出返回
    public string RStr_DFA = "";
    public string RStr_ANA = "";

    // 分析表
    public void SLRAnaly()
    {
        Table tnode = new Table();

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

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

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

        for (int i = 0; i < Gy_itemset.Count; i++)
        {
            SLRNode gyNode = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]];
            if (gyNode.Right == "$") // 如果是 S'->S 则为 acc
            {
                tnode = new Table('A', 0);
                SLRAna[Gy_itemset[i]][Echar.Count] = tnode;
            }
            else // 否则为 r 状态
            {
                tnode = new Table('r', Find_pro(gyNode));
                for (int j = 0; j < Echar.Count; j++)
                {
                    SLRAna[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);
                SLRAna[dfa[i].from][CID + Echar.Count] = tnode;
            }
            else // 不是归约项目 添加状态 S
            {
                int CID = FindID(Echar, dfa[i].symbol);
                tnode = new Table('S', dfa[i].to);
                SLRAna[dfa[i].from][CID] = tnode;
            }
        }
    }
}

代码解释

1. 类定义： 代码中定义了多个类，用于存储 SLR 分析过程中需要用到的数据结构，包括 SLRNode (产生式结点)、SLRitemsets (项目集)、DFA (DFA 结点)、Table (分析表结点)、Analyze (分析句子信息)。

2. SLRAnaly 方法： 该方法用于构造 SLR 分析表。

   • 初始化分析表： 首先初始化分析表 SLRAna，并将所有项设为 error 状态。
   • 接受状态 (acc): 将项目集 1 的 # 项设置为 acc 状态，表示接受状态。
   • 归约状态 (r): 遍历 Gy_itemset 集合，找到每个归约项目的对应产生式序号，并将对应分析表项设置为 r 状态。
   • 移进状态 (S): 遍历 dfa 数组，根据 DFA 结点的 symbol 和 from、to 值，在分析表中添加相应的移进状态 S。
   • 状态 (N): 遍历 dfa 数组，对于非终结符，在分析表中添加相应的 N 状态。

总结

本文提供了用 C# 代码构造 SLR 分析表的示例代码，并对代码进行了详细的解释。代码示例包含了 SLR 分析表构造过程中的核心步骤，以及关键数据结构的定义。希望本文能够帮助您理解 SLR 分析表构造过程，并将其应用于实际的编译器设计中。

注意： 本文仅提供代码示例，并进行基本的解释，您需要根据实际情况进行修改和完善。