C# 单步分析句子 - LL(1) 语法分析器

//--------------------预处理
Dictionary<string, List<string>> production;
Dictionary<string, List<string>> firsts;
Dictionary<string, List<string>> follows;
Dictionary<string, List<string>> selects;
Dictionary<string, Dictionary<string, string>> table;
List<string> terminals;
List<string> nonterminals;
Stack<char> analyse; // 分析栈
Stack<char> input; // 输入栈
List<string> result_analys; // 分析栈的每一步变化
List<string> result_input; // 输入栈的每一步变化
List<string> result_parse; // 每一步分析的结果，包括推导所用产生式或匹配成功/失败的信息

public class analyse_sentence
{
    public string text; // 输入句子
    public Dictionary<string, List<string>> select; // 选择集
    public Stack<char> analyse; // 分析栈
    public Stack<char> input; // 输入栈
    public List<string> result_analys; // 分析栈的每一步变化
    public List<string> result_input; // 输入栈的每一步变化
    public List<string> result_parse; // 每一步分析的结果，包括推导所用产生式或匹配成功/失败的信息

    public analyse_sentence(string text, Dictionary<string, List<string>> select)
    {
        this.text = text;
        this.select = select;
        this.analyse = new Stack<char>();
        input = new Stack<char>();
        result_analys = new List<string>();
        result_input = new List<string>();
        result_parse = new List<string>();
        analyseresult();
    }

    void analyseresult()
    {
        var selects = select.getselects(); // 获取选择集
        analyse.Push('#');
        analyse.Push(selects.First().Key[0]); // 将起始符号压入分析栈
        input.Push('#');
        for (int i = text.Length - 1; i >= 0; i--)
            input.Push(text[i]); // 将输入句子倒序压入输入栈
        result_analys.Add(analyse.getString());
        result_input.Add(input.getString());

        while (true)
        {
            // 如果分析栈栈顶元素为终结符
            if (IsTerminal(analyse.Peek()))
            {
                // 当两个栈都只剩下#时，说明匹配成功
                if (analyse.Peek() == input.Peek() && analyse.Count == 1 && input.Count == 1)
                {
                    result_parse.Add('成功'.ToString());
                    return;
                }
                if (analyse.Peek() == input.Peek())
                {
                    result_parse.Add(''' + analyse.Peek() + ''' + "匹配");
                    analyse.Pop();
                    input.Pop();
                    result_analys.Add(analyse.getString());
                    result_input.Add(input.getString());
                    continue;
                }
                else
                {
                    result_parse.Add('失败'.ToString());
                    return;
                }
            }

            int flag = 0;
            string nofinal = analyse.Peek().ToString();
            string final = input.Peek().ToString();
            foreach (var parse in selects[nofinal])
            {
                if (parse.Value.Contains(final))
                {
                    result_parse.Add(nofinal + "->" + parse.Key);
                    analyse.Pop();
                    // 当推出的产生式不为空时，对分析栈进行添加
                    if (!parse.Key.Equals("#"))
                    {
                        addanalyse(parse.Key);
                    }
                    result_analys.Add(analyse.getString());
                    result_input.Add(input.getString());
                    flag = 1; break;
                }
            }
            // 说明该非终结符中没有可推导出该终结符的产生式
            if (flag == 0)
            {
                result_parse.Add('失败'.ToString());
                return;
            }
        }
    }

    void addanalyse(string t)
    {
        for (int i = t.Length - 1; i >= 0; i--)
        {
            analyse.Push(t[i]);
        }
    }

    static bool IsTerminal(char symbol)
    {
        return !char.IsUpper(symbol);
    }

    public string getString()
    {
        string result = string.Empty;
        foreach (char c in analyse)
        {
            result += c;
        }
        return result;
    }
}

//--------------------单步分析
private void button8_Click(object sender, EventArgs e)
{
    // 判断是否已经初始化分析器
    if (production == null)
    {
        MessageBox.Show("请先进行文法分析");
        return;
    }

    // 判断输入是否为空
    if (string.IsNullOrWhiteSpace(textBox1.Text))
    {
        MessageBox.Show("输入为空，分析失败");
        return;
    }

    // 初始化分析器
    analyse_sentence analyser = new analyse_sentence(textBox1.Text, selects);

    // 获取分析器结果
    List<string> analys = analyser.result_analys; // 分析栈变化
    List<string> inputs = analyser.result_input; // 输入栈变化
    List<string> parses = analyser.result_parse; // 推导过程

    // 如果listView4中已有内容，则从上次分析的位置继续显示
    int startIndex = listView4.Items.Count;

    // 将每一步分析结果显示在listView4中
    for (int i = startIndex; i < analys.Count; i++)
    {
        ListViewItem item = new ListViewItem((i + 1).ToString());
        item.SubItems.Add(analys[i]);
        item.SubItems.Add(inputs[i]);
        item.SubItems.Add(parses[i]);
        listView4.Items.Add(item);
    }
}

//--------------------初始化
private void button7_Click(object sender, EventArgs e)
{
    // 清空listView4中的内容
    listView4.Columns.Clear();
    listView4.Items.Clear();
    listView4.View = View.Details;

    // 添加列标题
    listView4.Columns.Add("步骤", 60, HorizontalAlignment.Center);
    listView4.Columns.Add("分析串", 60, HorizontalAlignment.Center);
    listView4.Columns.Add("剩余输入串", 80, HorizontalAlignment.Center);
    listView4.Columns.Add("推导所用产生式或匹配", 150, HorizontalAlignment.Center);

    // 禁用“单步分析”和“自动分析”按钮
    button8.Enabled = false;
    button9.Enabled = false;
}