编译原理课程实验报告示例(共27页).doc

《编译原理课程实验报告示例(共27页).doc》由会员分享，可在线阅读，更多相关《编译原理课程实验报告示例(共27页).doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上1完成日期：2007-6-20指导老师：蒋宗礼 张悦编译原理实验报告 张悦专心-专注-专业2词法的正规式描述标识符：|(|)*(|_|.) (|)*十 进 制 数 ： (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)五系统实现（一）词法分析器的实现四系统设计完成整个系统，实现本个实验的要求，需要两个比较大的模块：词法分析器 和语法分析器。词法分析器的功能是将输入的程序串分解成一个一个独立的单词，并且记录 下每个单词的类型以及数值。这里词法分析器的实现有两种方法：调用一次词法

2、分析器，返回一个词的类型以及数值，以此类推；还有一种方法是条用一次词法 分析器将程序串的所有单词都分解出来并保存到一个地方（比如线形表）以便将 来使用。我采用的是前者，因为这样只需要对整个程序访问一遍语法分析器的功能是将已经分解好的单词按照一定的规范（产生式）组合起 来，由此来确定输入程序的意思。我的设计是“语法分析器调用词法分析器”， 当语法分析其分析进行不下去的时候调用词法分析器获取一个单词，继续进行分 析。而语义功能是镶嵌在语法分析其当中的，当语法分析器分析出用什么产生式 的时候作相应的语义处理。3 编写测试程序，反复调用函数scan( )，输出单词种别和属性。4 改写文法，构造语法分析

3、程序，要求按照最左派生的顺序输出派生的产 生式序列；5 改写语法分析程序，构造三地址代码生成程序。6 处理的源程序存放在文件中，它可以包含多个语句；从键盘读入数据，分析出一个单词。返回单词种别（用整数表示）， 返回单词属性（不同的属性可以放在不同的全局变量中）。1）2）3）三. 实验要求1 编制正规式以及正规文法，画出状态图；2 根据状态图，设计词法分析函数int scan( )，完成以下功能：二. 实验内容1编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法 分析程序。2用二维预约分析表，编制一个能够进行语法分析并生成派生的产生式序 列的编译程序。3用递归子程序法，编制一个能够进

4、行语法分析并生成三地址代码的微型 编译程序。一. 实验目的基本掌握计算机语言的词法分析程序的开发方法。以及掌握计算机语言的语 法分析程序设计与属性文法应用的实现方法。锻炼自己的编程能力和逻辑思维能 力，体会计算机编译器的奥妙之处 张悦3、状态图：-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|

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)母字、改变后的

