LL1 预测分析表生成算法：SELECT 集的计算 (无 LL1Item)

在 LL1 预测分析表生成算法中，SELECT 集是一个重要的概念。它用于确定每个非终结符在特定产生式下能够接受的输入符号集。传统上，SELECT 集的计算需要使用 LL1Item 对象来存储产生式、非终结符和终结符等信息。然而，我们可以通过直接传递产生式、FIRST 集和 FOLLOW 集来实现 SELECT 集的计算，从而避免使用 LL1Item 对象。

算法实现

以下代码展示了不使用 LL1Item 计算 SELECT 集的算法实现：

private Dictionary<string, List<string>> GetSelect(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
    // 初始化 SELECT 集
    Dictionary<string, List<string>> selects1 = new Dictionary<string, List<string>>();
    foreach (var item in production1)
        selects1.Add(item.Key, new List<string>());

    // 遍历每个产生式，计算对应的 SELECT 集
    foreach (var nonterm in production1.Keys)
    {
        foreach (var prod in production1[nonterm])
        {
            List<string> select = new List<string>();
            bool flag = true;
            // 对于产生式中的每个符号，计算其 FIRST 集
            foreach (var s in prod)
            {
                if (IsTerminal(s))
                {
                    select.Add(s.ToString());
                    flag = false;
                    break;
                }
                else
                {
                    GetFirst(s.ToString(), production1, firsts1);
                    foreach (var f in firsts1[s.ToString()])
                    {
                        if (!f.Equals('#') && !select.Contains(f))
                            select.Add(f);
                    }
                    if (!IsReachEmpty(s.ToString(), production1))
                    {
                        flag = false;
                        break;
                    }
                }
            }
            // 如果产生式中所有符号的 FIRST 集都包含空串，则将 FOLLOW 集加入 SELECT 集中
            if (flag)
            {
                foreach (var f in follows1[nonterm])
                {
                    if (!select.Contains(f))
                        select.Add(f);
                }
            }
            selects1[nonterm].Add(string.Join("", select.ToArray()));
        }
    }

    return selects1;
}

该算法的实现逻辑如下：

初始化 SELECT 集，每个非终结符对应一个空的列表。
遍历每个产生式，计算对应 SELECT 集。
对于每个产生式，逐个遍历其符号。
如果当前符号为终结符，将其加入 SELECT 集并结束循环。
如果当前符号为非终结符，则调用 GetFirst 函数获取其 FIRST 集，将 FIRST 集中除空串外的符号加入 SELECT 集。
如果当前符号的 FIRST 集包含空串，继续遍历下一个符号。
如果遍历完所有符号，且所有符号的 FIRST 集都包含空串，则将当前非终结符的 FOLLOW 集加入 SELECT 集。
最终，将所有符号的 FIRST 集和 FOLLOW 集合并成一个字符串，加入 SELECT 集。

总结

本文介绍了如何在不使用 LL1Item 的情况下，使用产生式、FIRST 集和 FOLLOW 集来计算 SELECT 集。这种方法更加灵活，可以方便地进行算法的修改和扩展。