4语法分析-递归下降法

第三章：语法分析

递归下降法自顶向下语法分析的实现方式LL(1)递归下降法(Recursive-DescentParsing)

对每个非终极符构造相应的一个子程序(称为语法分析子程序)，其功能是识别、分析该非终极符所能推导出的字符串.

1.1递归下降法的基本原理例如：一条产生式：While_Stm→whileExpdoStm则对应产生式右部的语法分析程序部分如下：begin

Match(while);

Exp;

Match(do);

Stm;

end

begin

Match(while)；Exp；

Match(do)；

Stm；

end

while

x>y

do

ifx>ythenx:=y+xelsey:=x递归下降分析示图复杂任务的不断拆解细化，直至直接匹配。1.2对文法的要求为了保证推导的唯一性，对文法的要求与LL(1)文法相同。即对于文法G中任一非终极符A，其任意两个产生式A和A，都要满足下面条件：

Predict(A)Predict(A)=2.语法分析程序的构造两个标准函数ReadToken：把输入流的头符读入变量token中Match(a):iftoken=athenReadToken else出错匹配两个动作读取下一个字符2.语法分析程序的构造当产生式形如:A

1|2|…|n,则按下面的方法编写子程序A：

procedureA()beginiftokenPredict(A1)then(1)elseiftokenPredict(A2)then(2)

else……iftokenPredict(An)then

(

n)

elseerror()end其中对

i=X1X2…Xn，(

i)='(X1);'(X2);…;'(Xn);如果XVN，

'(X)=X();如果XVT，'(X)=Match(X);//即if(token==X)ReadToken();如果X=，'(

)=skip(空语句).两句话①对于终极符匹配②对于非终极符调用2.语法分析程序的构造主程序：voidmain(){

ReadToken();S(); if(token=='#')成功； else失败}

2.语法分析程序的构造具体构建流程给定一个文法G求每条规则的Predict集写针对每个非终极符的函数写主函数优点：构造简单缺点：频繁的函数调用影响效率程序比较长终极符产生匹配命令，而非终极符则产生调用命令.因为文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法.与文法相关，文法变，程序变例：假设有文法

Z→aBa B→bB|cPredict(Z→aBa)={a},Predict(B→bB)={b},Predict{B→c}={c}则相应的递归子程序可如下：procedureZ()beginiftoken=athenMatch(a)；

B；

Match(a)elseerr(1)end;procedureB()beginiftoken=bthenMatch(b);B;elseiftoken=cthenMatch(c);elseerr(2)end;语法分析主程序：BeginReadToken;Z；Match(#)

EndReadTokenReadToken

(aBa)

'(a);'(

B);'(a)匹配调用匹配读取下一个字符例： ETE’ E’+TE’|

TFT’ T’*FT’|

Fi|(E)Predict(ETE’)=first(TE’)={i,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={i,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={i}Predict(F(E))=first((E))={(}procedureE()beginiftoken

{i,(}thenT；

E’

；

elseerr(1)end;语法分析主程序：BeginReadToken;E；Match(#)

endprocedureE’

()beginiftoken=“+”thenMatch(+);T；

E’

elseiftoken

{),#}

thenskipelseerr(2)end;例： ETE’ E’+TE’|

TFT’ T’*FT’|

Fi|(E)Predict(ETE’)=first(TE’)={i,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={i,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={i}Predict(F(E))=first((E))={(}例： ETE’ E’+TE’|

TFT’ T’*FT’|

Fi|(E)Predict(ETE’)=first(TE’)={i,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={i,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={i}Predict(F(E))=first((E))={(}procedureT()beginiftoken

{i,(}thenF；

T’

elseerr(3)end;procedureT’

()beginiftoken=“*”thenMatch(*);F；

T’

elseiftoken

{+,),#}

thenskipelseerr(4)end;例： ETE’ E’+TE’|

TFT’ T’*FT’|

Fi|(E)Predict(ETE’)=first(TE’)={i,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={i,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={i}Predict(F(E))=first((E))={(}procedureF

()beginiftoken=“i”thenMatch(i

)

elseiftoken=“(”

thenMatch((

); E;

Match())elseerr(5)end;例： ETE’ E’+TE’|

TFT’ T’*FT’|

Fi|(E)Predict(ETE’)=first(TE’)={i,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={i,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={i}Predict(F(E))=first((E))={(}ETFiiM(i)E’TFiiM(i)E’T’FT’例：i+i*i#递归下降分析过程+++M(+)*#*M(*)i###skip####M(i)skipE→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iT’++skipTE’FT’+TE’FT’εiiiε*FT’ε语法分析主程序：BeginReadToken;E；Match(#)

endTEE'T'F大量函数调用！！ETFiiM(i)E’TFiiM(i)T’F例：i+i*+i#递归下降分析过程+++M(+)**M(*)+E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iT’++skipTE’+TE’FT’ii*FT’ε语法分析主程序：BeginReadToken;E；Match(#)

endFT’Err(5)ETE'T'F练习题：已知文法G[S]:SAB|bCA|bB|aDCAD|bDaS|c1、计算每个非终极符的First集、Follow集.2、计算每个产生式的Predict集合.3、判断该文法是否为递归下降文法？文法符号First集step1step2step3SABCD

SAB|bCA|bB|aDCAD|bDaS|c{b,a,

}{b,

}{a,

}{b,a,c}{a,c}{b}{b,

}{a,

}{b}{a,c}{b}{b,

}{a,

}{b}{a,c}文法符号First集S{a,b,

}A{b,

}B{a,

}C{a,b,c}D{a,c}

SAB|bCA|bB|aDCAD|bDaS|c文法符号Follow集step1S

ABS

bCBaDCADDaSSABCD{#}{

}{

}{}{}{#}{a,#

}{#}{}{}{#}{a,#

}{#}{#}{}{#}{a,#

}{#}{#}{#}{#}{a,#,c

}{#}{#}{#}Predict(SAB

)={a,b,#}Predict(SbC

)={b}Predict(A

)={a,c,#}Predict(Ab)={b}Predict(B

)={#}Predict(BaD)={a}Predict(