SLR1 分析：文法分析与分析表构建错误修正

给定文法：

E->E+T|T
T->T*F|F
F->(E)|d

本文将分析 SLR1 分析表构建过程中的错误，并给出修正后的代码。

错误分析:

在 SLR 分析表的构建中，对于含有归约项目的项目集，只有在 follow 集合中出现的终结符才能被标记为 r 状态，其他终结符应该是没有对应状态的，即应该赋值为 ERROR 属性。原始代码在处理含有归约项目的项目集时，将所有终结符都标记为 r 状态，这与 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);//终结符集合

        public List<char>[] Follow; //每个非终结符的follow集合

        public string RStr = '';
        public string RStr_obitemset = '';//输出返回
        public string RStr_DFA = '';
        public string RStr_ANA = '';
public Table[][] GET_ANA()
        {
            SLRAnaly();
            RStr_ANA += '
SLR0分析表:
    ';
            int i;
            for (i = 0; i < Echar.Count; i++)
            {
                RStr_ANA += Echar[i].ToString() + '     ';
            }
            for (i = 0; i < Nchar.Count; i++)
            {
                RStr_ANA += Nchar[i].ToString() + '     ';
            }
            RStr_ANA += '
';
            for (i = 0; i < proitemset.Count; i++)
            {
                RStr_ANA += i.ToString() + '  ';
                for (int j = 0; j < Echar.Count + Nchar.Count; j++)
                {

                    if (SLRAna[i][j].error)
                    {
                        RStr_ANA += '  ' + '    ';
                    }
                    else if (i == 1 && j == Echar.Count - 1)
                    {
                        RStr_ANA += 'AC' + '    ';
                    }
                    else if (SLRAna[i][j].type != 'N')
                    {
                        RStr_ANA += SLRAna[i][j].type.ToString() + SLRAna[i][j].id.ToString() + '    ';
                    }
                    else
                        RStr_ANA += SLRAna[i][j].id.ToString() + '    ';
                }
                RStr_ANA += '
';
            }

            return SLRAna;

        } 
//分析表
        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 + Nchar.Count];

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

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

            for (int i = 0; i < Gy_itemset.Count; i++)
            {
                SLRNode item = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]];
                char left = item.Left[0];
                List<char> follow = GetFollow(left);
                foreach (char c in follow)
                {
                    int CID = FindID(Echar, c);
                    SLRAna[Gy_itemset[i]][CID] = new Table('r', Find_pro(item));
                }
                foreach (char c in Echar)
                {
                    if (!follow.Contains(c))
                    {
                        int CID = FindID(Echar, c);
                        SLRAna[Gy_itemset[i]][CID] = tnode;
                    }
                }
            }

            for (int i = 0; i < Pindex; i++)
            {
                if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N
                {
                    int CID = FindID(Nchar, dfa[i].symbol);
                    SLRAna[dfa[i].from][CID + Echar.Count] = new Table('N', dfa[i].to);
                }
                else //不是归约项目 添加状态S
                {
                    int CID = FindID(Echar, dfa[i].symbol);
                    SLRAna[dfa[i].from][CID] = new Table('S', dfa[i].to);
                }
            }
        }


        public List<char> GetFollow(char c)
        {
            List<char> follow = new List<char>();
            if (c == 'E')
                follow.Add('#');
            foreach (SLRNode node in SLRproNum)
            {
                int index = node.Right.IndexOf(c);
                if (index != -1 && index < node.Right.Length - 1)
                {
                    char next = node.Right[index + 1];
                    if (isFinalsymbol(next))
                        follow.Add(next);
                    else
                    {
                        List<char> first = GetFirst(next);
                        if (first.Contains('#'))
                        {
                            first.Remove('#');
                            follow.AddRange(first);
                            follow.AddRange(GetFollow(node.Left[0]));
                        }
                        else
                        {
                            follow.AddRange(first);
                        }
                    }
                }
                else if (index != -1 && index == node.Right.Length - 1)
                {
                    follow.AddRange(GetFollow(node.Left[0]));
                }
            }
            follow = follow.Distinct().ToList();
            return follow;
        }


        public List<char> GetFirst(char c)
        {
            List<char> first = new List<char>();
            if (isFinalsymbol(c))
                first.Add(c);
            else
            {
                foreach (SLRNode node in SLRproNum)
                {
                    if (node.Left[0] == c)
                    {
                        if (node.Right[0] == c)
                            continue;
                        else if (isFinalsymbol(node.Right[0]))
                            first.Add(node.Right[0]);
                        else
                        {
                            List<char> subFirst = GetFirst(node.Right[0]);
                            if (subFirst.Contains('#'))
                            {
                                subFirst.Remove('#');
                                first.AddRange(subFirst);
                                first.AddRange(GetFirst(node.Right[1]));
                            }
                            else
                            {
                                first.AddRange(subFirst);
                            }
                        }
                    }
                }
            }
            first = first.Distinct().ToList();
            return first;
        }

改正后的代码在处理含有归约项目的项目集时，只在 follow 集合中出现的终结符才被标记为 r 状态，其他终结符则被赋值为 ERROR 属性，符合 SLR 分析表的构建规则。

通过分析和修正错误，我们获得了正确的 SLR1 分析表，并能更准确地进行语法分析。