C++实现LL1语法分析：first集、follow集与分析表

LL1语法分析是一种自左向右的逐词分析方法，适用于处理上下文无关文法。在C++中实现LL1解析器，主要涉及到以下几个关键概念： 1. **First集**：First集是文法中非终结符或终结符的所有可能的起始符号集合。对于非终结符A，First(A)包括所有可能由A开始的产生式的起始符号，如果A能推导出空串，则First(A)也包含空字符'ε'。 2. **Follow集**：Follow集是文法中非终结符的后续符号集合，表示在非终结符A之后可能接续的任何终结符。Follow(A)包括在所有产生式B→αAβ中，当B→α结束后可能出现在β之前的任何终结符，以及在开始符号的产生式S'→S$中，如果S推导出A，则Follow(A)包含'$'（表示输入结束）。 3. **分析表**：LL1分析表是根据First集和Follow集构造的，用于指导分析过程。表中的每个条目指示在当前非终结符和输入符号的情况下，应该采取的动作。如果表中的值是1，表示可以进行一次移进操作；如果是一个非终结符，表示进行归约操作。 4. **分析栈**：在分析过程中，会用一个栈来保存当前分析路径的信息。栈顶元素代表当前正在处理的非终结符，栈底通常包含开始符号。 5. **C++实现**：在这个实现中，定义了多个数据结构，如`pRNode`和`pNode`，分别表示产生式右部节点和产生式节点。`Vn`和`Vt`存储非终结符和终结符，`P`数组存储产生式，`first`和`follow`数组存储First集和Follow集，`analyseTable`是分析表，`analyseStack`是分析栈。 6. **函数**： - `Init()`：初始化相关数据结构。 - `IndexCh(char ch)`：将字符转换为对应的索引。 - `InputVt()` 和 `InputVn()`：输入终结符和非终结符。 - `ShowChArray(char* collect, int num)`：输出字符数组的内容。 - `InputP()`：输入产生式。 - `CheckP(char* st)`：检查产生式是否符合LL1文法。 - `First(int U)`：计算非终结符U的First集。 - `AddFirst(int U, char ch)`：向First集中添加元素。 - `Follow(int V, char ch)`：计算非终结符V的Follow集。 - `BuildAnalyseTable()`：根据First集和Follow集构建分析表。 - `Analyse()`：执行LL1分析过程。 7. **LL1解析过程**：首先，根据用户输入的文法规则计算First集和Follow集，然后构建分析表。接着，分析栈从开始符号开始，依次比较栈顶非终结符和输入符号，根据分析表决定是移进（Push）输入符号到栈中，还是归约（Reduce）栈顶的产生式。分析过程持续到输入字符串完全处理且分析栈只剩下一个开始符号。 这个文档包含了LL1解析器的C++实现，从输入文法规则、计算First集和Follow集，到构建分析表和执行分析，完整地展示了LL1语法分析的过程。