WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1 系统描述按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。

该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。

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

该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。

通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。

该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。

2 文法及属性文法的描述2．1文法描述语句 > ::= while (< 条件表达式 > (< 赋值语句 > | 语句 ><条件表达式> ::= (<标识符>|<无符号整数>）<条件运算符> (<标识符>|<无符号整数><标识符> ::= <字母> (<字母>|<数字><条件运算符> ::= > | < | =<无符号整数> ::= <数字>（<数字><赋值语句> ::= <标识符>=(<标识符> | <数字> <算术运算符> (<标识符> | <数字><算术运算符> ::= + | - | * | /<赋值语句> ::= <标识符>=<标识符> | <数字>2．2递归文法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 -> (EF | iF | nFF -> +EF | -EF | *EF | /EF | ε2．3属性文法的描述产生式属性文法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 E2 B.place:=newlabel;B.code:=E1.code || relop.code ||E2.code ||gen(B.place ‘:=’ , E1.place , r elop.place , E2.place;relop -> < | =relop.place:=newlabel;| >relop.code:=gen(‘<’||gen(‘=’||gen(‘>’;E -> (E1F E.place:=newlabel;E.code:=E1.code ||F.code ||gen(E.place ‘:=’ ,‘(’, E1.place , ‘’, F.place;E -> iF E.palce:=newlabel;E.code:=i.code ||F.code ||gen(E.palce ‘:=’ ,i.place , F.place;E -> nF E.place:=newlabel;E.code:=n.code ||F.code ||gen(E.place ‘:=’ , n.place , F.place;F -> +EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= + ’, E.place , F1.place;F -> -EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= - ’, E.place , F1.place;F -> *EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= * ’, E.place , F1.place;F -> /EF1 F.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 中间代码形式的描述4．1三地址代码在本程序中用到了三地址语句的输出包括以下的种类：赋值语句：x:= y op z复制语句：x:= y条件转移语句：if x relop y goto L例如，本程序中语句while (B S ,可以输出三地址代码为：if B goto L else goto Lnext；而E -> (EF可以输出三地址代码为：E1:= (E2 F。

4．2本程序中的三地址代码L0:=if (B goto L1 else goto Lnext S -> while (BSS -> i=E L:= i=EB -> E relopB:= E1 relop E2Erelop -> < relop:= <relop -> = relop:= =relop -> > relop:= >E -> (EF E1:= (E2 FE -> iF E:= I FE -> nF E:= n FF -> +EF F1:= +E F2F -> -EF F1:= -E F2F -> *EF F1:= *E F2F -> /EF F1:= /E F2F ->εF:= ε图2 三地址代码5 概要设计5．1简要分析递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。

在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。

单词类型主要包括变量，关键字，常量，各种符号等，每种符号都是一种类型。

在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。

根据文法可以得到这个递归下降程序可以分析包含有while嵌套的语句，在文法的开始符号S中就嵌套了S 本身，因此这个文法的递归中就要考虑到while的自身嵌套。

在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会报错。

5．2程序的概要设计在本程序中，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 详细的算法描述（流程图或伪代码）关闭文件6．1main(主函数的算法描述图3 mian(流程图主程序执行时首先会测试input.txt文件是否存在，因为程序就是通过该文件得到需要进行递归下降分析方法分析的输入符号串；然后建立output.txt文件，问以后的输出结果做基础；接着调用递归下降分析法的入口程序S(来开始对文件中的输入字符串进行词法，语法和语义分析；最后关闭文件结束程序。

6．2Getsymbol(子程序的算法描述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是<）返回11；Else if（sym是=）返回10；Else if（sym是>）返回9；Else if（sym是；）返回20；}该程序就是对输入串进行分析，分析到不同的数据类型就相应返回它的机内码，这样方便在语法分析中进行分析。