• 日期: 2028-08-20
  • 标签: 常规

SLR1 分析器实现：代码详解及优化

本文提供详细的 SLR1 分析器实现代码，涵盖了产生式构建、项目集生成、分析表构建、以及句子分析等关键步骤。并对代码进行了优化，使其更易于理解和使用。

核心代码

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 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);//终结符集合

    Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集

    public string RStr = '';
    public string RStr_obitemset = '';//输出返回
    public string RStr_DFA = '';
    public string RStr_ANA = '';

    public void Buildprod(string str)
    {
        string[] p = str.Split('
');
        foreach (string s in p)
        {
            string[] temp = s.Split('-');
            SLRNode node = new SLRNode(temp[0], temp[1].Trim());
            SLRproNum.Add(node);
        }
    }

    public void Creteitemsets()
    {
        //初始化第一个项目集
        SLRitemsets itemset = new SLRitemsets();
        itemset.Container.Add(0);
        proitemset.Add(itemset);

        //遍历所有项目集
        for (int i = 0; i < proitemset.Count; i++)
        {
            //遍历所有终结符和非终结符
            foreach (char ch in Nchar)
            {
                SLRitemsets newitemset = new SLRitemsets();
                //遍历项目集中的所有项目
                foreach (int num in proitemset[i].Container)
                {
                    SLRNode node = SLRobjNum[num];
                    //找到非终结符所在的位置
                    int index = node.Right.IndexOf(ch);
                    //如果非终结符存在于项目中
                    if (index != -1 && index < node.Right.Length - 1)
                    {
                        //将非终结符后面的符号加入新的项目中
                        string str = CreObj(node.Right, index + 1);
                        //找到加入符号后的产生式
                        int proindex = Find_pro(new SLRNode(node.Left, str));
                        //如果产生式不存在于项目集中
                        if (!isnexist(newitemset.Container, proindex))
                        {
                            newitemset.Container.Add(proindex);
                        }
                    }
                }
                //如果新的项目集不为空，且不存在于项目集合中
                if (newitemset.Container.Count != 0 && isexist(newitemset.Container) == -1)
                {
                    proitemset.Add(newitemset);
                }
            }

            foreach (char ch in Echar)
            {
                SLRitemsets newitemset = new SLRitemsets();
                //遍历项目集中的所有项目
                foreach (int num in proitemset[i].Container)
                {
                    SLRNode node = SLRobjNum[num];
                    //找到终结符所在的位置
                    int index = node.Right.IndexOf(ch);
                    //如果终结符存在于项目中
                    if (index != -1 && index < node.Right.Length - 1)
                    {
                        //将终结符后面的符号加入新的项目中
                        string str = CreObj(node.Right, index + 1);
                        //找到加入符号后的产生式
                        int proindex = Find_pro(new SLRNode(node.Left, str));
                        //如果产生式不存在于项目集中
                        if (!isnexist(newitemset.Container, proindex))
                        {
                            newitemset.Container.Add(proindex);
                        }
                    }
                }
                //如果新的项目集不为空，且不存在于项目集合中
                if (newitemset.Container.Count != 0 && isexist(newitemset.Container) == -1)
                {
                    proitemset.Add(newitemset);
                }
            }
        }
    }

    //生成分析表
    public Table[][] GET_ANA()
    {
        //初始化分析表
        SLRAna = new Table[proitemset.Count][];
        for (int i = 0; i < proitemset.Count; i++)
        {
            SLRAna[i] = new Table[Echar.Count + Nchar.Count + 1];
            for (int j = 0; j < Echar.Count + Nchar.Count + 1; j++)
            {
                SLRAna[i][j] = new Table();
            }
        }

        //填充移进、归约、接受表格
        for (int i = 0; i < proitemset.Count; i++)
        {
            foreach (int num in proitemset[i].Container)
            {
                SLRNode node = SLRobjNum[num];
                if (node.Right.IndexOf('.') < node.Right.Length - 1)
                {
                    char ch = node.Right[node.Right.IndexOf('.') + 1];
                    if (isFinalsymbol(ch))
                    {
                        int j = FindID(Echar, ch);
                        SLRAna[i][j].type = 's';
                        SLRAna[i][j].id = dfa[i * (Echar.Count + Nchar.Count + 1) + j + 1].to;
                        SLRAna[i][j].error = false;
                    }
                }
                else if (node.Right.IndexOf('.') == node.Right.Length - 1)
                {
                    if (node.Left == 'S')
                    {
                        SLRAna[i][Echar.Count + Nchar.Count].type = 'a';
                        SLRAna[i][Echar.Count + Nchar.Count].error = false;
                    }
                    else
                    {
                        foreach (int gy in Gy_obj)
                        {
                            if (gy == num)
                            {
                                foreach (char ch in follow[node.Left[0]])
                                {
                                    int j = FindID(Echar, ch);
                                    SLRAna[i][j].type = 'r';
                                    SLRAna[i][j].id = Find_pro(node);
                                    SLRAna[i][j].error = false;
                                }
                            }
                        }
                    }
                }
            }
        }

        //填充转移表格
        for (int i = 0; i < proitemset.Count; i++)
        {
            foreach (char ch in Nchar)
            {
                int j = FindID(Nchar, ch);
                foreach (DFA d in dfa)
                {
                    if (d.from == i && d.symbol == ch)
                    {
                        SLRAna[i][j + Echar.Count].type = 'g';
                        SLRAna[i][j + Echar.Count].id = d.to;
                        SLRAna[i][j + Echar.Count].error = false;
                    }
                }
            }
        }

        return SLRAna;
    }

    //SLR分析器
    public void SLRAnaly()
    {
        //生成项目集、DFA、SLR1分析表
        Creteitemsets();
        CreateDFA();
        GET_ANA();

        //初始化分析栈和输入串
        Jz = new Analyze();
        Jz.stack_state.Add('0');
        Jz.Input_str.AddRange(RStr.Split(' '));

        //SLR分析
        while (!Success)
        {
            int state = int.Parse(Jz.stack_state[Jz.stack_state.Count - 1]);
            string symbol = Jz.Input_str[0];
            int id = -1;
            if (Echar.Contains(symbol[0]))
            {
                id = FindID(Echar, symbol[0]);
            }
            else if (Nchar.Contains(symbol[0]))
            {
                id = FindID(Nchar, symbol[0]) + Echar.Count;
            }

            if (SLRAna[state][id].type == 's')
            {
                Jz.stack_symbol.Add(symbol);
                Jz.stack_state.Add(SLRAna[state][id].id.ToString());
                Jz.Input_str.RemoveAt(0);
            }
            else if (SLRAna[state][id].type == 'r')
            {
                SLRNode node = SLRproNum[SLRAna[state][id].id];
                for (int i = 0; i < node.Right.Length * 2; i++)
                {
                    Jz.stack_symbol.RemoveAt(Jz.stack_symbol.Count - 1);
                    Jz.stack_state.RemoveAt(Jz.stack_state.Count - 1);
                }
                Jz.stack_symbol.Add(node.Left);
                int newstate = int.Parse(Jz.stack_state[Jz.stack_state.Count - 1]);
                Jz.stack_state.Add(SLRAna[newstate][FindID(Nchar, node.Left[0]) + Echar.Count].id.ToString());
                Jz.Tran_pro.Add(node.Left + '->' + node.Right);
            }
            else if (SLRAna[state][id].type == 'g')
            {
                Jz.stack_symbol.Add(symbol);
                Jz.stack_state.Add(SLRAna[state][id].id.ToString());
            }
            else if (SLRAna[state][id].type == 'a')
            {
                Success = true;
            }
            else
            {
                Success = false;
                break;
            }
        }
    }

    //分析句子
    public void sen_Analyze(string text)
    {
        RStr = text;
        SLRAnaly();
    }


      
    //构造项目 在right[index]位置插入'.'
    public string CreObj(string right, int index)
    {
        int i = 0;
        string Restr = '';
        while (i < right.Length)
        {
            if (i == index)
                Restr += '.';

            Restr += right[i];
            i++;
        }
        if (i == index)
            Restr += '.';
        return Restr;
    }

    //判断ch是否为非终结符
    public bool isFinalsymbol(char ch1)
    {
        //char ch1=ch[0];
        if (ch1 >= 'A' && ch1 <= 'Z')
            return true;
        else
            return false;
    }


    //判断集合是I否存在于proitemset
    //如果存在就返回已存在的项目集序号 
    //如果不存在就返回-1
    public int isexist(List<int> I)
    {
        I.Sort();
        for (int i = 0; i < proitemset.Count; i++)
        {
            proitemset[i].Container.Sort();
            if (I.SequenceEqual(proitemset[i].Container))
            {
                return i;
            }
        }
        return -1;

    }

    //判断num是否存在于I
    //存在返回true 不存在返回False
    public bool isnexist(List<int> I, int num)
    {
        for (int i = 0; i < I.Count; i++)
        {
            if (I[i] == num)
                return true;
        }
        return false;
    }

    //判断ch是否存在于I
    //存在返回true 不存在返回False
    public bool exist(List<char> I, char ch)
    {
        for (int i = 0; i < I.Count; i++)
        {
            if (I[i] == ch)
                return true;

        }
        return false;
    }
    //寻找ch在I中的序号
    public int FindID(List<char> I, char ch)
    {
        for (int i = 0; i < I.Count; i++)
        {
            if (I[i] == ch)
                return i;

        }
        return -1;
    }

    //寻找项目最初的产生式序号  E->.ab  ====>  E->a
    public int Find_pro(SLRNode SLR)
    {
        string s = '';
        for (int i = 0; i < SLR.Right.Length; i++)
        {
            if (SLR.Right[i] != '.')
                s += SLR.Right[i];
        }
        for (int i = 0; i < SLRproNum.Count; i++)
        {
            if (SLRproNum[i].Left == SLR.Left && SLRproNum[i].Right == s)
                return i;
        }
        return -1;
    }

    // 创建 DFA
    public void CreateDFA()
    {
        // 初始化第一个 DFA 状态
        dfa[Pindex] = new DFA(0, ' ', 0);
        Pindex++;

        // 遍历所有项目集
        for (int i = 0; i < proitemset.Count; i++)
        {
            // 遍历所有终结符和非终结符
            foreach (char ch in Echar)
            {
                // 创建新的项目集
                SLRitemsets newitemset = new SLRitemsets();
                // 遍历项目集中的所有项目
                foreach (int num in proitemset[i].Container)
                {
                    SLRNode node = SLRobjNum[num];
                    // 找到终结符所在的位置
                    int index = node.Right.IndexOf(ch);
                    // 如果终结符存在于项目中
                    if (index != -1 && index < node.Right.Length - 1)
                    {
                        // 将终结符后面的符号加入新的项目中
                        string str = CreObj(node.Right, index + 1);
                        // 找到加入符号后的产生式
                        int proindex = Find_pro(new SLRNode(node.Left, str));
                        // 如果产生式不存在于项目集中
                        if (!isnexist(newitemset.Container, proindex))
                        {
                            newitemset.Container.Add(proindex);
                        }
                    }
                }
                // 如果新的项目集不为空，且不存在于项目集合中
                if (newitemset.Container.Count != 0)
                {
                    // 找到新的项目集在 proitemset 中的索引
                    int j = isexist(newitemset.Container);
                    // 创建新的 DFA 状态
                    dfa[Pindex] = new DFA(i, ch, j);
                    Pindex++;
                }
            }

            foreach (char ch in Nchar)
            {
                // 创建新的项目集
                SLRitemsets newitemset = new SLRitemsets();
                // 遍历项目集中的所有项目
                foreach (int num in proitemset[i].Container)
                {
                    SLRNode node = SLRobjNum[num];
                    // 找到非终结符所在的位置
                    int index = node.Right.IndexOf(ch);
                    // 如果非终结符存在于项目中
                    if (index != -1 && index < node.Right.Length - 1)
                    {
                        // 将非终结符后面的符号加入新的项目中
                        string str = CreObj(node.Right, index + 1);
                        // 找到加入符号后的产生式
                        int proindex = Find_pro(new SLRNode(node.Left, str));
                        // 如果产生式不存在于项目集中
                        if (!isnexist(newitemset.Container, proindex))
                        {
                            newitemset.Container.Add(proindex);
                        }
                    }
                }
                // 如果新的项目集不为空，且不存在于项目集合中
                if (newitemset.Container.Count != 0)
                {
                    // 找到新的项目集在 proitemset 中的索引
                    int j = isexist(newitemset.Container);
                    // 创建新的 DFA 状态
                    dfa[Pindex] = new DFA(i, ch, j);
                    Pindex++;
                }
            }
        }
    }
}

