SLR(1)分析表的构建算法及C#实现

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()
        {
            //构建分析表
            List<List<string>> table = new List<List<string>>();
            List<int> states = Enumerable.Range(0, proitemset.Count).ToList();
            Dictionary<int, List<string>> transitions = new Dictionary<int, List<string>>();
            for (int i = 0; i < Pindex; i++)
            {
                if (!transitions.ContainsKey(dfa[i].from))
                {
                    transitions.Add(dfa[i].from, new List<string>());
                }
                transitions[dfa[i].from].Add(dfa[i].symbol.ToString() + dfa[i].to.ToString());
            }

            for (int i = 0; i < states.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.ToString()))
                            {
                                strings.Add('S' + item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        foreach (var itemId in proitemset[i].Container)
                        {
                            var item = SLRobjNum[itemId];
                            if (item.Right.Length > 1 && item.Right[item.Right.Length - 1] == '.' && !item.Left.Equals("S'"))
                            {
                                int index = Gy_obj.IndexOf(itemId);
                                if (index != -1)
                                {
                                    foreach (var follow in followSets[item.Left])
                                    {
                                        if (follow == symbol)
                                        {
                                            flag = 1;
                                            strings.Add('r' + (index + 1).ToString());
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                        if (flag == 0)
                        {
                            if (SLRobjNum[proitemset[i].Container.First()].Left.Equals("S'") && i != 0)
                            {
                                if (symbol.Equals('#')) strings.Add("acc");
                                else strings.Add("");
                            }
                            else strings.Add("");
                        }
                    }
                    //只有归约项的
                    else
                    {
                        if (SLRobjNum[proitemset[i].Container.First()].Left.Equals("S'"))
                        {
                            if (symbol.Equals('#')) strings.Add("acc");
                            else strings.Add("");
                        }
                        else
                        {
                            flag = 0;
                            foreach (var itemId in proitemset[i].Container)
                            {
                                var item = SLRobjNum[itemId];
                                //如果该终结集在FOLLOW集中则加入分析表
                                if (followSets[item.Left].Contains(symbol) || symbol.Equals('#'))
                                {
                                    flag = 1;
                                    int index = Gy_obj.IndexOf(itemId);
                                    strings.Add('r' + (index + 1).ToString());
                                    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.ToString()))
                            {
                                strings.Add(item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        if (flag == 0) strings.Add("");
                    }
                    else strings.Add("");
                }
                table.Add(strings);
            }

            //初始化分析表
            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();
                }
            }
            //填写分析表
            for (int i = 0; i < table.Count; i++)
            {
                for (int j = 0; j < Echar.Count; j++)
                {
                    if (table[i][j] == "")
                    {
                        continue;
                    }
                    else if (table[i][j][0] == 'S')
                    {
                        int to = int.Parse(table[i][j].Substring(1));
                        SLRAna[i][getIndex(Echar[j])] = new Table('S', to);
                    }
                    else if (table[i][j][0] == 'r')
                    {
                        int to = int.Parse(table[i][j].Substring(1));
                        SLRAna[i][getIndex(Echar[j])] = new Table('r', to);
                    }
                    else if (table[i][j] == "acc")
                    {
                        SLRAna[i][getIndex(Echar[j])] = new Table('a', 0);
                    }
                }
                for (int j = Echar.Count; j < Echar.Count + Nchar.Count; j++)
                {
                    if (table[i][j] == "")
                    {
                        continue;
                    }
                    else
                    {
                        int to = int.Parse(table[i][j]);
                        SLRAna[i][getIndex(Nchar[j - Echar.Count])] = new Table('G', to);
                    }
                }
            }
        }

        //获取终结符或非终结符在Echar或Nchar中的下标
        public int getIndex(char c)
        {
            if (isFinalsymbol(c))
            {
                return Echar.IndexOf(c);
            }
            else
            {
                return Nchar.IndexOf(c);
            }
        }

        // ... (其他方法和属性代码)
    }