编译原理--算符优先分析法研究--源程序.doc

编译原理 算符优先分析法研究 源程序 目 录 1 课程设计的目的和要求 2 1.1 课程设计的目的 2 1.2 课程设计的要求 2 2 系统描述 2 2.1 自底向上分析方法的描述: 2 2.2 算符优先文法的描述： 2 3）输入符号串，进行移进-规约分析。 3 3 概要设计 3 3.1 设计思路 3 3.2 系统功能结构 4 3.3 技术路线或实现方法 5 3.4 开发环境 5 4 详细设计 5 4.1 模块划分 5 4.2 主要算法的流程图 7 4.3 数据分析与定义 8 4.4 系统界面设计 8 5 测试方法和测试结果 9 5.1 测试用例1 9 5.2 测试用例2 10 5.3 测试用例3 11 5.4 测试用例4 12 6 结论和展望 13 结论 13 展望 13 学习编译技术课程的体会和对本门课程的评价 13 7 参考文献 13 8 源代码 14 1 课程设计的目的和要求 1.1 课程设计的目的 本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。 1.2 课程设计的要求 1、文法使用产生式来定义； 2、用大写字母和小写字母分别表示非终结符和终结符；产生式使用-； 3、文法中的空字符串统一使用@表示； 4、分别给出每一个非终结符的FIRSTVT集和LASTVT集； 5、画出算符优先关系表 6、判定给定的文法是否是算符优先文法； 7、给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。 2 系统描述 本次实验使用windows vista操作系统下visual C++6.0平台，使用C语言，利用读文件方式将待分析的文法读入到程序中，通过定义数组和结构体作为具有一定意义或关系的表或栈，存放FIRSTVT、LASTVT、算符优先关系表的元素。 系统能够对由文件读入的文法进行分析，构造出FIRSTVT表和LASTVT表以及算符优先关系表。可以根据构造的优先关系表对输入的任意符号串进行分析，判断是否为本文法的句子，若是则打印规约过程。结果显示到DOS界面上。 2.1 自底向上分析方法的描述: 对输入的符号串自左向右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时（该句柄对应某个产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这一过程称为规约。重复这一过程，直到栈中只剩下文法的开始符则分析成功。 2.2 算符优先文法的描述： 只规定算符之间的优先关系，也就是说只考虑终结符之间的优先关系。由于算富有先分析不考虑非终结符之间的优先关系，在规约过程中只要找到最左素短语就可以规约。 如给定一个文法G[S]： S-#E# E-E+T E-T T-T*F T-F F-P/F F-P P-(E) P-i 利用算符优先文法分析过程处理如下： 1）计算给定文法中任意两个终结符对(a,b)之间的优先关系，首先计算两个集合 FIRSTVT(B)={b|B-b…或B-Cb…} LASTVT(B)={a|B-…a或B-…aC} 表2-1 FIRSTVT集和LASTVT集 　 S E　 T　 F　 P　 　FIRSTVT # +*/i(　 */i(　 /i(　 i(　 　LASTVT 　# +*/i)　 */i)　 /i)　 i)　 2）计算三种优先关系，求出算符优先关系表： 表2-2算符优先关系表 + * / i ( ) # + ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ * ﹒﹥ ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ / ﹒﹥ ﹒﹥ ﹤﹒ ﹤﹒ ﹤﹒ ﹒﹥ ﹒﹥ I ﹒﹥ ﹒﹥ ﹒﹥ ﹒﹥ ﹒﹥ ( ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹦﹒ ) ﹒﹥ ﹒﹥ ﹒﹥ ﹒﹥ ﹒﹥ # ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹤﹒ ﹦﹒ 3）输入符号串，进行移进-规约分析。 3 概要设计 3.1 设计思路 1）首先在源程序相同的目录下创建一个txt文档，并在文档中输入待分析的文法。然后定义一个输入流文件，调用这个流文件中的open函数打开该txt文件，再定义一个二维数组通过循环接收读入的产生式。 2）接着开始构造FIRSTVT、LASTVT、算符优先关系表。在构造表的时候首先定义了两个重要的结构体。一个结构体作为存放具有一定关系的一对非终结符和终结符，另一个结构体作为存放上述元素的栈，包括栈顶指针、栈底指针、栈的长度。既然定义了栈，就存在对栈的初始化、栈是否为空的判断、入栈、出栈操作，利用循环和指针的操作来定义这些函数，以完成元素的进栈和弹出。 定义了这两个结构体，就可以用来构造FIRSTVT、LASTVT