WHILE循环语句的翻译程序设计.doc

编译原理课程设计说明书WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1 系统描述按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。词法分析器应能识别关键字，标示符，常量，操作符等。该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。2 文法及属性文法的描述21文法描述 := while () ( | ) := (|） (|) := (|) := | | = := （) := =( | ) ( | ) := + | - | * | / := = | 22递归文法while语句文法：S - while (B) S | i=EB - E relop Erelop - E - E+E | E-E | E*E | E/E | (E) | i | n在编写程序的时候用到的是递归下降法，而递归下降法对文法的要求是不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法：S - while (B) S | i=EB - E relop Erelop - E - (E)F | iF | nFF - +EF | -EF | *EF | /EF | 23属性文法的描述产生式属性文法S - while (B) S1S.begin:=newlabel;S.next:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin, :) | B.code |gen(S.true, :) | S1.code | gen(goto,S.begin) | gen(B.false, :) | gen(goto Lnext);B - E1 relop E2B.place:=newlabel;B.code:=E1.code | relop.code |E2.code |gen(B.place := , E1.place , relop. place , E2.place);relop - relop.place:=newlabel;relop.code:=gen();E - (E1)FE.place:=newlabel;E.code:=E1.code | F.code |gen(E.place := ,(, E1.place , ), F.place);E - iFE.palce:=newlabel;E.code:=i.code | F.code | gen(E.palce := ,i.place , F.place);E - nFE.place:=newlabel;E.code:=n.code | F.code | gen(E.place := , n.place , F.place);F - +EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= + , E.place , F1.place);F - -EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= - , E.place , F1.place);F - *EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= * , E.place , F1.place);F - /EF1F.place:=newlabel;F.code:=E.code | F1.code | gen(F.place:= / , E.place , F1.place);F - F.place:=newlabel;F.code:=gen(F.code:= );图1 属性文法3 语法分析方法描述按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。该子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，总是先执行被调用的子程序，然后再执行后继的程序。在本程序中，首先要做的就是将设计的文法根据递归下降分析技术对文法的要求改为非左递归的文法。程序中5个子程序，其中S 是开始符号，也是递归下降分析的入口，通过调用int Getsymbol()对输入的字符串进行单词分析，并返回当前所分析到的单词，然后在递归语法分析中根据这个单词分析下一步要执行的子程序。4 中间代码形式的描述41三地址代码在本程序中用到了三地址语句的输出包括以下的种类：赋值语句：x:= y op z复制语句：x:= y条件转移语句：if x relop y goto L 例如，本程序中语句while (B) S ,可以输出三地址代码为：if B goto L else goto Lnext；而E - (E)F可以输出三地址代码为：E1:= (E2) F。42本程序中的三地址代码 S - while (B) SL0:=if (B) goto L1 else goto LnextS - i=EL:= i=EB - E relop EB:= E1 relop E2relop - relop:= =relop:= =relop - relop:= E - (E)FE1:= (E2) FE - iFE:= I FE - nFE:= n FF - +EFF1:= +E F2F - -EFF1:= -E F2F - *EFF1:= *E F2F - /EFF1:= /E F2F -F:= 图2 三地址代码5 概要设计51简要分析递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括变量，关键字，常量，各种符号等，每种符号都是一种类型。在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。根据文法可以得到这个递归下降程序可以分析包含有while嵌套的语句，在文法的开始符号S中就嵌套了S本身，因此这个文法的递归中就要考虑到while的自身嵌套。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会报错。52程序的概要设计在本程序中，Getsymbol()子程序就是对当前输入的字符串进行词法分析，包括对变量，常量，关键字，各种符号的分析。主程序main()主要就是进行各种变量的初始化，调用递归分析程序的入口子程序。子程序间的嵌套关系如下：void main() S(); void Getsymbol() void ERROR() void S() re=Getsymbol(); if(re=while(关键字) B(); S();else(re=i(变量) re=Getsymbol(); if(re= =) E(); void B() E(); relop(); E();void E() re=Getsymbol();if(re= ( ) E();re=Getsymbol();if(re=) F();else if(re=i) F();else if(re=n) F();void F() re=Getsymbol();if(re=+) E(); F();else if(re=-) E(); F();else if(re=*) E(); F();else if(re=/) E(); F();6 详细的算法描述（流程图或伪代码）初始化各变量打开文件调用S()子程序关闭文件61main()主函数的算法描述图3 mian()流程图主程序执行时首先会测试input.txt文件是否存在，因为程序就是通过该文件得到需要进行递归下降分析方法分析的输入符号串；然后建立output.txt文件，问以后的输出结果做基础；接着调用递归下降分析法的入口程序S()来开始对文件中的输入字符串进行词法，语法和语义分析；最后关闭文件结束程序。62Getsymbol()子程序的算法描述Int Getsymbol()sym=fgetc(intput); /取当前文件指针指向的字符While(sym不为空) if(sym是a-z的字符)将该字符保存在token1数组中；继续取下一个是a-z的字符保存在数组中；当sym不是字符时，则判断该数组中的符号串是不是关键字，是就返回16（while的机内码）；不是就返回13（变量的机内码）；Else if（sym是0-9之间的数字）将该数字保存在token2数组中；继续取下一为0-9的数字，并保存到数组中去；当sym不是数字是，就返回12（常数的机内码）；Else if（sym是+）返回4；Else if（sym是-）返回3；Else if（sym是*）返回2；Else if（sym是/）返回1；Else if（sym是）返回9；Else if（sym是；）返回20；该程序就是对输入串进行分析，分析到不同的数据类型就相应返回它的机内码，这样方便在语法分析中进行分析。本程序还保存了变量和常量在结构数组中，方便在语义分析的时候使用。63 S()子程序的算法描述void S()re=Getsymbol(); /取下一个字符的机内码if(re=关键字) /执行S-while (B) Sre=Getsymbol(); /取下一个字符的机内码If(re=左括号)调用B()；re=Getsymbol(); /取下一个字符的机内码if(re=右括号)调用S();Else if(re=变量) /执行S-i = E re=Getsymbol(); /取下一个字符的机内码If(re=等号)调用E()；ElseERROR()；该程序就是对通过Getsymbol()词法分析程序得到的单词，进行不同的程序语句执行。当得到了while是就分析下一个是不是(，是的话就调用B()；否则就出错。取下一个单词，是)就调用S()；否则也出错。当得到的是变量i时，去下一个单词，如果是=就调用E()。64 B()和relop()子程序的算法描述在B()子程序中，不用判断任何的单词，就依次调用E()，relop()，E()，执行B-E relop EVoid relop() re=Getsymbol(); /取下一个字符的机内码 If(sym=大于号) ； /执行relop-= Else if(syn=小于号) ； /执行relop- Else ERROR()；在relop程序中就主要上判断当前取得的单词是不是条件运算符。65 E()子程序的算法描述Void E() re=Getsymbol(); /取下一个字符的机内码if(re=左括号) /执行E-(E)F E()；re=Getsymbol(); /取下一个字符的机内码if(re=右括号)F()；Else if(re=变量) /执行E-iF F()；Else if(re=常量) /执行E-nF F()；66 F()子程序算法描述Void F() re=Getsymbol(); /取下一个字符的机内码 If(re=加号) /执行F-+EF E(); F(); Else if(re=减号) /执行F-EF E(); F(); Else if(re=乘号) /执行F-*EF E(); F(); Else if(re=除号) /执行F-/EF E(); F();这个子程序和E()合起来就是一个完整的可递归的算术操作运算，但由于递归下降分析方法不能含有左递归文法，所以消去左递归后就成了两个子程序。7 软件的测试方法和测试结果由于该程序是用递归下降分析法来编写的，根据文法可以知道它可以对while语句进行嵌套，条件判断，赋值语句等的语句进行分析。而且赋值语句也可以嵌套。根据这些，我们在选择测试用例的时候就要选择比较典型的，尽量找到文法中有但程序中没能很好实现的地方。下面就用到了几个典型的用例：输入字符串：while (n10) a=(b+c)*d;测试分析：这个输入字符串是正确的，是最简单的while语句测试结果：图4 输出结果输入字符串：whil (n10) a=b+c;测试分析：该字符串不符合本程序的文法，其中是while出错测试结果：图5 输出结果输入字符串：while (tomn10) while (tomm10) toma=(tomb+c23)*d45;测试分析：该字符串符合文法，它嵌套了while语句，而且变量名包含数字和字符测试结果：图6 测试结果输入字符串：while (tomn10) toma=tomb+c23;测试分析：在嵌套的语句中，第二个while书写错误测试结果：图7 测试结果8 研制报告这次的课程设计要求比较严格，但是题目给得比较早，我在做第一个课程设计的时候就开始了该次课程设计的分析工作。对递归下降分析方法的了解，递归分析方法的实现原理，三地址输出等都做了详细的了解。并且在编程之前就已经将程序的概要设计都做出来了，所以在编写程序的时候相对比较容易。词法分析，语法分析都是很容易的，只要你理解了分析方法的实现原理，编写程序判断输入字符串是否满足给定的文法是比较简单的。比较麻烦的就是语义分析输出三地址代码，由于在递归下降分析技术