编译原理

《编译原理》考核学号：201《编译原理》实验报告姓名院系计算机与信息技术学院专业计算机科学与技术教师2017年12月前言《编译原理实验指导》的目的是让学生动手设计和实现某一规模适中的语言的编译器，该编译器不仅涉及编译程序的各个阶段，而且也强调了编译的总体设计、各个阶段的接口安排等等。通过上机实践，来设计这个相对完整的编译器，一方面可以使学生增加对编译程序的整体认识和了解——巩固《编译原理》课程所学知识，另一方面，通过上机练习，学生也可以学到很多程序调试技巧和设计大型程序一般的原则，如模块接口的协调，数据结构的合理选择等等。学生应该首先阅读《编译原理实验指导》第一部分，对PL/0编译程序有个初步的印象，其次要认真阅读理解第三部分所给出的PL/0编译器源程序，使上一阶段的初步印象得以加深、具体化，最后按照第二部分的实验要求扩充PL/0语言的功能并加以实现。编译原理的上机实验部分求学生对PL/0语言及其编译器进行扩充和修改。每个扩充或修改方式可得到不同的分数，满分为100分。完成上机作业后，必须提交下列文档：（1）修改后的PL/0语言文本，包含词法分析（正规表达式、DFA、NFA），语法分析（BNF或文法、语法分析表）。（2）给出改动后的编译器源程序清单，并标记出你所修改的部分。比较你的编译器和原来的编译器之间的差别。（3）以实例详细说明改动后的编译器是如何编译新的PL/0语言程序的。（4）说明你的编译器中可能存在的错误。（5）总结经验与教训，如果重做一遍，你会有哪些新的改进？实验一词法分析主要在getsym中完成，实验要求使用正则表达式和自动机理论改写该函数，具体要求为：1.参考getsym，使用正则表达式写出PL/0程序设计语言的词法表达式；（3分）2.将上述正则表达式转为DFA；（4分）3.使用DFA驱动程序改写getsym函数；（4分）4.比较改写前和改写后的getsym函数，分析各自的优缺点；（4分）实验过程1、参考getsym，使用正则表达式写出PL/0程序设计语言的词法表达式；（3分）解答:Algh={‘a-z’,’A-Z’}Digit={0，1，2，3，4，5，6，7，8，9}fuhao={:,=,,}Number={Digit}+Sym={fuhao}+Name=Algh(Algh|Digit)+2、将上述正则表达式转为DFA；（4分）解答：615Other1203457891011121413AlghNumber:==OtherOther=OtherNotNumberNumberNotAlghorNumberAlghorNumberAlgh3、使用DFA驱动程序改写getsym函数；（4分）解答：voidgetsym(void){inti,k;intstate=0;chara[MAXIDLEN+1];while(ch=='')//忽略空白getch();while(1){switch(state){case0:if(isalpha(ch)){k=0;a[k++]=ch;state=1;}elseif(isdigit(ch)){k=num=0;num=num*10+ch-'0';k++;state=2;}elseif(ch==':')state=3;elseif(ch=='')state=4;elseif(ch=='')state=5;elsestate=6;break;case1:getch();if(isalpha(ch)||isdigit(ch)){a[k++]=ch;state=1;}elsestate=7;break;case2:getch();if(isdigit(ch)){num=num*10+ch-'0';k++;state=2;if(kMAXNUMLEN)error(25);}elsestate=8;break;case3:getch();if(ch=='=')//:=state=9;else//:state=10;break;case4:getch();if(ch=='=')//=state=11;else//state=12;break;case5:getch();if(ch=='=')//=state=13;elseif(ch='')//state=14;else//state=15;break;case6:i=NSYM;//i=10csym[0]=ch;while(csym[i--]!=ch);if(++i){sym=ssym[i];printf(识别到SYM_NSYM\n);getch();}else{printf(error:未知字符。\n);exit(1);}return;case7:a[k]=0;strcpy(id,a);word[0]=id;i=NRW;//i=11while(strcmp(id,word[i--]));if(++i){sym=wsym[i];//symbolisareservedwordprintf(识别到保留字\n);}else{sym=SYM_IDENTIFIER;//symbolisanidentifierprintf(识别到SYM_IDENTIFIER\n);}return;case8:sym=SYM_NUMBER;printf(识别到数字\n);return;case9:sym=SYM_BECOMES;printf(识别到SYM_BECOMES\n);getch();return;case10:sym=SYM_NULL;printf(识别到SYM_NULL\n);return;case11:sym=SYM_GEQ;printf(识别到SYM_GEQ\n);getch();return;case12:sym=SYM_GTR;printf(识别到SYM_GTR\n);return;case13:sym=SYM_LEQ;printf(识别到SYM_LEQ\n);getch();return;case14:sym=SYM_NEQ;printf(识别到SYM_NEQ\n);getch();return;case15:sym=SYM_LES;printf(识别到SYM_LES\n);return;}}}4、比较改写前和改写后的getsym函数，分析各自的优缺点；（4分）解答：改写前：可以实现词法分析且简单易懂，但是程序较复杂。进行功能扩展时，需要在全篇的基础上进行修改。改写后：进行功能扩展时，仅需通过增加switch的情况即可。结果分析实验结果：第30行、31行、32行结果在程序运行中，输出了每条语句的内容以及识别到的字符类型。与改写前相同。在识别保留字的过程中，使用传统的匹配识别，速度较慢。实验二添加注释的识别，其中注释由(*和*)包含，不允许嵌套，具体要求为：1.在改写前的getsym函数添加注释的识别；（3分）2.在改写后的getsym函数添加注释的识别；（7分）实验过程1、在改写前的getsym函数添加注释的识别；（3分）解答：if(ch=='('){tmp=ch;getch();if(ch=='*'){getch();do{while(ch!='*'){getch();}getch();}while(ch!=')');printf(这里是注释\n);getch();while(ch=='')getch()；}else{cc--;ch=tmp;}}2、在改写后的getsym函数添加注释的识别；（7分）解答：intflag=0;…elseif(ch=='(')state=16;…switch(stage){…case16:getch();if(flag==0){if(ch=='*'){flag=1;state=16;}else{ch='(';cc--;state=15;}}elseif(flag==1){if(ch=='*'){getch();if(ch==')'){printf(这里是注释);flag=0;getch();while(ch=='')getch();state=0;continue;}}else{state=16;}}结果分析实验结果：改写前和改写后都实现了注释的识别。由于括号可能成对出现，所以给注释的识别添加一定的难度。在改写前的getsym中，若识别为括号，则返回执行原有的判断语法。若识别为注释符号，则进行注释的识别。改写后的getsym中，只需要识别括号和*号即可。实验三语法分析主要在block中完成，分析block函数（不需要考虑语义分析和代码生成部分），并1、参考第一部分的2.6节，理解test函数在错误处理和恢复中用途，并以block函数中test调用为例（在三处调用中选择一处），解释test函数的具体用途；（6分）2、使用LL(1)方法改写该函数；（20分）3、比较改写前和改写后的block函数，分析各自的优缺点；（4分）实验过程1、参考第一部分的2.6节，理解test函数在错误处理和恢复中用途，并以block函数中test调用为例（在三处调用中选择一处），解释test函数的具体用途；（6分）解答：test函数的定义voidtest(symsets1,symsets2,intn){//参考第一部分2.6节symsets;if(!inset(sym,s1)){error(n);s=uniteset(s1,s2);while(!inset(sym,s))getsym();destroyset(s);}}//testtest函数调用处voidfactor(symsetfsys)函数中：voidexpression();inti;symsetset;test(facbegsys,fsys,24);//Thesymbolcannotbeasthebeginningofanexpression.test(symsets1,symsets2,intn);s1是当语法分析进入或退出某一语法单元时当前字符属于的集合。s2是在某一出错状态下，可恢复语法分析正常工作的补充单词集合。n是出错信息的编号，当前字符不属于当前语法的集合时，发出的出错信息。此处的test函数作用为：当前符号不能作为表达式的开头进行语法分析的恢复工作。2、使用LL(1)方法改写该函数；（20分）解答：#defineSTACK_INIT_SIZE100//堆栈最大长度#defineSTACKINCREMENT10//堆栈增加长度enumTERMINAL{IDENT=1,NUMBER,CONST,VAR,ODD,CALL,WHILE,IF,END,DO,BEGIN,THEN,PROCEDURE,FEN,ZK,YK,JIA,JIAN,CHEN,CHU,DENG,XIAO,XIAOD,DA,DAD,BUD,DOT,OVER};enumNONTERMINAL{Prog=100,Prog1,Statement,Statement1,Condition,Expr,Expr1,Term,Term1,Factor,Adding,Mult,Relation};structLead_expression{//表示文法的数据结构intlength;//文法右部的长度intright[37][4];//文法右部的字符序列};structLeadExpleadExp[37];//分配37条文法的空间typedefstruct{//堆栈结构体int*base;int*top;intstacksize;}Stack;Stack*s;voidInitStack(Stack*S){//初始化堆栈S-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S-base){printf(erroe!);exit(0);}S-top=S-base;S-stacksize=STACK_INIT_SIZE;}intGetTop(StackS){//返回栈顶元素inte;if(S.top==S.base){printf(空