1、实验 1-词法分析程序的设计与开发精品文档编译原理实验报告课程名称 : 编译原理班级: 计算 1614实验成绩 :指导教师 : 付永钢姓名: 施心萍实验项目名称 :学号: 201621121097上机实践日期 :实验一 词法分析程序设计与开发一、实验目的? 深入理解有限自动机及其应用? 掌握词法分析程序的开发。? 掌握根据语言的词法规则构造识别其单词的有限自动机的方法? 深入理解词法分析程序自动生成原理二、实验要求? 掌握各类单词的形式描述?用直接转向法实现有限自动机的代码编写。? 独立完成 PL0 语言的词法分析器。? 掌握词法分析程序自动生成工具 LEX的使用。三、实验原理词法分析是编译过
2、程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描,根据源程序的词法规则识别具有独立意义的单词(符号),并输出与其等价的 Token 序列。有限自动机是描述程序设计语言单词构成的工具,而状态转换图是有限自动机的比较直观的描述方法。我们使用确定的有限状态自动机,简记为DFA。PL/0 的语言的词法分析器将要完成以下工作:(1)跳过分隔符(如空格,回车,制表符);(2)识别诸如 begin ,end, if ,while 等保留字;(3)识别非保留字的一般标识符,此标识符值(字符序列)赋给全局量 id ,而全局量 sym赋值为 SYM_IDENTIFIER。(4) 识别数字序列,当
3、前值赋给全局量 NUM,sym 则置为SYM_NUMBER;收集于网络,如有侵权请联系管理员删除精品文档字母 ,数字入口字母S标识符状态 , INID标识符数字数字无符号整数数字状态 , INNUM+,-,*,/,(,),;,=,EOF, 空白单分界符完成状态 , DONE其它符号出错:=双分界符赋值状态 INASSIGN字母 ,数字注释状态 , INCOMMENT注释注释结束其它符号出错“字母或数字“字符串字符串状态 , INCHAR完成状态 DONE其他出错出口识别 PL0 单词的 DFA 表示(5) 识别 := ,=之类的特殊符号,全局量 sym则分别被赋值为SYM_BECOMES,YM
4、LEQ, SYM_GEQ等。相关过程(函数)有 getsym() , getch() ,其中 getch() 为获取单个字符的过程,除此之外,它还完成:(1)识别且跳过行结束符;(2)将输入源文件复写到输出文件;收集于网络,如有侵权请联系管理员删除精品文档(3)产生一份程序列表,输出相应行号或指令计数器的值。下面给出能够识别PL0 语言中各类单词的DFA:根据语言的词法规则构造出识别其单词的确定有限自动机DFA, 仅仅是词法分析程序的一个形式模型,距离词法分析程序的真正实现还有一定的距离。状态转换图的程序实现通常是采用直接转向法。直接转向法又称为程序中心法,是把状态转换图看成一个流程图,从状
5、态转换图的初态开始,对它的每一个状态结点都编写一段相应的程序。四、实验步骤一、构造识别单词的自动机1. 根据给定的词法构成规则对程序语言的单词按类构造出相应的状态转换图,并根据具体需求对该状态转换图进行完善。2. 对各类单词的状态转换图合并,构成一个能识别语言所有单词的状态转换图。合并步骤为:(1) 将各类单词的状态转换图的初始状态合并为一个唯一的初态;(2) 化简调整状态冲突和对冲突状态重新编号;(3) 对上述形成的状态图进行修正,以满足识别合适单词的要求。(4) 如有必要,在合适的位置增加出错状态。二、用直接转向法实现有限自动机的代码,生成对应的词法分析程序。要严格按照给出的 DFA,对每
6、个状态编写对应的识别代码,然后对每个状态的代码用合适的分支、循环等语句进行整合,完成整个代码的合成工作,并上机进行调试。对实现的代码进行测试,给出合适的测试用例(要求至少有 3 个用例,二个正确识别所有的保留字、标识符、分界符、数字等;另外一个识别错误的单词。1. 样例 1输入收集于网络,如有侵权请联系管理员删除精品文档输出生成的 txt程序列表2. 样例 2输入(部分)收集于网络,如有侵权请联系管理员删除精品文档输出(部分)生成的 txt程序列表(部分)收集于网络,如有侵权请联系管理员删除精品文档3. 样例 3(小数)三、用自动生成工具 LEX生成上述给定 DFA所对应的 PL0语言的词法分
7、析程序。并进行调试,用上述 3 个测试用例进行测试,给出测试结果。编写 LEX文件运用 flex生成 lex.yy.c文件收集于网络,如有侵权请联系管理员删除精品文档运行结果样例 1样例 2(部分)收集于网络,如有侵权请联系管理员删除精品文档样例 3(小数)五、实验小结FLEX通过对 LEX源文件的扫描自动生成相应的语法分析函数,生成lex.yy.c程序。 LEX具有“最长匹配原则”和“最先匹配原则”,能够使用简洁的正规表达式去实现语法分析程序,而且lex.yy.c中定义了很多用户可定义的全局变量以及在LEX源文件的动作中可调用的函数和宏,具有良好的可移植性。但是 LEX对源文件的格式要求非常
8、严格,而且 LEX本身的查错能力很弱,所以书写时一定要特别注意。C语言提供大量的函数,其中包括系统生成的函数和用户定义的函数,语法也很容易理解,使用 C 语言实现语法分析程序可以较好地掌握程序的分支和流程,但是代码量很多,容易出现错误,书写的时候需要特别细心。实验的处理单词集 ( 仅供参考 )(注:单词种类统一分类如下:)单词符号单词种类空0标识符1整数2+3-4*5/6=7收集于网络,如有侵权请联系管理员删除精品文档8910=12(13)141516;17,18“19:=20var21if22then23else24while25for26begin27writeln28procedure29end30出错100收集于网络,如有侵权请联系管理员删除