• 日期: 2027-02-18
  • 标签: 常规

该函数的作用是构建 SLR 分析表，具体原理如下：

  1. 对于每个状态 i，遍历所有终结符 symbol，判断该状态经过终结符 symbol 的情况。

  2. 如果该状态存在移进项，遍历该状态的移进项，如果移进项的第一个符号与当前终结符相同，则在分析表中添加一个 'S' 加上移进项的编号。

  3. 遍历该状态的所有归约项，如果归约项的点号已经到达右侧，则判断该归约项的左侧非终结符的 FOLLOW 集是否包含当前终结符 symbol，如果包含，则在分析表中添加一个 'r' 加上该归约项的编号。

  4. 如果该状态既不存在移进项，也不存在归约项，则在分析表中添加一个空字符串。

  5. 对于每个状态 i，遍历所有非终结符 t，判断该状态经过非终结符 t 的情况。

  6. 如果该状态存在移进项，遍历该状态的移进项，如果移进项的第一个符号与当前非终结符相同，则在分析表中添加移进项的编号。

  7. 如果该状态不存在移进项，则在分析表中添加一个空字符串。

  8. 将每个状态 i 的所有情况添加到分析表中，构建完整的 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 Buildprod(string str)
        {

            SLRNode SLr;
            int i = 0;
            string left = '';
            string right = '';
            left += 'S'';
            right += str[0];
            SLr = new SLRNode(left, right);//拓广文法开始
            SLRproNum.Add(SLr);
            while (i < str.Length)
            {
                left = right = '';//还原
                int j = i;
                while (i < str.Length && str[i] != '\r' && str[i] != '\n')//换行符‘\r\n’
                {
                    if (str[i] == ' ')
                    {
                        i++;
                        continue;
                    }
                    if (str[i] == '|')                 //  遇到'|'可构造一条产生式
                    {
                        SLr = new SLRNode(left, right);
                        SLRproNum.Add(SLr);
                        right = '';                    //产生式左边相同 右边重新积累
                        i++;                           //跳过'|'
                        continue;
                    }
                    if ((i - j) == 0)
                    {
                        if (!exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar  产生式左边 只有非终结符 不必判断终结符
                            Nchar.Add(str[i]);
                        left += str[i++];
                    }
                    else if (i - j <= 2)
                        i++;
                    else
                    {
                        if (isFinalsymbol(str[i]) && !exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar  isfinalsymbol 非终结符返回T 终结符返回F
                            Nchar.Add(str[i]);
                        else if (!isFinalsymbol(str[i]) && !exist(Echar, str[i]))//产生式右边 需要判断终结符
                            Echar.Add(str[i]);
                        right += str[i++];
                    }


                }//while

                i++;//跳过换行符
                if (left != '' && right != '')
                {
                    SLr = new SLRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
                    SLRproNum.Add(SLr);
                }
            }//while
            Echar.Add('#');

            //构造项目 对产生式集合LRproNum中的所有产生式都循环插'.'
            SLRNode Lobj;
            for (i = 0; i < SLRproNum.Count; i++)
            {
                left = '';
                right = '';
                for (int j = 0; j <= SLRproNum[i].Right.Length; j++)//j可以等于length  项目共length+1个
                {
                    left = SLRproNum[i].Left;
                    right = CreObj(SLRproNum[i].Right, j);//在第j个位置插入'.'
                    if (j == SLRproNum[i].Right.Length && SLRobjNum.Count != 1)
                    {//在产生式最后的位置插入. 即为归约项目   项目集中1号位置为接受项目
                        Gy_obj.Add(SLRobjNum.Count);//归约项目在项目集中的序号 不用+1 本身就是从0开始的
                    }
                    Lobj = new SLRNode(left, right);
                    SLRobjNum.Add(Lobj);
                    left = '';//还原
                    right = '';
                }
            }
            Creteitemsets();//项目集
            RStr_obitemset += '\r\n项目集构建：\r\n';
            for (int j = 0; j < proitemset.Count; j++)
            {
                RStr_obitemset += 'I' + j.ToString() + ':' + '\r\n';
                for (i = 0; i < proitemset[j].Container.Count; i++)
                {
                    RStr_obitemset += SLRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + SLRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';
                }
            }
        }

        //求项目集
        public void Creteitemsets()
        {
            List<int> lr_item = new List<int>(100);//记录项目的序号
            lr_item.Add(0);
            lr_item = Closure(lr_item);//构造初始项目集 求闭包

            SLRitemsets LR_C = new SLRitemsets();
            LR_C.Container = lr_item;//集合----项目集序号的集合
            proitemset.Add(LR_C);//集合的集合----存放项目集序号集合 的集合


            for (int i = 0; i < proitemset.Count; i++)//整体集合中 第i个项目集
            {
                proitemset[i].Container.Sort();//排序由小到大 后面用于判断是否存在的比较
                int[] flag = new int[proitemset[i].Container.Count];
                for (int fi = 0; fi < proitemset[i].Container.Count; fi++)//标志位，用来判断该序号是否已经构造
                {
                    flag[fi] = 0;
                }

                for (int j = 0; j < proitemset[i].Container.Count; j++)//第i个项目集的第j个项目
                {
                    if (flag[j] == 1)//如果已经访问过 就不再构造 找下一个项目
                        continue;
                    int index = proitemset[i].Container[j];
                    for (int pi = 0; pi < SLRobjNum[index].Right.Length - 1; pi++)//length-1是避免匹配到.在最后的规约项目
                    {
                        if (SLRobjNum[index].Right[pi] == '.')
                        {

                            List<int> lr2_club = new List<int>(100);//记录项目的序号
                            char symbol = SLRobjNum[index].Right[pi + 1];//记录.a转移状态a.的符号a
                            lr2_club.Add((index + 1));//如果遇到.a形式的项目序号为index 那么项目a.的序号为index+1
                            for (int m1 = j + 1; m1 < proitemset[i].Container.Count; m1++)
                            {//在第i个项目集中找到了可以移动的.：.a  重新遍历第i个项目集j项目之后的 找到同样可以移动a的项目集
                                int index2 = proitemset[i].Container[m1];
                                for (int m2 = 0; m2 < SLRobjNum[index2].Right.Length - 1; m2++)
                                {
                                    if (SLRobjNum[index2].Right[m2] == '.' && SLRobjNum[index2].Right[m2 + 1] == symbol)
                                    {
                                        flag[m1] = 1;//标记位置为1 已经访问 之后不再访问
                                        lr2_club.Add(index2 + 1);
                                    }
                                }
                            }
                            lr2_club = Closure(lr2_club);//求闭包
                            int value = isexist(lr2_club);
                            if (value == -1)//-1表示不存在相同的
                            {
                                for (int m3 = 0; m3 < Gy_obj.Count; m3++)
                                {
                                    if (isnexist(lr2_club, Gy_obj[m3]))
                                    {
                                        Gy_itemset.Add(proitemset.Count);
                                    }
                                }
                                SLRitemsets LR_C2 = new SLRitemsets();
                                dfa[Pindex++] = new DFA(i, symbol, proitemset.Count);//count不用加1  本身从0开始
                                LR_C2.Container = lr2_club;
                                proitemset.Add(LR_C2);
                            }
                            else
                            {
                                dfa[Pindex++] = new DFA(i, symbol, value);
                            }
                            break;
                        }
                    }
                }
            }

        }

        //分析表
       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();
        }
    }

    //遍历每个状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        //遍历每个终结符
        for (int j = 0; j < Echar.Count; j++)
        {
            bool flag = false;
            int index = -1;
            //遍历移进项
            for (int k = 0; k < proitemset[i].Container.Count; k++)
            {
                int itemIndex = proitemset[i].Container[k];
                if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Echar[j])
                {
                    flag = true;
                    index = k;
                    break;
                }
            }
            if (flag)
            {
                SLRAna[i][j] = new Table('S', proitemset[Move(proitemset[i], Echar[j])].Container[index + 1]);
            }
            else
            {
                SLRAna[i][j] = new Table();
            }
        }

        //遍历每个非终结符
        for (int j = 0; j < Nchar.Count; j++)
        {
            int index = -1;
            //遍历移进项
            for (int k = 0; k < proitemset[i].Container.Count; k++)
            {
                int itemIndex = proitemset[i].Container[k];
                if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Nchar[j])
                {
                    index = k;
                    break;
                }
            }
            if (index != -1)
            {
                SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])].Container[index + 1]);
            }
            else
            {
                SLRAna[i][Echar.Count + j] = new Table();
            }
        }

        //遍历归约项
        for (int j = 0; j < Gy_obj.Count; j++)
        {
            int itemIndex = Gy_obj[j];
            if (proitemset[i].Container.Contains(itemIndex))
            {
                foreach (char c in Follow(SLRobjNum[itemIndex].Left))
                {
                    if (SLRAna[i][GetIndex(c)].error)
                    {
                        SLRAna[i][GetIndex(c)] = new Table('r', itemIndex);
                    }
                    else
                    {
                        Console.WriteLine('Conflict: state ' + i + ' ' + c + ' ' + SLRAna[i][GetIndex(c)].type + SLRAna[i][GetIndex(c)].id + ' r' + itemIndex);
                    }
                }
            }
        }
    }

    //处理接受状态
    int acceptState = -1;
    for (int i = 0; i < proitemset.Count; i++)
    {
        if (proitemset[i].Container.Contains(0))
        {
            acceptState = i;
            break;
        }
    }
    SLRAna[acceptState][GetIndex('#')] = new Table('A', 0);
}