6、正规文法- - 0 - 0x -+| - |* |/ | |= |( | ) |；-if| then| else |while |do(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|

7、4|5|6|7|8|9|a|b|c|d|e|f)*运算符和分隔符：+ - * / = ( ) ;关键字：if then else while do 张悦09091.2309070719.567.07170040.13x|X0f0f字母81f9.100f1112分隔符014.|_字母或数字1516字母或数字17字母或数字4strcpy(node-type,#);strcpy(node-value,_);return false; /表示文件结束if(temp = #)读取一个字符到 temp;node = new CNode;while(1)/返回的节点/当前状态号int state = 0;i

8、nt si = 0; /对于控制 s 的下标/保留字符串char s100;、算法（伪码）：bool MyScan(FILE* fp,CNode* &node)char temp; /当前读取的字符、数据结构：char* arrBao5 = if,then,else,do,while;/保留字表typedef structchar typeTYPE_MAX;char valueVALUE_MAX;CNode;/词法分析的节点，保留分析出的 token 的种类和值 张悦5;添 加 当 前 字 符state=14;state=9;添 加 当 前 字 符if(temp 为十六进制数)continue

9、;if(temp 为 0)else 出错处理; return false;case 8: /状态 8return true;保存为 INT8;if(temp 为分隔符)添加当前字符; continue;添加当前字符; continue;else 出错处理; return false;case 6: /状态 6if(temp 为 07) state=7;else 出错处理; return false;case 7: /状态 7if(temp 为 07) state=7;return true;保存为 INT8;if(temp 为分隔符)if(temp 为 07) state=5;state=6;

10、添加当前字符; continue;添加当前字符; continue;if(temp 为小数点)else 出错处理; return false;case 5: /状态 5return true;保存为 INT10;state=8;if(temp 为 x 或 X)if(temp 为分隔符)state=5;state=13;if(temp 为 17)if(temp 为 0)state=2;添加当前字符; continue;添加当前字符; continue; 添加当前字符; continue; 添加当前字符; continue;if(temp 为小数点)else 出错处理; return false;

11、case 4: /状态 4return true;保存为 REAL10;if(temp 为分隔符)添加当前字符; continue;添加当前字符; continue;else 出错处理; return false;case 2: /状态 2if(temp 为数字) state=3;else 出错处理; return false;case 3: /状态 3if(temp 为数字) state=3;保存为 INT10; return true;state=2;if(temp 为小数点)if(temp 为分隔符)添加当前字符; continue;添加当前字符; continue;else 出错处理;

12、 return false;case 1: /状态 1if(temp 为数字) state=4;和制表符/忽略多个空格和回车if(temp 为空格或回车或 tab) continue;return true;保存相应的分隔符到 node;state=4;state=1;state=12;添加当前字符; continue;添加当前字符; continue;添加当前字符; continue;switch（state）case 0: /状态 0 if(temp 为 0) if(temp 为 1 到 9) if(temp 为字母) if(temp 为分隔符) 张悦6添加当前字符 ;state=16;i

13、f(temp 为数字或者字母)case 16:/状态 16else 出错处理; return false;return true;else 保存为 IDN;if(temp 为分隔符)if(为保留字) 保存为保留字; return true;continue;state=16;添加当前字符 ;if(temp 为数字或者字母)/状态 15case 15:else 出错处理; return false;保存为 INT16; return true;if(temp 为分隔符)添加当前字符; continue;if(temp 为.) state=10;case 14:/状态 14else 出错处理; r

14、eturn false;return true;保存为 INT8;添加当前字符; continue;if(temp 为.) state=6;if(temp 为分隔符)case 13:/状态 13else 出错处理; return false;return true;else 保存为 IDN;state=15;添加当前字符 ;if(temp 为_或者.)continue;if(temp 为分隔符)if(为保留字) 保存为保留字; return true;continue;state=12;添加当前字符 ;if(temp 为数字或者字母)/状态 12case 12:else 出错处理; retur

15、n false;return true;保存为 INT16;if(temp 为分隔符)continue;符字前当添 加if(temp 为十六进制数)state=11;/状态 11case 11:;符字前当添 加if(temp 为十六进制数)state=11;continue;else 出错处理; return false;case 10:/状态 10else 出错处理; return false;return true;保存为 INT16;符字前当添 加state=10;if(temp 为小数点)continue;if(temp 为分隔符);符字前当添 加continue;else 出错处理;

16、 return false;case 9: /状态 9if(temp 为十六进制数)state=9;continue; 张悦7注：没有按照书上的程序框架进行编程，而且个人认为这种程序框架比书上的好：1，模块化比较强。2，更贴近状态图，可读性高，书上的程序是以“一个终极符得导出”作为 思路，而我是以“一个状态的变化”作为思路。所以只要有了正确的状 态图，不需要梳理复杂的状态的意义，只需要机械的按照每个状态的动 作编程即可。某种意义上来说这样可以让计算机自己生成程序（模块化 非常强）3，容易修改，比如在状态图上新增加或删除一个状态或者一条线，只需要 在相应的状态中作适当的修改即可，无须作大的改动。

17、比如开始我没有 注意标识符的附加要求，知道了之后整个程序已经编写完了，再改动的 时候只是在状态图上添加了两个状态，相应修改了一点点程序，就成功 了。因为各个状态的操作之间基本上没有交集，相对独立。个人比较崇尚这种编程风格。不过这种方式对状态图的正确性要求比较高。 注：算法中的分隔符+ - * / = ( )和空格还有回车。注：此法分析器 MyScan 返回值为 boolean，表示程序是否结束（在文件到最后 用#表示输入结束），而在错误的 token 中，CNode 指针会置为空，以此来表 示该处单词有错误。注：关于出错处理。我的出错处理仅仅是显示 ERROR+出错的状态号，相当于 给出一个出

18、错类型号，而没有实现续编译功能。因为在词法中的续编译功能 没有必要，原因如下：如果一个 token 不符合规范，那么在语法分析器中会fclose(fp); getchar(); return 0;else printf(n);printf(%st%sn,node-type,node-value);/分析成功/主函数源程序int main() FILE* fp; fp=fopen(code1.txt,r); CNode* node; while(MyScan(fp,node) if(node != NULL)else 出错处理; return false;/switch/whilereturn

19、true;else 保存为 IDN;if(temp 为分隔符)if(为保留字) 保存为保留字; return true;continue; 张悦8、思考题1 词法分析能否用空格来区分单词 不能光用空格来区分，比如 3+2，就要用+来分隔出 3、实验过程中遇到的问题我的程序的结构和状态转移图联系非常紧密，所以在最后编程的时候基本上 没有遇到什么困难，主要的问题还是集中在画状态图上。由于对十六进制和八进制数的结构定义不是非常清楚，在读正规式的时候有 了一些偏差，以至于我的状态转移图画了好几遍。而在转移图正确之后，编程过 程就没有什么太大困难了。、测试测试用例：0 92+data 0x3f 00 w

20、hile a+accxx do x=x-1;a=6.2+a*0X88.80;if ab then a=b else a=b-1+c;# 测试用例说明：本测试用例测试了十进制数，八进制数，十六进制数，十进制0， 八进制0，十进制小数，八进制小数，十六进制小数，各个关键字以及分隔符， 对于空格，回车，制表符的测试，基本上全了。由于词法分析器中不支持续编译（理由已在上面阐述），所以出错的例子无法在一个文件中给出，这里忽略。 分析的结果如下：报告错误，然后语法分析器会再次调用此法分析器，以分解出下一个 token，不会对程序造成影响，所以词法分析器的出错处理不需要续编译 张悦92 程序设计中哪些环节影

21、响词法分析的效率？如何提高效率我的程序中由于用了 while（1），每次都要判断一下当前状态，所以会有一 些效率的影响。解决的方法是改成书上的结构，即以“一个终极符的产生”作为 分支。但是这样会失去了上面所说的好处。所以我不打算修改 张悦X- null22F-int1621E-TE10F-int1020E-+TE9F-int819E-TE8F-id18C- =E7C-EC17C- (E)16C- E5T-null15S-while C do S4T-/FT14X- else S3T-*FT13S-if C then S X2T-FT12S-ID = E1E-null11S-S;23产生式序号产

22、生式序号,=CId, int8, int10, int16,(FThen,do,),;,=+,-EId, int8, int10, int16,(EId, int8, int10, int16,(C;elseXId,if,whileSId,if,whileSFOLLOWFIRST232323S+dowhileelsethenifint16int10int8id10、二维预测分析表注：判断文法是不是 LL（1）的方法还有一个：按照 FIRST 集和 FOLLOW 集画二维预约分析表，如果分析表每一个格种至多有一个取值，则文法为 LL（1）文法。 这里没有求出所有的 FOLLOW 集，可以画预约分

23、析表然后看该文法是否为 LL（1）（事实表明该文法是 LL（1）的）集、求各个变量的 FIRST 集和 FOLLOW、改写后的产生式集合（二）使用二维预测分析表做语法分析器写在前面：这个模块我用的是二维预约分析表。如果想用这个方法，首先要 将产生式改写为 LL（1）文法，即去掉左递归，提出最左公因子。然后分别求出 各个变量的 FIRST 集和 FOLLOW 集，判断该文法是否为 LL（1）文法，之后按照 FIRST 集和 FOLLOW 集建立二维预约分析表。这里我自己对文法做了一个规定： 每条语句（多重嵌套的语句算一条语句）之间用；隔开，所以在原来的起始状态 S 前再加一个状态 S。 张悦C2

24、1201918F151515T12121212T91111E8888E17171717C3X421S756C16F1515151515141315T12T111111111110E8E17C22XSS=E,E, =E,/0char* arrChanShengShi24 = ,、程序中用到的数据结构为了节省空间，在二维预约分析表的实现只是记录了产生式序号，然后所有的变 量以及下标（终极符和变量所对应的预约分析表的横纵座标）都存在一维线形表 中，各个表通过下表对应（这种对应方式比较危险，不易修改，但是简单） char* arrBianLiang10 = S,S,X,C,E,E,T,T,F,C;/预

25、约表的 纵坐标char* arrZhongJiFu19 =IDN,INT8,INT10,INT16,if,then,else,while,do,+,-,*,/,(,) ,;,=;/预约表的横坐标int YuYue1019;/二维预约分析表int MyChangeStack(int loc); /完成相应的入栈出栈的程序int getZhongJiFu(char* tmp)bool isBianLiang(char* tmp) /*是否为变量*/int getBianLiang(char* tmp)（续表） 张悦12/出栈popMyS();if(strcmp(node-type,lookTopM

26、yS()=0) /当前字符与栈顶元素匹配/当栈不空（没有规约完成），循环/*语法错误*/while(!isEmptyMyS()if(node = NULL)return;/将 S（始态）入栈while(MyScan(fp,node)if(node = NULL)return; pushMyS(S); printf(n);/开始分析一条语句/*语法错误*/、语法分析器（使用二维预测分析表，输出产生式序列）的算法void MyYuYue(FILE* fp) CNode* node;/*出栈*/*访问栈顶*/*栈是否为空*/*匹配时的栈处理，出栈，并将产生式右边的符号反bool popMyS()ch

27、ar* lookTopMyS()bool isEmptyMyS()int MyChangeStack(int loc)向入栈*/bool pushMyS(char* tmp)/*进栈*/CNode;/词法分析结果/8/9/10/11/12/13/14/15/16/17/18/19/20/21/22/23TE,+TE, -TE, null, FT, *FT, /FT, null, (E), EC, id, int8, int10, int16, null, S;/产生式char* MyStackSTACK_MAX = ;/简单的栈结构typedef structchar typeTYPE_MAX

28、;char valueVALUE_MAX; 张悦13利用二维预约分析表，主要的程序框架看起来非常简单，就是一个循环查表过程。而主要的东西就是建表过程和查到表之后值得相应操作。所以说，用二维 预约分析表和 SLR（1）等等方法在一定程度上都可以说是一个思路，只不过在 建表和程序实现上略有不同。由于我在编写完程序之后才知道有“续编译”这个“要求”，而我的这个程 序已经封装好了，所以不是非常容易修改（需要将预约分析表中所有的没有产生 式的地方加上出错处理），在此不再修改，遇到错误时直接退出程序（不是死机）。fclose(fp);getchar();return 0;MyYuYue(fp);int m

29、ain()FILE* fp;fp=fopen(code2.txt,r);printf(HERE IS AN ERROR! %s n,node-value);return;/else/while/whileelse /出错处理（栈顶元素既不匹配又不是变量）else/出错处理（预约表中没有产生式指向）printf(HERE IS AN ERROR! %s n,node-value);return;/else ifint a = getZhongJiFu(node-type);int b = getBianLiang(lookTopMyS();if(YuYueba != 0)printf(%s%sn

30、,lookTopMyS(),arrChanShengShiYuYueba); MyChangeStack(YuYueba); continue;/获取预约表的横坐标/获取预约表的纵坐标/查表，输出，做栈操作-else if(getBianLiang(lookTopMyS() = 0)/当栈顶元素为变量MyScan(fp,node);continue;一个 token/当语句没有规约完成时，向下读取if(strcmp(node-type,;)!=0) 张悦14、实验过程中遇到的问题在做预约分析表的时候需要先将各个变量的 FIRST 集和 FOLLOW 集求出，由 于产生式比较多，所以在求各个集合

31、的时候总是出问题，做出的预约分析表总是 不对，以至于不能通过某些测试用例。这时再对预约分析表进行修改，如此反复 几次之后，终于可以了。在 MyChangeStack 函数中，需要将栈顶元素出栈，然后根据不同的产生式将 产生式的右部依次反向入栈，在做这个操作的时候，总是不自觉地就正向入栈了。if a = 2 then a = 3 else a = x + y / z;#测试用例说明：由于本程序不支持续编译，所以本测试用例都为正确的语句， 包括了 while do 语句，if then else 语句的测试以及语句之间的嵌套，赋值语句， 条件语句中的带括号的判断语句，四则运算语句（包括运算顺序），

32、基本上涵盖 了所有情况。结果如下：、测试测试用例：while (a3+15)0xa do if x2 = 07 then while yvalue，然后退出程序，可以将之视为一个非常简单的出错处理的方法 张悦If ET E.code = T.code; E.place = T.place; ElseE.place=newtemp()ET1(+|-)T2)*C.code=E1.code|E2.code|gen(“if”,E1.place,”=”,E2.place)|gen(“goto”CE1=E2C.code=E1.code|E2.code|gen(“if”,E1.place,”,E2.plac

33、e)|gen(“goto”C E1”,E2.place)|gen(“goto”C E1E2tmplabel = S.begin;S.begin = newlabel();C.isTrue =newlabel();S1.begin = tmpC-isTrue;C.isFalse = tmpS-next; S1.next = tmpS-begin; S.code=gen(S.begin,”:”)|C.code|gen(C.isTrue,”:”)|S1.code|gen(got o,S.begin)Swhile C doS1X.next = X.begin; X.iselse = false; X.

34、code =”X nullX.next = newlabel();S.next = X.next;S.begin = X.begin; X.iselse = true;X.code=gen(“goto”,X.next)|gen(X.begin,”:”)|S.codeX else SC-isTrue = newlabel();X-begin = S-next;C-isFalse = X-begin;S1-next = X-begin;X-next = S1-next;S.code = C.code|gen(C.isTrue”:”)|S1.code|tmpX.codeSif C then S1XS

35、.code = E.code|gen(IDN,”=”,E.place)SID = ES.next = 0;SS;15,C.isTrue)|gen(“goto”,C.isFalse),C.isTrue)|gen(“goto”,C.isFalse),C.isTrue)|gen(“goto”,C.isFalse)S.code = S.code|gen(S.next, ” :”)、语义规则。用递归子程序时，最左公因子可以不用提取，原因见上（三）使用递归子程序法做三地址码生成器写在前面：递归子程序法的基本思路是：给每一个变量都编写一个函数，产 生式中如果存在变量则调用相应的程序。主函数中调用最开始的程序

36、。这种方法 的思路非常清晰，容易理解，易于控制。我的理解是如果采用此种方法文法可以不是 LL（1）的，原因如下：首先， 文法必须是没有左递归的，否则系统栈会溢出。但是最左公因子可以不用提取出 来：在一个程序中可以先统一做某些操作，然后根据不同的 token 决定接下来走 哪一个分支。而这些“统一的操作”就是最左公因子。所以为了实现简便，也更 容易理解，我没有提取最左公因子。另外，这种方法中可以存在形如 A-B(+B) * 的产生式，因为在用子程序的时候这种产生式可以用循环控制（循环条件为下一 个 token 为+），将两者结合起来，如下的产生式 E-T1(+|-)T2)*也是合法的， 但用预约

37、分析表决不允许这样的产生式出现，这也是递归子程序这种方法的灵活 以及更贴近最原始的产生式的体现。之后，在确定了程序应该进入那个分支后，需要在相应的分支之前加入语义 规则。以此来实现三地址码的生成。 张悦F.place=int16.value;F.code=;Fint16F.place=int10.value;F.code=;Fint10F.place=int8.value;F.code=;Fint8F.place=id.name;F.code=;FidF.place=E.place;F.code=E.code;F (E)If TF T.code = F.code; T.place = F.pl

38、ace; ElseT.place=newtemp() T.code=F1.code|F2.code|gen(T.place,”=”,F1.place,*or/,F2.place) F1.code=T.code;F1.place=T.place;TF1(*|/)F2)*E.code=T1.code|T2.code|gen(E.place,”=”,T1.place,+or-,T2.place) T1.code=E.code;T1.place=E.place;16char codeCODE_MAX;char placeVALUE_MAX;str_T;/Ttypedef structchar codeCODE_MAX;char placeVALUE_MAX;str_E;/Etypedef structchar codeCODE_MAX;int isFalse,isTrue;str_C;/Ctypedef structchar codeCODE_MAX;int begin,next;bool iselse;str_X;/Xtypedef structchar codeCODE_MAX;int begin,next;str_S;/Stypedef structchar codeCODE_MAX;str_S_;/Stypedef struct、三地