安徽工程大学课程设计(论文)
过流程图及算法描述，编写程序构造分析表。
4.1.3 LL(1)预测语法分析
LL（1）语法分析的模块原理如下：
首先初始化栈，#进栈，E进栈作为文法开始的状态。 初始化产生式表、非终结符表、终结符表。
根据产生式表的产生式生成每个非终结符的FIRST集及FOLLOW集。
参考2、3模块，由一个算法生成预测分析表，该预测分析表是由一个二维数组M[n1][n2]构成。由定理可知：若a∈SELECT(A →α),则把A →α放于矩阵M[A,a]。而这里生成的二维数组M[n1][n2]与该定理类似。不过这里n1是指A在非终结符表中的序号，n2是指a在终结符表中的序号，而M[n1][n2]的值是指产生式A →α在产生式表中的序号。这样做就为下面的预测分析程序带来了方便。
预测分析程序分为检测不合法输入模块和对输入字符串的语法分析模块。对输入字符串的语法分析是通过栈及产生式表和预测分析表的相关联系构建一个算法来对这个字符串进行语法分析。通过算法将栈顶元素与输入字符串的比对、出栈及相关产生式的推导的右部的逆序入栈等操作可完成对输入字符串的语法分析。
第 16 页
安徽工程大学课程设计(论文)
LL（1）语法预测分析总流程图
第 17 页
安徽工程大学课程设计(论文)
4.1.4构造生成LL(1)语法树
第 18 页
安徽工程大学课程设计(论文)
算法思想：
本模块的主要功能是将产生式的序列以语法树的方式显示，本组对其进行详
细研究后，发现可以将其分成两个模块分别处理。第一个模块是将产生式结构转换成树形的结构进行存储，第二个模块是将以树形结构存储的语法树以树形目录的方式输出。
第一个模块，涉及到两个数据结构：产生式的数据结构和树的数据结构。产
生式的结构定义存放在Generation.h文件中，在此简述，有两个属性：产生式左部string类型的left和产生式右部vector
其产生式序列必然为： S->BaF B->ACD A->a C->c D->d F->a
第 19 页
安徽工程大学课程设计(论文)
如此在构造树的时候必然也要按照如下次序： 构造节点S 构造S的子节点 构造B的子节点 构造A的子节点 构造C的子节点 构造D的子节点 构造F的子节点
1可设置一个current指向当前节点，最初current指向根节点。
2扫描产生式，每次得到一个产生式，将其左部存到current指向的节点，然后申请若干新节点存放产生式右部的符号。
3 若右部有非终结符，则将current指向第一个，进行下一次扫描
4 若右部没有非终结符，则说明这次推导已到一个子树的树叶。向上回溯，找父节点的相邻非终结符节点，若父节点没有相邻非终结符则继续向上回溯，直到找到为止，并将current指向它，进行下一次扫描。若回溯到根节点则说明树已构造完毕。
在构造非终结符节点的时候需要设置该节点的next指针，例如构造A时要设置其next指针指向C，目的是构造完a之后可以寻找下一个要构造的节点，father指针指向B，目的是在构造完D之后可以向上回溯通过B的next指针找到下一个要构造的节点F。
对于第二个显示模块，思想如下： 1首先current指向根节点，并输出根节点
2 输出current的子节点，并将current指向最左的一个非终结符子节点，用递归的思想输出该节点的子树，然后current继续第二个非终结符子节点，并用递归输出其子树。
第 20 页