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

"LL1语法分析c++实现-first集-follow集-分析表-分析栈.doc" 这篇文档是关于使用C++实现LL1语法分析的详细过程。LL1解析是一种自左向右、一步看一个输入符号的解析方法，它基于产生式右部的First集和Follow集来构造分析表，从而进行语法分析。以下是文档中涉及的关键知识点： 1. **LL1解析**: LL1解析器从输入串的左侧开始，每次查看一个输入符号，并根据当前栈顶非终结符和输入符号决定下一步操作。LL1解析器需要满足每个产生式的左部非终结符与右部第一个可能的终结符之间存在唯一对应关系。 2. **产生式（Production）**: 产生式是形式语言理论中的概念，用来描述非终结符如何转换成终结符的规则。在代码中，`struct pNode`定义了产生式结构，包括产生式的左部非终结符、右部结点头指针以及右部长度。 3. **First集和Follow集**: - **First集**: 对于非终结符A，First集包含了所有可能出现在A的产生式右部开头的终结符集合。例如，如果A->aB|b，那么First(A)={a,b}。 - **Follow集**: 对于非终结符A，Follow集包含了所有可能在A之后出现的终结符，这些情况通常出现在句柄的右侧或错误恢复时。例如，如果S->AB且没有其他产生式以S结束，那么$（结束符号）在Follow(S)中。 4. **分析表**: 分析表是LL1解析的核心，用于存储每个非终结符在遇到不同终结符时的解析动作。在代码中，`int analyseTable[MaxVnNum+1][MaxVtNum+1+1]`表示这个二维数组。 5. **分析栈**: 分析过程中使用的栈，用于存储非终结符和临时的终结符。`int analyseStack[MaxStackDepth+1]`表示分析栈，`int topAnalyse`表示栈顶索引。 6. **输入处理函数**: - `InputVt()`: 输入终结符，用于构建终结符集合。 - `InputVn()`: 输入非终结符，用于构建非终结符集合。 - `InputP()`: 输入产生式，检查并存储用户输入的文法规则。 7. **检查和计算函数**: - `CheckP(char* st)`: 检查输入的产生式是否正确。 - `First(int U)`: 计算非终结符U的First集。 - `AddFirst(int U, int nCh)`: 将一个终结符添加到非终结符的First集中。 - `HaveEmpty(int U)`: 检查非终结符的First集中是否存在空产生式。 8. **初始化函数**: - `Init()`: 初始化相关数据结构，如非终结符和终结符的计数，以及First集和Follow集。 通过这些函数和数据结构，程序能够构建出LL1解析所需的全部信息，然后执行语法分析，判断输入的符号串是否符合文法规则。整个过程涉及到编译原理中的词法分析、语法分析等核心概念，是理解编译器设计的重要部分。