LR(0) 文法分析器实现

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Diagnostics;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.Header;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.ListView;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.Status;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.ToolBar;

namespace byyljxfzxt
{
    public partial class Form5 : Form
    {
        public Form5()
        {
            InitializeComponent();
        }

        //--------------------预处理
        private List<string> productions = new List<string>(); // 存储文法产生式
        private List<string> symbols = new List<string>(); // 存储文法符号
        List<string> terminals;//终结符
        List<string> nonterminals;//非终结符
        private List<string> states = new List<string>(); // 存储状态
        private List<string> itemsets = new List<string>(); // 存储项目族
        private Dictionary<string, List<string>> gotoTable = new Dictionary<string, List<string>>(); // 存储GOTO表
        private Dictionary<string, List<string>> actionTable = new Dictionary<string, List<string>>(); // 存储ACTION表

        private void button2_Click(object sender, EventArgs e)//判别LR0文法
        {
            string inputGrammar = textBox1.Text;
            isLR_0_ lr0 = new isLR_0_(inputGrammar);
            if (lr0.is_LR)
            {
                MessageBox.Show('该文法是LR(0)文法！');
                LR0 lr0Analyzer = lr0.getLR0();
                // 获取状态和项目集信息
                foreach (var state in lr0Analyzer.states)
                {
                    string itemSetInfo = '状态 ' + state.Key + ' | ' + string.Join('\n', state.Value.items.Select(item => item.ToString()));
                    itemsets.Add(itemSetInfo);
                }
                // 打印项目族信息
                richTextBox1.Text = string.Join('\n\n', itemsets);
                // 打印分析表
                foreach (var entry in lr0Analyzer.table)
                {
                    string stateRow = '状态 ' + entry.Key + ' | ' + string.Join(' | ', entry.Value);
                    states.Add(stateRow);
                }
                richTextBox2.Text = string.Join('\n', states);
            }
            else
            {
                MessageBox.Show('该文法不是LR(0)文法！');
            }
        }

        private void button4_Click(object sender, EventArgs e)//生成项目族信息
        {
            string inputGrammar = textBox1.Text;
            isLR_0_ lr0 = new isLR_0_(inputGrammar);
            if (lr0.is_LR)
            {
                LR0 lr0Analyzer = lr0.getLR0();
                // 获取状态和项目集信息
                foreach (var state in lr0Analyzer.states)
                {
                    string itemSetInfo = '状态 ' + state.Key + ' | ' + string.Join('\n', state.Value.items.Select(item => item.ToString()));
                    itemsets.Add(itemSetInfo);
                }
                // 打印项目族信息
                richTextBox1.Text = string.Join('\n\n', itemsets);
            }
            else
            {
                MessageBox.Show('该文法不是LR(0)文法！');
            }
        }

        private void button5_Click(object sender, EventArgs e)//构造LR分析表
        {
            string inputGrammar = textBox1.Text;
            isLR_0_ lr0 = new isLR_0_(inputGrammar);
            if (lr0.is_LR)
            {
                LR0 lr0Analyzer = lr0.getLR0();
                // 打印分析表
                foreach (var entry in lr0Analyzer.table)
                {
                    string stateRow = '状态 ' + entry.Key + ' | ' + string.Join(' | ', entry.Value);
                    states.Add(stateRow);
                }
                richTextBox2.Text = string.Join('\n', states);
            }
            else
            {
                MessageBox.Show('该文法不是LR(0)文法！');
            }
        }

    }
}

// 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);
        }
    }

}

// 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);
        if (LL1Item.is_LL == 1)
        {
            this.is_LL = 1;
            product = LL1Item.product;
        }
    }
}

// LL(1) 项目类
class LL1Item
{
    public Dictionary<string, List<string>> product;
    public List<string> final;//终结符集合
    public List<string> nofinal;//非终结符集合
    public int is_LL = 0;
    public LL1Item(string text)
    {
        product = new Dictionary<string, List<string>>();
        final = new List<string>();
        nofinal = new List<string>();
        List<string> strings = new List<string>();
        //将输入的字符串进行格式化，将产生式分割成不同的字符串
        foreach (var item in text.Split(' '))
        {
            if (item.IndexOf('->') != -1)
            {
                string[] pro = item.Split('->');
                if (!nofinal.Contains(pro[0])) nofinal.Add(pro[0]);
                if (!product.ContainsKey(pro[0])) product.Add(pro[0], new List<string>());
                product[pro[0]].Add(pro[1]);
                //分割产生式右部
                foreach (var item2 in pro[1].Split(','))
                {
                    if (!nofinal.Contains(item2) && !final.Contains(item2))
                    {
                        if (item2 != '')
                            final.Add(item2);
                    }
                }
            }
        }
        if (!final.Contains('#')) final.Add('#');
        //first集的计算
        if (FirstSet(product, final, nofinal) == 1) is_LL = 1;
    }
    //计算First集
    private int FirstSet(Dictionary<string, List<string>> product, List<string> final, List<string> nofinal)
    {
        Dictionary<string, List<string>> firstSet = new Dictionary<string, List<string>>();
        foreach (var item in nofinal)
        {
            if (!firstSet.ContainsKey(item))
            {
                firstSet.Add(item, new List<string>());
                foreach (var item2 in product[item])
                {
                    //如果产生式右部为空，则将空串加入到first集中
                    if (item2 == '')
                    {
                        if (!firstSet[item].Contains('')) firstSet[item].Add('');
                    }
                    else
                    {
                        //如果产生式右部第一个符号是非终结符，则递归计算其first集
                        if (nofinal.Contains(item2[0].ToString()))
                        {
                            //获取该非终结符的first集
                            List<string> temp = new List<string>(firstSet[item2[0].ToString()]);
                            //将该非终结符的first集加入到当前非终结符的first集中
                            foreach (var item3 in temp)
                            {
                                if (!firstSet[item].Contains(item3)) firstSet[item].Add(item3);
                            }
                            //如果该非终结符的first集中包含空串，则将该非终结符之后的符号的first集加入到当前非终结符的first集中
                            if (temp.Contains(''))
                            {
                                for (int i = 1; i < item2.Length; i++)
                                {
                                    if (nofinal.Contains(item2[i].ToString()))
                                    {
                                        List<string> temp2 = new List<string>(firstSet[item2[i].ToString()]);
                                        foreach (var item4 in temp2)
                                        {
                                            if (!firstSet[item].Contains(item4)) firstSet[item].Add(item4);
                                        }
                                        if (temp2.Contains('')) continue;
                                        else break;
                                    }
                                    else
                                    {
                                        if (!firstSet[item].Contains(item2[i].ToString())) firstSet[item].Add(item2[i].ToString());
                                        break;
                                    }
                                }
                            }
                        }
                        else
                        {
                            if (!firstSet[item].Contains(item2[0].ToString())) firstSet[item].Add(item2[0].ToString());
                        }
                    }
                }
            }
        }
        //判断是否为LL(1)文法，遍历所有产生式，如果一个非终结符的first集中包含两个相同的符号，则不是LL(1)文法
        foreach (var item in product)
        {
            foreach (var item2 in product[item.Key])
            {
                foreach (var item3 in product[item.Key])
                {
                    if (item2 != item3)
                    {
                        List<string> temp1 = new List<string>(firstSet[item.Key]);
                        List<string> temp2 = new List<string>(firstSet[item.Key]);
                        if (temp1.Contains(item2[0].ToString()) && temp2.Contains(item3[0].ToString()) && item2[0].ToString() == item3[0].ToString()) return 0;
                    }
                }
            }
        }
        return 1;
    }
}