第05章、自顶向下语法分析

《第05章、自顶向下语法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自顶向下语法分析方法5.1自顶向下分析简介5.2递归子程序分析法5.3LL(1)分析法(预测分析法)•FIRST和FOLLOW集定义和计算•LL(1)文法定义•LL(1)分析程序的生成5.4非LL(1)文法的改造15.1自顶向下分析简介一、分析算法要点：.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前输入符匹配SaaabABaAS–>ABA–>aA

2、B–>b

3、bBaaab.SABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>aaabB–>b

4、2二、带回溯的自顶向下分析S–>ABA–>aA

5、B–>b

6、bB对aaabb.S(1)A...S–>AB(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaB...A–>(6)aaabB–>b分析结论错误！aaabb.S(1)A...S–>AB(2)aA...A–>aA(3)aaA...A–>aA(4)aaaA...A–>aA(5)aaaBA–>(6’)aaabBB–>bB(7)aaabbB–>b分析结论正确！3三、预测分析程序P

7、redictiveparser--------无回溯的自顶向下分析程序特征——根据下一个输入符号为当前要处理的非终结符选择产生式要求——文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号（lookahead)预测分析程序的实现技术1.递归（下降）子程序2.表驱动分析程序45.2递归子程序分析法主要思想：对每个非终结符，根据它的规则式写出相应的子程序，由于文法递归，所以相应的子程序也就递归。递归子程序由此得名。例文法：G[E]:E->aAA->a

8、bAc5G[E]:E->

9、aAA->a

10、bAcviodE(){if(ch==’a’){GETCH();//读下一字符A();}elseERROR();}6G[E]:E->aAA->a

11、bAcviodA(){if(ch==’a’)GETCH();elseif(ch==’b’){GETCH();A();if(ch==’c’)GETCH();elseERROR();}elseERROR();}7一、表驱动预测分析程序模型Input#总控程序预测分析表stack5.3LL(1)分析法(预测分析法)8带a0a1a2a3a4a5a6a7

12、a8…an-1an有限控制器磁头二、识别程序的数学模型----下推自动机91.FIRST集和FOLLOW集的定义（首符、随符）设G=(VN,VT,P,S)是上下文无关文法,A∈VNFIRST（）={a

13、=>a...,a∈VT,∈V*}若=>ε则规定ε∈FRIST（）FOLLOW（A）={aS=>...Aa...,a∈VT}若S=>...A,则#∈FOLLOW(A)三、LL(1)文法****102.计算FIRST集(1)若XV,则FIRST(X)={X}；(2)若XVN,且有产生式Xa…,

14、则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中；(3)若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)=>),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,…,K)均含有,则把加到FRIST(X

15、)中.*11例：G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>(4)T–>FT’(5)T’–>*FT’(6)T’–>(7)F–>(E)(8)F–>i各非终结符的FIRST集合：FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝各非终结符的FOLLOW集合：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOL

16、LOW(F)=｛*,＋，),#}123.计算FOLLOW集(1)对于文法的开始符号S,置#于FOLLOW(S)中;(2)若ＡαBβ是一个产生式,则把FIRST(β)-{}加至FOLLOW(B)中;(3)若ＡαB是一个产生式,或ＡαBβ是一个产生式而β=>(即FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。（例题见上页)*134.SELECT集的定义给定上下文无关文法的产生