IF-ELSE条件语句的翻译程序设计（简单优先法、输出四元式）.doc

1、武汉理工大学编译原理课程设计说明书 课程设计任务书题目: IF-ELSE条件语句的翻译程序设计（简单优先法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附

2、件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次

3、周星期一上午10点。指导教师签名： 2012年 10月 23日系主任（或责任教师）签名： 2012年 10月 23日 IF-ELSE条件语句的翻译程序设计（简单优先法、输出四元式）1系统描述1.1实验目的对条件语句：IF THEN ELSE （1） 按给定的题目写出符合语法分析方法要求的文法和属性文法描述。（2） 按给定的题目给出语法分析方法的思想及分析表的设计。（3） 按给定题目给出中间代码序列的结构设计。（4） 完成相应的词法分析、语法分析和语义分析程序设计。（5） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。1.2开发平台Visual C+ 6.0、Windows X

4、P2文法及属性文法的描述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” -)

5、;emit(“goto” -)（2）E-(A)E.place=A.place（3）A-idp=lookup(id.name);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简单优先文法定义若一个文法是简单优先文法

6、必须满足以下条件：（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为文法符号3.5.1.2 改造后的优先关系

7、计算当文法中存在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,

8、/*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

9、,/*)*/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,

10、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,

11、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）

12、（*，b，d，t2）（3）（+，t1，t2，t3）（4）（=，t3，-，a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。5编译系统的概要设计（1） 系统主要分为两个模块：词法分析和语法分析（包括语义分析）。并且在分析过程中将词法分析产生的单词输出到文件，语法分析过程中分析栈的变化情况输出到文件。（2） 系统设计采用过程化的设计方法，将词法分析、语法分析等功能模块在独立的过程中实现。（3） 系统概要结构如下：1） 预定义模块2） 词法分析模块3） 语法分析模块4） 其他辅助模块5）

13、 主程序模块（主要指程序入口函数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;/栈定

14、义（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;读取一个字符到c

15、h;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)外的其他所有

16、辅助函数。语法分析的过称描述如下：初始化分析栈；while(还有单词)判断当前栈顶单词与输入单词的优先级；if()while(栈顶元素优先级等于输入单词)保存输入单词；置输入单词为栈顶单词；栈顶元素出栈；判断保存单词串是否为句柄；if(是句柄)进行规约；进行语义规则计算；输出栈的变化情况；使规约后单词为新的输入符号；else输出规约出错；else输出输入单词错误；6.4其他模块其他模块描述如下：（1）栈操作模块void InitStack (SqStack &S) /栈初始化S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/分配存储空间 if

17、(!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.

18、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 =

19、 *(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;el

20、se 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

21、: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

22、,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(输入单词输出

23、文件（包括路径）：);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=layn

24、ax(*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

25、）简单优先分析法是一种规范规约。具有准确、规范等优点。（2）四元式为普遍的中间代码形式。（3）程序结构清晰，功能模块划分合理。（4）程序具有坚实的基础，可扩展性强。8.2设计缺点（1）规范规约本身具有效率低的缺点。（2）分析表结构庞大，占据大量内存空间，但其中却有好多冗余。（3）程序只能进行简单的if-else语句进行翻译，功能有限。（4）程序容错能力较差，遇到输入错误时，只能进行简单处理，即，终止程序。在极端情况下可能导致不可预知错误。8.3考虑改进（1）使用算符优先分析法代替简单优先分析方法。（2）采用优先链的方式存储优先表，代替数组。（3）提高程序的容错能力。例如：遇到错误时，将错误文法

26、尽可能补全为正确文法，使分析能够继续进行。（4）增强程序的功能，使其能适应复杂的源程序输入。9收获与体会本次课程设计可以说是对编译原理课程本学期所学内容的一次综合应用，虽然称不上一个完整的编译程序，但已经展现了一个完整编译程序的雏形。通过本次课程设计，不仅进一步熟悉了编译程序所涉及的各方面知识，更掌握了一个编译程序的整体架构方式以及编译程序构造的整体流程。并且，从中认识到，编译程序模块化(词法分析、语法分析、语义分析等)的重要，更是程序设计模块化的重要。但，在其过程中也暴漏了自身知识的匮乏，包括，编译原理知识学习不扎实，不能很好的运用；编程语言运用不熟练，导致频繁因查找编程语言语法知识耗费大量

27、时间等等。但总的来说，本次编程还是收获不少，不仅仅是实现了课程设计所要求的内容，更为以后深入的学习（包括课程相关与不相关）打下了坚实的基础。10参考文献【1】 张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第二版）清华大学出版社2005【2】 闵联营、何克右. C+程序设计教程. 武汉理工大学出版社. 2005【3】 Stanley B.Lippman、Josee Lajoie、Barbara E.Moo著,李师贤、蒋爱军、梅晓勇、林瑛 译. C+ Primer中文版. 2006 本科生课程设计成绩评定表班级：1007班姓名：杨星 学号：0121010340704序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：20 年月日 16