C# 实现 LR0 文法分析器：状态和项目族信息显示示例

实现 LR0 文法分析器的步骤如下：
定义文法规则，包括产生式和终结符号、非终结符号等。
构建项目集规范族，即求出所有可能的项目集。
构建 DFA 状态转移图，即根据项目集规范族构建 DFA 图。
构建 LR 分析表，即根据 DFA 图和文法规则构建 LR 分析表。
使用 LR 分析表进行语法分析。
以下是一个示例的 C# 代码，实现了 LR0 文法分析器，并将状态和项目族信息显示在 dataGridView1 中：
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
    {
        // 定义文法规则
        private string[] productions = new string[] {
            "S->E",
            "E->E+T",
            "E->T",
            "T->T*F",
            "T->F",
            "F->(E)",
            "F->i"
        };

        // 定义终结符号和非终结符号
        private string[] terminals = new string[] { "+", "*", "(", ")", "i", "$" };
        private string[] nonTerminals = new string[] { "S", "E", "T", "F" };

        // 定义 LR 分析表
        private Dictionary<int, Dictionary<string, string>> lrTable = new Dictionary<int, Dictionary<string, string>>();

        // 定义状态和项目族信息
        private List<HashSet<string>> states = new List<HashSet<string>>();
        private List<Dictionary<string, List<string>>> itemSets = new List<Dictionary<string, List<string>>>();

        public Form1()
        {
            InitializeComponent();

            // 构建项目集规范族
            BuildItemSets();

            // 构建 LR 分析表
            BuildLRTable();

            // 显示状态和项目族信息
            for (int i = 0; i < states.Count; i++)
            {
                dataGridView1.Rows.Add(i, string.Join(",", itemSets[i]["kernel"]), string.Join(",", itemSets[i]["closure"]));
            }
        }

        // 构建项目集规范族
        private void BuildItemSets()
        {
            // 初始化第一个项目集
            HashSet<string> startSet = new HashSet<string>();
            startSet.Add("S'->.S");
            states.Add(startSet);

            // 循环遍历所有项目集
            for (int i = 0; i < states.Count; i++)
            {
                Dictionary<string, List<string>> itemSet = new Dictionary<string, List<string>>();
                itemSet.Add("kernel", new List<string>());
                itemSet.Add("closure", new List<string>());

                // 计算 kernel 和 closure
                foreach (string item in states[i])
                {
                    string[] parts = item.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
                    string left = parts[0];
                    string right = parts[1];
                    string dot = ".";
                    int dotIndex = right.IndexOf(dot);

                    // 如果 dot 不在最后一个位置，则计算 kernel 和 closure
                    if (dotIndex < right.Length - 1)
                    {
                        string nextSymbol = right[dotIndex + 1].ToString();
                        string newItem = left + "->" + right.Insert(dotIndex + 2, dot);

                        if (!itemSet["kernel"].Contains(newItem))
                        {
                            itemSet["kernel"].Add(newItem);
                        }

                        HashSet<string> closure = Closure(newItem);
                        foreach (string c in closure)
                        {
                            if (!itemSet["closure"].Contains(c))
                            {
                                itemSet["closure"].Add(c);
                            }
                        }
                    }
                }

                // 如果新的项目集已经存在，则不再添加
                bool exists = false;
                foreach (HashSet<string> s in states)
                {
                    if (s.SetEquals(itemSet["closure"]))
                    {
                        exists = true;
                        break;
                    }
                }

                if (!exists)
                {
                    states.Add(itemSet["closure"]);
                }

                itemSets.Add(itemSet);
            }
        }

        // 计算 closure
        private HashSet<string> Closure(string item)
        {
            HashSet<string> closure = new HashSet<string>();
            closure.Add(item);

            string[] parts = item.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
            string left = parts[0];
            string right = parts[1];
            string dot = ".";
            int dotIndex = right.IndexOf(dot);

            // 如果 dot 在最后一个位置，则不需要计算 closure
            if (dotIndex == right.Length - 1)
            {
                return closure;
            }

            string nextSymbol = right[dotIndex + 1].ToString();

            // 如果 nextSymbol 是终结符号，则不需要计算 closure
            if (terminals.Contains(nextSymbol))
            {
                return closure;
            }

            // 计算 closure
            foreach (string p in productions)
            {
                parts = p.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
                left = parts[0];
                right = parts[1];

                if (left == nextSymbol)
                {
                    string newItem = left + "->." + right;
                    closure.Add(newItem);
                    HashSet<string> subClosure = Closure(newItem);
                    foreach (string c in subClosure)
                    {
                        if (!closure.Contains(c))
                        {
                            closure.Add(c);
                        }
                    }
                }
            }

            return closure;
        }

        // 构建 LR 分析表
        private void BuildLRTable()
        {
            // 初始化 LR 分析表
            for (int i = 0; i < states.Count; i++)
            {
                lrTable.Add(i, new Dictionary<string, string>());
                foreach (string t in terminals)
                {
                    lrTable[i].Add(t, "");
                }
                lrTable[i].Add("$", "");
            }

            // 填充 LR 分析表
            for (int i = 0; i < states.Count; i++)
            {
                foreach (string item in states[i])
                {
                    string[] parts = item.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
                    string left = parts[0];
                    string right = parts[1];
                    string dot = ".";
                    int dotIndex = right.IndexOf(dot);

                    // 如果 dot 在最后一个位置，则需要处理规约
                    if (dotIndex == right.Length - 1)
                    {
                        foreach (string t in terminals)
                        {
                            if (lrTable[i][t] == "")
                            {
                                lrTable[i][t] = "r" + Array.IndexOf(productions, item);
                            }
                        }

                        if (lrTable[i]["$"] == "")
                        {
                            lrTable[i]["$"] = "r" + Array.IndexOf(productions, item);
                        }
                    }
                    else
                    {
                        string nextSymbol = right[dotIndex + 1].ToString();

                        // 如果 nextSymbol 是终结符号，则需要处理移进
                        if (terminals.Contains(nextSymbol))
                        {
                            HashSet<string> nextSet = new HashSet<string>();
                            foreach (string s in itemSets[i]["closure"])
                            {
                                parts = s.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
                                left = parts[0];
                                right = parts[1];
                                dot = ".";
                                dotIndex = right.IndexOf(dot);

                                if (dotIndex < right.Length - 1 && right[dotIndex + 1].ToString() == nextSymbol)
                                {
                                    string newItem = left + "->" + right.Insert(dotIndex + 2, dot);
                                    nextSet.Add(newItem);
                                }
                            }

                            int nextIndex = -1;
                            for (int j = 0; j < states.Count; j++)
                            {
                                if (states[j].SetEquals(nextSet))
                                {
                                    nextIndex = j;
                                    break;
                                }
                            }

                            if (nextIndex != -1)
                            {
                                if (lrTable[i][nextSymbol] == "")
                                {
                                    lrTable[i][nextSymbol] = "s" + nextIndex;
                                }
                                else
                                {
                                    string action = lrTable[i][nextSymbol];
                                    if (action[0] == 's')
                                    {
                                        int state = int.Parse(action.Substring(1));
                                        if (state != nextIndex)
                                        {
                                            MessageBox.Show("Error: Conflict in LR table.");
                                        }
                                    }
                                    else if (action[0] == 'r')
                                    {
                                        int production = int.Parse(action.Substring(1));
                                        if (production != Array.IndexOf(productions, item))
                                        {
                                            MessageBox.Show("Error: Conflict in LR table.");
                                        }
                                    }
                                }
                            }
                        }
                        else // 如果 nextSymbol 是非终结符号，则需要处理 goto
                        {
                            HashSet<string> nextSet = new HashSet<string>();
                            foreach (string s in itemSets[i]["closure"])
                            {
                                parts = s.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
                                left = parts[0];
                                right = parts[1];
                                dot = ".";
                                dotIndex = right.IndexOf(dot);

                                if (dotIndex < right.Length - 1 && right[dotIndex + 1].ToString() == nextSymbol)
                                {
                                    string newItem = left + "->" + right.Insert(dotIndex + 2, dot);
                                    nextSet.Add(newItem);
                                }
                            }

                            int nextIndex = -1;
                            for (int j = 0; j < states.Count; j++)
                            {
                                if (states[j].SetEquals(nextSet))
                                {
                                    nextIndex = j;
                                    break;
                                }
                            }

                            if (nextIndex != -1)
                            {
                                if (lrTable[i][nextSymbol] == "")
                                {
                                    lrTable[i][nextSymbol] = nextIndex.ToString();
                                }
                                else
                                {
                                    string action = lrTable[i][nextSymbol];
                                    if (action[0] == 's')
                                    {
                                        int state = int.Parse(action.Substring(1));
                                        if (state != nextIndex)
                                        {
                                            MessageBox.Show("Error: Conflict in LR table.");
                                        }
                                    }
                                    else if (action[0] == 'r')
                                    {
                                        int production = int.Parse(action.Substring(1));
                                        if (production != Array.IndexOf(productions, item))
                                        {
                                            MessageBox.Show("Error: Conflict in LR table.");
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}