1、编译原理语法分析器课程设计 1 一一 要求：要求： 建立一个针对 LL(1)文法编译器的自动生成器。要完成此编译器的生成器需对源文件进行两遍处理： 第一遍词法分析，第二遍语法分析。语法分析程序用 LL(1)语法分析方法。首先输入定义好的文法书写 文件(所用的文法可以用 LL(1)分析)，然后建立词法分析器，包括词法分析主程序、扫描器部分、关键 字表等。经词法分析后分别计算所输入的文法的每个非终结符号的 FIRST 集合，每个非终结符号的 FOLLOW集合， 以及每个规则的 SELECT集合， 并判断任意一个非终结符号的任意两个规则的 SELECT 集的交集是不是都为空，如果是则输入文法符合 L
2、L(1)文法则可以进行分析。 二二 语法分析器实现语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程 序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向 下的 LL(1)分析方法。 语法分析程序的流程图如图 5-4 所示。 1.计算 FIRST 集 对于文法 G 的任意一个符号串=X1X2Xn可按下列步骤构造其FIRST()集合： 令 FIRST()=，i=1； (1) 若 XiVT，则 XiFIRST()； (2) 若 XiVN： 若 FIRST(Xi)，则FIRST(Xi) FIRST()； 若 F
3、IRST(Xi)，则FIRST(Xi)- FIRST()； i=i+1； 重复(1)(2)，直到(XiVT(i=2,3,n)或 XiVN 且 FIRST(Xi)或 in 为止)。 (3)若对于一切 1in，FIRST(Xi)，则将 符号加进FIRST()。 实例中求单个符号的 FIRST集的算法描述如下： void findSingleFIRST(int i) 参数 i为符号在所有输入符号中的序号 X 等于指示器 i所指向的符号 在保存终结符元素的 terSymbol数组查找 X if X 为终结符(XVT )，then FIRST(X)=X 在保存终结符元素的 non_ter数组查找 X i
4、f X 是非终结符(XVN ) 在所有产生式中查找 X 所在的产生式 if 产生式右部第一个字符为终结符或空(即 Xa (aVT)或 X) then 把 a 或加进 FIRST(X) if 产生式右部第一个字符为非终结符 then if 产生式右部的第一个符号等于当前字符 then 跳到下一条产生式进行查找 求当前非终结符在所有字符集中的位置 if 当前非终结符还没求其FIRST 集 then 开始 读入文法 有效？ 判断句型 报错 结束 语法分析程序流程图 是 LL(1) 文法？ 编译原理语法分析器课程设计 2 查找它的 FIRST 集并标识此符号已求其FIRST 集 求得结果并入到 X 的 FIRST 集. if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符 then 获取右部符号下一个字符在所有字符集中的位置 if 此字符的 FIRST 集还未查找 then 找其 FIRST 集,并标其查找状态为1 把求得的 FIRST 集并入到X 的 FIRST 集. i
