学号：课程设计题目编译原理学院计算机科学与技术专业计算机科学与技术班级姓名指导教师2 年月日课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目: 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点。

指导教师签名： 2011年 12月 23日系主任（或责任教师）签名： 2011年 12月 23日DO-WHILE语句的翻译程序设计(LL（1）文法输出3地址表达式)1课设的描述1.1课设要求首先按照课程设计的要求，写一个能识别do-while循环语句的文法，并使它符合LL(1)法的要求，按照这个文法编写一个程序，该程序能识别输入的语句是否符合do-while语句的文法，或者通过文法的开始符号能判断是否能推导出该语句。

程序应该包括词法分析器，能对输入的语句进行词法分析，对输入的源程序从左到右进行扫描并将其分解为一个个的单词符号。

然后再对结果进行语法分析。

词法分析器应能识别关键字，标识符，常量，操作符等。

该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足do-while循环语句的文法，如果不是则提示错误，如果满足do-while循环语句文法，判断是否符合LL(1)法，运用最左推导对其进行分析，看能否通过开始符号推导出来。

将语法和语义分析的结果用输出三地址形式表示出来。

1.2课设中所用概念1)词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号：关键字(do,while)、标识符、常量、操作符等。

2)语法分析：在词法分析的基础上，根据语法规则，把单词符号串分解成各类语法单位。

3)语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译(产生中间代码)。

4)LL(1)文法：LL(1)文法是一种自上而下的语法分析方法。

第一个L是自上而下的分析，第二个L是从最左单词开始分析，1代表只通过下1个单词分析需要用到的语法。

5)预测分析程序：实现LL(1)法分析的一种有效方法，使用一张预测分析表和一个栈进行联合控制。

预测分析程序就是属于这种类型的LL(1)分析器。

2文法的描述2.1 do.. While 语句文法描述K->dLwS L->SPP->;SP P->εS->iQE E->TGG->+TG G->-TGG->εT->FRR->*FR R->/FRR->εF->(E)F->I Q->=Q->< Q->>非终结符集V N{K,L,P,S,G,R,E,F,Q,T}终结符集V*{ do,while,(,), ε,+,-,*,/,i,>,=,<,;}预测分析表i = < > + - * / ( ) do ε; while K dLwSL SPP ε;SPS iQEE -TG TGG +TG -TG εεεT FR FRR εε*FR /FR εεεF i (E)Q = < >3语法分析方法及中间代码形式的描述3.1语法分析方法描述LL(1)文法的定义：First 集：设G={VT ,VN,S,P}是上下文无关文法First(α)={a|α=>aβ,a∈VT,α,β∈V*}若a=>ε，则规定ε∈First(α)，称为First(α)为α的开始符号集或首符号集。

FOLLOW 集：设G={VT ,VN,S,P}是上下文无关文法FOLLOW(A)={a|S=>μAβ且a∈VT ,a∈First(β),μ∈V*T,β∈V+ }若S=>μAβ,且β=>ε,则#∈FOLLOW(A)SELECT 集:给定上下文无关文法的产生式 A-->α A∈VN,α∈V* ,若α≠>ε,则SELECT(A-->α)=First(α)如果α=>ε,则SELECT(A-->α)=(First(α)-{ε})U FOLLOW(A).LL(1)文法:一个上下文无关文法是LL(1)文法的充分必要条件是,对每个非终结符A的两个不同的产生式,A-->α A-->β,满足SELECT(A-->α)∩SELECT(A-->β)= ф其中α,β不能同时推导出空.3.2 中间代码形式三地址码是由下面一般形式的语句构成的序列：x := y op z其中，x y z为名字、常数或临时变量；op代表运算符号。

每个语句中只能有一个运算符。

三地址码类似于汇编语言代码。

语句可以带有符号标号，而且存在各种控制流语句，本程序输出中用到了：复制语句x := y条件转移语句if x relop y goto L //L为带标号L的三地址语句无条件转移语句goto L //转移到标号为L的三地址语句。

