《编译原理》课程设计说明书-IF-ELSE条件语句的翻译程序设计（简单优先法、输出四元式）.doc

武汉理工大学编译原理课程设计说明书课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题目: if-else条件语句的翻译程序设计（简单优先法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1系统描述1.1目的1.2设计内容及步骤1.3开发平台2文法及属性文法的描述2.1文法描述2.2属性文法描述3语义分析方法的描述及分析表设计3.1优先关系定义3.2简单优先文法定义3.3简单优先文法的算法步骤3.4语义分析方法描述3.5分析表构造4中间代码形式描述及结构设计5编译系统的概要设计6算法描述6.1预定义模块6.2词法分析6.3语法分析6.4其他模块6.5主程序7测试方法和结果7.1测试方法7.2测试结果8设计总结8.1设计优点8.2设计缺点8.3考虑改进9收获与体会10参考文献if-else条件语句的翻译程序设计（简单优先法、输出四元式）1系统描述1.1实验目的对条件语句：if then else （1） 按给定的题目写出符合语法分析方法要求的文法和属性文法描述。（2） 按给定的题目给出语法分析方法的思想及分析表的设计。（3） 按给定题目给出中间代码序列的结构设计。（4） 完成相应的词法分析、语法分析和语义分析程序设计。（5） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。1.2开发平台visual c+ 6.0、windows xp2文法及属性文法的描述2.1文法描述(1) s-if e then b else b(2) e-(aa)(3) e-(a(a)(5) a-d(6) a-num(7) b-d=c(8) c-a+a(9) c-a-a(10) c-a*a(11) c-a/a(12) c-a其中，d代表变量，num代表常量（这里仅限数字）,e布尔表达式，b为赋值表达式，c为算术表达式2.2属性文法描述（1）e-a rop ae.true=nextstat;e.codebegin=nextstat;e.false=nextstat+1;emit(“if” a.place “rop” a.place “goto” -);emit(“goto” -)（2）e-(a)e.place=a.place（3）a-idp=lookup();if p!=null thena.place=pelse error（4）b-d=cd.place=c.place（5）c-a op ac.place=newtemp;emit(c.place “=” a.place “op” a.place)（6）c-ac.place=a.place注：rop为或y表示x的优先性比y的优先性大xxy（2）xy当且仅当g中存在产生式规则a-xb，b=y，by（3）xbd,b=x,bx,d=y3.2简单优先文法定义若一个文法是简单优先文法必须满足以下条件：（1） 在文法符号集v中，任意两个符号之间最多只有一种优先关系成立（2） 在文法中任意两个产生式没有相同的右部其中第一条是必须满足的，第二条若不满足则会导致规约不唯一。3.3简单优先文法的算法步骤首先根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈s，算法步骤如下：（1） 将输入符号串a1,a2an#依次逐个存入符号栈s中，直到遇到栈顶符号ai的优先性下一个带输入符号aj时为止。（2） 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1a，sa，a为文法符号la（s）=a|s=a，sa，a为文法符号 改造后的优先关系计算当文法中存在a-xy时，x=y当文法中存在a-xb时，xbd时，la（b）d且la（b）fa（d）3.5.2分析表结构分析表采用二维数组存储方式，文法中的每一个符号对应数组a中的一个位置，而aij代表第i个和第j个的优先关系：（1）aii=0无优先关系（2）aii=1i对应元素优先级小于j的（3）aii=2i对应元素优先级大于j的（4）aii=3i对应元素优先级等于j的而在分析过程中规约产生式的选择则在语法分析过程中，在语法分析过程中实现。分析表最终结果如下：int anltable2222=/*s*/0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,/*if*/0,0,3,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,/*e*/0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,/*then*/0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,/*b*/0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,/*else*/0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,/*(*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*)*/0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,/*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*=*/0,0,0,0,0,0,0,0,0,0,0,1,1,1,3,0,0,0,0,0,0,0,/*a*/0,0,0,0,0,0,0,3,3,3,0,0,0,0,0,0,2,3,3,3,3,0,/*d*/0,0,0,0,0,0,0,2,2,2,3,0,0,0,0,0,2,2,2,2,2,0,/*num*/0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,0,2,2,2,2,2,0,/*c*/0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,/*/0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,/*/0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,/*+*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*_*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*/*/0,0,0,0,0,0,0,0,0,0,0,3,1,1,0,0,0,0,0,0,0,0,/*#*/1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,;/0-error ,1= ,3=4中间代码形式描述及结构设计四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象arg1和arg2及运算结果result。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如：a=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（=，t3，-，a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。5编译系统的概要设计（1） 系统主要分为两个模块：词法分析和语法分析（包括语义分析）。并且在分析过程中将词法分析产生的单词输出到文件，语法分析过程中分析栈的变化情况输出到文件。（2） 系统设计采用过程化的设计方法，将词法分析、语法分析等功能模块在独立的过程中实现。（3） 系统概要结构如下：1） 预定义模块2） 词法分析模块3） 语法分析模块4） 其他辅助模块5） 主程序模块（主要指程序入口函数main()）各模块调用关系如下：预定义主程序语法分析词法分析其他辅助模块6算法描述6.1预定义模块预定义模块主要包括宏定义、常量定义、类型定义以及全局变量定义等。具体如下：（1）宏定义#define ok 1 /正常#define error -1 /出错#define failure -1 /分析失败（2）类型定义struct att/名字表类型string sname;char select;char addre;typedef struct sqstack char *base; char *top; int stacksize; sqstack;/栈定义（3）全局变量int lineno = 1;/输出时的当前行号char ch ; /当前字符char allname3030;/单词全名char out3030;/保存单词简称att attname40;/名字表（4）优先关系表初始化（见3.5.2）6.2词法分析词法分析主要为analysis(ifstream &fin,ofstream &fout)函数，其中fin为输入文件流，fout为单词输出文件流。辅助函数为judge(char *string)，判断单词是否为关键字。分析算法如下描述：while(true)字符串存放临时数组temp;if(到文件末尾) break;读取一个字符到ch;if(ch是换行) lineno+=1;else if(ch是字符)while(ch是字符或数字)ch存入temp;读取下一个字符;判断temp是否为关键字，并根据判断结果使temp入名字表并设置正确的属性。else if(ch是数字)while(ch是数字)ch存入temp;读取下一个字符;temp入名字表并设置正确的属性。else if(ch为其他合法字符(如：,=等等) 填入名字表。else 输出错误，无法识别的字符。6.3语法分析语法分析主要为laynax(ofstream &f)函数，其中，f为栈变化情况输出文件。其他辅助函数为除judge(char *string)外的其他所有辅助函数。语法分析的过称描述如下：初始化分析栈；while(还有单词)判断当前栈顶单词与输入单词的优先级；if()while(栈顶元素优先级等于输入单词)保存输入单词；置输入单词为栈顶单词；栈顶元素出栈；判断保存单词串是否为句柄；if(是句柄)进行规约；进行语义规则计算；输出栈的变化情况；使规约后单词为新的输入符号；else输出规约出错；else输出输入单词错误；6.4其他模块其他模块描述如下：（1）栈操作模块void initstack (sqstack &s) /栈初始化s.base=(char*)malloc(stack_init_size*sizeof(char);/分配存储空间 if(!s.base) exit(overflow); /为栈s分配存储空间失败 s.top=s.base; s.stacksize=stack_init_size; int push(sqstack &s,char ch)/将元素e插入到栈s中，成为新的栈顶元素 if(s.top-s.base s.stacksize) /判定栈是否满 s.base=(char*)realloc(s.base,(s.stacksize+stackincrement *sizeof(char); if(!s.base) printf(分配存储单元失败.n); /存储单元分配失败 exit(overflow); s.top=s.base+s.stacksize; /指明栈顶指针的基址 s.stacksize+=stackincrement; /指明栈的空间大小 *s.top+=ch; /先将e送入栈顶指针所指向的单元，再将栈顶指针加 return(ok); int pop(sqstack &s,char &ch) /栈顶元素出栈if(s.top=s.base) printf(溢出); return (error); ch=*-s.top; return(ok); char gettop(sqstack s) /返回栈顶元素if(s.top=s.base) cout栈空，出错endl;char e; e = *(s.top-1); return e; void printstack(sqstack &s,int naa,int ty,ofstream &fout)/输出栈当前情况char temp4020;for(int k=0;k40;k+)for(int t=0;t20;t+)tempkt=null;int te=0;int i=0,j=0;int nu=0;char *ku;ku=s.base;i=naa+1;char *contrl;contrl=s.base;while(contrl!=s.top)if(*contrl!=1)if(*contrl=i)foutif;nu=nu+2;else if(*contrl=t)foutthen;nu=nu+4;else if(*contrl=e)foutelse;nu=nu+4;elsefout*contrl;nu+;contrl+;foutttt;for(i;i=length;i+)if(gettop(s)=s)fout#;elsefoutattnamei.select;if(gettop(s)=s)fout#;elsefouttempte;te+;fout:return 8;break;case :return 9;break;case =:return 10;break;case a:return 11;break;case d:return 12;break;case n:return 13;break;case c:return 14;break;case :return 15;break;case :return 16;break;case +:return 17;break;case -:return 18;break;case *:return 19;break;case /:return 20;break;case #:return 21;break;default:return 88;int judge(char *string) /判断是否是关键字 char *keywords1000=if,then,else;for(int i = 0;i = 2;i+) if (!strcmp(string,*(keywords+i)return 1;return 0; 6.5主程序主程序主要负责，用户界面的初始化，以及程序执行控制。程序如下:int main()int test=0;cout=endl;cout= if-else条件语句的翻译程序设计（简单优先法、输出四元式） =endl;cout=infile;fin=new ifstream(infile);if(fin=null)printf(输入源文件名错误！n);continue;break;while(true)printf(输入单词输出文件（包括路径）：);cinwordoutfile;wordout=new ofstream(wordoutfile);if(wordout=null)printf(输入文件名错误！n);continue;break;while(true)printf(输入栈情况输出文件（包括路径）：);cinstackfile;stackout=new ofstream(stackfile);if(stackout=null)printf(输入文件名错误！n);continue;break;getchar();test=analysis(*fin ,*wordout);if(test=1)test=laynax(*stackout);elsereturn 0;if(test=1)printfou();return 0;7测试方法和结果7.1测试方法（1）程序设计过程中采用单步测试的方法，每完成一个独立的功能模块则对其进行单独测试。各模块测试成功之后，则对程序整体进行测试。（2）程序整体测试时，利用多种变化的输入数据进行测试，以验证程序的正确性，并且提供错误的输入来观察程序的反应。7.2测试结果7.2.1程序运行界面7.2.2测试一（正确数据）（1）输入数据（2）输出结果单词输出（部分）：分析栈输出（部分）：四元式输出：7.2.3测试二（不正确数据）输入数据：输出结果：8设计总结8.1设计优点（1）简单优先分析法是一种规范规约。具有准确、规范等优点。（2）四元式为普遍的中间代码形式。（3）程序结构清晰，功能模块划分合理。（4）程序具有坚实的基础，可扩展性强。8.2设计缺点（1）规范规约本身具有效率低的缺点。（2）分析表结构庞大，占据大量内存空间，但其中却有好多冗余。（3）程序只能进行简单的if-else语句进行翻译，功能有限。（4）程序容错能力较差，遇到输