logo资料库

编译原理实验报告1编译原理实验报告1.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：doc 举报 版权申诉
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页，剩余部分请下载后查看
    编译原理实验报告 04070010 张悦 指导老师:蒋宗礼 完成日期:2007-6-20 04070010 张悦 2 一. 实验目的 基本掌握计算机语言的词法分析程序的开发方法.以及掌握计算机语言的语 法分析程序设计与属性文法应用的实现方法.锻炼自己的编程能力和逻辑思维能 力,体会计算机编译器的奥妙之处 二. 实验内容 1.编制一个能够分析三种整数,标识符,主要运算符和主要关键字的词法 分析程序. 2.用二维预约分析表,编制一个能够进行语法分析并生成派生的产生式序 列的编译程序. 3.用递归子程序法,编制一个能够进行语法分析并生成三地址代码的微型 编译程序. 三. 实验要求 1. 编制正规式以及正规文法,画出状态图; 2. 根据状态图,设计词法分析函数 int scan( ),完成以下功能: 1) 从键盘读入数据,分析出一个单词. 2) 返回单词种别(用整数表示), 3) 返回单词属性(不同的属性可以放在不同的全局变量中). 3. 编写测试程序,反复调用函数 scan( ),输出单词种别和属性. 4. 改写文法,构造语法分析程序,要求按照最左派生的顺序输出派生的产 生式序列; 5. 改写语法分析程序,构造三地址代码生成程序. 6. 处理的源程序存放在文件中,它可以包含多个语句; 四.系统设计 完成整个系统,实现本个实验的要求,需要两个比较大的模块:词法分析器 和语法分析器. 词法分析器的功能是将输入的程序串分解成一个一个独立的单词,并且记录 下每个单词的类型以及数值.这里词法分析器的实现有两种方法:调用一次词法 分析器,返回一个词的类型以及数值,以此类推;还有一种方法是条用一次词法 分析器将程序串的所有单词都分解出来并保存到一个地方(比如线形表)以便将 来使用.我采用的是前者,因为这样只需要对整个程序访问一遍 语法分析器的功能是将已经分解好的单词按照一定的规范(产生式)组合起 来,由此来确定输入程序的意思.我的设计是"语法分析器调用词法分析器", 当语法分析其分析进行不下去的时候调用词法分析器获取一个单词,继续进行分 析.而语义功能是镶嵌在语法分析其当中的,当语法分析器分析出用什么产生式
    的时候作相应的语义处理. 五.系统实现 (一)词法分析器的实现 词法的正规式描述 标识符:|(|)*(ε|_|.) (|)* 十进制数:(0|(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*)(ε|.)(0|1|2|3|4|5|6|7|8|9) 04070010 张悦 3 (0|1|2|3|4|5|6|7|8|9)* 八进制数:0(0|(1|2|3|4|5|6|7) (0|1|2|3|4|5|6|7)*) (ε|.)(0|1|2|3|4|5|6|7) (0|1|2|3|4|5|6|7)* 十六进制数:0x(0(|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f) (0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)*) (ε|.)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f) (0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)* 运算符和分隔符:+ - * / = ( ) ; 关键字:if then else while do ,改变后的正规文法 -> -> -> 0 -> 0x ->+| - |* |/ |>| < |= |( | ) |; ->if| then| else |while |do ->a|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q| R|S|T|U|V|W|X|Y|Z ->0|1|2|3|4|5|6|7|8|9 -> (|)|ε -> (ε|_|.) -> (ε|.) -> (0|1|2|3|4|5|6|7)|ε -> (0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f) |ε 将状态合起来,得: (0)->(1)|0(4)|(12)|(17) (1)->(1)|. (2) (2)->(3) (3)->(3) (4)->.(2)|(5)|0(13)|x(8)|X(8) (5)->(5)|.(6) (6)->(7) (7)->(7) (8)->(9)|(9)|0(14) (9)->(9)|(9)|.(10) (10)->(11)|(11) (11)->(11)|(11)
    (12)->(12)|(12)|(12)|.(15)|_(15) (13)->.(6) (14)->.(10) (15)->(16)|(16)|(16) (16)->(16)|(16)|(16) ,状态图: 04070010 张悦 4 0 1 8 23 4 567 13 9 12 14 10 11 1516 0 1~9 字母 . . . . . . 0~9 0~9 1~7 0~70~7 0~9 0~7 0 x|X 0 1~f 0~f 0~f 0~f 字母或数字 字母或数字
    字母或数字 .|_ 分隔符 17 ,数据结构: char* arrBao[5] = {"if","then","else","do","while"};//保留字表 typedef struct{ char type[TYPE_MAX]; char value[VALUE_MAX]; }CNode;//词法分析的节点,保留分析出的 token 的种类和值 ,算法(伪码): bool MyScan(FILE* fp,CNode* &node){ char temp; //当前读取的字符 char s[100]; //保留字符串 int si = 0; //对于控制 s 的下标 int state = 0; //当前状态号 node = new CNode; //返回的节点 while(1){ 读取一个字符到 temp; if(temp == '#') { strcpy(node->type,"#"); strcpy(node->value,"_"); return false; //表示文件结束 } 04070010 张悦 5 switch(state){ case 0: //状态0 if(temp 为0) state=4; 添加当前字符; continue; if(temp 为1到9) state=1; 添加当前字符; continue; if(temp 为字母) state=12; 添加当前字符; continue; if(temp 为分隔符) 保存相应的分隔符到 node; return true; if(temp 为空格或回车或 tab) continue; //忽略多个空格和回车 和制表符 else 出错处理; return false; case 1: //状态1 if(temp 为数字) state=4; 添加当前字符; continue; if(temp 为小数点) state=2; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT10; return true; else 出错处理; return false; case 2: //状态2 if(temp 为数字) state=3; 添加当前字符; continue; else 出错处理; return false;
    case 3: //状态3 if(temp 为数字) state=3; 添加当前字符; continue; if(temp 为分隔符) 保存为 REAL10; return true; else 出错处理; return false; case 4: //状态4 if(temp 为小数点) state=2; 添加当前字符; continue; if(temp 为1~7) state=5; 添加当前字符; continue; if(temp 为0) state=13; 添加当前字符; continue; if(temp 为 x 或 X) state=8; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT10; return true; else 出错处理; return false; case 5: //状态5 if(temp 为小数点) state=6; 添加当前字符; continue; if(temp 为0~7) state=5; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT8; return true; else 出错处理; return false; case 6: //状态6 if(temp 为0~7) state=7; 添加当前字符; continue; else 出错处理; return false; case 7: //状态7 if(temp 为0~7) state=7; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT8; return true; else 出错处理; return false; case 8: //状态8 if(temp 为十六进制数) state=9; 添加当前字符; continue; if(temp 为0) state=14; 添加当前字符; 04070010 张悦 6 continue; else 出错处理; return false; case 9: //状态9 if(temp 为十六进制数) state=9; 添加当前字符; continue; if(temp 为小数点) state=10; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT16; return true; else 出错处理; return false; case 10: //状态10 if(temp 为十六进制数) state=11; 添加当前字符; continue; else 出错处理; return false; case 11: //状态11 if(temp 为十六进制数) state=11; 添加当前字符;
    continue; if(temp 为分隔符) 保存为 INT16; return true; else 出错处理; return false; case 12: //状态12 if(temp 为数字或者字母) state=12; 添加当前字符; continue; if(temp 为_或者.) state=15; 添加当前字符; continue; if(temp 为分隔符) if(为保留字) 保存为保留字; return true; else 保存为 IDN; return true; else 出错处理; return false; case 13: //状态13 if(temp 为.) state=6; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT8; return true; else 出错处理; return false; case 14: //状态14 if(temp 为.) state=10; 添加当前字符; continue; if(temp 为分隔符) 保存为 INT16; return true; else 出错处理; return false; case 15: //状态15 if(temp 为数字或者字母) state=16; 添加当前字符; continue; if(temp 为分隔符) if(为保留字) 保存为保留字; return true; else 保存为 IDN; return true; else 出错处理; return false; case 16: //状态16 if(temp 为数字或者字母) state=16; 添加当前字符; 04070010 张悦 7 continue; if(temp 为分隔符) if(为保留字) 保存为保留字; return true; else 保存为 IDN; return true; else 出错处理; return false; }//switch }//while } //主函数源程序 int main(){ FILE* fp; fp=fopen("code1.txt","r"); CNode* node;
    while(MyScan(fp,node)) { if(node != NULL){ //分析成功 printf("%s\t%s\n",node->type,node->value); } else printf("\n"); } fclose(fp); getchar(); return 0; } 注:没有按照书上的程序框架进行编程,而且个人认为这种程序框架比书上的好: 1,模块化比较强. 2,更贴近状态图,可读性高,书上的程序是以"一个终极符得导出"作为 思路,而我是以"一个状态的变化"作为思路.所以只要有了正确的状 态图,不需要梳理复杂的状态的意义,只需要机械的按照每个状态的动 作编程即可.某种意义上来说这样可以让计算机自己生成程序(模块化 非常强) 3,容易修改,比如在状态图上新增加或删除一个状态或者一条线,只需要 在相应的状态中作适当的修改即可,无须作大的改动.比如开始我没有 注意标识符的附加要求,知道了之后整个程序已经编写完了,再改动的 时候只是在状态图上添加了两个状态,相应修改了一点点程序,就成功 了.因为各个状态的操作之间基本上没有交集,相对独立. 个人比较崇尚这种编程风格.不过这种方式对状态图的正确性要求比较高. 注:算法中的分隔符+ - * / = ( )和空格还有回车. 注:此法分析器 MyScan 返回值为 boolean,表示程序是否结束(在文件到最后 用#表示输入结束),而在错误的 token 中,CNode 指针会置为空,以此来表 示该处单词有错误. 注:关于出错处理.我的出错处理仅仅是显示 ERROR+出错的状态号,相当于 给出一个出错类型号,而没有实现续编译功能.因为在词法中的续编译功能 没有必要,原因如下:如果一个 token 不符合规范,那么在语法分析器中会 04070010 张悦 8 报告错误,然后语法分析器会再次调用此法分析器,以分解出下一个 token, 不会对程序造成影响,所以词法分析器的出错处理不需要续编译 ,测试 测试用例: 0 92+data> 0x3f 00 while a+acc>xx do x=x-1; a=6.2+a*0X88.80; if a>b then a=b else a=b-1+c;# 测试用例说明:本测试用例测试了十进制数,八进制数,十六进制数,十进制0, 八进制0,十进制小数,八进制小数,十六进制小数,各个关键字以及分隔符, 对于空格,回车,制表符的测试,基本上全了.由于词法分析器中不支持续编译 (理由已在上面阐述),所以出错的例子无法在一个文件中给出,这里忽略. 分析的结果如下:
    ,实验过程中遇到的问题 我的程序的结构和状态转移图联系非常紧密,所以在最后编程的时候基本上 没有遇到什么困难,主要的问题还是集中在画状态图上. 由于对十六进制和八进制数的结构定义不是非常清楚,在读正规式的时候有 了一些偏差,以至于我的状态转移图画了好几遍.而在转移图正确之后,编程过 程就没有什么太大困难了. ,思考题 1词法分析能否用空格来区分单词 不能光用空格来区分,比如3+2,就要用+来分隔出3 04070010 张悦 9 2程序设计中哪些环节影响词法分析的效率 如何提高效率 我的程序中由于用了 while(1),每次都要判断一下当前状态,所以会有一 些效率的影响.解决的方法是改成书上的结构,即以"一个终极符的产生"作为 分支.但是这样会失去了上面所说的好处.所以我不打算修改 04070010 张悦 10 (二)使用二维预测分析表做语法分析器 写在前面:这个模块我用的是二维预约分析表.如果想用这个方法,首先要 将产生式改写为 LL(1)文法,即去掉左递归,提出最左公因子.然后分别求出 各个变量的 FIRST 集和 FOLLOW 集,判断该文法是否为 LL(1)文法,之后按照 FIRST 集和 FOLLOW 集建立二维预约分析表.这里我自己对文法做了一个规定: 每条语句(多重嵌套的语句算一条语句)之间用;隔开,所以在原来的起始状态 S 前再加一个状态 S'. ,改写后的产生式集合 序号 产生式 序号 产生式 23 S'->S; 11 E'->null 1 S->ID = E 12 T->FT' 2 S->if C then S X 13 T'->*FT' 3 X-> else S 14 T'->/FT' 4 S->while C do S 15 T'->null 5 C'-> >E 16 F->(E) 6 C'-> EC' 7 C'-> =E 18 F->id 8 E->TE' 19 F->int8 9 E'->+TE' 20 F->int10 10 E'->-TE' 21 F->int16 22 X-> null
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料