SLR文法分析算法实现 - 解析SLR分析表构建

{ "title": "SLR文法分析算法实现 - 解析SLR分析表构建", "description": "本文深入解析SLR文法分析算法，详细讲解SLR分析表的构建过程，并提供C#代码示例，帮助读者理解SLR分析算法的原理与实现。", "keywords": "SLR文法, SLR分析算法, SLR分析表, C#代码, 文法分析, 编译原理", "content": "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 Container = new List(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 List<string> terminals; // 终结符集合
    public List<string> nonterminal;// 非终结符集合
    public Dictionary<string, List<string>> production;//继承LL1中的原始产生式
    public Dictionary<string, List<List<string>>> productions; // 产生式规则（包含全部规则）

    public Dictionary<int, HashSet<string>> transitions; // 状态转移函数
    public Dictionary<ItemSet, int> stateNumbers; // 状态编号
    public Dictionary<int, ItemSet> states; // 状态集合
    public Dictionary<int, List<string>> table;

    public DFA[] dfa = new DFA[100];
    public Table[][] SLRAna;//分析表

    public void SLRAnaly()
    {
        int state = 0;
        string input = "a+b*c#";
        Stack<char> stack = new Stack<char>();
        stack.Push('#');
        stack.Push('$');

        while (true)
        {
            char symbol = input[0];
            if (symbol == '#' && stack.Peek() == '$')
            {
                Console.WriteLine("分析成功");
                break;
            }

            if (SLRAna[state][terminals.IndexOf(symbol)].error == false)
            {
                // 分析表中存在对应项
                if (SLRAna[state][terminals.IndexOf(symbol)].type == 'S')
                {
                    // 移进操作
                    stack.Push(symbol);
                    state = SLRAna[state][terminals.IndexOf(symbol)].id;
                    input = input.Substring(1);
                    Console.WriteLine("移进 " + symbol + " 到状态 " + state);
                }
                else if (SLRAna[state][terminals.IndexOf(symbol)].type == 'r')
                {
                    // 归约操作
                    int proIndex = SLRAna[state][terminals.IndexOf(symbol)].id;
                    string pro = productions.Keys.ElementAt(proIndex - 1);
                    List<string> proRight = productions[pro][proIndex - 1];
                    int len = proRight.Count;
                    Console.WriteLine("归约 " + pro + "->" + string.Join(" ", proRight));
                    for (int i = 0; i < len; i++)
                    {
                        stack.Pop();
                    }
                    stack.Push(pro[0]);
                    state = SLRAna[state][terminals.IndexOf(stack.Peek())].id;
                    Console.WriteLine("状态转移到状态 " + state);
                }
                else if (SLRAna[state][terminals.IndexOf(symbol)].type == 'a')
                {
                    // 接受操作
                    Console.WriteLine("接受");
                    break;
                }
            }
            else
            {
                // 分析表中不存在对应项
                Console.WriteLine("分析失败");
                break;
            }
        }
    }
}

内容：相关调用的函数代码：

SLR_fourpro SLR_fourpro = new SLR_fourpro(text); if (SLR_fourpro.is_SLR == 1) { SLR SLR = SLR_fourpro.getSLR(); SLR.buildtable(); SLR.SLRAnaly(); }

未给出但使用到了的变量定义代码：

public List terminals; // 终结符集合 public List nonterminal;// 非终结符集合 public Dictionary<string, List> production;//继承LL1中的原始产生式 public Dictionary<string, List<List>> productions; // 产生式规则（包含全部规则）

public Dictionary<int, HashSet> transitions; // 状态转移函数 public Dictionary<ItemSet, int> stateNumbers; // 状态编号 public Dictionary<int, ItemSet> states; // 状态集合 public Dictionary<int, List> table;

public DFA[] dfa = new DFA[100]; public Table[][] SLRAna;//分析表