编译IF-ELSE条件语句的翻译程序设计(简单优先法、输出三地址表示)代码+报告

学号：0120910340205编译课程设计题目IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）学院计算机科学与技术学院专业计算机科学与技术专业班级计算机科学与技术0902班姓名指导教师郭羽成2012年1月5日武汉理工大学《编译原理》课程设计1课程设计任务书学生姓名：专业班级：计算机0902班指导教师：郭羽成工作单位：计算机科学与技术学院题目:IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码三地址表示的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1系统描述（问题域描述）；2文法及属性文法的描述；3语法分析方法描述及语法分析表设计；4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5编译系统的概要设计；6详细的算法描述（流程图或伪代码）；7软件的测试方法和测试结果；8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名：2011年11月18日系主任（或责任教师）签名：2011年11月18日武汉理工大学《编译原理》课程设计2一.系统描述IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）对条件语句：IF〈布尔表达式〉THEN〈赋值语句〉ELSE〈赋值语句〉（1）写出符合语法分析方法要求的文法和属性文法描述。（2）给出语法分析方法的思想及分析表设计。（3）给出中间代码序列的结构设计。（4）完成相应的词法分析、语法分析和语义分析程序设计。（5）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。二．文法及属性文法的描述ifthenelse文法的产生式为：①S→ifEthenBelseB②E→id1Aid2|id1③A→||==④B→id1=num根据条件语句：IF〈布尔表达式〉THEN〈赋值语句〉ELSE〈赋值语句〉，描述相应的文法，其中共有4个非终结符（S，E，A，B）,终结符10个（if，then，else，id1，id2，，，==，=，num）。E为布尔表达式，B为赋值语句。三．语法分析方法描述及语法分析表设计首先根据已知优先文法构造相应的优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下：1)将输入符号串a1a2……an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。2)栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak，为止。3)由句柄ak……ai在文法的产生式中查找右部为ak……ai的产生式，若找到则用相应左武汉理工大学《编译原理》课程设计3部代替句柄，若找不到则为出错，这是可断定输入串不是该文法的句子。4)重复上述的三个步骤直到归约完输入符号串，栈中只剩文法的开始符号为止。按照优先关系矩阵对输入串ifxythena=2elseu=9的分析过程步骤符号栈优先关系移近或归约输入串1#移近ifxythena=2elseu=9#2#if移近xythena=2elseu=9#3#ifx移近ythena=2elseu=9#4#ifx移近ythena=2elseu=9#5#ifxy归约thena=2elseu=9#6#ifE=移近thena=2elseu=9#7#ifEthen移近a=2elseu=9#8#ifEthena=移近=2elseu=9#9#ifEthena==移近2elseu=9#10#ifEthena=2归约elseu=9#11#ifEthenB=移近elseu=9#12#ifEthenBelse移近u=9#13#ifEthenBelseu=移近=9#14#ifEthenBelseu==移近9#15#ifEthenBelseu=9归约#16#ifEthenBelseB归约#17#S分析成功#四.中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式描述此设计要求使用的是三地址的中间代码,三地址代码是由下面一般形式构成的语句序列:x:=yopz;其中x,y,z为名字,常数或编译时产生的临时变量;op代表运算符号如标点,浮点运算符号等等。每个语句的右边只能有一个运算符。表达式x+y*z翻译成的三地址语句序列是：武汉理工大学《编译原理》课程设计4t1:=y*zt2:=x+t1常用的三地址语句有：赋值语句x:=yopz，x:=opy，x:=y无条件转移gotoL条件转移ifxrelopygotoL过程调用paramx和callp,n过程返回returny索引赋值x:=y[i]和x[i]:=y地址和指针赋值x:=&y，x:=*y和*x:=y4.2中间代码序列的结构设计在本程序的文法中，中间代码的三地址码为：L1：ifid1Aid2gotoL2gotoL3L2：id1=numgotoLnextL3：id1=numgotoLnextLnext：其中id1，id2在具体的程序运行中用输入的单词符号所确定，A代表，，==三种符号，num代表数字。五.编译系统的概要设计在词法分析部分，应用函数word()来识别标识符和关键字，其中用ASCII码来识别字母，如遇到不合法的字符就会报错。在语法分析部分，用简单优先法完成此次文法分析的关键在于构造该文法的简单优先关武汉理工大学《编译原理》课程设计5系矩阵，以及如何运用该矩阵完成移入和归约的过程，从而完成整个文法的分析。求非终结符号的FIRST集和LAST集，利用FIRST集和LAST集求出优先关系，最终构造出简单优先关系矩阵。在整个简单优先关系矩阵构造成功后，我们还应该构造一个堆栈，用来存放符号；并将符号栈中的栈顶元素与输入串队列的队头元素进行比较，然后查找简单优先关系矩阵得到相应的优先关系，从而完成分析表中所要求完成的动作，如果栈中的栈顶元素比输入串队列的队头元素优先关系为或=则将输入串队列的队头元素移入栈中，若为则要将栈中的符号进行归约，这时要找到栈中的句柄归约，若找不到句柄进行归约则输入的符号串不是该文法的句子。找到句柄归约完之后再重复上面的步骤，最后符号栈中最后只剩该文法的开始符号，则整个过程分析成功，否则则分析失败或出现错误。根据栈的归约操作通过cout语句将三地址输出。六．源代码#defineN100#includeiostream#includestring.h#includestdio.husingnamespacestd;staticchara[N];/*存放输入的语句*/staticcharstr[N];/*存放构成单词符号的字符串*/staticintb[N];staticcharcopyy[N][N];staticcharch;staticinti=0;staticintj=0;staticintm;staticintn;intp;inth[14][14];武汉理工大学《编译原理》课程设计6intl[14][14];structlist//定义结点{intdata;list*next;};classstack//定义栈类{private:list*ptr;public:stack(){ptr=NULL;}voidpush(inti);intpop();};voidstack::push(intx){list*q=newlist;q-data=x;q-next=ptr;ptr=q;}intstack::pop(){list*p;intvalue;value=ptr-data;p=ptr;ptr=ptr-next;武汉理工大学《编译原理》课程设计7deletep;returnvalue;}//***************词法分析程序***********************intword(){if((a[i]=65&&a[i]=90)||(a[i]=97&&a[i]=122)){/*识别标识符和关键字*/ch=a[i];str[j]=ch;i++;j++;while((a[i]=65&&a[i]=90)||(a[i]=97&&a[i]=122)||(a[i]=48&&a[i]=57)){ch=a[i];str[j]=ch;i++;j++;}if(a[i]!='')i--;/*使i回调*/if(strcmp(str,if)==0||strcmp(str,IF)==0)return(2);elseif(strcmp(str,then)==0||strcmp(str,THEN)==0)return(3);elseif(strcmp(str,else)==0||strcmp(str,ELSE)==0)return(4);elseif(strcmp(str,AND)==0||strcmp(str,and)==0)武汉理工大学《编译原理》课程设计8return(5);elseif(strcmp(str,or)==0||strcmp(str,OR)==0)return(6);elseif(strcmp(str,not)==0||strcmp(str,NOT)==0)return(7);elsereturn(1);}elseif(a[i]=48&&a[i]=57){/*识别常数*/ch=a[i];str[j]=ch;i++;j++;while((a[i]=48&&a[i]=57)&&iN){ch=a[i];str[j]=ch;i++;j++;}if(a[i]!='')i--;return(8);}elseif(a[i]==''){ch=a[i];str[j]=ch;i++;j++;武汉理工大学《编译原理》课程设计9if(a[i]=='='){ch=a[i];str[j]=ch;return(10);}else{i--;return(9);}}elseif(a[i]==''){ch=a[i];str[j]=ch;i++;j++;if(a[i]=='='){ch=a[i];str[j]=ch;return(12);}else{i--;return(11);}}elseif(a[i]=='!'){ch=a[i];str[j]=ch;i++;武汉理工大学《编译原理》课程设计10j++;if(a[i]=='='){ch=a[i];str[j]=ch;return(13);}else{i--;return(-1);}}elseif(a[i]=='='){ch=a[i];str[j]=ch;i++;j++;if(a[i]=='='){ch=a[i];str[j]=ch;return(15);}else{i--;return(14);}}elseif(a[i]=='('){ch=a[i];str[j]=ch;武汉理工大学《编译原理》课程设计11return(17);}elseif(a[i]==')'){ch=a[i];str[j]=ch;return(18);}elseif(a[i]==''){return(16);}elsereturn(-1);}intbn(){intk=0;while(kstrlen(a)){b[n]=word();if(b[n]==16){i++;k=i;n--;}elseif