1、完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2011年 12月 23日系主任（或责任教师）签名：WHILE语句的翻译程序设计（LL（1）文法、输出三地址表达式）1课设的描述1.1课设要求首先按照课程设计的要求，写一个能识别while循环语句的文法，并使它符合LL（1）法的要求，按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者通过文法的开始符号能判断是否能推导出该语句。程序应该包括词法分析器，能对输入的语
2、句进行词法分析，对输入的源程序从左到右进行扫描并将其分解为一个个的单词符号。然后再对结果进行语法分析。词法分析器应能识别关键字，标识符，常量，操作符等。该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法，如果不是则提示错误，如果满足while循环语句文法，判断是否符合LL（1）法，运用最左推导对其进行分析，看能否通过开始符号推导出来。将语法和语义分析的结果用输出三地址形式表示出来。1.2课设中所用概念1） 词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号：关键字（do,while）、标识符、常量、操作符等。2） 语法分析：在词
3、法分析的基础上，根据语法规则，把单词符号串分解成各类语法单位。3） 语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。4） LL（1）文法：LL（1）文法是一种自上而下的语法分析方法。第一个L是自上而下的分析，第二个L是从最左单词开始分析，1代表只通过下1个单词分析需要用到的语法。5） 预测分析程序：实现LL（1）法分析的一种有效方法，使用一张预测分析表和一个栈进行联合控制。预测分析程序就是属于这种类型的LL（1）分析器。2文法的描述2.1 While 语句文法描述K-dLwS L-SPP-;SP P-S-iQE E-TGG-+TG G-TG
4、 T-FRR-*FR R-/FR F-（E）F-I Q-=Q-非终结符集 VNK,L,P,S,G,R,E,F,Q,T终结符集V* do,while,（,）, ,+,-,*,/,i,=,a,aVT,V* 若a=，则规定First（），称为First（）为的开始符号集或首符号集。 FOLLOW 集： FOLLOW（A）=a|S=A且aVT,aFirst（）,V*T,V+ 若S=A,且=,则#FOLLOW（A） SELECT 集: 给定上下文无关文法的产生式 A- AVN,V* ,若,则SELECT（A-）=First（） 如果=）=（First（）-）U FOLLOW（A）. LL（1）文法: 一
5、个上下文无关文法是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的三地
6、址语句。4简要的分析与概要设计 4.1 基本框架 输入 while语句 词法分析 语法语义分析 输出三地址代码 4.2 构成图 4.2.1 主函数构成 4.3 各个部分构成整个工程分为四个部分,词法分析部分,和语法分析部分,具体函数执行部分,以及语义分析部分（最终部分在main函数中执行的）lexical（） - 程序的入口点，读入输入的待分析的字符串后,把其装入一给定数组,先进行词法分析，然后输出生成的词法分析结果。syntax（） - 语法分析阶段,利用Wordanalyze（） 中分析出的词法,进行语法 分析.如果不是LL（1）文法则输出语法出错,仅对LL（1）文法的输入进行分析.具体函
7、数执行部分 - 定义了各种操作函数以方便调用,入读入输入的句字的函数,提 取字符函数,判断字符函数等等语义分析式部分-主函数中进行的输出,形式为给定句子的三地址表达式5算法描述5.1词法分析的主要算法 void lexical（） /词法分析 int i,j,d; char ch; j=d=0; for（i=0;vari!=#i+） /判断关键字 ch=vari; if（ch=d&vari+1=o coutdot关键字endl; queuej+=i+=1; else if（ch=w） ch=vari+1; if（ch=h ch=vari+2; if（ch=i ch=vari+3; if（ch=
8、l ch=vari+4; if（ch=e ch=vari+5; whilei+=4; else if（index（ch,VT）=0） /判断标示符分隔符运算符 if（ch!ch!（） coutch标识符 arr_id-1=ch; queuej+= else cout0）运算符 queuej+=ch; queuej=queuei!i+）coutqueuei; cout语法分析主要算法void syntax（） /语法分析 int n; count+; print（）; X=stacksp; a=queuefront; if（X=a=）f=4; if（XZ if（X=a） sp-; front+;
9、 if（a! if（a!a! opr=index（a,VT）; else if（a=|a= opr=-2;a匹配 else opd=c;arr_ic+ else f=1; /字符不匹配,转去出错处理 else int tx=index（X,VN）; int ta=index（a,VT）; n=Mtxta; tdt+=Mtxta; if（ta=-1） f=2;cout /字符没有出现在产生式终结符集VT中,转去出错处理 else if（n=-1）f=3; /没有找到合适的候选产生式来做进一步推导,转去出错处理 else /用产生式Mtxta来做进一步推导X if（len（pn）!=0） for（
10、int i=len（pn）-1;i=0;i-） stack+sp=pni; coutpnlen（pn）-1-i;空串 if（f=0）syntax（）; tdt=-1 err（f）; 具体执行函数： len 求字符串长度 index 查找字符串中是否有ch 返回ch位置 err 输出错误和错误原因 print 打印6上机测试6.1测试方法在visual c+ 6.0 下调试并通过.输入不同的语句进行测试，测试的主要目的是看程序能否正确判断条件语句是否正确，赋值语句的格式有没有错误以及最后结果输出的三地址是否正确。6.2测试过程和结果现用一下用例来测试本程序：测试1：输入一个最简单的do whil
11、e循环语句，正确输入看能否得出正确结果，程序运行结果如下：测试2：输入一错误语句查看结果：如下程序不能认出so所以程序不能编译。7 结果7.1研制过程 这次课程设计要求我用LL（1）分析法来翻译while循环语句，这就要求对编译原理语法分析方面有一定的了解，熟悉各种语法分析的方法，特别是本题中所要求的LL（1）法，需要弄清楚LL（1）法的概念，过程，需要注意的地方等。另外还需要对编程语言联系，才能编出符合要求的程序。看到题目以后，首先将编译原理书上相关知识仔细看了一遍，不清楚的地方搞清楚特别是关系程序设计的部分。然后参阅了编译程序构造方面的书籍，对编译程序的实现有了一定的了解。最后是从编程语言
12、方面，根据编译原理方面的知识，找出实现课程设计要求的解决方式，然后编写程序来实现。编好以后，对其测试，找出其中存在的问题，不过程序不能像c+一样很好的实现对while的翻译，有些复杂的输入还是不能识别。7.2 本次课程设计的缺点 这个对while的编译程序不能像C+那样完美的编译，不能识别太过复杂的语句，循环的嵌套，带小括号的运算是这次课程设计的缺点。7.3本次课程设计的收获课程设计是不同于上机实验的一种更考验学生能力的方式，由于每个人的课设题目都不一样所以很大程度的消除了学生的依赖感。本次课设我学到了很多。首先,巩固了编译原理的知识。为了做好这次课程设计,要求我必须重新复习一遍编译的课本,特
13、别是需要实现的那部分原理。除此之外,还有上网查询一些编译资料，和一些实际问题实现的例子，通过看别人实现的过程，学习实现的一些基本思路。这次课程设计的题目是用LL（1）进行while循环语句的语法分析,并输出三地址表达式.设计的特点是利用定义每个终极符和非终极符之间优先关系,来进行符号的移进与规约,如果栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。这样使得程序简化,只需定义一个栈用来存放移进的字符,然后用栈顶指针指向它后与待移进字符比较优先级即可,设计简单.此设计的严重不足是只能进行一个固定句子的词法与语法分析,因为在定义优先关系
14、时已固定了DO,和WHILE的每个字符之间的优先关系,且赋值表达式和条件式也已固定,所以只能进行本程序已约定好的语句.最大的收获是在提出一个难题以后，如果能比较顺手的解决的话，那是一件比较开心的事。只是有些时候越想问题就会越多，也越难解决，那就得慢慢调试，慢慢推导了。相信只要想得出，就能调得出，当然耐心是很重要的，花在上面的时间也是要多一点的。其次,通过本次课程设计检验了我的数据结构的知识。因为在语法分析中需要用到数据结构的一些知识,这就敦促我去重新温习数据结构中相关的知识。8参考文献（1）编译原理（第2版） 清华大学出版社 张素琴 吕映芝 等人著 本科生课程设计成绩评定表班级：姓名：学号：序
15、号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性3设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性6设计验收总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格2012 年 1月日源代码#include#define MAX 100 char X,a;char VN11=K,LPSEGTRFQ0;char VT15=+-*/char p186=dLwS0,SP00iQE0TG0+TG0-TG0FR0, *FR0/FR0（E）0i0=0char stackMAX;
16、char queueMAX;int sp,front;int M1014= -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
17、,-1,-1,-1,-1,-1, 9,-1,-1,-1,-1,-1, -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, ;int f=0;int count=0;int c=0;char arr_iMAX;char varMAX;int tdMAX; /输出产生式序列int t=0;int opd=-1;int opr=-1;int id=0;int d=0;char arrMAX10;/
18、存放待输出的三地址int len（char str） /求字符串长度 int i=0; while（stri!）i+; return i;int index（char ch,char str） /查找字符串中是否有ch 返回ch位置 if（ch!=stri）i+; else break; if（stri=）return -1;void err（int n） /输出错误和错误原因 if（n=1） cout字符不匹配 else if（n=2）字符没有出现在产生式终结符集VT中 else if（n=3）没有找到合适的候选产生式来做进一步推导该句子是文法语言的句子！void print（）（ if（count10）cout0count） int i;i=sp;stacki; for（;=20;front;void semantic（） int j=0,k; while（varj! if（varj= k=0; for（j=j-1;（varj!）&）;j+,k+） arrdk=varj; arrdk= d+; j-;|varj=varj! arrdk=varj; j+; els
