DO-WHILE循环语句的翻译程序设计(LL(1)法、输出三地址表示)

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目:DO-WHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码三地址表示的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1系统描述（问题域描述）；2文法及属性文法的描述；3语法分析方法描述及语法分析表设计；4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5编译系统的概要设计；6详细的算法描述（流程图或伪代码）；7软件的测试方法和测试结果；8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名：年月日系主任（或责任教师）签名：年月日武汉理工大学《编译原理》课程设计说明书2DO-WHILE循环语句的翻译程序设计（LL（1）方法、输出三地址表示）1.系统描述1.1目的通过设计、编制、生成、调试一个do-while循环语句的语法及语义分析程序，以加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.2设计内容对循环语句：do{赋值语句}while表达式1)设计符合自身语法分析方法要求的文法和属性文法（LL(1)语法）。2)设计LR分析法相关的语法分析表（LL(1)分析表）。3)设计中间代码格式（三地址中间代码）。4)对源文件进行词法和语法分析的同时进行语义处理（语法制导分析）。5)对源文件中的错误进行输出。1.3系统体系结构描述本系统为子模块的体系结构风格，系统由两大模块组成：1)词法分析模块2)语法分析模块（调用语义分析模块）1.3.1系统结构图说明：输入do-while语句后，词法分析模块对文件进行处理并输出单词序列到队列queue[i]，随后的语法分析模块将此队列内容作为输入，通过语法制导分析方法调用语源代码词法分析语法分析语义分析中间代码武汉理工大学《编译原理》课程设计说明书3义分析模块最终生成中间代码。1.3.2词法分析模块说明：对输入的源文件进行处理，逐个读入字符，将字符流进行合并并进行判断归类，将单词和其类型输入队列并保存。1.3.3语法分析模块说明：接受由词法分析得到的队列queue，进行语法分析和语法制导翻译，最后得到三地址中间代码。队列queue中间代码（三地址码）语法分析（LL(1)分析法）语义分析（语法制导）错误处理（打印错误）源文件读取一个字符判断字符类型单词归类（关键字、标识符…）存入队列queue武汉理工大学《编译原理》课程设计说明书42.文法及属性文法描述2.1文法：文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。DO-WHILE循环语句的文法如下所示：K-DLWSL-SPP-;SPP-εD-doW-while2.2属性文法：属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。在一个属性文法中，对应于每个产生式A→a都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,…，ck)其中f是一个函数，而且或者①b是A的一个综合属性并且c1,c2,…，ck是产生式右边文法符号的属性或者②非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。属性文法为：1-{if(S.value==true)emit(‘if(‘,S.value,‘)goto’,codebegin)elseemit(‘-‘,‘-‘,‘goto’,nextstate)}2-{p=lookup(id.name);if(p!=NULL)L.place=p;elseerror;E.place=L.place;emit(‘=‘,id,‘-’,L.place)}3-{L.place=newtemp;emit(‘+’,F1.place,F2.place,F.place)}4-{S.place=newtemp;S.value=(F1.valueF2.value);emit(‘’,F1.place,F2.place,S.place)}5-{F.place=newtemp;p=lookup(id.name);if(p!=NULL)F.place=p;elseerror}6-{F.place=newtemp;p=lookup(digit.name);if(p!=NULL)F.value=digit.value;elseerror}武汉理工大学《编译原理》课程设计说明书53.语法分析方法描述及语法分析表设计3.1语法分析为实现LL(1)算法,可以使用栈结构，算法的基本思想是:首先定义栈结构，栈中的元素是一个二维数组：voidsemantic(){if(VT[opr]=='='){arr[d][0]=arr_i[opd];arr[d][1]='=';arr[d][2]=id;arr[d][3]='';arr[d][4]='';id++;}elseif(opr==-2){arr[d][0]=id-1;arr[d][1]='=';arr[d][2]=arr_i[opd];arr[d][3]='';arr[d][4]='';}else{if(VT[opr]!=''&&VT[opr]!='')arr[d][0]=id-1;elsearr[d][0]=id+1;arr[d][1]='=';arr[d][2]=arr_i[opd];arr[d][3]='+';arr[d][4]=id;id++;}d++;}3.2预测分析部分：intM[10][14]={{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1},{1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,2,-1},{4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1},{-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1,8,8,8},{9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1},武汉理工大学《编译原理》课程设计说明书6{-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12},{14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1},{-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},};3.3语法分析过程：voidsyntax(){intn;count++;print();X=stack[sp];//将sp压入栈STACK中a=queue[front];//从queue队列中读取词法分析后的字符if(X=='#'&&a=='#')f=4;if(X'A'||X'Z'){if(X==a){sp--;front++;if(a!='i'){if(a!='d'&&a!='w'&&a!=';'&&a!='#'){opr=index(a,VT);semantic();//语法分析调用}elseif(a==';'||a=='w'||a=='#'){opr=-2;semantic();//语法分析调用}cout'\t''\''a'匹配endl;}else{opd=c;//coutopd1opd2;cout'\t''\''arr_i[c++]'匹配endl;}}elsef=1;//转入出错处理}else{inttx=index(X,VN);intta=index(a,VT);n=M[tx][ta];td[t++]=M[tx][ta];武汉理工大学《编译原理》课程设计说明书7if(ta==-1){f=2;//转入出错处理coutaendl;}elseif(n==-1)f=3;//转入出错处理else{sp--;cout'\t'X-;if(len(p[n])!=0){for(inti=len(p[n])-1;i=0;i--){stack[++sp]=p[n][i];coutp[n][len(p[n])-1-i];}coutendl;}elsecout空串endl;}}if(f==0)syntax();else{td[t]='-1';err(f);}}4.中间代码形式及其序列的结构设计中间代码是3地址码形式来表示，即4元式的变形。三地址码由5个域构成：中间代码地址标号，操作符，左操作数，右操作数，目的操作数操作符：=，+，，（文法仅定义这些操作）；左操作数，右操作数：opt，opr；目的操作数：用来存放操作值的变量。例如：i=（0）（0）=i+1（1）=i表示i=i+1。武汉理工大学《编译原理》课程设计说明书85.简要分析与概要设计5.1系统分析5.1.1词法分析输入源程序文本，对输入串进行预处理，然后从左至右逐个字符地对源程序进行扫（超前搜索法），产生一个一个的单词符号，在状态转换图的基础上，把作为字符串源程序改造成为单词符号串。概要流程图见图1.3.2。5.1.2语法分析在完成词法分析的基础上对DO-WHILE循环语句进行语法分析，对状态栈、符号栈分别进行移进、规约（采用LL(1)分析方法）、接受和出错处理四步操作，从而分析判定程序的语法结构是否符合语法规则。概要流程图见1.3.3节。5.1.3语义分析以及三地址码表示当在栈中找到可归前缀后，进行规约时，根据相应产生式对应的语义子程序进行语法制导翻译（在语法的分析过程中，随着分析的步步进展，根据每一个产生式所对应的语义子程序进行翻译的方法）.三地址指令很类似于四元式,这种中间表示通常称为三地址代码,三个地址即是两个为操作数,一个是操作符。5.1.4LL（1）语法分析中的出错处理1)字符不匹配,转去出错处理。2)字符没有出现在产生式终结符集VT[]中,转去出错处理3)没有找到合适的候选产生式来做进一步推导,转去出错处理5.2概要设计（系统总体描述）源代码词法分析语法分析语义分析中间代码武汉理工大学《编译原理》课程设计说明书96.详细的算法描述详细的伪代码（源程序）#includeiostream.h#defineMAX35charX,a;charVN[11]={'K','L','P','S','E','G','T','R','F','Q','\0'};charVT[15]={'i','=','','','+','-','*','/','(',')','d','w',';','#','\0'};charp[18][6]={dLwS\0,SP\0,;SP\0,\0,iQE\0,TG\0,+TG\0,-TG\0,\0,FR\0,*FR\0,/FR\0,\0,(E)\0,i\0,=\0,\0,\0};charstack[MAX];charqueue[MAX];in