LR(0) 文法分析器：判别、项目族生成和 LR 分析表构建

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

//  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);
        is_LL = LL1Item.judgeLL1();
        product = LL1Item.product;
    }
}

// LL(1)分析器项目类
class LL1Item
{
    public List<string> final; // 终结符集合
    public List<string> nofinal; // 非终结符集合
    public Dictionary<string, List<string>> product;// 产生式规则
    public Dictionary<string, Dictionary<string, List<string>>> FirstSet;//first集
    public Dictionary<string, Dictionary<string, List<string>>> FollowSet;//follow集

    public LL1Item(String text)
    {
        final = new List<string>();
        nofinal = new List<string>();
        product = new Dictionary<string, List<string>>();
        FirstSet = new Dictionary<string, Dictionary<string, List<string>>>();
        FollowSet = new Dictionary<string, Dictionary<string, List<string>>>();
        string[] textline = text.Split('
');
        foreach (string line in textline)
        {
            if (line.Equals('') || line.StartsWith('//')) continue;
            string[] textline2 = line.Split(new char[] { ' ', '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
            if (!nofinal.Contains(textline2[0])) nofinal.Add(textline2[0]);
            for (int i = 1; i < textline2.Length; i++)
            {
                if (!final.Contains(textline2[i]) && !nofinal.Contains(textline2[i]))
                {
                    if (!textline2[i].Equals('')) final.Add(textline2[i]);
                }
            }
            if (!product.ContainsKey(textline2[0])) product.Add(textline2[0], new List<string>());
            string temp = string.Join(' ', textline2.Skip(1));
            product[textline2[0]].Add(temp);
        }
        createFirstSet();
        createFollowSet();
    }

    //构造first集
    private void createFirstSet()
    {
        foreach (var item in product)
        {
            FirstSet.Add(item.Key, new Dictionary<string, List<string>>());
            foreach (var item2 in item.Value)
            {
                FirstSet[item.Key].Add(item2, new List<string>());
                FirstSet[item.Key][item2] = getFirstSet(item2);
            }
        }
    }

    private List<string> getFirstSet(string text)
    {
        List<string> result = new List<string>();
        string[] temp = text.Split(' ');
        if (final.Contains(temp[0]))
        {
            result.Add(temp[0]);
            return result;
        }
        else if (nofinal.Contains(temp[0]))
        {
            foreach (var item in product[temp[0]])
            {
                if (item.Equals(''))
                {
                    result.Add('');
                    continue;
                }
                if (final.Contains(item[0].ToString()))
                {
                    result.Add(item[0].ToString());
                    continue;
                }
                else
                {
                    result.AddRange(getFirstSet(item));
                }
            }
        }
        return result;
    }

    //构造follow集
    private void createFollowSet()
    {
        foreach (var item in product)
        {
            FollowSet.Add(item.Key, new Dictionary<string, List<string>>());
            foreach (var item2 in item.Value)
            {
                FollowSet[item.Key].Add(item2, new List<string>());
                FollowSet[item.Key][item2] = getFollowSet(item2, item.Key);
            }
        }
    }

    private List<string> getFollowSet(string text, string start)
    {
        List<string> result = new List<string>();
        string[] temp = text.Split(' ');
        if (temp.Length == 1 && start.Equals(temp[0]))
        {
            result.Add('#');
        }
        for (int i = 0; i < temp.Length; i++)
        {
            if (nofinal.Contains(temp[i]))
            {
                if (i == temp.Length - 1)
                {
                    result.AddRange(FollowSet[start][text]);
                }
                else
                {
                    List<string> tempResult = new List<string>();
                    if (final.Contains(temp[i + 1]))
                    {
                        tempResult.Add(temp[i + 1]);
                    }
                    else
                    {
                        tempResult.AddRange(getFirstSet(string.Join(' ', temp.Skip(i + 1))));
                        if (tempResult.Contains(''))
                        {
                            tempResult.Remove('');
                            tempResult.AddRange(getFollowSet(text, start));
                        }
                    }
                    result.AddRange(tempResult);
                }
            }
        }
        result = result.Distinct().ToList();
        return result;
    }

    // 判断是否为 LL(1) 文法
    public int judgeLL1()
    {
        foreach (var item in product)
        {
            foreach (var item2 in item.Value)
            {
                if (FirstSet[item.Key][item2].Intersect(FollowSet[item.Key][item2]).Any())
                {
                    return 0;
                }
            }
        }
        return 1;
    }
}

//  LR(0)分析器类
class isLR_0_
{
    public Dictionary<char, List<string>> product;
    public bool is_LR = false;
    public isLL_1_ isLL_1_;
    public LR0 LR0;

    public isLR_0_(String text)
    {
        isLL_1_ = new isLL_1_(text);
        if (isLL_1_.is_LL != 1) return;
        else LR0 = new LR0(isLL_1_);
        //当发生移进归约冲突或归约归约冲突时
        is_LR = LR0.judgeLR0();
    }

    public LR0 getLR0()
    {
        return LR0;
    }
}

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

}

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

    private void button2_Click(object sender, EventArgs e)
    {
        string text = richTextBox1.Text;
        isLR_0_ isLR_0_ = new isLR_0_(text);
        if (isLR_0_.is_LR)
        {
            MessageBox.Show('该文法是LR(0)文法');
        }
        else
        {
            MessageBox.Show('该文法不是LR(0)文法');
        }
    }

    private void button4_Click(object sender, EventArgs e)
    {
        string text = richTextBox1.Text;
        isLL_1_ isLL_1_ = new isLL_1_(text);
        if (isLL_1_.is_LL != 1)
        {
            MessageBox.Show('该文法不是LL(1)文法，无法生成项目族信息');
            return;
        }
        LR0 LR0 = new LR0(isLL_1_);
        Dictionary<int, List<string>> itemFamilies = new Dictionary<int, List<string>>();
        foreach (var item in LR0.states)
        {
            List<string> itemList = new List<string>();
            foreach (var subItem in item.Value.items)
            {
                itemList.Add(subItem.ToString2());
            }
            itemFamilies.Add(item.Key, itemList);
        }
        dataGridView1.DataSource = new BindingSource(itemFamilies, null);
        dataGridView1.Columns[0].HeaderText = '状态';
        dataGridView1.Columns[1].HeaderText = '项目族信息';
    }

    private void button5_Click(object sender, EventArgs e)
    {
        string text = richTextBox1.Text;
        isLL_1_ isLL_1_ = new isLL_1_(text);
        if (isLL_1_.is_LL != 1)
        {
            MessageBox.Show('该文法不是LL(1)文法，无法构造LR分析表');
            return;
        }
        LR0 LR0 = new LR0(isLL_1_);
        Dictionary<int, Dictionary<string, string>> lrTable = new Dictionary<int, Dictionary<string, string>>();
        foreach (var state in LR0.table)
        {
            Dictionary<string, string> row = new Dictionary<string, string>();
            for (int i = 0; i < LR0.terminals.Count + LR0.nonterminal.Count; i++)
            {
                if (i < LR0.terminals.Count)
                {
                    row.Add(LR0.terminals[i], state.Value[i]);
                }
                else
                {
                    row.Add(LR0.nonterminal[i - LR0.terminals.Count], state.Value[i]);
                }
            }
            lrTable.Add(state.Key, row);
        }
        dataGridView2.DataSource = new BindingSource(lrTable, null);
        dataGridView2.Columns[0].HeaderText = '状态';
        foreach (var terminal in LR0.terminals)
        {
            dataGridView2.Columns[terminal].HeaderText = terminal;
        }
        foreach (var nonterminal in LR0.nonterminal)
        {
            dataGridView2.Columns[nonterminal].HeaderText = nonterminal;
        }
    }
}