//获取符号在分析表中的索引
private int GetIndex(char c)
{
    if (isFinalsymbol(c))
    {
        return Echar.IndexOf(c);
    }
    else
    {
        return Echar.Count + Nchar.IndexOf(c);
    }
}

//求FOLLOW集
private List<char> Follow(string symbol)
{
    List<char> followSet = new List<char>();
    if (symbol == 'S'')
    {
        followSet.Add('#');
    }
    foreach (SLRNode node in SLRproNum)
    {
        int index = node.Right.IndexOf(symbol);
        if (index != -1 && index < node.Right.Length - 1)
        {
            List<char> firstSet = First(node.Right.Substring(index + 1));
            if (firstSet.Contains('#'))
            {
                followSet.AddRange(Follow(node.Left));
                followSet.Remove('#');
            }
            followSet.AddRange(firstSet);
        }
    }
    return followSet;
}

//求FIRST集
private List<char> First(string str)
{
    List<char> firstSet = new List<char>();
    if (str == '#' || str.Length == 0)
    {
        firstSet.Add('#');
        return firstSet;
    }
    if (isFinalsymbol(str[0]))
    {
        firstSet.Add(str[0]);
        return firstSet;
    }
    foreach (SLRNode node in SLRproNum)
    {
        if (node.Left == str[0].ToString())
        {
            List<char> tempSet = First(node.Right);
            firstSet.AddRange(tempSet);
            if (tempSet.Contains('#'))
            {
                firstSet.Remove('#');
                firstSet.AddRange(First(str.Substring(1)));
            }
            return firstSet;
        }
    }
    return firstSet;
}

//移动项目集 private int Move(SLRitemsets itemset, char symbol) { List moveitem = new List(); for (int i = 0; i < itemset.Container.Count; i++) { int index = itemset.Container[i]; if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1] == symbol) { moveitem.Add(index + 1); } } moveitem = Closure(moveitem); int value = isexist(moveitem); if (value == -1) { proitemset.Add(new SLRitemsets { Container = moveitem }); return proitemset.Count - 1; } else { return value; } }

//求项目集的闭包 private List Closure(List lr_item) { List temp = new List(lr_item); bool flag = false; do { flag = false; for (int i = 0; i < temp.Count; i++) { int index = temp[i]; if (SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1) { char symbol = SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1]; if (isFinalsymbol(symbol)) { continue; } for (int j = 0; j < SLRobjNum.Count; j++) { if (SLRobjNum[j].Left == symbol.ToString() && !temp.Contains(j)) { temp.Add(j); flag = true; } } } } } while (flag); return temp; }

//判断项目集是否已经存在 private int isexist(List lr_item) { lr_item.Sort();//排序 for (int i = 0; i < proitemset.Count; i++) { if (proitemset[i].Container.Count == lr_item.Count && proitemset[i].Container.SequenceEqual(lr_item)) { return i; } } return -1; }

//判断归约项目是否在项目集内 private bool isnexist(List lr_item, int value) { lr_item.Sort();//排序 for (int i = 0; i < lr_item.Count; i++) { if (lr_item[i] == value) { return true; } } return false; }

//判断是否为终结符 private bool isFinalsymbol(char c) { return !Nchar.Contains(c); }

//判断字符c是否在集合中 private bool exist(List charlist, char c) { for (int i = 0; i < charlist.Count; i++) { if (charlist[i] == c) return true; } return false; }

//在产生式字符串的指定位置插入'.' private string CreObj(string str, int index) { if (index == str.Length) { return str + ' '; } string left = str.Substring(0, index) + '.'; string right = str.Substring(index, str.Length - index); return left + right; }

SLR 分析表构建函数 - 原理及代码实现

原文地址: https://www.cveoy.top/t/topic/f1Qc 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录