LR（1）分析程序实验目的与要求

  编制一个允许规范族有冲突的项目集用向前查看一个符号的办法来进行处理，并且能够解决存在的无效归约问题，以解决冲突的分析过程。

实验内容

• 本次实验最主要的部分构建语法分析表，理解分析表的使用，明确分析步骤。
  本次实验主要用到的数据结构有List, Stack,二维数组等。
• 根据用户输入，给出分析过程。

实验步骤

• Main函数：在while循环中，根据状态栈栈顶元素，输入字符串的首字符，查询Action表，根据其值判断分析是否结束。未结束，则分为成功，移进，规约三种状态进行分析。

主要函数介绍：

1. 根据S后的数字，获取产生式右部：static string GetRight(int n)
2. 打印分析步骤：Display(string inputString,string action,string Go)
3. 用于将状态栈，符号栈的内容逆序转化成字符串：GetStringFromStack(Stack stack)
4. 根据终结符查找其在Vt表的位置：GetIndexByTerminalOnVt (char target)
5. 根据非终结符查找其在Vn表的位置：GetIndexByNonTerminalOnVt (char target)

实验中遇到的问题：

  因为不需要通过编程的方式构建分析表，所以我觉得本次实验的难点主要在于分析表的使用，其不难理解但是实现起来相对繁琐。

  比如：需要要获取S或者r后边的数字之后对状态表、动作表的查询，并决定是添加到状态栈或是归约处理；栈元素逆序转化成字符串打印；对输入字符串的裁剪操作等都比较繁琐。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;

namespace LR1
{
    class Program
    {
        static List<char> Vt = new List<char> { 'i', '+', '*', '(', ')', '#' };//终结符集合
        static  List<char> Vn = new List<char> { 'E', 'T', 'F' };//非终结符集合
        static List<string> production = new List<string> {
            "","E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i"};//产生式
        static int[,] GoTo = 
        {
            {1,2,3 },
            {-1,-1,-1 },
            {-1,-1,-1 },
            {-1,-1,-1 },
            {8,2,3 },
            {-1,-1,-1 },
            {-1,9,3 },
            {-1,-1,10 },
            {-1,-1,-1 },
            {-1,-1,-1 },
            {-1,-1,-1 },
            {-1,-1,-1 },
        };
        static string[,] actions =
        {
            {"S5",null,null,"S4",null,null },
            {null,"S6",null,null,null,"acc" },
            {null,"r2","S7",null,"r2","r2" },
            {null,"r4","r4",null,"r4","r4" },
            {"S5",null,null,"S4",null,null },
            {null,"r6", "r6", null, "r6", "r6" },
            {"S5",null,null,"S4",null,null },
            {"S5",null,null,"S4",null,null },
            {null,"S6",null,null, "S11",null },
            {null,"r1","S7",null,"r1","r1" },
            {null,"r3","r3",null, "r3", "r3" },
            {null,"r5","r5",null, "r5", "r5" },
        };

        static Stack<int> status = new Stack<int>();//状态栈
        static Stack<char> symbol = new Stack<char>();//符号栈

        static void Main(string[] args)
        {
            Write("请输入待分析的句子：");
            string inputString = ReadLine();
            inputString += "#";
            status.Push(0);
            WriteLine($"{"状态栈",-15}{"符号栈",-15}{"剩余输入串",-15}{"Action",-20}{"GoTo",-15}");
            while (true)
            {
                char terminal = inputString[0];
                int state = status.Peek();
                int index = GetIndexByTerminalOnVt(terminal);
                if (index < 0 || actions[state, index] == null)
                {
                    Error();
                }
                else
                {
                    string action = actions[state, index];
                    if (action == "acc")
                    {
                        Display(inputString, action, "");
                        WriteLine("分析结束，该文法接受此类型句子，接受成功");
                        Environment.Exit(0);
                    }
                    else if (action[0] == 'S')
                    {
                        Display(inputString,action, "");
                        int next = Convert.ToInt32(action.Remove(0, 1));//查找动作表，移进后转到第几个状态
                        symbol.Push(terminal);
                        status.Push(next);
                        if (inputString[0]!='#')
                        {
                            inputString = inputString.Remove(0, 1);
                        }
                    }
                    else if (action[0] == 'r')
                    {
                        //归约动作
                        int n = Convert.ToInt32(action.Remove(0, 1));//查找动作表，用第几个产生式归约
                        string right = GetRight(n);//获取第n个产生式的右部
                        int sp = status.ElementAt(right.Length);
                        int go = GetIndexByNonTerminalOnVt(production[n][0]);
                        int k = GoTo[sp,go];//查找goto表，转到第几号状态
                        Display(inputString,action, k.ToString());

                        for (int i = 0; i < right.Length; i++)
                        {
                            symbol.Pop();
                            status.Pop();
                        }

                        status.Push(k);
                        symbol.Push(production[n][0]);
                    }
                    
                }
            }
        }
        /// <summary>
        /// 获取产生式右部
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        static string GetRight(int n)
        {
            try
            {
                return production[n].Remove(0, 3);
            }
            catch
            {                
                Error();
            }
            return "";
        }

        static void Display(string inputString,string action,string Go)
        {
            string state = GetStringFromStack(status);
            string sym = GetStringFromStack(symbol);
            WriteLine($"{state,-20}{sym,-20}{inputString,-20}{action,-20}{Go,-20}");
        }

        static string GetStringFromStack(Stack<int> stack)
        {
            Stack<int> s = new Stack<int>();
            StringBuilder sb = new StringBuilder();
            foreach(int o in stack)
            {
                s.Push(o);
            }
            foreach(int o in s)
            {
                sb.Append(o);
            }
            return sb.ToString();
        }
        static string GetStringFromStack(Stack<char> stack)
        {
            Stack<char> s = new Stack<char>();
            StringBuilder sb = new StringBuilder();
            foreach (char o in stack)
            {
                s.Push(o);
            }
            foreach (char o in s)
            {
                sb.Append(o.ToString());
            }
            return sb.ToString();
        }

        /// <summary>
        /// 根据终结符查找其在Vt表的位置
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        static int GetIndexByTerminalOnVt(char target)
        {
           return Vt.FindLastIndex(r=>r==target);
        }

        /// <summary>
        /// 根据非终结符查找其在Vn表的位置
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        static int GetIndexByNonTerminalOnVt(char target)
        {
            return Vn.FindLastIndex(r => r == target);
        }
        /// <summary>
        /// 出错处理函数
        /// </summary>
        static void Error()
        {
            WriteLine("分析结束，该文法不接受此类型句子，接受失败");
            Environment.Exit(0);
        }
    }
}