递归下降法推选优秀ppt

递归下降(xiàjiàng)法第一页，共23页。递归下降(xiàjiàng)分析法基本(jīběn)思想对文法中的每个非终结符编写一个函数(或子程序),每个函数（或子程序）的功能(gōngnéng)是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。第二页，共23页。递归下降(xiàjiàng)分析法构造(gòuzào)递归下降分析程序的方法:为每个非终结符编制一个递归下降分析函数(hánshù)，每个函数(hánshù)名是相应的非终结符，函数(hánshù)体则是根据规则右部符号串的结构和顺序编写。A→α1α2…αnαi∈VTαi∈VNα1α2…αn=ε第三页，共23页。递归下降(xiàjiàng)分析法(1)当遇到(yùdào)终结符a时，则编写语句if(当前(dāngqián)读来的输入符号==a)读下一个输入符号；(2)当遇到非终结符A时，则编写语句调用A()；第四页，共23页。(4)当某个非终结符的规则(guīzé)有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。(3)当遇到(yùdào)规则A→ε时，则编写语句递归下降(xiàjiàng)分析法if(当前读来的输入符号FOLLOW(A))

error()；第五页，共23页。F();T'→*FT'|εGetSym();E'→+TE'|εE→E+T|TE→E+T|T(1)函数GetSym()printf(“success”);elseif(sym==‘(’)if(sym==‘)’)GetSym();error();GetSym();if(sym==‘+’)递归下降(xiàjiàng)分析法F→(E)|idelseprintf(“fail”);E→E+T|TT→T*F|FF→(E)|id例设有文法(wénfǎ)G[E]：试构造一个识别该文法(wénfǎ)句子的递归下降分析程序。递归下降(xiàjiàng)分析法第六页，共23页。 分析首先(shǒuxiān)消去文法左递归，得到文法G'[E]E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idE→E+T|TT→T*F|FF→(E)|id递归下降(xiàjiàng)分析法第七页，共23页。经过(jīngguò)验证，文法G'[E]是LL(1)文法。递归下降(xiàjiàng)分析法第八页，共23页。分析程序中定义(dìngyì)两个函数：(1)函数GetSym()功能:读进源程序的下一个单词符号并将它放在全程(quánchéng)变量sym。(2)函数error()功能(gōngnéng):出错处理程序。递归下降分析法第九页，共23页。对文法(wénfǎ)G'[E]可写出相应的递归下降分析程序如下：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idmain(){GetSym();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}递归下降(xiàjiàng)分析法第十页，共23页。E(){T();E'();}E'(){if(sym==‘+’){GetSym();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}递归下降(xiàjiàng)分析法E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id第十一页，共23页。T(){F();T();}

E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|idT(){if(sym==‘*’){GetSym();F();T();}elseif(symfollow(T'))error();}递归下降(xiàjiàng)分析法练习(liànxí)：编写T’()?第十二页，共23页。F(){if(sym==‘id’)GetSym();elseif(sym==‘(’){ GetSym();E();if(sym==‘)’)GetSym();elseerror();}elseerror();}E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id递归下降(xiàjiàng)分析法第十三页，共23页。递归下降(xiàjiàng)分析法main(){GetSym();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}id+id#E(){T();E'();}T(){F();T();}

见F见E'见T'返回(fǎnhuí)下一页第十四页，共23页。F(){if(sym==‘id’)GetSym();elseif(sym==‘(’){ GetSym();E();if(sym==‘)’)GetSym();elseerror();}elseerror();}递归下降(xiàjiàng)分析法返回(fǎnhuí)T第十五页，共23页。递归下降(xiàjiàng)分析法T(){if(sym==‘*’){GetSym();F();T();}elseif(symfollow(T'))error();}follow(T')={+,),#}返回(fǎnhuí)T第十六页，共23页。递归下降(xiàjiàng)分析法E'(){if(sym==‘+’){GetSym();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}返回(fǎnhuí)E见T返回(fǎnhuí)E第十七页，共23页。递归下降(xiàjiàng)分析法递归下降(xiàjiàng)分析法elseprintf(“fail”);F();if(sym==‘)’)GetSym();递归下降(xiàjiàng)分析法递归下降(xiàjiàng)法elseprintf(“fail”);递归下降(xiàjiàng)分析法经过(jīngguò)验证，文法G'[E]是LL(1)文法。if(sym==‘+’)对这个例子，若采用(cǎiyòng)扩充的BNF表示法改写文法，得到G"[E]：E→T{+T}T→F{*F}F→(E)|id递归下降(xiàjiàng)分析法E→E+T|TT→T*F|FF→(E)|id第十八页，共23页。该文法是LL(1)文法，其递归下降分析程序中主函数和函数F()同上，对函数E()和函数T()用while语句描述(miáoshù)如下：递归下降(xiàjiàng)分析法第十九页，共23页。E(){T();while(sym==‘+’){GetSym();T();}}T(){F();while(sym==‘*’){GetSym();F();}}E→T{+T}T→F{*F}F→(E)|id递归下