4简要的分析与概要设计 4.1 基本框架输入do while 语句 → 词法分析 → 语法语义分析 → 输出三地址代码4.2 构成图4.2.1 主函数构成4.3 各个部分构成整个工程分为四个部分,词法分析部分,和语法分析部分,具体函数执行部分,以及语义分析部分(最终部分在main 函数中执行的)lexical() ----- 程序的入口点，读入输入的待分析的字符串后,把其装入一给定数组,先进行词法分析，然后输出生成的词法分析结果。

syntax() ----- 语法分析阶段,利用Wordanalyze() 中分析出的词法,进行语法 分析.如果不是LL(1)文法则输出语法出错,仅对LL(1)文法的输入进行分析.具体函数执行部分 ----- 定义了各种操作函数以方便调用,入读入输入的句字的函数,提 取字符函数,判断字符函数等等语义分析式部分-------主函数中进行的输出,形式为给定句子的三地址表达式词法分析语法语义分析Main( )控制输出三地址码5算法描述5.1词法分析的主要算法void lexical() //词法分析{int i,j,d;char ch;j=d=0;for(i=0;var[i]!='#';i++) //判断关键字{ch=var[i];if(ch=='d'&&var[i+1]=='o'){cout<<"do"<<'\t'<<"关键字"<<endl;queue[j++]='d';i+=1;}else if(ch=='w'){ch=var[i+1];if(ch=='h'){ch=var[i+2];if(ch=='i'){ch=var[i+3];if(ch=='l'){ch=var[i+4];if(ch=='e'){ch=var[i+5];}}}}cout<<"while"<<'\t'<<"关键字"<<endl;queue[j++]='w';i+=4;}else if(index(ch,VT)<=0) //判断标示符分隔符运算符{if(ch!='{'&&ch!='}'&&ch!='('&&ch!=')'){cout<<ch<<'\t'<<"标识符"<<endl;arr_i[d-1]=ch;queue[j++]='i';}else cout<<ch<<'\t'<<"分隔符"<<endl;}else if(index(ch,VT)>0){cout<<ch<<'\t'<<"运算符"<<endl;queue[j++]=ch;}}queue[j]='#';for(i=0;queue[i]!='#';i++)cout<<queue[i];cout<<endl;}语法分析主要算法void syntax() //语法分析{int n;count++;print();X=stack[sp];a=queue[front];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);}else if(a==';'||a=='w'||a=='#'){opr=-2;}cout<<'\t'<<'\''<<a<<"'匹配"<<endl;}else{opd=c;cout<<'\t'<<'\''<<arr_i[c++]<<"'匹配"<<endl;}}else f=1; //字符不匹配,转去出错处理}else{int tx=index(X,VN);int ta=index(a,VT);n=M[tx][ta];td[t++]=M[tx][ta];if(ta==-1){f=2;cout<<a<<endl;} //字符没有出现在产生式终结符集VT中,转去出错处理else if(n==-1)f=3; //没有找到合适的候选产生式来做进一步推导,转去出错处理else{ //用产生式M[tx][ta]来做进一步推导sp--;cout<<'\t'<<X<<"->";if(len(p[n])!=0){for(int i=len(p[n])-1;i>=0;i--){stack[++sp]=p[n][i];cout<<p[n][len(p[n])-1-i];}cout<<endl;}else cout<<"空串"<<endl;}}if(f==0)syntax();else{td[t]='-1';err(f);}}具体执行函数：len 求字符串长度index 查找字符串中是否有ch 返回ch位置err 输出错误和错误原因print 打印6上机测试6.1测试方法在visual c++ 6.0 下调试并通过.输入不同的语句进行测试，测试的主要目的是看程序能否正确判断条件语句是否正确，赋值语句的格式有没有错误以及最后结果输出的三地址是否正确。