资源描述：
《语法分析自顶向下的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、语法分析——自顶向下的分析重点与难点重点：自顶向下分析的基本思想，预测分析器总体结构，预测分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点：FIRST和FOLLOW集的求法，对它们的理解以及在构造LL(1)分析表时的使用。递归子程序法中如何体现分析的结果。基本要求掌握语法分析、2型文法的概念和自顶向下分析的基本思想，预测分析器总体结构，预测分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。熟练掌握推导、FIRST集和FOLLOW集的求法、消除左递归、提取左因子、
2、LL(1)文法、文法的改写、递归子程序法、预测分析法。例题解析例1求表达式文法的语法符号的FIRST集和FOLLOW集表达式文法:E→TE'E'→+TE’
3、εT→FT'T'→*FT’
4、εF→(E)
5、idFIRST(F)={(,id}FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)={(,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(()={(}FIRST())={)}FIRST(id)={id
6、}FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+,),#}FOLLOW(T')=FOLLOW(T)={+,},#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={*,+,},#}例2消除下述文法的左递归。S→Ac
7、cA→Bb
8、bB→Sa
9、a【解】先将间接左递归,变成直接左递归4将B的定义代入A产生式得：A→Sab
10、ab
11、b，将A的定义代入S产生式得:S
12、→Sabc
13、abc
14、bc
15、c采用引进新的非终结符的方法消除直接左递归：S→abcS’
16、bcS’
17、cS’S’→abcS’
18、ε删除“多余的”产生式：A→Sab
19、ab
20、b和B→Sa
21、a得到文法G[S]：S→abcS’
22、bcS’
23、cS’S’→abcS’
24、ε例3已知文法Ｇ：
S→(L
25、a
L→S,L
26、)（1）构造文法Ｇ的预测分析表。（2）若输入串为“（ａ，）”，请给出语法分析过程。【解】（１）1）求各非终结符的FISRT集和FOLLOW集：FIRST(S)={(,a)FIRST(L)={a}ÈFIRST(S)={(,
27、),a}FOLLOW(S)={’,’,#}FOLLOW(L)=FOLLOW(S)={’,’,#}2）预测分析表：(a,}#SS→(LS→aLL→S,LL→S,LL→)（２）对输入串“（ａ，）”的分析处理过程如表1所示。表1对输入串“（ａ，）”的分析过程步骤分析栈输入串所用产生式０＃Ｓ（ａ，）＃１＃L(（ａ，）＃S→(L２＃Lａ，）＃３＃L,Sａ，）＃L→S,L４＃L,aａ，）＃S→a５＃L,，）＃６＃L）＃７＃））＃L→)８＃＃例4给定文法Ｇ＝（｛ｉ，ｄ，'('，')'｝，｛Ｅ，Ａ｝，Ｅ，Ｐ）其中Ｐ：Ｅ→
28、ｉＡＥ→ ＥＡＡ→ｉＡ→ ｄＡ→(Ｅ)(1)消除左递归；4(2)计算改写后文法中各非终结符的FIRST集和FOLLOW集；(3)构造改写后文法的预测分析表；该文法是LL(1)文法吗?。【解】(1)消除左递归后的文法为:E→iAＥ＇Ｅ＇→e
29、AＥ＇A→iA→ｄA→(E)(2)各非终结符的FISRT集和FOLLOW集FIRST(E)=｛ｉ｝FIRST(Ｅ＇)=｛ｉ,ｄ,(,e)FIRST(A)=｛ｉ,ｄ,()FOLLOW(E)=｛),#｝FOLLOW(Ｅ＇)=｛｝,#｝FOLLOW(A)=｛ｉ,ｄ,(,),#｝
30、(3)改写后文法的预测分析表：ｉｄ()#EE→ｉAＥ＇Ｅ＇Ｅ＇→AＥ＇Ｅ＇→AＥ＇Ｅ＇→AＥ＇E→eE→eAA→ｉA→ｄA→(E)预测分析表中无多重入口,因此该文法是LL(1)文法.例5if语句的原始文法S→ifEthenS
31、ifEthenSelseS
32、other存在左因子ifEthenS,改写此文法消除左因子。.【解】引进非终结符S’S'→ε
33、elseS提取左因子：S→ifEthenSS’
34、other改写后的文法:S→ifEthenSS’
35、otherS'→ε
36、elseS例6构造简单算术表达式的分析器【解】
37、E的子程序(E→T(+T)*)procedureE;beginT;Ｔ的过程调用whilelookhead='+'dobegin当前符号等于＋时match(‘+’);处理终结符＋TＴ的过程调用endend;lookhead：当前符号4T的子程序(T→F(*F)*)procedureT;beginF;F的过程调用whilelookhead='*'thenbegin当前符号等于＊时match('*');处理终结符＊FF
