1、武汉理工大学编译原理课程设计说明书课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题目: IF-ELSE 条件语句的翻译程序设计（简单优先法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并
2、通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周 1、周 2：完成系统分析及设计。周 3、周 4：完成程序调试及测试。周 5：撰写课程设计报告。设计验收安排：设计周的星期五第 1
3、节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午 10 点。指导教师签名：年月日系主任（或责任教师）签名：年月日8目录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
4、测试结果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 文法及属
5、性文法的描述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 A E.true=nextstat;E.codebegin=nextstat; E.false=nextstat+1;emit(“if” A.place “rop” A.place “got
6、o” -); emit(“goto” -)（2）E-(A)E.place=A.place（3）A-idp=lookup(id.name);if p!=null thenA.place=p else error（4）B-d=Cd.place=C.place（5）C-A op A C.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
7、简单优先文法定义若一个文法是简单优先文法必须满足以下条件：（1） 在文法符号集 V 中，任意两个符号之间最多只有一种优先关系成立（2） 在文法中任意两个产生式没有相同的右部其中第一条是必须满足的，第二条若不满足则会导致规约不唯一。3.3 简单优先文法的算法步骤首先根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈 S，算法步骤如下：（1） 将输入符号串 a1,a2aN#依次逐个存入符号栈 S 中，直到遇到栈顶符号ai 的优先性下一个带输入符号 aj 时为止。（2） 栈顶当前符号 ai 为句柄尾，由此向左在栈中找句柄的头符号 ak，即找到ak-1a，Sa，a 为文法符号 LA
8、（S）=a|S=a，Sa，a 为文法符号3.5.1.2 改造后的优先关系计算当文法中存在 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 anlta
9、ble2222=/*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,
10、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,
11、/*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
12、,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。运算对象和运算结
13、果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如：a=b*c+b*d 的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（=，t3，-，a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。5 编译系统的概要设计（1） 系统主要分为两个模块：词法分析和语法分析（包括语义分析）。并且在分析过程中将词法分析产生的单词输出到文件，语法分析过程中分析栈的变化情况输出到文件。（2） 系统设计采用过程化的设计方法，将词法分析、语
14、法分析等功能模块在独立的过程中实现。（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 ad
15、dre;typedef struct SqStackchar*base;char*top;intstacksize;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
16、*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 为其他合法字符(如
17、：,=等等) 填入名字表。else 输出错误，无法识别的字符。6.3 语法分析语法分析主要为 laynax(ofstream &f)函数，其中，f 为栈变化情况输出文件。其他辅助函数为除 judge(char *string)外的其他所有辅助函数。语法分析的过称描述如下：初始化分析栈；while(还有单词)判断当前栈顶单词与输入单词的优先级；if()while(栈顶元素优先级等于输入单词)保存输入单词；置输入单词为栈顶单词； 栈顶元素出栈；12判断保存单词串是否为句柄；if(是句柄)进行规约；进行语义规则计算； 输出栈的变化情况；使规约后单词为新的输入符号；else输出规约出错；else输出输
18、入单词错误；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*)rea
19、lloc(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
20、(溢出);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;
21、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)19foutthen;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(g
22、ettop(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
23、*: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-
24、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） 程序设计过程中采用单步测试的方法，每完成一个独立的功能模块则对其进行单独测试。各模块测试成功之后，则对程
