编译原理课程设计WHILE循环语句的翻译程序设计(递归下降法、输出四元式).doc

武汉理工大学编译原理课程设计说明书学 号： 课 程 设 计题 目WHILE循环语句的翻译程序设计（递归下降法、输出四元式）学 院计算机科学与技术专 业计算机科学与技术班 级计算机班姓 名指导教师2012年1月6日目 录1问题描述31.1问题描述31.2主要任务31.3测试数据32文法及属性文法的描述42.1文法的描述42.2 while-do循环语句的文法42.3递归文法的优化42.4属性文法的描述53语法分析方法描述63.1程序设计对文法的要求63.2语法分析的思想73.3递归下降文法实现原理73.4中间代码形式84简要的分析与概要设计941全局程序的概要设计94.2词法分析94.3递归下降翻译器的设计94.4语法制导翻译105详细的算法描述105.1算法描述105.2运行结果146. 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）156.1研制过程156.2本设计的评价、特点166.3感受和体会166.4对程序改进的想法17课程设计任务书学生姓名： 专业班级： 计算机班 指导教师： 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2012年 1月6日系主任（或责任教师）签名： 2012年 1月 6日课程设计报告书1问题描述1.1问题描述设计一个WHILE布尔表达式DO赋值语句循环语句的词法语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。1.2主要任务通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。首先写出一个能识别while循环语句的文法，通过消除左递归使它符合LL(1)即递归下降法的要求，然后按照这个文法编写一个集词法分析，语法分析和语义分析为一体的程序，该程序首先可以检查输入语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。1.3测试数据编写好源代码后，进行调试，主要调试数据有：新建一个文本，输入一个while循环语句的内容，保存；打开该文件，进行词法、语法的分析，给出分析结果。2文法及属性文法的描述2.1文法的描述用扩充巴科斯-瑙尔范式（EBNF）给出的while循环语句的文法描述，如下： := while () do := := | = | = := + | - | := * | / | :=() | |:=；2.2 while-do循环语句的文法产生式为S- while E do A，为便于语法制导翻译将其改写如下： 文法G(s)如下：S-WEDG （意思是while E do G）G-c=RR-dTe|dT-+|-|*|/E-aFbF- |=| while (A) do B2.A - CDC3.D - | = | = | C+E | C-E | E5.E - E*F | E/F | E6.F - (C) | i | n因为此while循环语句的翻译程序设计用的是递归下降法，而递归下降法对文法的要求是文法要满足是LL（1）文法，故文法中不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法:1.S-while (A) do B 2.A-CDC3.D- | = | = | EG 5.G-+EG | -EG | 6.E-FH 7.H-*FH | / FH | 8.F-(C) | i | n 9.B-i=C；2.4属性文法的描述(1)、任一非终结符B都不是左递归的，否则会产生死循环。(2)、对A的任意两个右部i , j ,有：first(i)first(j)=， First(i)表i所能导出串的第一个符号的集合。显然，每个i的first(i)是互不相同的，否则则无法判断应执行哪个(i )。产生式 语义规则S-while (A) do B S.first:=newtemp; S.second:=newtemp;A.true:=newtemp;emit（A.false:=S.second;S1.second:=S.first; S.place:=(S.begin, :) | B.place |printf(S.true, :) |S1.place | printf(goto,S.begin) | printf(B.false, :) | printf(goto Lnext);）A-CDCA.place:=newpemt;emit(A.place:=C1.place D.place C2.place).D- D.place:=newtemp ;Emit(D.Place:=).D- D.place:=newtemp ;Emit(D.Place:= =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=EG C.Place:=newtemp;Emit(C.Place:=E.Place G.place)G-+EG G.Place:=newtemp;Emit(G1.Place:=+E.Place G2.place)G-EG G.Place:=newtemp;Emit(G1.Place:=-E.Place G2.place)G-G.Place:=newtemp;Emit(G.Place:=H-*FH H.Place:=newtemp;Emit(H1.Place:=*F.Place H2.place)H- /FHH.Place:=newtemp;Emit(H1.Place:=+F.Place H2.place)H-G.Place:=newtemp;Emit(H1.Place:=+E.Place H2.place)F-(C) F.Place:=C.PlaceB-i=C;p:=lookup()If p!=nil thenEmit(p:=C.PlaceElse error)3语法分析方法描述3.1程序设计对文法的要求递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一地确定选择某个候选进行推导。它的优点是简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率其文法可以表示为： ETE+T TFT*F Fi（E）可以用语法图来表示语言的文法，如图：+TTE*ETFFFT(E)iF3.2语法分析的思想递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H)。每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S 是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=l.Yufa_Queue.front()来得到当前所分析到的单词，然后在递归语法分析中根据这个单词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。3.3递归下降文法实现原理设A是一个非终结符：A1 A2 An则写 (A) if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示调用处理符号串i的子程序。对A的任一右部i 设为： i = y1 y2 yn则定义( i) begin(y1);(y2);(yn) end其中yj可分为下列两种情况（j=1,n):1) yjVT,则 ( yj) if char yj then ERROR else READ(char)2) yjVN,则(yj)表示调用关于yj的递归子程序。3.4中间代码形式中间代码采用四元式输出，一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while ab do a=a+b的四元式输出形式如下： 100 ( , a , b , 102 ) 101 ( j , _ , _ , 105 ) 102 ( + , a , b , n ) 103 ( = , n , _ , a ) 104 ( j , _ , _ , 100) 1054简要的分析与概要设计41全局程序的概要设计递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。4.2词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。4.3递归下降翻译器的设计对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。1. 对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。2. 对于每个非终结符号B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,，bk)3. 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。4.4语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。5详细的算法描述5.1算法描述按照递归下降法求WaDGWEn); printf(G-c=Rn); printf(R-dTe|dn); printf(T-+|-|*|/n); printf(E-aFbn); printf(F- |=|n); printf(请输入while-do语句(D代表do,W代表while),并以#结束:n);do scanf(%c,&ch); aj=ch; j+;while(ch!=#);n1=j;ch=a0; S(); printf(n); if (ch=#) printf(输出四元式为：n); printf(100 (WEDG形式的调用分析void S() printf(%dtS-WEDGn,total);total+; W(); E();W（）判断第一个输入字母是否合法：void W() if(ch!=W) printf(有非法字符%c请按回车返回!,ch); getchar(); getchar(); exit(1); E()给出E-aFb的推倒：void E() ch=a+i1; if(ch!=a) printf(有非法字符%c %c请按回车返回!,ch); getchar(); getchar(); exit(1); printf(%dtE-aFbn,total);total+; F();F()给出F-、F-=、F-: printf(%dtF-n,total);total+; break; case =: printf(%dtF-=n,total);total+; break; default: printf(%dtF-c=R的形式分析：void D() +i1; ch=a+i1; if(ch!=D) printf(有非法字符%c请按回车返回!,ch); getchar(); getchar(); exit(1); ch=a+i1; void G() int i=i1+1; if(ch!=c&ai!=) printf(有非法字符%c %c请按回车返回!,ch,ai); getchar(); getchar(); exit(1); printf(%dtG-c=Rn,total);total+; R();R()给出R-dTe的形式分析、T()给出T-+/-/*/形式分析void R() int i; i=i1+1;i1=i1+2; ch=ai1; if(ai!=&ch!=d) printf(有非法字符%c %c请按回车返回!,ai,ch); getchar(); getchar(); exit(1); else if(ai1+1=+)|(ai1+1=-)|(ai1+1=*)|(ai1+1=/)printf(%dtR-dTen,total);total+; T();elseprintf(%dtR-dn,total);total+;W();E();void T() ch=a+i1; switch(ch) case +: printf(%dtT-+n,total);total+;break; case -: printf(%dtT-n,total);total+; break; case *: printf(%dtT-*n,total);total+; break; default: printf(%dtT-/n,total);total+; break; ch=#; 5.2运行结果编写好源程序，连接运行无误后，用几个简单的while语句检测其正确性，如：输入while语句：WabDa=a+b#，看其输出结果是否与我们所预期的结果一致，如果不一致，则需对源程序进行检查修正，我们可以用逐步调试的方法来对源程序进行跟踪分析，找出出错的地方和原因，在对其进行修改，重新调试运行，直到输出正确的结果为止。若输出结果正确，还要多用几个while语句对其进行检测，直到所有输出结果正确。测试结果如下：6. 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等） 6.1研制过程在做本次实验之前我对LL(1)文法的构成,递归下降原理不是很了解,在查阅了相关资料后,对此有了深入了解.在整个设计过程中,将词法分析做为一个单独的模块,它可以被任何语法分析调用,提高独立性.并且在编程之前就已经将程序的概要设计都做出来了，所以在编写程序的时候相对比较容易。词法分析，语法分析都是很容易的，只要理解了分析方法的实现原理，编写程序判断输入字符串是否满足给定的文法是比较简单的。6.2本设计的评价、特点 本人设计的程序基本上实现了用递归下降分析法实现了while语句的翻译，并能够用四元式将其输出，使人一目了然。同时，对复杂的赋值表达式也能够进行正确的翻译，如a=(a+b)/2+c用四元式表示为：(1) (+,a,b,t1) (2) （/,t1,2,t2） (3) (+,t2,c,t3) (4) (:=,t3,-,a)。在本次设计中,程序具有良好的用户界面,独立的词法与语法接口,并且在语法分析过程中可以准确指出语句中有错误的位置。在编制整个设计的过程中,利用了所学的软件工程,软件设计面向对象的方法。6.3感受和体会编译原理这门课程是计算机专业一门基础性学科，重要性可见一斑，学好这门课程对以后学习具有深远的影响。而课程设计便是对学习效果的检验。课程设计不仅可以锻炼我们独立思考问题、解决问题的能力，而且可以培养我们的整体性思维的能力；通过课程设计，使我了解了很多编译原理应用的知识，比如：读取一个文件、对一个输入语句进行词法分析、语法分析，给出分析结果，对基本的语法分析过程有了一定的了解等。虽然一开始对于此次课设的题目一头雾水，不知从何下手，但是最后通过查阅课本相关内容和实验手册的相关内容，最后渐渐明白；知道了如何对输入文件中的内容进行扫描读取，对读取的字符或字符串进行词法和语法分析，确定关键字，同时提取出关键字while，对while的循环条件进行扫描判断，最终确定一个满足while语法要求的循环条件，对满足条件以后的语句进行分析，最终用四元式表示出分析的结果。 这次课程设计，我明白了对于编写程序，解题的思路为重要。在编写程序之前，如果没有比较清晰的思路，根本不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也不会很强。在编程之前，我们应反复研究题目要求，对题目涉及的情况进行比较充分的分析，以便编写出更加符合题意的程序；其次要充分考虑各种临界情况，对一些错误的输入进行处理。因此在我们编程序之前一定要做好充分的准备，首先要理清自