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 string startSymbol; // 文法开始符号

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 lvi = new ListViewItem(states[i]);
        lvi.SubItems.Add(itemsets[i]);
        listView1.Items.Add(lvi);
    }
    listView1.GridLines = true;
}

private void BuilditemFamily()
{
    // 初始化文法
    InitializeGrammar();
    // 初始化项目族
    List<ItemSet> itemFamily = new List<ItemSet>();
    ItemSet firstSet = new ItemSet();
    firstSet.items.Add(new Item(startSymbol, new List<string> { symbols[0] }, 0));
    itemFamily.Add(Closure(firstSet));
    // 构造项目族
    for (int i = 0; i < itemFamily.Count; i++)
    {
        ItemSet currentItemSet = itemFamily[i];
        for (int j = 0; j < symbols.Count; j++)
        {
            char symbol = symbols[j][0];
            ItemSet gotoItemSet = Goto(currentItemSet, symbol);
            if (gotoItemSet.items.Count > 0 && !itemFamily.Contains(gotoItemSet))
            {
                itemFamily.Add(gotoItemSet);
            }
        }
        states.Add('I' + i);
        itemsets.Add(string.Join('\n', currentItemSet.items.Select(item => item.ToString())));
    }
}

// 初始化文法
private void InitializeGrammar()
{
    // 解析输入
    productions.Clear();
    symbols.Clear();
    string[] lines = richTextBox1.Lines;
    for (int i = 0; i < lines.Length; i++)
    {
        string line = lines[i].Trim();
        if (line.Length == 0) continue;
        productions.Add(line);
        string lhs = line.Split(new char[] { ' ', '-' }, StringSplitOptions.RemoveEmptyEntries)[0];
        if (!symbols.Contains(lhs)) symbols.Add(lhs);
        string[] rhs = line.Split(new char[] { ' ', '-', '>' }, StringSplitOptions.RemoveEmptyEntries)[1].Split(new char[] { ' ', '|' }, StringSplitOptions.RemoveEmptyEntries);
        foreach (string symbol in rhs)
        {
            if (!symbols.Contains(symbol)) symbols.Add(symbol);
        }
    }
    startSymbol = productions[0].Split(new char[] { ' ', '-' }, StringSplitOptions.RemoveEmptyEntries)[0];
}

// 计算闭包
private ItemSet Closure(ItemSet itemSet)
{
    ItemSet closure = new ItemSet();
    while (true)
    {
        int originalLength = closure.items.Count;
        foreach (Item item in itemSet.items)
        {
            if (item.dotIndex == item.RHS.Count) continue;
            char nextSymbol = item.RHS[item.dotIndex][0];
            List<string> productions = GetProductions(nextSymbol);
            foreach (string production in productions)
            {
                Item newItem = new Item(production.Split(new char[] { ' ', '-' }, StringSplitOptions.RemoveEmptyEntries)[0],
                    production.Split(new char[] { ' ', '-', '>' }, StringSplitOptions.RemoveEmptyEntries)[1].Split(new char[] { ' ', '|' }, StringSplitOptions.RemoveEmptyEntries).ToList(),
                    0);
                if (!closure.items.Contains(newItem))
                {
                    closure.items.Add(newItem);
                }
            }
        }
        if (closure.items.Count == originalLength) break;
    }
    return closure;
}

// 计算Goto
private ItemSet Goto(ItemSet itemSet, char symbol)
{
    ItemSet gotoSet = new ItemSet();
    foreach (Item item in itemSet.items)
    {
        if (item.dotIndex == item.RHS.Count) continue;
        if (item.RHS[item.dotIndex][0] == symbol)
        {
            gotoSet.items.Add(new Item(item.LHS, item.RHS, item.dotIndex + 1));
        }
    }
    return Closure(gotoSet);
}

// 获取所有左部为symbol的产生式
private List<string> GetProductions(char symbol)
{
    return productions.Where(p => p.StartsWith(symbol + ' -')).ToList();
}

// 项目类
private class Item
{
    public string LHS; // 产生式左部
    public List<string> RHS; // 产生式右部
    public int dotIndex; // 点的位置

    public Item(string lhs, List<string> rhs, int dotIndex)
    {
        this.LHS = lhs;
        this.RHS = rhs;
        this.dotIndex = dotIndex;
    }

    // 判断两个项目是否相等
    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }

        Item other = (Item)obj;
        return LHS == other.LHS && dotIndex == other.dotIndex && RHS.Count == other.RHS.Count
                && new HashSet<string>(RHS).SetEquals(other.RHS);
    }

    public override int GetHashCode()
    {
        return LHS.GetHashCode() ^ dotIndex.GetHashCode() ^ RHS.GetHashCode();
    }

    public override string ToString()
    {
        List<string> tempRHS = new List<string>(RHS);
        tempRHS.Insert(dotIndex, '.');
        return $'{LHS}->{string.Join('', tempRHS)}';
    }
}

// 项目集类
private class ItemSet
{
    public List<Item> items = new List<Item>();

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }

        ItemSet otherSet = (ItemSet)obj;
        return items.SequenceEqual(otherSet.items);
    }

    public override int GetHashCode()
    {
        return items.GetHashCode();
    }
}