using System;using SystemCollectionsGeneric;using SystemComponentModel;using SystemData;using SystemDrawing;using SystemLinq;using SystemText;using SystemThreadingTasks;using SystemWindowsForms;using

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

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

    //--------------------预处理
    Dictionary<string, List<string>> production;//产生式
    Dictionary<string, List<string>> firsts;// first集
    Dictionary<string, List<string>> follows;//follow集
    Dictionary<string, List<string>> selects;//select集
    Dictionary<string, Dictionary<string, string>> table;//预测分析表
    List<string> terminals;//终结符
    List<string> nonterminals;//非终结符

    Stack<char> analyseStack;// 分析栈
    Stack<char> inputStack;// 输入栈
    List<string> resultAnalyse;// 分析栈的每一步变化
    List<string> resultInput;// 输入栈的每一步变化
    List<string> resultParse;// 每一步分析的结果，包括推导所用产生式或匹配成功/失败的信息

    private int step = 0; // 记录当前分析到第几步

    private void Form1_Load(object sender, EventArgs e)
    {
        // 初始化
        production = new Dictionary<string, List<string>>();
        firsts = new Dictionary<string, List<string>>();
        follows = new Dictionary<string, List<string>>();
        selects = new Dictionary<string, List<string>>();
        table = new Dictionary<string, Dictionary<string, string>>();
        terminals = new List<string>();
        nonterminals = new List<string>();
        analyseStack = new Stack<char>();
        inputStack = new Stack<char>();
        resultAnalyse = new List<string>();
        resultInput = new List<string>();
        resultParse = new List<string>();

        // 读入文法
        string[] lines = System.IO.File.ReadAllLines(@"grammar.txt");
        foreach (string line in lines)
        {
            string[] parts = line.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            string left = parts[0];
            List<string> right = new List<string>();
            for (int i = 2; i < parts.Length; i++)
            {
                right.Add(parts[i]);
                if (!terminals.Contains(parts[i]) && !nonterminals.Contains(parts[i]))
                {
                    if (i == 2)
                    {
                        nonterminals.Add(parts[i]);
                    }
                    else
                    {
                        terminals.Add(parts[i]);
                    }
                }
            }
            production.Add(left, right);
        }

        // 计算first集
        foreach (string symbol in terminals)
        {
            firsts.Add(symbol, new List<string> { symbol });
        }
        foreach (string symbol in nonterminals)
        {
            firsts.Add(symbol, new List<string>());
        }
        bool updated = true;
        while (updated)
        {
            updated = false;
            foreach (KeyValuePair<string, List<string>> entry in production)
            {
                string left = entry.Key;
                List<string> right = entry.Value;
                foreach (string symbol in right)
                {
                    bool flag = true;
                    foreach (string s in firsts[symbol])
                    {
                        if (!firsts[left].Contains(s))
                        {
                            firsts[left].Add(s);
                            updated = true;
                        }
                    }
                    if (!right.Last().Equals(symbol))
                    {
                        flag = false;
                    }
                    foreach (string s in firsts[symbol])
                    {
                        if (!s.Equals("ε") && !firsts[left].Contains(s))
                        {
                            firsts[left].Add(s);
                            updated = true;
                        }
                    }
                    if (flag && !firsts[left].Contains("ε"))
                    {
                        firsts[left].Add("ε");
                        updated = true;
                    }
                }
            }
        }

        // 计算follow集
        foreach (string symbol in nonterminals)
        {
            follows.Add(symbol, new List<string>());
        }
        follows["S"].Add("$");
        updated = true;
        while (updated)
        {
            updated = false;
            foreach (KeyValuePair<string, List<string>> entry in production)
            {
                string left = entry.Key;
                List<string> right = entry.Value;
                for (int i = 0; i < right.Count; i++)
                {
                    if (nonterminals.Contains(right[i]))
                    {
                        bool flag = true;
                        for (int j = i + 1; j < right.Count; j++)
                        {
                            foreach (string s in firsts[right[j]])
                            {
                                if (!s.Equals("ε") && !follows[right[i]].Contains(s))
                                {
                                    follows[right[i]].Add(s);
                                    updated = true;
                                }
                            }
                            if (!firsts[right[j]].Contains("ε"))
                            {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                        {
                            foreach (string s in follows[left])
                            {
                                if (!follows[right[i]].Contains(s))
                                {
                                    follows[right[i]].Add(s);
                                    updated = true;
                                }
                            }
                        }
                    }
                }
            }
        }

        // 计算select集
        foreach (KeyValuePair<string, List<string>> entry in production)
        {
            string left = entry.Key;
            List<string> right = entry.Value;
            selects.Add(left, new List<string>());
            bool flag = true;
            foreach (string symbol in right)
            {
                foreach (string s in firsts[symbol])
                {
                    if (!s.Equals("ε") && !selects[left].Contains(s))
                    {
                        selects[left].Add(s);
                    }
                }
                if (!firsts[symbol].Contains("ε"))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                foreach (string s in follows[left])
                {
                    if (!selects[left].Contains(s))
                    {
                        selects[left].Add(s);
                    }
                }
            }
        }

        // 构造预测分析表
        foreach (string symbol in nonterminals)
        {
            table.Add(symbol, new Dictionary<string, string>());
            foreach (string s in terminals)
            {
                table[symbol].Add(s, "");
            }
        }
        foreach (KeyValuePair<string, List<string>> entry in production)
        {
            string left = entry.Key;
            List<string> right = entry.Value;
            foreach (string s in selects[left])
            {
                table[left][s] = entry.Key + " → " + String.Join(" ", right);
            }
        }

        // 初始化分析栈和输入栈
        analyseStack.Push('$');
        analyseStack.Push('S');
        inputStack.Push('$');
    }

    private void button1_Click(object sender, EventArgs e)
    {
        // 读入输入串
        string input = textBox1.Text;
        inputStack.Clear();
        foreach (char c in input)
        {
            inputStack.Push(c);
        }
        inputStack.Push('$');

        // 初始化分析栈和输出
        analyseStack.Clear();
        analyseStack.Push('$');
        analyseStack.Push('S');
        resultAnalyse.Clear();
        resultInput.Clear();
        resultParse.Clear();
        step = 0;

        // 开始分析
        while (analyseStack.Count > 0)
        {
            char top = analyseStack.Pop();
            char next = inputStack.Pop();
            resultAnalyse.Add(new string(analyseStack.Reverse().ToArray()));
            resultInput.Add(new string(inputStack.Reverse().ToArray()));
            if (top == next)
            {
                resultParse.Add("匹配 " + top);
            }
            else if (nonterminals.Contains(top.ToString()) && terminals.Contains(next.ToString()) && !table[top.ToString()][next.ToString()].Equals(""))
            {
                string production = table[top.ToString()][next.ToString()];
                resultParse.Add("使用产生式 " + production);
                string[] parts = production.Split(new char[] { ' ', '→' }, StringSplitOptions.RemoveEmptyEntries);
                for (int i = parts.Length - 1; i > 0; i--)
                {
                    analyseStack.Push(parts[i][0]);
                }
            }
            else
            {
                resultParse.Add("错误");
                break;
            }
            step++;
        }

        // 输出分析结果
        button7.Enabled = true;
        button8.Enabled = true;
    }

    private void button7_Click(object sender, EventArgs e)
    {
        if (step < resultAnalyse.Count)
        {
            ListViewItem item = new ListViewItem((step + 1).ToString());
            item.SubItems.Add(resultAnalyse[step]);
            item.SubItems.Add(resultInput[step]);
            item.SubItems.Add(resultParse[step]);
            listView1.Items.Add(item);
            step++;
        }
        else
        {
            MessageBox.Show("输出完毕");
            button7.Enabled = false;
            button8.Enabled = false;
        }
    }

    private void button8_Click(object sender, EventArgs e)
    {
        listView1.Items.Clear();
        for (int i = 0; i < resultAnalyse.Count; i++)
        {
            ListViewItem item = new ListViewItem((i + 1).ToString());
            item.SubItems.Add(resultAnalyse[i]);
            item.SubItems.Add(resultInput[i]);
            item.SubItems.Add(resultParse[i]);
            listView1.Items.Add(item);
        }
        MessageBox.Show("输出完毕");
        button7.Enabled = false;
        button8.Enabled = false;
    }
}