自顶向下语法分析方法第第4 4章章4.1 确定的自顶向下分析思想n确定的自顶向下分析方法，首先要解决从文法 的开始符号出发，如何根据当前的输入符号（ 单词符号）唯一地确定选用哪个产生式替换相 应非终结符往下推导，或构造一棵相应的语法 树。n例4.1 设文法G1S： S pA | qB A cAd | a B dB | b 考虑对输入串w=pccadd的分析。n这个文法有以下两个特点：q每个产生式的右部都由终结符号开始。q如果两个产生式有相同的左部，那么它们的右部由 不同的终结符开始。n例4.2 设文法G2S： S Ap S Bq A a A cA B b B db 考虑对输入串w= ccap的分析。n这个文法有以下两个特点：q产生式的右部不全是由终结符开始q如果两个产生式有相同的左部，它们的右部是由不同 的终结符或非终结符开始。q文法中无空产生式n定义4.1 设G=(VT,VN,P，S)是上下文无关文法FIRST()=a| a,aVT, ,V*若 ，则规定FRIST()。如： FIRST(Ap) = a, c FIRST(Bq) = b, dn例4.3 设文法GS： SaA Sd AbAS A 考虑对输入串w= abd的分析。n结论q当某一非终结符的产生式中含有空产生式时，它的 非空产生式右部的首符号集两两不相交，并与在推 导过程中紧跟该非终结符右边可能出现的终结符集 也不相交则仍可构造确定的自顶向下分析。n定义4.2 设G=(VT,VN,P,S)是上下文无关文法, 对AVN 定义 FOLLOW(A)=aS A 且aVT ， aFRIST()，V*，V+ 若S uA，且 ，则规定 #FOLLOW(A)如： FOLLOW(A)=FIRST(S) #=a,d,#n定义4.3 给定上下文无关文法的产生式A， AVN， V*, 若 ，则SELECT(A ) = FIRST()若如果 ，则SELECT(A ) = (FIRST()-)FOLLOW(A)n定义4.4 一个上下文无关文法是LL(1)文法的充分必要 条件是，对每个非终结符A的两个不同产生式 ，A， A，满足 SELECT(A) SELECT(A ) = 其中、不能同时 。nLL(1)文法的含义q第1个“L”指的是由左向右地处理输入。q第2个“L”指的是它为输入串描绘出一个最左推导。q括号中的数字1意味着它只需向右看1个符号便可决 定如何推导即选择哪个产生式（规则）进行推导。4.2 LL(1)文法的判别n求出能推出的非终结符n计算FIRST集n计算FOLLOW集n计算SELECT集n判别是否是LL(1)文法n例：设文法GS 为: SAB SbC A Ab B BaD CAD Cb DaS Dc 判断它是否是LL(1)文法。1.求出能推出的非终结符SAB SbC A Ab B BaD CAD Cb DaS Dc非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否2.计算FIRST集n根据定义计算 1.若XV,则FIRST(X)=X 2.若XVN,且有产生式Xa， a V,则 aFIRST(X);若X也是一条产生式,则 FIRST(X). 3.若XY是一个产生式且YVN,则把FIRST(Y) 中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Yi-1都是非终结 符,而且对于任何j,1j i-1,FIRST(Yj)都含有(即Y1Yi-1 ),则把FIRST(Yj)中的所有非元素都加 到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中.n用关系图法求文法符号的FIRST集(自学)3.计算FOLLOW集n根据定义计算 1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若B是一个产生式,则把 FIRST()-加至FOLLOW(B)中; 3.若B是一个产生式,或B是一个产生式而 ，则把FOLLOW(A)加至 FOLLOW(B)中n用关系图法求非终结符的FOLLOW集(自学)4.计算SELECT集SELECT(SAB)=a,b,# SELECT(SbC)=b SELECT(A)=a,c,# SELECT(Ab)=b SELECT(B)=#SELECT(BaD)=a SELECT(CAD)=a,b,c SELECT(Cb)=b SELECT(DaS)=a SELECT(Dc)=c5. 判别是否是LL(1)文法所以文法GS 不是LL(1)文法。4.3 某些非LL(1)文法到LL(1)文法的等价变换n提取左公共因子n消除左递归1. 提取左公共因子n例4.6 文法G1S : SaSb SaS S化为： SaS(b|) S进一步化为： SaSA Ab A S 结果仍然不是LL(1)文法。因此，文法中不含左公共 因子只是LL(1)文法的必要条件。A1|2|n 变换为 A(1|2|n) ，即 AA A 1|2|nn例4.7 文法G2A: Aad ABc BaA BbB1.化为： Aad AaAc AbBc BaA BbB2.化为： Aa(d|Ac) AbBc BaA BbB3.化为： AaA AbBc Ad AAc BaA BbBn例4.8 文法G3S : SaSd SAc AaS Ab1.化为： SaSd SaSc Sbc AaS Ab2.化为： SaS(d|c) Sbc AaS Ab3.化为： SaSA Sbc Ad Ac AaS Ab 结果中A是不可达到的符号 。n例4.9 文法G4S : SAp|Bq AaAp|d BaBq|e1.化为： SaApp|aBqq|dp|eq AaAp|d BaBq|e2.化为： Sa(App|Bqq) Sdp|eq AaAp|d BaBq|e3.化为： SaS Sdq|eq SApp|Bqq AaAp|d BaBq|e4.化为： SaS Sdp|eq S aAppp|aBqqq|dpp|eqq AaAp|d BaBq|en结论q不一定每个文法的左公共因子都能在有限的步 骤内替换成无左公共因子的文法。q一个文法提取了左公共因子后，只解决了相同 左部产生式右部的FIRST集不相交问题，当改 写后的文法不含空产生式，且无左递归时，则 改写后的文法是LL(1)文法，否则还需用LL(1) 文法的判别方式进行判断才能确定是否为LL(1) 文法。2. 消除左递归n直接左递归 AA AVN, V*n间接左递归 AB BA A,BVN, , V*n例4.10 G5S: SSa Sb 考虑对输入串baaaa#的分析n例4.11 G6A： AaB ABb BAc Bd 考虑对输入串adbcbcbc#的分析SbS SaS|BaBc BBbc BdBaBcB | dB BbcB| 消除直接左递归nAA1| A2| Am|1|2|n 其中： i 不等于 ， j不以A开头。 改为： A 1A| 2A | nA A 1A | 2A | mA |消除间接左递归n将间接左递归变为直接左递归，然后消除直接 左递归。消除文法中一切左递归的算法1. 以某种顺序将文法非终结符排列A1 ,A2 An 2. for i:=1 to n dobegin for j:=1 to i-1 do 用Aj1| 2 | k关于Aj的全部产生式替代形如Ai Ajr的产生式为:Ai 1r| 2r|kr;end;消除Ai的直接左递归; 3.化简由2得到的文法n例文法GS: SQc|c QRb|b RSa|aR Qca|ca|a R Rbca|bca|ca|a R (bca|ca|a)R R bcaR|将非终结符排序为S、Q、R4.5 LL(1)分析的实现n递归下降LL(1)分析程序n表驱动LL(1)分析程序4.5.2表驱动LL(1)分析程序n一个预测分析器是由三个部分组成q预测分析程序q符号栈q预测分析表预测分析程序预测分析表输入单词流符号栈iptop输出预测分析表n预测分析表可用一个矩阵M表示。矩阵的元素 MA, a中的内容为一条关于A的产生式，表明当 用非终结符A向下推导且面临输入符a时，所应采 取的候选产生式，当元素内容无产生式时，则出 错。n一个文法的预测分析表不含有多重入口，当且仅 当该文法是LL(1)的。n预测分析表的构造算法q若aSELECT(A)，则把A放入MA, a中。q把所有无定义的MA，a标上出错标记。n例 文法GE： E TE E +TE| T FT T *FT| F i | ( E )构造过程：1.判断文法是否为LL(1)文法2.构造预测分析表预测分析程序算法分析栈 #E #ET #ETF #ETi #ET #E #ET+ #ET #ETF #ETi #ET #ETF* #ETF #ETi #ET #E #剩余串 i+i*i# i+i*i# i+i*i# i+i*i# +i*i# +i*i# +i*i# i*i# i*i# i*i# *i# *i# i# i# # # #产生式 ETE TFT F i i i 匹配匹配 T E +TE + + 匹配匹配 T FT F i i i 匹配匹配 T *FT * * 匹配匹配 F i i i 匹配匹配 T E 接受接受n例 对输入串 i+i*i的分析4.5.1递归下降LL(1)分析程序（自学）n实现思想q对文法中每个非终结符编写一个递归过程，每个过 程的功能是识别由该非终结符推出的串，当某非终 结符的产生式有多个候选时能够按LL(1)形式可唯一 地确定选择某个候选进行推导。n限制q对文法要求高，必须满足LL(1)文法；q速度慢，占用空间多。