SLR1 分析表构建错误分析及修正

问题出在 SLRAnaly 方法中对归约状态的处理上。在给含有归约项目的集合的状态添加归约状态时，应该是遍历集合中所有项目的左部符号的 follow 集合，而不是只取第一个项目的左部符号的 follow 集合。因此，需要修改 SLRAnaly 方法中的以下部分：

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));
    if (c == '#' )
    {
        int EID = FindID(Echar, '#');
        SLRAna[Gy_itemset[i]][EID] = new Table('r', Find_pro(item));
    }
}

修改为：

List<char> follow = new List<char>();
foreach (int index in proitemset[Gy_itemset[i]].Container)
{
    SLRNode item = SLRobjNum[index];
    follow.AddRange(GetFollow(item.Left[0]));
}
follow = follow.Distinct().ToList();
foreach (char c in follow)
{
    int CID = FindID(Echar, c);
    SLRAna[Gy_itemset[i]][CID] = new Table('r', Find_pro(item));
    if (c == '#')
    {
        int EID = FindID(Echar, '#');
        SLRAna[Gy_itemset[i]][EID] = new Table('r', Find_pro(item));
    }
}

这样就能正确地添加归约状态了。

代码示例:

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++)
            {
                // 修改：遍历集合中所有项目的左部符号的 follow 集合
                List<char> follow = new List<char>();
                foreach (int index in proitemset[Gy_itemset[i]].Container)
                {
                    SLRNode item = SLRobjNum[index];
                    follow.AddRange(GetFollow(item.Left[0]));
                }
                follow = follow.Distinct().ToList();

                foreach (char c in follow)
                {
                    int CID = FindID(Echar, c);
                    SLRAna[Gy_itemset[i]][CID] = new Table('r', Find_pro(item));
                    if (c == '#')
                    {
                        int EID = FindID(Echar, '#');
                        SLRAna[Gy_itemset[i]][EID] = new Table('r', Find_pro(item));
                    }
                }
            }

            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;
        }