LR(0) 分析器：判断 LR(0) 文法、生成项目族信息和构造 LR 分析表

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace LR0Analyzer
{
    // LL(1) 分析器类
    class isLL_1_
    {
        public Dictionary<char, List<string>> product;
        public int is_LL = 0;
        public LL1Item LL1Item;
        public isLL_1_(String text)
        {
            LL1Item = new LL1Item(text);
            product = LL1Item.product;
            if (LL1Item.is_LL != 0) is_LL = 1;
        }
    }

    // LL(1) 项类
    class LL1Item
    {
        public Dictionary<char, List<string>> product;
        public List<string> final;
        public List<string> nofinal;
        public List<string> start;
        public Dictionary<string, List<string>> first;
        public Dictionary<string, List<string>> follow;
        public Dictionary<string, Dictionary<string, List<string>>> select;
        public int is_LL = 0;

        public LL1Item(String text)
        {
            // 初始化参数
            final = new List<string>();
            nofinal = new List<string>();
            start = new List<string>();
            product = new Dictionary<char, List<string>>();
            first = new Dictionary<string, List<string>>();
            follow = new Dictionary<string, List<string>>();
            select = new Dictionary<string, Dictionary<string, List<string>>>();

            // 解析文法
            string[] lines = text.Split('
');
            foreach (string line in lines)
            {
                string[] parts = line.Split(' ');
                if (parts.Length > 1)
                {
                    string lhs = parts[0].Trim();
                    string rhs = parts[1].Trim();
                    if (!product.ContainsKey(lhs[0]))
                    {
                        product.Add(lhs[0], new List<string>());
                    }
                    product[lhs[0]].Add(rhs);
                }
            }

            // 初始化终结符和非终结符
            foreach (char c in product.Keys)
            {
                if (!nofinal.Contains(c.ToString()))
                {
                    nofinal.Add(c.ToString());
                }
            }
            foreach (var c in product.Values)
            {
                foreach (var item in c)
                {
                    for (int i = 0; i < item.Length; i++)
                    {
                        if (!nofinal.Contains(item[i].ToString()) && !final.Contains(item[i].ToString()) && item[i].ToString() != 'ε')
                        {
                            final.Add(item[i].ToString());
                        }
                    }
                }
            }
            // 添加开始符号
            start.Add(product.Keys.First().ToString() + ''');
            nofinal.Add(product.Keys.First().ToString() + ''');

            // 计算 FIRST 集
            calculateFirst();
            // 计算 FOLLOW 集
            calculateFollow();
            // 计算 SELECT 集
            calculateSelect();

            // 判断是否为 LL(1) 文法
            is_LL = judgeLL1();
        }

        private void calculateFirst()
        {
            foreach (char nonterminal in product.Keys)
            {
                first.Add(nonterminal.ToString(), new List<string>());
                foreach (string rhs in product[nonterminal])
                {
                    // 遍历产生式右部的每个符号
                    for (int i = 0; i < rhs.Length; i++)
                    {
                        char symbol = rhs[i];
                        // 如果是终结符，直接加入 FIRST 集
                        if (final.Contains(symbol.ToString()) || symbol.ToString() == 'ε')
                        {
                            if (!first[nonterminal.ToString()].Contains(symbol.ToString()))
                            {
                                first[nonterminal.ToString()].Add(symbol.ToString());
                            }
                            break;
                        }
                        // 如果是非终结符，递归计算其 FIRST 集
                        else
                        {
                            if (!first[nonterminal.ToString()].Contains(symbol.ToString()))
                            {
                                first[nonterminal.ToString()].AddRange(first[symbol.ToString()]);
                            }
                            // 如果 FIRST 集中包含 ε，继续遍历下一个符号
                            if (!first[symbol.ToString()].Contains('ε'))
                            {
                                break;
                            }
                        }
                    }
                }
            }
        }

        private void calculateFollow()
        {
            // 初始化 FOLLOW 集
            foreach (char nonterminal in product.Keys)
            {
                follow.Add(nonterminal.ToString(), new List<string>());
            }

            // 开始符号的 FOLLOW 集添加 #
            follow[product.Keys.First().ToString() + '''].Add('#');

            // 迭代计算 FOLLOW 集
            bool changed = true;
            while (changed)
            {
                changed = false;
                foreach (char nonterminal in product.Keys)
                {
                    foreach (string rhs in product[nonterminal])
                    {
                        // 遍历产生式右部的每个符号
                        for (int i = 0; i < rhs.Length; i++)
                        {
                            char symbol = rhs[i];
                            // 如果是终结符，则继续遍历下一个符号
                            if (final.Contains(symbol.ToString()))
                            {
                                continue;
                            }
                            // 如果是非终结符
                            else
                            {
                                // 如果是最后一个符号
                                if (i == rhs.Length - 1)
                                {
                                    // 如果是开始符号，则将 # 加入其 FOLLOW 集
                                    if (nonterminal == product.Keys.First())
                                    {
                                        if (!follow[symbol.ToString()].Contains('#'))
                                        {
                                            follow[symbol.ToString()].Add('#');
                                            changed = true;
                                        }
                                    }
                                    // 否则将 FOLLOW(A) 加入其 FOLLOW 集
                                    else
                                    {
                                        if (!follow[symbol.ToString()].Contains(follow[nonterminal.ToString()]))
                                        {
                                            follow[symbol.ToString()].AddRange(follow[nonterminal.ToString()]);
                                            changed = true;
                                        }
                                    }
                                }
                                // 如果不是最后一个符号
                                else
                                {
                                    // 将 FIRST(β) 中不包含 ε 的符号加入其 FOLLOW 集
                                    char nextSymbol = rhs[i + 1];
                                    if (final.Contains(nextSymbol.ToString()) || (nextSymbol.ToString() == 'ε'))
                                    {
                                        if (!follow[symbol.ToString()].Contains(nextSymbol.ToString()))
                                        {
                                            follow[symbol.ToString()].Add(nextSymbol.ToString());
                                            changed = true;
                                        }
                                    }
                                    else
                                    {
                                        if (!follow[symbol.ToString()].Contains(first[nextSymbol.ToString()]))
                                        {
                                            follow[symbol.ToString()].AddRange(first[nextSymbol.ToString()]);
                                            changed = true;
                                        }
                                        // 如果 FIRST(β) 包含 ε，则将 FOLLOW(A) 加入其 FOLLOW 集
                                        if (first[nextSymbol.ToString()].Contains('ε'))
                                        {
                                            if (!follow[symbol.ToString()].Contains(follow[nonterminal.ToString()]))
                                            {
                                                follow[symbol.ToString()].AddRange(follow[nonterminal.ToString()]);
                                                changed = true;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        private void calculateSelect()
        {
            foreach (char nonterminal in product.Keys)
            {
                select.Add(nonterminal.ToString(), new Dictionary<string, List<string>>());
                foreach (string rhs in product[nonterminal])
                {
                    string str = string.Format('{0}->{1}', nonterminal, rhs);
                    List<string> temp = new List<string>();
                    for (int i = 0; i < rhs.Length; i++)
                    {
                        if (final.Contains(rhs[i].ToString()) || rhs[i].ToString() == 'ε')
                        {
                            temp.Add(rhs[i].ToString());
                            break;
                        }
                        else
                        {
                            temp.AddRange(first[rhs[i].ToString()]);
                            if (!first[rhs[i].ToString()].Contains('ε')) break;
                        }
                    }
                    if (temp.Contains('ε'))
                    {
                        temp.RemoveAll(s => s == 'ε');
                        temp.AddRange(follow[nonterminal.ToString()]);
                    }
                    if (!select[nonterminal.ToString()].ContainsKey(str))
                    {
                        select[nonterminal.ToString()].Add(str, temp);
                    }
                }
            }
        }

        private int judgeLL1()
        {
            // 检查 SELECT 集是否有冲突
            foreach (char nonterminal in product.Keys)
            {
                foreach (string rhs1 in product[nonterminal])
                {
                    string str1 = string.Format('{0}->{1}', nonterminal, rhs1);
                    foreach (string rhs2 in product[nonterminal])
                    {
                        string str2 = string.Format('{0}->{1}', nonterminal, rhs2);
                        if (str1 != str2)
                        {
                            // 如果 SELECT 集有冲突，返回 0
                            if (select[nonterminal.ToString()][str1].Intersect(select[nonterminal.ToString()][str2]).Any())
                            {
                                return 0;
                            }
                        }
                    }
                }
            }

            // SELECT 集没有冲突，返回 1
            return 1;
        }
    }

    // LR(0) 项目类
    class Item
    {
        public string LHS; // 产生式左部
        public List<string> RHS; // 产生式右部
        public int dotIndex; // 点的位置

        public Item(string lhs, List<string> rhs, int dotIndex)
        {
            this.LHS = lhs;
            this.RHS = rhs;
            this.dotIndex = dotIndex;
        }

        // 判断两个项目是否相等
        public bool Equals(Item other)
        {
            return LHS == other.LHS && dotIndex == other.dotIndex && RHS.Count == other.RHS.Count
                    && new HashSet<string>(RHS).SetEquals(other.RHS);
        }

        public override string ToString()
        {
            List<string> tempRHS = new List<string>(RHS);
            tempRHS.Insert(dotIndex, '.');
            return $'{LHS}->{string.Join('',tempRHS)}';
        }

        public string ToString2()
        {
            List<string> tempRHS = new List<string>(RHS);
            return $'{LHS}->{string.Join('', tempRHS)}';
        }
    }

    // 项集类
    class ItemSet
    {
        public HashSet<Item> items;

        public ItemSet()
        {
            items = new HashSet<Item>();
        }

        public override bool Equals(object other)
        {
            if (other == null || GetType() != other.GetType())
            {
                return false;
            }

            ItemSet otherSet = (ItemSet)other;
            return items.SetEquals(otherSet.items);
        }

        //public override string ToString()
        //{
        //    return string.Join('\n', items);
        //}
    }

    // LR(0) 分析器类
    class LR0
    {
        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 LR0(isLL_1_ isLL_1_)
        {
            this.terminals = isLL_1_.LL1Item.final;
            this.nonterminal = isLL_1_.LL1Item.nofinal;

            this.production = isLL_1_.product;

            productions = new Dictionary<string, List<List<string>>>();
            transformpro();

            transitions = new Dictionary<int, HashSet<string>>();
            buildDFA(); // 构建 DFA
            buildtable(); //构建分析表
        }

        private void transformpro() 
        {
            foreach (var item in production)
            {
                productions.Add(item.Key, new List<List<string>>());
                foreach(var item2 in item.Value)
                {
                    List<string> proitem = new List<string>();
                    for (int i = 0; i < item2.Length; i++)
                        proitem.Add(item2[i].ToString());
                    productions[item.Key].Add(proitem);
                }
            }
        }

        private ItemSet CLOSURE(ItemSet I)
        {
            ItemSet J = new ItemSet();
            foreach (var item in I.items)
                J.items.Add(item);
            Stack<Item> stack = new Stack<Item>();

            foreach (Item i in I.items)
            {
                stack.Push(i);
            }

            while (stack.Count > 0)
            {
                Item i = stack.Pop();
                if (i.dotIndex < i.RHS.Count && nonterminal.Contains(i.RHS[i.dotIndex])) // dot 后的符号为非终结符
                {
                    string X = i.RHS[i.dotIndex];
                    foreach (List<string> prod in productions[X]) // 考虑 X -> Y1 Y2 ... Yk 的每个产生式
                    {
                        Item newI = new Item(X, prod, 0);
                        if (!J.items.Contains(newI))
                        {
                            J.items.Add(newI);
                            stack.Push(newI);
                        }
                    }
                }
            }
            return J;
        }

        private ItemSet GOTO(ItemSet I, string X)
        {
            ItemSet J = new ItemSet();
            foreach (Item i in I.items)
            {
                if (i.dotIndex < i.RHS.Count && i.RHS[i.dotIndex] == X)
                {
                    Item newI = new Item(i.LHS, i.RHS, i.dotIndex + 1);
                    J.items.Add(newI);
                }
            }

            return CLOSURE(J);
        }

        private int iscommon(Dictionary<ItemSet, int> states, ItemSet itemSet)
        {
            int flag;
            int index=-1;
            foreach(var item in states.Keys)
            {
                flag = 0;
                if (item.items.Count == itemSet.items.Count)
                {
                    foreach (var j in itemSet.items)
                    {
                        foreach (var i in item.items)
                        {
                            if (i.Equals(j))
                            {
                                flag++;
                                break;
                            }
                        }
                    }
                    if (flag == item.items.Count) index=states[item];
                }
            }
            return index;
        }

        private void buildDFA()
        {
            //构造初始项目集
            string s = productions.Keys.First() + ''';
            Item startItem = new Item(s, new List<string>() { productions.Keys.First() }, 0);
            ItemSet startSet = new ItemSet();
            startSet.items.Add(startItem);
            startSet = CLOSURE(startSet);

            // 初始化状态编号
            stateNumbers = new Dictionary<ItemSet, int>();
            states = new Dictionary<int, ItemSet>();

            // 使用队列保存待处理的项集
            Queue<ItemSet> queue = new Queue<ItemSet>();
            stateNumbers[startSet] = 0;
            states.Add(0, startSet);
            queue.Enqueue(startSet);

            while (queue.Count > 0)
            {
                ItemSet I = queue.Dequeue();
                int stateNumber = stateNumbers[I];

                // 计算 I 中每个符号的移进操作后得到的新项集，并添加到 DFA 中
                foreach (string symbol in nonterminal.Union(terminals))
                {
                    ItemSet J = GOTO(I, symbol);
                    int index;

                    if (J.items.Count > 0) 
                    {
                        index = iscommon(stateNumbers, J);
                        if(index == -1)// 如果该项集不为空且还没有被加入到状态集合中
                        {
                            stateNumbers[J] = states.Count;
                            states.Add(states.Count, J);
                            queue.Enqueue(J);
                        }
                        if (!transitions.ContainsKey(stateNumber))// 如果该项集不为空
                        {
                            transitions[stateNumber] = new HashSet<string>();
                        }
                        transitions[stateNumber].Add(symbol + (index!=-1? index:stateNumbers[J]));
                    }
                }
            }
        }

        public bool judgeLR0()
        {
            int back = 0;
            int put = 0;

            foreach(var item in stateNumbers.Keys)
            {
                back = 0;
                put = 0;
                foreach (var pro in item.items)
                {
                    if (pro.dotIndex == pro.RHS.Count) back++;
                    else if (terminals.Contains(pro.RHS[pro.dotIndex])) put++;
                }
                if (back > 0 && put > 0) return false;
                if (back >= 2) return false;
            }
            return true;
        }

        private int getproconut(ItemSet itemSet)
        {
            int index = 1;
            if (itemSet.items.Count == 1)
            {
                foreach (var item in itemSet.items)
                    if(item.dotIndex == item.RHS.Count)
                    {
                        foreach(var key in productions.Keys)
                        {
                            if (key.Equals(item.LHS))
                            {
                                foreach( var item2 in productions[key])
                                {
                                    if (item.RHS.Equals(item2)) return index;
                                    else index++;
                                }
                            }
                            index += productions[key].Count;
                        }
                        return index;
                    }
            }
            return -1;
        }
        private void buildtable()
        {
            int flag = 0;
            table = new Dictionary<int, List<string>>();
            for(int i=0;i<states.Count; i++)
            {
                //对每个状态经过终结符的情况进行判断
                List<string> strings = new List<string>();
                foreach(var symbol in terminals)
                {
                    flag = 0;
                    if (transitions.ContainsKey(i))
                    {
                        foreach (var item in transitions[i])
                        {
                            if (item[0].ToString().Equals(symbol))
                            {
                                strings.Add('S'+item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        if (flag==0)strings.Add('');
                    }
                    else
                    {
                        if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
                        {
                            if(symbol.Equals('#')) strings.Add('acc');
                            else strings.Add('');
                        }
                        else
                        {
                            int index = getproconut(states[i]);
                            strings.Add('r' + index);
                        }
                    }
                }
                //对每个状态经过非终结符的情况进行判断
                foreach(var t in nonterminal)
                {
                    flag = 0;
                    if (transitions.ContainsKey(i))
                    {
                        foreach (var item in transitions[i])
                        {
                            if (item[0].ToString().Equals(t))
                            {
                                strings.Add(item.Substring(1));
                                flag = 1;
                                break;
                            }
                        }
                        if (flag == 0) strings.Add('');
                    }
                    else strings.Add('');
                }
                table.Add(i,strings);
            }
        }

    }
    // 定义一个 LR0_ 类的实例
    class isLR_0_
    {
        // 定义 LR0_ 类的属性
        public Dictionary<char, List<string>> product;
        public bool is_LR = false;
        public isLL_1_ isLL_1_;
        public LR0 LR0;

        // 定义 LR0_ 类的构造函数
        public isLR_0_(string text)
        {
            // 初始化 isLL_1_ 对象
            isLL_1_ = new isLL_1_(text);

            // 如果 isLL_1_ 对象的 is_LL 属性不等于 1，则返回
            if (isLL_1_.is_LL != 1) return;

            // 否则，初始化 LR0 对象
            else LR0 = new LR0(isLL_1_);

            // 当发生移进归约冲突或归约归约冲突时
            is_LR = LR0.judgeLR0();
        }

        // 定义一个方法，返回 LR0 对象
        public LR0 getLR0()
        {
            return LR0;
        }
    }

    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            // 获取输入的文法
            string text = richTextBox1.Text;

            // 创建一个 LR0_ 对象
            isLR_0_ isLR0 = new isLR_0_(text);

            // 判断文法是否为 LR(0) 文法
            if (isLR0.is_LR)
            {
                // 如果是 LR(0) 文法，则显示提示信息
                MessageBox.Show('该文法是 LR(0) 文法！');
            }
            else
            {
                // 如果不是 LR(0) 文法，则显示提示信息
                MessageBox.Show('该文法不是 LR(0) 文法！');
            }
        }

        private void button4_Click(object sender, EventArgs e)
        {
            // 获取输入的文法
            string text = richTextBox1.Text;

            // 创建一个 isLL_1_ 对象
            isLL_1_ isLL1 = new isLL_1_(text);

            // 判断文法是否为 LL(1) 文法
            if (isLL1.is_LL != 1)
            {
                // 如果不是 LL(1) 文法，则显示提示信息并返回
                MessageBox.Show('该文法不是 LL(1) 文法！');
                return;
            }

            // 创建一个 LR0 对象
            LR0 lr0 = new LR0(isLL1);

            // 清空 dataGridView1 中的内容
            dataGridView1.Rows.Clear();

            // 遍历 LR0 对象的状态集合
            foreach (var state in lr0.states)
            {
                // 获取状态编号
                string stateNum = state.Key.ToString();

                // 获取项目集信息
                string itemSet = '';
                foreach (var item in state.Value.items)
                {
                    // 将每个项目信息添加到 itemSet 字符串中
                    itemSet += item.ToString2() + '\n';
                }

                // 将状态编号和项目集信息添加到 dataGridView1 中
                dataGridView1.Rows.Add(stateNum, itemSet);
            }
        }

        private void button5_Click(object sender, EventArgs e)
        {
            // 获取输入的文法
            string text = richTextBox1.Text;

            // 创建一个 isLL_1_ 对象
            isLL_1_ isLL1 = new isLL_1_(text);

            // 判断文法是否为 LL(1) 文法
            if (isLL1.is_LL != 1)
            {
                // 如果不是 LL(1) 文法，则显示提示信息并返回
                MessageBox.Show('该文法不是 LL(1) 文法！');
                return;
            }

            // 创建一个 LR0 对象
            LR0 lr0 = new LR0(isLL1);

            // 清空 dataGridView2 中的内容
            dataGridView2.Rows.Clear();

            // 添加表头
            dataGridView2.Columns.Add('State', 'State');
            foreach (var symbol in lr0.terminals.Union(lr0.nonterminal))
            {
                dataGridView2.Columns.Add(symbol, symbol);
            }

            // 添加表格内容
            foreach (var state in lr0.table)
            {
                // 创建一个新的行
                List<string> row = new List<string>();

                // 添加状态编号
                row.Add(state.Key.ToString());

                // 添加每个符号对应的动作
                row.AddRange(state.Value);

                // 将行添加到 dataGridView2 中
                dataGridView2.Rows.Add(row.ToArray());
            }
        }
    }
}