LR(0) 项目族生成算法实现

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 void button4_Click(object sender, EventArgs e)//生成项目族信息
{
    BuilditemFamily();

    // 显示状态和项目族信息

    listView1.Columns.Clear();
    listView1.Items.Clear();
    listView1.View = View.Details;
    
    // 添加列名
    listView1.Columns.Add('状态', 150);   
    listView1.Columns.Add('项目集信息', 300);

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

    listView1.GridLines = true;

}

private void BuilditemFamily()
{
    // 生成文法符号集合
    foreach (string production in productions)
    {
        string[] productionParts = production.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        symbols.Add(productionParts[0]);
        for (int i = 1; i < productionParts.Length; i++)
        {
            if (!symbols.Contains(productionParts[i]))
            {
                symbols.Add(productionParts[i]);
            }
        }
    }

    // 生成初始项目集
    HashSet<string> initialItemSet = new HashSet<string>();
    initialItemSet.Add(''' + productions[0].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)[0] + '' -> .'' + productions[0].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)[1] + ''');

    // 构造CLOSURE函数
    Func<HashSet<string>, HashSet<string>> CLOSURE = null;
    CLOSURE = (I) =>
    {
        HashSet<string> J = new HashSet<string>(I);
        while (true)
        {
            int count = J.Count;
            foreach (string item in new HashSet<string>(J))
            {
                if (item.IndexOf('.') < item.Length - 1 && symbols.Contains(item.Substring(item.IndexOf('.') + 1, 1)))
                {
                    string symbol = item.Substring(item.IndexOf('.') + 1, 1);
                    foreach (string production in productions)
                    {
                        string[] productionParts = production.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                        if (productionParts[0] == symbol)
                        {
                            string newItem = ''' + symbol + '' -> .'' + string.Join(' ', productionParts.Skip(1)) + ''';
                            if (!J.Contains(newItem))
                            {
                                J.Add(newItem);
                            }
                        }
                    }
                }
            }
            if (J.Count == count)
            {
                break;
            }
        }
        return J;
    };

    // 构造GOTO函数
    Func<HashSet<string>, string, HashSet<string>> GOTO = (I, X) =>
    {
        HashSet<string> J = new HashSet<string>();
        foreach (string item in I)
        {
            if (item.IndexOf('.') < item.Length - 1 && item.Substring(item.IndexOf('.') + 1, 1) == X)
            {
                J.Add(item.Substring(0, item.IndexOf('.') + 1) + item.Substring(item.IndexOf('.') + 2));
            }
        }
        return CLOSURE(J);
    };

    // 构造项目族
    Dictionary<string, HashSet<string>> itemFamily = new Dictionary<string, HashSet<string>>();
    string startSymbol = productions[0].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)[0];
    string initialState = 'I0';
    itemFamily.Add(initialState, CLOSURE(initialItemSet));
    states.Add(initialState);
    Queue<string> stateQueue = new Queue<string>();
    stateQueue.Enqueue(initialState);
    while (stateQueue.Count > 0)
    {
        string currentState = stateQueue.Dequeue();
        Dictionary<string, HashSet<string>> transitions = new Dictionary<string, HashSet<string>>();
        foreach (string item in itemFamily[currentState])
        {
            if (item.IndexOf('.') < item.Length - 1)
            {
                string symbol = item.Substring(item.IndexOf('.') + 1, 1);
                HashSet<string> nextState = GOTO(itemFamily[currentState], symbol);
                if (nextState.Count > 0)
                {
                    string nextStateName = 'I' + itemsets.Count.ToString();
                    if (!itemFamily.ContainsKey(nextStateName))
                    {
                        stateQueue.Enqueue(nextStateName);
                        itemFamily.Add(nextStateName, nextState);
                        states.Add(nextStateName);
                    }
                    if (!transitions.ContainsKey(symbol))
                    {
                        transitions.Add(symbol, new HashSet<string>());
                    }
                    transitions[symbol] = nextState;
                }
            }
        }
        foreach (string symbol in transitions.Keys)
        {
            string nextStateName = itemFamily.First(x => x.Value.SetEquals(transitions[symbol])).Key;
            if (!symbols.Contains(symbol))
            {
                symbols.Add(symbol);
            }
            itemsets.Add($'GOTO({currentState}, {symbol}) = {nextStateName}');
        }
        foreach (string item in itemFamily[currentState])
        {
            if (item.IndexOf('.') == item.Length - 1)
            {
                if (!symbols.Contains(item.Substring(1, item.IndexOf(' ') - 1)))
                {
                    symbols.Add(item.Substring(1, item.IndexOf(' ') - 1));
                }
                itemsets.Add($'[{currentState}] {item.Substring(1, item.Length - 2)}');
            }
        }
    }
}