C++实现编译原理：求非终结符的first集与follow集

"该资源是关于编译原理的程序实现，用于求解上下文无关文法的非终结符first集合和follow集合。作者为YFLAHU09，编写时间为2011年10月30日。程序使用C++语言编写，包括对输入文法规则的处理、符号表的管理以及first集和follow集的计算。" 在编译原理中，`first集`和`follow集`是构建解析表的关键概念，它们用于分析上下文无关文法（Context-Free Grammar, CFG）。这两个集合帮助我们理解语法结构并指导自顶向下的语法分析过程，如LL(1)或LR(1)解析。 1. **First集**： - 首先，`first集`是文法中一个非终结符或起始符号的所有可能的开始符号（终结符）的集合。如果非终结符可以产生空串（ε），那么空串也会被包含在first集中。 - 在程序中，`fir`集合用于存储每个非终结符的first集。 - 程序通过遍历文法规则，检查非终结符能否以不同的终结符开始，逐步构造first集。 - `isToEmpty()`函数可能是用来判断非终结符是否能产生空串的。 2. **Follow集**： - `follow集`是文法中每个非终结符在句子中可能出现在哪些终结符之后的集合。 - 在程序中，`follow`集合用于存储每个非终结符的follow集。 - 计算follow集时，我们需要考虑文法规则的右部，以及first集的信息，尤其是当非终结符出现在右部的尾部时。 - `capL()`函数用于判断字符是否为大写字母，这可能是为了区分非终结符（通常大写）和终结符（通常小写）。 3. **算法流程**： - 输入文法规则，将它们存储在`sentence`和`senRever`映射中。 - 初始化`ter`集合来存储终结符，`toEmpty`映射记录非终结符是否可以产生空串。 - 初始化`fir`和`follow`集合，分别用于first集和follow集。 - 使用循环和递归策略更新first集和follow集。 - 当first集不再变化时，表示计算完成。 4. **程序结构**： - `multimap<char, string>` `sentence`用于存储文法规则，`multimap<string, char> senRever`用于规则的反向引用。 - `set<char> ter`存储所有终结符，`map<char, bool> toEmpty`标记非终结符是否能产生空串。 - `vector<string> rightSide`存储文法规则的右部，便于处理。 - `char Begin`可能是起始符号，程序中的其他辅助函数如`capL()`用于字符判断。 这个C++程序提供了一个基础的框架，用于计算给定上下文无关文法的first集和follow集。然而，完整的算法和实现细节可能在注释的剩余部分，这部分代码没有提供。实际应用中，还需要考虑处理递归、左递归和左因子提取等问题，以确保算法的正确性和效率。