- 1 - 河河海海大大学学物物联联网网工工程程学学院院 编译原理课程实践 学年学期学年学期 2015-20162015-2016 第二学期第二学期 实验名称实验名称 语法分析、语义分析语法分析、语义分析 作作 者者 13628102251362810225 刘云瞻刘云瞻 组组 员员 刘云瞻刘云瞻 华路华路 授课班号授课班号 62825066282506 专专 业业 计算机科学与技术计算机科学与技术 1313 级级 指导教师指导教师 金永霞金永霞 2016 年年 6 月月 - 2 - 目录 1引言 .- 2 - 1.1 实验目的- 2 - 1.2 实践内容- 3 - 2.算法设计- 3 - 2.1 语法分析- 4 - 2.1.1 生成（非）终结符表- 4 - 2.1.2 构造 FirstVT 集和 LastVT 集- 4 - 2.1.4 算符优先分析- 7 - 2.2 语义分析- 10 - 2.2.1 算术表达式和简单赋值语句的翻译- 10 - 3. 运行结果与测试 .- 11 - 3.1 运行结果- 11 - 3.2 错误测试- 13 - 4.心得体会- 14 - - 3 - 1 1引言引言 1.11.1 实验目的实验目的 通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题 目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。 1.21.2 实践内容实践内容 本实验通过“算符优先分析法”来解决实验任务中的“语法分析”与“语 义分析”这两个任务点。其中， “语法分析”是根据输入串和根据文法规则得出 的优先关系表，完成一系列移进、归约的过程， “语义分析”在本实验中是通过 对归约串进行的解释以及中间代码的生成。 具体来说，这里我通过 Java 编程语言完成整个实验的设计，根据文法规 则求得 FirstVT 集和 LastVT 集，然后生成算符优先关系表，最终实现算符优先 分析总控程序，输出识别过程及结论；此处，在归约时候根据赋值语句的语法 致导定义，为输入的赋值语句生成四元式序列。 2.2. 算法设计算法设计 本实验的算法设计主要分为“语法分析”和“语义分析”两部分。其中， “语 法分析”由生成（非）终结符表、构造 FirstVT 集和 LastVT 集、生成算符优先 关系表和算符优先分析四个部分组成；“语义分析”是对实现“算术表达式和 简单赋值语句的翻译” ，找到归约采用文法、输出赋值过程及四元式序列。 这里，我使用的文法规则为： A-#S# S-d=E E-E+T E-T T-T*F - 4 - T-F F-P F-P P-(E) P-i 输入串为：d=i+i*i# 赋值 i=6 2.12.1 语法分析语法分析 2.1.12.1.1 生成（非）终结符表生成（非）终结符表 根据算符文法的定义简单判断文法是否合法，具体通过 BaseUtil.isLegal(grammars)来实现，主要是不存在两个连续相继的非终结符。 终结符：文法规则的左部 非终结符：文法规则的右部中除了终结符以外都是非终结符 2.1.22.1.2 构造构造 FirstVTFirstVT 集和集和 LastVTLastVT 集集 求这两个集合主要是根据定义来求得，定义形式为： FirstVT： 产生式 P-a或者 P-Qa，则 a 属于 FirstVT(P) 产生式 P-Q，则 FirstVT(Q)属于 FirstVT(P) LastVT： 产生式 P-a 或者 P-aQ，则 a 属于 FirstVT(P) 产生式 P-Q，则 LastVT(Q)属于 LastVT(P) 2.1.3 生成算符优先关 系表 public static char getFirstVt(String wfs, char vt, char C) String firstVtStr = “; for (int i = 0; i . 0 1 2 下标从3开始 / A-a. - 5 - if (isVt(cj, vt) firstVtStr += cj; else / A-B. if (c.length = 4) firstVtStr += String.valueOf(getFirstVt(wfs, vt, cj);/ 求该非终结符的头符 else / A-Ba. firstVtStr += cj + 1; return removeRepeat(firstVtStr); public static char getLastVt(String wfs, char vt, char C) String lastVtStr = “; for (int i = 0; i .a if (isVt(cj, vt) lastVtStr += cj; else / A-.B if (c.length = 4) lastVtStr += String.valueOf(getLastVt(wfs, vt, cj);/ 求该非终结符的尾符 else / A-.aB lastVtStr += cj - 1; lastVtStr += String.valueOf(getLastVt(wfs, vt, cj);/ 求该非终结符的尾符 return removeRepeat(lastVtStr); 根据 FIrstVT、LastVT 求出优先关系表 产生式右部 aQ，则 a产生式右部 Qa，则 LastVT(Q)a - 6 - 注：文法中右部含有ab或aQb时，a=b 算符优先关系表 public static void setTable(String wfs, char vt, char table) int wfLen = wfs.length; for (int i = 0; i a if (j + 1 ); #d()i*+=- #= i * - 7 - 2.1.42.1.4 算符优先分析算符优先分析 （1）移进归约的过程如下图所示。 程序图 （2）对于程序图具体说明： Str：输入串 Array：当前栈 a：输入串中当前的读入字符串 归约方法：归约方法：（找 2 个大于） （1） 栈中第一个终结符输入符号 （2） 自顶向下扫描符号栈，找到某个 i，满足 Arrayi = BaseUtil.getOperator(stackj, a, table) Q = stackj; - 9 - s_top = stackj;/ 输出用 if (BaseUtil.isVt(stackj - 1, vts) j = j - 1; else j = j - 2; String record4print = “;/ 输出用 while (= = BaseUtil.getOperator(stackj, Q, table) record4print = = + “ + Q + “ + record4print;/ 输出用 Q = stackj; if (BaseUtil.isVt(stackj - 1, vts) j = j - 1; else j = j - 2; formatPrint(step, i, stack, input, a, stackj + “ + BaseUtil.getOperator(stackj, Q, table) + “ + Q + “ + record4print + BaseUtil.getOperator(s_top, a, table) + “ + a + “, “归约“); step+; String temp = “; / 查找规约的字符串 for (int m = j + 1; m （1）输出当前归约串 （2）归约所使用的文法 （3）归约成结果的 Value 值 （4）四元式表示运算过程 - 11 - （5）显示输入串最终结果 3.3. 运行结果与测试运行结果与测试 3.13.1 运行结果运行结果 （1）具体输出结果如图 1-4 所示，分别为（非）终结符表、FirstVT 集和 LastVT 集、算符优先关系表、 图 1 （非）终结符 - 12 - 图 2 FirstVT 集合 LastVT 集 图 3 算符优先关系表 - 13 - 图 4 语法分析中的移进、归约过程 3.23.2 错误错误测试测试 （1）当输入串为“d=i+i*i#”时，运行结果正确。 （2）在其他进行归约时如果待归约串找不到归约采用的文法规则，程序会进行 出错处理，同时停留在出错的地方，便于查看出错位置。如输入串为 “d=(i+i*i#”时，图 6 所示。 出错处理 - 14 - 4.4. 心得体会心得体会 在做课设刚开始的时候，对此次的实验是一头雾水不知从何处。在刚开始布置的词法 分析时，尽管不是自己的负责部分，但还是积极地讨论了一下，对编译原理实验中“词法 分析”的目的有了一定的了解。 本次实验我们基本完成了实验题目的要求。求出了一个文法中每一个非终结符的 FIRSTVT 集和 LASTVT 集，画出算符优先关系表，并判定出给定的文法是否是算符优先 文法。当给定一个符号串时，能够判定是否是文法中的句子，并能够将分析过程打印出来。 通过算符优先分析方法，可以对任意一个文法进行自底向上的分析。同时，算符优先分析 法也存在不足之处，由于忽略文法中的非终结符，会将本不属于文法的句子正确规约，从 而引起错误 此次的课程设计巩固了之前所学的编译原理的知识，我也更加透彻地了解编译语言的 工作原理 从本次课程设计学习到了： （1）做任何事情都要细心，不然极小的错误都会引发完全错误的后果； （2）在做任何事情的时候都要有极大的耐心，这样在错误发生后才能找出错误并纠正； （3）要时常与他人协作交流，不能一味的自己埋头苦干。不懂就要问，争取能够将遇 到的问题快速的解决； （4）自己一定要坚持，不断挑战自己，别人做一个，我要想着做出比别人更多的东西， 这样，收获的才会更多。