LR(0) 文法项目集族构建算法 - C# 实现 - 常规

private void BuilditemFamily()
{
    // 初始化
    List<ItemSet> itemsets = new List<ItemSet>();
    Dictionary<string, List<string>> product = new Dictionary<string, List<string>>();
    HashSet<string> nonTerminals = new HashSet<string>();
    HashSet<string> terminals = new HashSet<string>();

    // 读入产生式
    foreach (string production in productions)
    {
        string[] temp = production.Split(new string[] { '->' }, StringSplitOptions.None);
        string lhs = temp[0];
        string rhs = temp[1];
        if (!product.ContainsKey(lhs))
        {
            product.Add(lhs, new List<string>());
        }
        product[lhs].Add(rhs);
        nonTerminals.Add(lhs);
        foreach (char c in rhs)
        {
            if (!nonTerminals.Contains(c.ToString()))
            {
                terminals.Add(c.ToString());
            }
        }
    }

    // 构建初始项目集
    ItemSet initialSet = new ItemSet();
    string startSymbol = productions[0].Split(new string[] { '->' }, StringSplitOptions.None)[0];
    initialSet.Add(new Item(startSymbol, new List<string>() { product[startSymbol][0] }, 0));
    itemsets.Add(initialSet);

    // 构建项目集族
    for (int i = 0; i < itemsets.Count; i++)
    {
        ItemSet set = itemsets[i];
        Dictionary<string, ItemSet> gotoDict = new Dictionary<string, ItemSet>();

        // 计算GOTO集合
        foreach (Item item in set)
        {
            if (item.dotIndex < item.RHS.Count)
            {
                string symbol = item.RHS[item.dotIndex];
                Item newItem = new Item(item.LHS, item.RHS, item.dotIndex + 1);
                if (!gotoDict.ContainsKey(symbol))
                {
                    gotoDict.Add(symbol, new ItemSet());
                }
                gotoDict[symbol].Add(newItem);
            }
        }

        // 构建新的项目集
        foreach (KeyValuePair<string, ItemSet> entry in gotoDict)
        {
            ItemSet newSet = entry.Value;

            // 求闭包
            for (int j = 0; j < newSet.Count; j++)
            {
                Item currentItem = newSet[j];
                if (currentItem.dotIndex < currentItem.RHS.Count && nonTerminals.Contains(currentItem.RHS[currentItem.dotIndex]))
                {
                    string symbol = currentItem.RHS[currentItem.dotIndex];
                    foreach (string rhs in product[symbol])
                    {
                        Item newItem = new Item(symbol, new List<string>(rhs), 0);
                        if (!newSet.Contains(newItem))
                        {
                            newSet.Add(newItem);
                        }
                    }
                }
            }

            // 检查是否已存在
            bool isNew = true;
            foreach (ItemSet existingSet in itemsets)
            {
                if (existingSet.Equals(newSet))
                {
                    isNew = false;
                    break;
                }
            }

            // 添加到项目集族
            if (newSet.Count > 0 && isNew)
            {
                itemsets.Add(newSet);
            }
        }

        // 添加状态
        states.Add($'I{i}');

        // 添加项目集信息
        List<string> setInfo = new List<string>();
        foreach (Item item in set)
        {
            setInfo.Add(item.ToString2());
        }
        itemsets.Add(string.Join('
', setInfo));
    }
}

// Item 类
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)
    {
        this.LHS = lhs;
        this.RHS = rhs;
        this.dotIndex = dotIndex;
    }

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

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

// ItemSet 类
class ItemSet : List<Item>
{
    public bool Equals(ItemSet other)
    {
        if (other == null || GetType() != other.GetType())
        {
            return false;
        }

        return this.SequenceEqual(other);
    }
}

代码解释:

初始化: 创建几个容器：
- itemsets: 存储所有的项目集。
- product: 存储产生式，以左部非终结符为键，右部产生式列表为值。
- nonTerminals: 存储所有非终结符。
- terminals: 存储所有终结符。
读入产生式: 将产生式字符串解析成 product 字典，并提取出非终结符和终结符。
构建初始项目集: 创建一个新的项目集，包含开始符号的第一个产生式的第一个项目（点在第一个符号前面）。
构建项目集族: 循环遍历每个项目集，进行如下操作：
- 计算GOTO集合: 对于每个项目，判断点的位置，如果点不是在末尾，则根据点后的符号计算 GOTO 集合。
- 求闭包: 对于每个 GOTO 集合，对其中所有点在非终结符前的项目，根据该非终结符的产生式，将所有对应项目加入到 GOTO 集合中，直到没有新的项目加入为止。
- 检查是否已存在: 将每个 GOTO 集合与现有的项目集比较，如果已经存在，则跳过；否则，添加新的项目集。
- 添加状态: 将每个项目集标记为状态 I 以及对应的索引。
- 添加项目集信息: 将每个项目集中的所有项目格式化为字符串，并添加到 itemsets 列表中。

代码的使用:

您需要将自己的文法产生式保存在 productions 列表中。
执行 BuilditemFamily() 函数后，itemsets 列表将包含所有项目集的字符串信息，states 列表将包含所有状态信息。
可以使用 listView1 或其他控件将这些信息显示出来。

注意事项:

代码中假设产生式已经以 LHS -> RHS 的形式存储在 productions 列表中。
代码只展示了 LR(0) 项目集族的构建，并没有实现 LR(0) 分析器。

改进建议:

可以使用更简洁的代码来实现求闭包操作。
可以使用数据结构来存储状态之间的转移关系，以便更方便地进行 LR(0) 分析。
可以使用 GUI 或控制台程序来方便地输入文法产生式和查看结果。