LR(0) 项目族构建算法的C#实现

private void BuilditemFamily()
{
    // 初始化产生式和符号列表
    productions = textBox1.Lines.ToList();
    productions.RemoveAll(s => s == ''); // 去除空白行
    symbols = productions.SelectMany(p => p.Split(' ')).Distinct().ToList();

    // 初始化状态和项目族列表
    states = new List<string> { 'I0' };
    itemsets = new List<string> { GetClosure(new List<Item> { new Item(productions[0].Split(' ')[0], productions[0].Split(' ').Skip(1).ToList(), 0) }).ToString() };

    // 构建项目族
    int i = 0;
    while (i < states.Count)
    {
        string state = states[i];
        List<Item> items = GetItems(itemsets[i]);
        Dictionary<string, List<Item>> gotoTable = GetGotoTable(items);

        foreach (KeyValuePair<string, List<Item>> entry in gotoTable)
        {
            string symbol = entry.Key;
            List<Item> gotoItems = entry.Value;

            if (!states.Any(s => s == $'I{itemsets.Count}') && gotoItems.Any())
            {
                states.Add($'I{itemsets.Count}');
                itemsets.Add(GetClosure(gotoItems).ToString());
            }
        }

        i++;
    }
}

// 获取项目集闭包
private List<Item> GetClosure(List<Item> items)
{
    List<Item> closure = new List<Item>(items);

    int i = 0;
    while (i < closure.Count)
    {
        Item item = closure[i];
        if (item.dotIndex < item.RHS.Count && symbols.Contains(item.RHS[item.dotIndex]))
        {
            string symbol = item.RHS[item.dotIndex];
            List<string> productionsWithSymbol = productions.Where(p => p.StartsWith($'{symbol} ')).ToList();

            foreach (string p in productionsWithSymbol)
            {
                Item newItem = new Item(p.Split(' ')[0], p.Split(' ').Skip(1).ToList(), 0);
                if (!closure.Any(c => c.Equals(newItem)))
                {
                    closure.Add(newItem);
                }
            }
        }

        i++;
    }

    return closure;
}

// 获取给定项目集的所有后继项目集
private Dictionary<string, List<Item>> GetGotoTable(List<Item> items)
{
    Dictionary<string, List<Item>> gotoTable = new Dictionary<string, List<Item>>();

    foreach (Item item in items)
    {
        if (item.dotIndex < item.RHS.Count)
        {
            string symbol = item.RHS[item.dotIndex];
            List<Item> gotoItems = items.Where(i => i.LHS == item.LHS && i.RHS.SequenceEqual(item.RHS) && i.dotIndex == item.dotIndex + 1).ToList();
            gotoTable[symbol] = gotoItems;
        }
    }

    return gotoTable;
}

// 获取给定项目集的所有项目
private List<Item> GetItems(string itemset)
{
    List<Item> items = new List<Item>();
    string[] lines = itemset.Split('\n');

    foreach (string line in lines)
    {
        if (line.Trim() != '')
        {
            string[] parts = line.Split(new string[] { '->', '.' }, StringSplitOptions.RemoveEmptyEntries);
            string lhs = parts[0].Trim();
            List<string> rhs = parts[1].Trim().Split(' ').ToList();
            int dotIndex = int.Parse(parts[2].Trim());
            items.Add(new Item(lhs, rhs, dotIndex));
        }
    }

    return items;
}

// 项目类
private class Item
{
    public string LHS { get; set; }
    public List<string> RHS { get; set; }
    public int dotIndex { get; set; }

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

    // 判断两个项目是否相等
    public override bool Equals(object obj)
    {
        if (obj == null || !(obj is Item))
        {
            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)}';
    }
}