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 DFA[] dfa = new DFA[100];
        public int Pindex = 0; //dfa数组指针
        public Table[][] SLRAna;//分析表
        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 SLRAnaly()
        {
            // 初始化分析表
            SLRAna = new Table[proitemset.Count][];
            for (int i = 0; i < proitemset.Count; i++)
            {
                SLRAna[i] = new Table[Echar.Count + Nchar.Count];
                for (int j = 0; j < Echar.Count + Nchar.Count; j++)
                {
                    SLRAna[i][j] = new Table();
                }
            }

            // 构建分析表
            buildtable();

            // 填写移进和归约项
            for (int i = 0; i < proitemset.Count; i++)
            {
                for (int j = 0; j < Echar.Count; j++)
                {
                    string s = table[i][j];
                    if (s.Length > 0)
                    {
                        if (s[0] == 'S')
                        {
                            int nextState = int.Parse(s.Substring(1));
                            SLRAna[i][j].type = 's';
                            SLRAna[i][j].id = nextState;
                        }
                        else if (s[0] == 'r')
                        {
                            int productionNum = int.Parse(s.Substring(1));
                            SLRAna[i][j].type = 'r';
                            SLRAna[i][j].id = productionNum;
                        }
                    }
                }
            }

            // 填写goto项
            for (int i = 0; i < proitemset.Count; i++)
            {
                for (int j = 0; j < Nchar.Count; j++)
                {
                    string s = table[i][j + Echar.Count];
                    if (s.Length > 0)
                    {
                        int nextState = int.Parse(s);
                        SLRAna[i][j + Echar.Count].type = 'g';
                        SLRAna[i][j + Echar.Count].id = nextState;
                    }
                }
            }

            // 填写接受项
            int acceptState = proitemset.Count - 1;
            int acceptSymbolIndex = Echar.IndexOf('#');
            SLRAna[acceptState][acceptSymbolIndex].type = 'a';
        }

        // ... 其他方法 ...

        // 构建 SLR 分析表
        private List<List<string>> table = new List<List<string>>();
        private void buildtable()
        {
            for (int i = 0; i < proitemset.Count; i++)
            {
                //对每个状态经过终结符的情况进行判断
                List<string> strings = new List<string>();
                foreach (var symbol in Echar)
                {
                    int flag = 0;
                    //包含移进项的
                    if (transitions.ContainsKey(i))
                    {
                        foreach (var item in transitions[i])
                        {
                            if (item[0].ToString().Equals(symbol))
                            {
                                strings.Add('S' + item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        foreach (var item in proitemset[i].Container)
                        {
                            // 获取对应项目的索引
                            int index = item;
                            if (SLRobjNum[index].Right.Length == SLRobjNum[index].Right.IndexOf('.') + 1 && !SLRobjNum[index].Left.Equals(SLRproNum[0].Left))
                            {
                                if (follow(SLRobjNum[index].Left).Contains(symbol))
                                {
                                    flag = 1;
                                    int productionIndex = getProductionIndex(SLRobjNum[index]);
                                    strings.Add('r' + productionIndex);
                                    break;
                                }
                            }
                        }
                        if (flag == 0)
                        {
                            if (proitemset[i].Container.First() == 0 && i != 0)
                            {
                                if (symbol.Equals('#')) strings.Add("acc");
                                else strings.Add("");
                            }
                            else strings.Add("");
                        }
                    }
                    //只有归约项的
                    else
                    {
                        if (proitemset[i].Container.First() == 0)
                        {
                            if (symbol.Equals('#')) strings.Add("acc");
                            else strings.Add("");
                        }
                        else
                        {
                            flag = 0;
                            foreach (var item in proitemset[i].Container)
                            {
                                // 获取对应项目的索引
                                int index = item;
                                //如果该终结集在FOLLOW集中则加入分析表
                                if (follow(SLRobjNum[index].Left).Contains(symbol) || symbol.Equals('#'))
                                {
                                    flag = 1;
                                    int productionIndex = getProductionIndex(SLRobjNum[index]);
                                    strings.Add('r' + productionIndex);
                                    break;
                                }
                            }
                            if (flag == 0) strings.Add("");
                        }
                    }
                }
                //对每个状态经过非终结符的情况进行判断
                foreach (var t in Nchar)
                {
                    int flag = 0;
                    if (transitions.ContainsKey(i))
                    {
                        foreach (var item in transitions[i])
                        {
                            if (item[0].ToString().Equals(t))
                            {
                                strings.Add(item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        if (flag == 0) strings.Add("");
                    }
                    else strings.Add("");
                }
                table.Add(strings);
            }
        }

        // ... 其他方法和属性 ...
    }