C#实现LR(0)分析器：判别文法与生成项目族信息

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;

namespace LR0Parser
{
    public partial class Form1 : Form
    {
        private List<string> productions = new List<string>(); // 存储文法产生式
        private List<string> symbols = new List<string>(); // 存储文法符号
        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表

        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)//判别LR0文法
        {
            // 读取文法产生式
            string[] productionsArr = richTextBox1.Text.Split(new string[] { '\r\n' }, StringSplitOptions.RemoveEmptyEntries);
            productions.AddRange(productionsArr);

            // 获取文法符号
            foreach (string production in productions)
            {
                string[] parts = production.Split(' ');
                foreach (string part in parts)
                {
                    if (!symbols.Contains(part))
                    {
                        symbols.Add(part);
                    }
                }
            }

            // 初始化状态0
            string initialState = '0';
            List<string> initialItemset = new List<string>();
            initialItemset.Add(productions[0] + ' .'); // 初始项目
            itemsets.Add(string.Join('\r\n', initialItemset));
            states.Add(initialState);

            // 生成项目族
            BuilditemFamily();

            // 生成GOTO表和ACTION表
            BuildTables();

            // 显示状态和项目族信息
            // 添加第一列
            listView1.Columns.Add('', 50);

            // 添加列名
            listView1.Columns.Add('状态', 50);
            listView1.Columns.Add('项目集信息', 50);

            // 添加数据
            for (int i = 0; i < states.Count; i++)
            {
                ListViewItem item = new ListViewItem();
                item.SubItems[0].Text = (i + 1).ToString();
                item.SubItems.Add(states[i]);
                item.SubItems.Add(itemsets[i]);
                listView1.Items.Add(item);
            }
        }

        private void BuilditemFamily()
        {
            int index = 0;
            while (index < itemsets.Count)
            {
                // 获取当前项目集的所有项目
                List<string> itemset = itemsets[index].Split(new string[] { '\r\n' }, StringSplitOptions.RemoveEmptyEntries).ToList();

                // 获取当前项目集中所有的非终结符
                List<string> nonterminals = new List<string>();
                foreach (string item in itemset)
                {
                    string[] parts = item.Split(' ');
                    for (int i = 0; i < parts.Length; i++)
                    {
                        if (i < parts.Length - 1 && !symbols.Contains(parts[i]) && !nonterminals.Contains(parts[i]))
                        {
                            nonterminals.Add(parts[i]);
                        }
                    }
                }

                // 对每个非终结符进行扩展
                foreach (string nonterminal in nonterminals)
                {
                    List<string> newItemset = new List<string>();
                    foreach (string item in itemset)
                    {
                        string[] parts = item.Split(' ');
                        for (int i = 0; i < parts.Length - 1; i++)
                        {
                            if (parts[i] == nonterminal)
                            {
                                string newItem = string.Join(' ', parts.Take(i)) + ' ' + nonterminal + ' .' + string.Join(' ', parts.Skip(i + 1));
                                if (!newItemset.Contains(newItem))
                                {
                                    newItemset.Add(newItem);
                                }
                            }
                        }
                    }

                    // 计算新的项目集
                    List<string> closure = Closure(newItemset);
                    string newState = Goto(index, nonterminal);
                    if (!states.Contains(newState))
                    {
                        states.Add(newState);
                        itemsets.Add(string.Join('\r\n', closure));
                    }
                }

                index++;
            }
        }

        private List<string> Closure(List<string> itemset)
        {
            List<string> closure = new List<string>();
            closure.AddRange(itemset);

            int index = 0;
            while (index < closure.Count)
            {
                string[] parts = closure[index].Split(' ');
                for (int i = 0; i < parts.Length - 1; i++)
                {
                    if (parts[i] == '.')
                    {
                        string nextSymbol = parts[i + 1];
                        if (symbols.Contains(nextSymbol))
                        {
                            // 扩展项目
                            foreach (string production in productions)
                            {
                                string[] productionParts = production.Split(' ');
                                if (productionParts[0] == nextSymbol)
                                {
                                    string newItem = nextSymbol + ' . ' + string.Join(' ', productionParts.Skip(1));
                                    if (!closure.Contains(newItem))
                                    {
                                        closure.Add(newItem);
                                    }
                                }
                            }
                        }
                    }
                }

                index++;
            }

            return closure;
        }

        private string Goto(int index, string symbol)
        {
            List<string> itemset = itemsets[index].Split(new string[] { '\r\n' }, StringSplitOptions.RemoveEmptyEntries).ToList();
            List<string> newItemset = new List<string>();
            foreach (string item in itemset)
            {
                string[] parts = item.Split(' ');
                for (int i = 0; i < parts.Length - 1; i++)
                {
                    if (parts[i] == '.' && parts[i + 1] == symbol)
                    {
                        string newItem = string.Join(' ', parts.Take(i)) + ' ' + symbol + ' .' + string.Join(' ', parts.Skip(i + 2));
                        if (!newItemset.Contains(newItem))
                        {
                            newItemset.Add(newItem);
                        }
                    }
                }
            }

            List<string> closure = Closure(newItemset);
            return string.Join(',', closure);
        }

        private void BuildTables()
        {
            for (int i = 0; i < states.Count; i++)
            {
                List<string> itemset = itemsets[i].Split(new string[] { '\r\n' }, StringSplitOptions.RemoveEmptyEntries).ToList();
                foreach (string item in itemset)
                {
                    string[] parts = item.Split(' ');
                    for (int j = 0; j < parts.Length - 1; j++)
                    {
                        if (parts[j] == '.')
                        {
                            string nextSymbol = parts[j + 1];
                            if (symbols.Contains(nextSymbol))
                            {
                                // GOTO表项
                                string newState = Goto(i, nextSymbol);
                                if (!gotoTable.ContainsKey(states[i]))
                                {
                                    gotoTable.Add(states[i], new List<string>());
                                }
                                gotoTable[states[i]].Add(newState + ':' + nextSymbol);
                            }
                            else
                            {
                                // ACTION表项
                                string action;
                                if (nextSymbol == '$')
                                {
                                    action = 'acc';
                                }
                                else
                                {
                                    action = 's' + states.IndexOf(Goto(i, nextSymbol));
                                }

                                if (!actionTable.ContainsKey(states[i]))
                                {
                                    actionTable.Add(states[i], new List<string>());
                                }
                                actionTable[states[i]].Add(action + ':' + nextSymbol);
                            }
                        }
                    }
                }
            }
        }

        private void button4_Click(object sender, EventArgs e)//生成项目族信息
        {
            BuilditemFamily();

            // 显示状态和项目族信息
            // 添加第一列
            listView1.Columns.Add('', 50);

            // 添加列名
            listView1.Columns.Add('状态', 50);
            listView1.Columns.Add('项目集信息', 50);

            // 添加数据
            for (int i = 0; i < states.Count; i++)
            {
                ListViewItem item = new ListViewItem();
                item.SubItems[0].Text = (i + 1).ToString();
                item.SubItems.Add(states[i]);
                item.SubItems.Add(itemsets[i]);
                listView1.Items.Add(item);
            }
        }
    }
}