编译原理课程设计将FOR语句转换成四元式的程序实现

PAGE3编译原理实验报告设计题目设计题目将FOR语句转换成四元式的程序实现学号学号学生姓名专业班级专业班级指导教师指导教师罗珣目录引言2第一章概述31.1设计内容31.2设计要求3第二章设计的基本原理32.1词法分析32.2语法分析32.3语义分析32.4文法描述32.5属性文法描述42.6语法分析方法描述52.7操作符优先级62.8中间代码形式描述62.9中间代码序列的结构设计7第三章程序设计73.1总体方案设计73.2各模块设计8程序测试94.1测试方法94.2测试结果9第五章结论16参考文献17附录程序清单17合肥工业大学课程设计任务书设计题目将FOR语句转换成四元式的程序实现成绩主要内容设计内容及要求：设计一个语法制导翻译器，将FOR语句翻译成四元式。要求：先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力。程序设计方案。论文论述，文理，格式。程序运行结果。程序验收时回答问题。签名：第一章概述1.1设计内容设计一个语法制导翻译器，将FOR语句翻译成四元式。1.2设计要求先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。第二章设计的基本原理2．1词法分析设计词法分析算法，每当语法分析程序需要一个单词时，则调用该算法函数。词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词，送给语法分析器2．2语法分析采用递归下降方法，为对应文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。若输入串是给定文法的句子，则从文法的开始符号出发一定能推导出与输入的单词串完全相同的句子。2．3语义分析在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并生成四元式的中间代码形式。2．4文法描述递归下降法要求文法满足LL(1)文法，则消除左递归后的文法如下：start→spsceofspsc→for[parse;parse;parse]{spsclist}|e list→parse;list |e parse→cdexprmorecdexprsmorecdexprs→=cdexprmorecdexprs|ecdexpr→cdsexprmorecdsexprsmorecdsexprs→||cdsexprmorecdsexprs |ecdsexpr→cdtermmorecdtermsmorecdterms→&&cdtermmorecdterms|ecdterm→cdstermmorecdstermsmorecdsterms→==cdstermmorecdsterms|!=cdstermmorecdsterms |ecdsterm→exprmoreexprsmoreexprs→<exprmoreexprs |<=exprmoreexprs |>exprmoreexprs |>=exprmoreexprs |eexpr→termmoretermsmoreterms→+termmoreterms |-termmoreterms |eterm→factormorefactorsmorefactors→*factormorefactors|/factormorefactors |efactor→!factor|(cdexpr)|id|num图1FOR循环语句文法描述2．5属性文法描述将语义规则附加在文法产生式的合适位置上，构成属性文法如下：start→spsceofspsc→for[parse;parse;parse]{spsclist}|e list→parse;list |e parse→cdexprmorecdexprsmorecdexprs→=cdexpr{print(“=”)}morecdexprs|ecdexpr→cdsexprmorecdsexprsmorecdsexprs→||cdsexpr{print(“||”)}morecdsexprs |ecdsexpr→cdtermmorecdtermsmorecdterms→&&cdterm{print(“&&”)}morecdterms|ecdterm→cdstermmorecdstermsmorecdsterms→==cdsterm{print(“==”)}morecdsterms|!=cdsterm{print(“!=”)}morecdsterms |ecdsterm→exprmoreexprsmoreexprs→<expr{print(“<”)}moreexprs |<=expr{print(“<=”)}moreexprs |>expr{print(“>”)}moreexprs |>=expr{print(“>=”)}moreexprs |eexpr→termmoretermsmoreterms→+term{print(“+”)}moreterms |-term{print(“-”)}moreterms |eterm→factormorefactorsmorefactors→*factor{print(“*”)}morefactors|/factor{print(“/”)}morefactors |efactor→!factor{print(“!”)}|(cdexpr)|id{print(id.lexeme)}|num{print(num.value)}图2FOR循环语句属性文法描述2.6语法分析方法描述递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根据输入字符串进行最左推导，试图推导出给定的字符串。或者说，从根节点（文法开始符号）开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法树的节点。递归下降分析法可能需要回溯，即需要重复地扫描输入。递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL（1）形式唯一地确定选择某个候选式进行推导，因此首先要消除左递归。其文法及属性文法如图1和图2所示。由于递归下降法对每个过程可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出规律，通常开辟栈来处理。2.7操作符优先级在对for循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。在文法的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表所示：优先级操作符类型操作对象的个数结合性1（）逻辑运算符——左—>右2!逻辑非运算符单目运算符右—>左3*,/算术运算符双目运算符左—>右4+，-算术运算符双目运算符左—>右5<,<=,>,>=关系运算符双目运算符左—>右6==,!=关系运算符双目运算符左—>右7&&逻辑与运算符双目运算符左—>右8||逻辑或运算符双目运算符左—>右9=赋值运算符双目运算符右—>左2.8中间代码形式的描述常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。本课题设计输出的中间代码的表示方法是四元式。它是带有四个域的记录结构，这四个域分别称为算符op，第一运算对象arg1，第二运算对象arg2及结果result。域op包含一个代表运算符的内部码。例如x=yopz的四元式表示为（op,y,z,x）,即将y置于arg1域，z置于arg2域，x置于result域，=置于算符域op，如果op是单目运算符，例如非‘！’(x=!y)的四元式表示形式中不用填arg2。通常，四元式中的arg1，arg2和result的内容都是一个指针，此指针指向有关名字的符号表入口。这样，临时变量名也要填入符号表中。2.9中间代码序列的结构设计型如for[parse1;parse2;parse3]{list}的中间代码序列的结构设计如下：parse1parse1parse2parse3listTRUEENDFALSE图3中间代码序列结构设计第三章程序设计3．1总体方案设计本程序采用递归下降的方法实现FOR循环语句的翻译，并以四元式的中间代码形式输出。经过词法分析，语法分析，同时执行语法制导翻译将中间结果表达出来，然后通过一个函数转化成要求的四元式结构的中间代码。上述的这个过程在一遍扫描过程中完成：在语法分析的过程中调用词法分析来不断的分解出下一个句柄；在用递归下降方法进行语法分析的同时进行中间形式数据的保存，在分析出操作符号的同时结合当前栈中的数据输出四元式。源文件源文件词法分析语法分析语义分析中间代码出错处理3.2各模块方案设计程序中各阶段的功能如下：词法分析阶段对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号表中没有此标识符的记录，那么将此标识符插入符号表。最后按照单词其所属的类别，把类标识返回，作为语法分析阶段的输入。词法分析算法在symr.h头文件中：voidsymbolnum()；voidsymbolchar()；voidsymbolothers()；intSymbolanalysis()；语法及语义分析阶段由文法开始符号对应的子程序控制for循环语句各个模块的执行顺序，并由文法开始符号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完成对输入字符进行匹配的工作，试图推导出与输入符号串一致的文法的句子。voidFor_s1(int*k,int*j)；//初值赋值语句voidFor_s2(int*k,int*j)；//条件判断语句voidFor_s3(int*k,int*j)；//变量更新语句voidTrans_for();//for语句入口voidphrasinganalyse()；//语法语义分析中间代码生成阶段控制代码的输出形式，以四元式形式输出中间代码。中间代码最终以cout语句和outfile、outfile2、oufile3文件输出结果。程序测试4.1测试方法由于本程序在设计上考虑到for循环语句的多种表现形式，如for嵌套的方式，条件语句的表述等，所以在理论上能完成的功能很全，因此为了测试程序在实际应用中能否完成这些功能，我设计了三种测试途径：输入最简单的for循环语句（无嵌套）增加条件语句的复杂度实现简单for嵌套，可包括多个赋值语句4.2测试结果（1）简单的for循环语句（无嵌套）图5简单FOR循环输入文件图6词法分析二元式结果图7四元式输出（2）增加条件语句的复杂度图8FOR循环输入图9词法分析结果图10四元式输出（3）简单for循环嵌套图11内嵌FOR循环输入图12词法分析结果图13四元式输出结论本程序实现的功能有：简单for循环，for循环嵌套，赋值语句，能完成的计算功能有布尔表达式，基本的四则运算，能将各个功能结合起来形成for循环，赋值语句，布尔表达式，空语句的复合出现。for语句的实现上，通过将之分解成三个表达式来分别调用，初值赋值语句、条件控制语句和变量更新语句。在词法分析阶段，区分一元和二元操作符的方法是：当取得的第一个字符为一元操作符时，继续取下一个字符，若仍为操作符，则返回宏定义的标号，若不是操作符则将其放回，返回一元操作符的标号。在词法分析阶段在每一个类型判断中都需要进行放回操作。对语法分析，词法分析，四元式输出分离设计，同步控制，使得代码更灵活，结构更紧凑，不必要对中间结果进行大量重复的存储后，然后逐一检索后使用。此次课程设计让我想了老师说过的一句话：“编译原理这门课很难”。经过这次课程设计，我更体会到了这句话的含义。编译原理这门课，不仅难理解而且很抽象。很多知识需要仔细琢磨才能理解，很多概念都很抽象，不找到例子很难搞明白。由于我本人C++编程并不好，很多的东西都不懂。所以，这次课程设计，我参考和查找了很多资料，也找同学询问不懂的地方，请他们帮忙讲解。经过几天的努力，按照以上所述的研制过程，终于做完了这次课程设计。将一个抽象的过程转变为详细的结果，显示出来。实现这个过程，是很有难度的。在设计时，通过仔细分析各功能程序段之间的联系、函数的调用实现和程序代码的运行效率，最终制定出了完整的程序实现方案。本程序采用C++语言编写，在编码的过程中使我熟悉了C++语言的语法和库函数的使用，以及数据结构的应用。现在我能熟练的运用他们了，而且通过查看源代码，对大部分库函数的内部实现有了一个很好的把握。通过此次课程设计，让我看到了自己的很多不足之处。很多知识点知识浅尝辄止，只看到了皮毛，没有深入理解。人都是有惰性的，我也不例外。很多问题，都不愿意仔细思考。做事没耐心，不能坚持到最后，轻易放弃也是我的重大缺点。这些问题，以后我必须尽量改正。只有这样，才能有利于自己的发展，自己才能成为一个合格的大学生。参考文献[1]陈火旺、刘春林、谭庆平、赵克佳、刘越．程序设计语言编译原理（第3版）．国防工业出版社．2007年8月第46次印刷[2]李师贤、李文军等.面向对象程序设计.高等教育出版社.2008年4月第6次印刷附录程序清单#include"symr.h"//S-->forS1S2S3Incycle//S1-->(E1；//S2-->E2;//S3-->E1)//Incycle-->E1;//(E1为赋值语句）//(E2为布尔表达式）voidphrasinganalyse();voideval(int*,int*);charjudge(string,string);voidTrans_for();strings[10]={"T1","T2","T3","T4","T5","T6","T7","T8","T9","T10"};stringad[5]={"Begin","Adress2","Again","Adress4","Exit"};stringad_e[20]={"(0)","(1)","(2)","(3)","(4)","(5)","(6)","(7)","(8)","(9)","(10)","(11)","(12)","(13)","(14)","(15)","(16)","(17)","(18)","(19)"};structgoto_adress{stringname;intvalue;}adress[5];//跳转地址structexpression_adress{stringname;intvalue;}e_adress[20];//四元式地址stack<string>sqstacks;stack<string>sqstackr;fstreamoutfile2("outfile2.txt",ios::out);fstreamoutfile3("outfile3.txt",ios::out);stringbuffer[50];externintn;externSymbolattributesymattri[100];inti;intmain(){i=Symbolanalysis();phrasinganalyse();cin>>i;outfile2.close();return0;}//语法语义分析voidphrasinganalyse(){for(intm=0;m<5;m++)adress[m].name=ad[m];for(m=0;m<20;m++)e_adress[m].name=ad_e[m]; stringtype; stringch; do{ type=symattri[i].stype; if(type=="4"){ ch=symattri[i].svalue; if(ch=="for")Trans_for(); } i++; }while(i<n); return;}//跳转地址回填voidbackpath(intl,int*j){adress[l].value=(*j);}/*循环语句*/voidIncircle(int*k,int*j){ into=i; cout<<adress[2].name<<":"<<endl; outfile2<<ad[2]<<":"<<"\n"; backpath(2,j); while(symattri[i].svalue!=")")i++; while(symattri[i].svalue=="{"||symattri[i].svalue==""||symattri[i].svalue==")"||symattri[i].svalue=="\n")i++; eval(k,j); i=o;}/*初值赋值语句*/voidFor_s1(int*k,int*j){ cout<<adress[0].name<<":"<<endl; outfile2<<adress[0].name<<":"<<"\n"; backpath(0,j); eval(k,j);}/*条件判断语句*/voidFor_s2(int*k,int*j){ cout<<adress[1].name<<":"<<endl; outfile2<<adress[1].name<<":"<<"\n";backpath(1,j); eval(k,j); Incircle(k,j);}/*变量更新语句*/voidFor_s3(int*k,int*j){ cout<<adress[3].name<<":"<<endl; outfile2<<adress[3].name<<":"<<"\n"; backpath(3,j); eval(k,j); cout<<e_adress[*j].name<<"(jump"+adress[1].name+")"<<endl; outfile2<<e_adress[*j].name<<"(jump"+adress[1].name+")"<<"\n"; (*j)++; e_adress[*j].value=(*j); cout<<adress[4].name<<":"<<endl;backpath(4,j); outfile2<<adress[4].name<<":"<<"\n"; cout<<"analysishasfinished"<<endl;}/*for语句入口*/voidTrans_for(){ i++; if(symattri[i].svalue!="(")return;//actually,hereshouldgotoerror(); i++; intk=0; intj=0; For_s1(&k,&j);//S=>S1S2S3 For_s2(&k,&j); For_s3(&k,&j);for(intm=0;m<5;m++){cout<<adress[m].name<<"="<<adress[m].value<<endl;outfile3<<adress[m].name<<"="<<adress[m].value<<"\n";} return;}/*赋值语句分析函数*/voideval(int*k,int*j){ intm=i; stringch; stringsh; string*p; string*q; sqstacks.push("#"); sqstackr.push("#"); while(!(symattri[i].svalue==";")&&!(symattri[i].svalue==")")){ if(symattri[i].stype=="1"||symattri[i].stype=="2"||symattri[i].stype=="3") { ch=symattri[i].svalue; sqstacks.push(ch); i++;} if(!(symattri[i].svalue==";")&&!(symattri[i].svalue==")")) if(symattri[i].stype=="6"){ ch=symattri[i].svalue; p=&sqstackr.top(); switch(judge(ch,*p)){ case'=':; case'>':; sqstackr.push(ch); i++; break; case'<': sqstacks.push(symattri[i+1].svalue); buffer[2]=sqstacks.top();sqstacks.pop(); buffer[1]=sqstackr.top();sqstackr.pop(); buffer[0]=sqstacks.top();sqstacks.pop(); buffer[0]=e_adress[*j].name+"("+buffer[1]+""+buffer[0]+""+buffer[2]+""+s[*k]+")"+"\n"; sqstacks.push(s[*k]); sqstackr.push(ch); (*k)++; (*j)++; e_adress[*j].value=(*j); cout<<*buffer; outfile2<<*buffer; i++; break;} if(!(symattri[i].stype=="1"||symattri[i].stype=="2"||symattri[i].stype=="3"||symattri[i].svalue==";")){ cout<<"cancel"<<endl; } } else{cout<<"wrongsentence"<<endl;i++;} else{while(sqstackr.top()!="#"&&sqstackr.top()!="="&&sqstackr.top()!="<"&&sqstackr.top()!=">"){ buffer[2]=sqstacks.top();sqstacks.pop(); buffer[1]=sqstackr.top();sqstackr.pop(); buffer[0]=sqstacks.top();sqstacks.pop(); buffer[0]=e_adress[*j].name+"("+buffer[1]+""+buffer[0]+""+buffer[2]+""+s[*k]+")"+"\n"; sqstacks.push(s[*k]); //sqstackr.push(ch); cout<<*buffer; outfile2<<*buffer; (*k)++;(*j)++;e_adress[*j].value=(*j);} if(sqstackr.top()=="="){ buffer[2]=sqs