代码详解

  1. 产生式构建

    Buildprod(string str) 函数用于从字符串中解析产生式，并将它们存储在 SLRproNum 列表中。

  2. 项目集生成

    Creteitemsets() 函数用于生成所有项目集，并将它们存储在 proitemset 列表中。

  3. 分析表构建

    GET_ANA() 函数用于构建 SLR1 分析表 SLRAna。分析表包含移进、归约、接受和转移四种操作。

  4. 句子分析

    SLRAnaly() 函数用于使用 SLR1 分析表对输入句子进行分析。分析结果存储在 Jz 对象中。

  5. 辅助函数

    代码中还包含一些辅助函数，例如 CreObj 用于构造项目、isFinalsymbol 用于判断符号类型、isexist 用于判断项目集是否存在、isnexist 用于判断项目是否存在于项目集中等等。

优化建议

  1. 代码结构优化 可以将代码拆分为多个类，例如将项目集、DFA 状态、分析表等分别封装为独立的类，以提高代码可读性和可维护性。
  2. 错误处理 添加错误处理机制，例如在分析过程中遇到错误时，可以抛出异常或者返回错误信息，以便更好地定位问题。
  3. 性能优化 可以使用更高效的数据结构和算法来提高代码性能，例如使用哈希表来存储项目集，使用更快的搜索算法来查找项目等等。

代码使用

  1. 定义产生式 例如，定义一个简单的文法： 
    S'->S
S->E
E->T+E
E->T
T->i
    将产生式字符串赋值给 str 变量。
  2. 创建 SLR1 分析器对象 
    SLR slr = new SLR();
  3. 构建产生式 
    slr.Buildprod(str);
  4. 设置非终结符和终结符集合 
    slr.Nchar.AddRange(new char[] { 'S', 'E', 'T' });
slr.Echar.AddRange(new char[] { '+', 'i' });
  5. 生成项目集 
    slr.Creteitemsets();
  6. 创建 DFA 
    slr.CreateDFA();
  7. 构建分析表 
    slr.GET_ANA();
  8. 分析句子 
    slr.sen_Analyze('i + i');

总结

本文提供的 SLR1 分析器代码示例，可以帮助你理解 SLR1 分析器的实现原理和关键步骤。通过代码优化和改进，可以构建一个更加高效、可靠的 SLR1 分析器。

SLR1 分析器实现：代码详解及优化

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

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