自顶向下语法分析方法(完).ppt

第5章 自顶向下语法分析方法,2019/6/7,第5章 自顶向下语法分析方法,Page 2,第五章 自顶向下语法分析方法,学习目标: 掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法 理解： LL(1)文法 了解：不确定的自顶向下分析,2019/6/7,Page 3,第5章 自顶向下语法分析方法,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子. 分类:,自顶向下的基本思想: 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子。,2019/6/7,第5章 自顶向下语法分析方法,Page 4,5.1 确定的自顶向下分析思想 5.2 LL(1)文法的判别 5.3 某些非LL(1)文法到LL(1)文法的等 价变换 5.4 不确定的自顶向下分析思想 5.5 确定的自顶向下分析方法,第五章 自顶向下语法分析方法,2019/6/7,第5章 自顶向下语法分析方法,Page 5,5.1 确定的自顶向下分析思想,1 确定分析的条件 2 开始符号集FIRST()的定义 3 后跟符号集FOLLOW(A)的定义 4 选择集合SELECT(A)的定义 5 LL(1)文法的定义,2019/6/7,Page 6,第5章 自顶向下语法分析方法,1 确定分析的条件,从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。,2019/6/7,Page 7,第5章 自顶向下语法分析方法,例1 设有文法G1S: SpA|qB AcAd|a BdB|b 若输入串W=pccadd。自顶向下的推导过程为:,S,S,=pA,=pcAd,=pccAdd,=pccadd,G1S有如下特点： (1) 每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同的终结符开头。 对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。,2019/6/7,Page 8,第5章 自顶向下语法分析方法,例2：设有文法G2S为: SAp|Bq Aa|cA Bb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,该例说明，当 (1) 产生式右部以终结符或非终结符开头（无空产生式）； (2) 同一非终结符的不同产生式的右部由不同的符号开头。 对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集）First集，分析过程可能是确定,若输入串W=ccap,自顶向下的推导过程为：,2019/6/7,Page 9,第5章 自顶向下语法分析方法,例3：设有文法G3S SaA|d AbAS| 若输入串W=abd，自顶向下的推导过程为：,S,=abd,S,=abAS,=abS,文法的特点是：包含空产生式 对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集）Follow集，分析过程可能是确定的。,=aA,2019/6/7,Page 10,第5章 自顶向下语法分析方法,1 确定分析的条件,要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法。 先研究三个定义 开始符号集FIRST集 后跟符号集FOLLOW集 选择集合SELECT集,2019/6/7,Page 11,第5章 自顶向下语法分析方法,2 开始符号集FIRST()的定义,定义: 设G=(VN, VT, P, S)是上下文无关文法，(VNVT)* FIRST() = a VT | * a 若* 则规定 FIRST() 直观上说，文法符号串 的开始符号集是由推导出的开头的终结符（包括）组成。,2019/6/7,Page 12,第5章 自顶向下语法分析方法,例文法G2S:,SAp SBq Aa AcA Bb BdB,FIRST(Ap)= FIRST(Bq)= FIRST(a)= FIRST(cA)= FIRST(b)= FIRST(dB)=,由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析,a,c,b,d,a,c,b,d,First:开始符号集,2019/6/7,Page 13,第5章 自顶向下语法分析方法,例2：设有文法G2S为: SAp|Bq Aa|cA Bb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,SAp FIRST(Ap)=a,c SBq FIRST(Bq)=b,d Aa FIRST(a)=a AcA FIRST(cA)=c Bb FIRST(b)=b BdB FIRST(dB)=d,若输入串W=ccap,自顶向下的推导过程为：,2019/6/7,Page 14,第5章 自顶向下语法分析方法,3 后跟符号集FOLLOW(A)的定义,定义 ： 设G=(VT, VN, P, S)是上下文无关文法，AVN ， FOLLOW(A)=a|S=*Aa，a VT， 若有S=* A，则规定 # FOLLOW(A) （注： # 输入串#，#做为输入串的结束符） 直观上说，非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,2019/6/7,Page 15,第5章 自顶向下语法分析方法,例 文法G3S: SaA|d AbAS|,由 S=* S 得 # FOLLOW(S) 由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW(S)=#,a,d,由S=* aA 得 # FOLLOW(A) 由S=* abAS=* abAaA 得 a FOLLOW(A) =* abAd 得 d FOLLOW(A) FOLLOW(A)=#,a,d,2019/6/7,Page 16,第5章 自顶向下语法分析方法,3 后跟符号集FOLLOW(A)的定义,说明： 对于非终结符A的两个产生式 AbAS 和 A： 当输入符号FIRST(bAS)=b时，选AbAS推导， 当输入符号FOLLOW(A)=#,a,d 时，选A推导。 由于FIRST(bAS)FOLLOW(A)=，所以可进行确定的自顶向下分析。,2019/6/7,Page 17,第5章 自顶向下语法分析方法,例3：设有文法G3S SaA|d AbAS| 若输入串W=abd，自顶向下的推导过程为：,=abd,S,=abAS,=abS,文法的特点是:包含空产生式 对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。,=aA,FIRST(bAS)=b FOLLOW(A)=#,a,d ,2019/6/7,Page 18,第5章 自顶向下语法分析方法,4 选择集合SELECT(A)的定义,定义 对给定的上下文无关文法的产生式A，AVN，V*， 若*, 则 SELECT(A)=FIRST() 若=*, 则 SELECT(A) =(FIRST()-)FOLLOW(A),2019/6/7,Page 19,第5章 自顶向下语法分析方法,4 选择集合SELECT(A)的定义,解释 当A面对应输入符a，若First()中包含a，在自顶向下的分析中应选择产生式A进行推导； 此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a属于Follow(A)时，选择产生式A也是可以的。 直观上说某产生式A的SELECT集是指遇到哪些输入符号（包括#）时选用该产生式向下推导。,SELECT(A)=a,b,c,2019/6/7,Page 20,第5章 自顶向下语法分析方法,4 选择集合SELECT(A)的定义,即： 若*, 则是否选择A这条产生式进行推导，主要是看当时输入字符是否属于FIRST()，若是，则选它。 若=*, 则是否选择A这条产生式进行推导，除了看当时输入字符是否属于FIRST()，还要看当时输入字符是否属于FOLLOW(A)，若属于其中一个集合，则选它。,若*,则SELECT(A)=FIRST() 若=*, 则SELECT(A) =(FIRST()-)FOLLOW(A),2019/6/7,Page 21,第5章 自顶向下语法分析方法,例 G3S: SaA Sd AbAS A,SELECT(SaA)= SELECT(Sd)= SELECT(AbAS)= SELECT(A)=,若*,则SELECT(A)=FIRST() 若=*, 则SELECT(A) =(FIRST()-)FOLLOW(A),FIRST(aA)=,FIRST(d)=,FIRST(bAS)=,FOLLOW(A)=,#,a,b,b,d,a,2019/6/7,Page 22,第5章 自顶向下语法分析方法,4 选择集合SELECT(A)的定义,说明： 同一非终结符的不同产生式A与A，若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析。,SELECT(A)=a,b SELECT(A)=c,d,SELECT(A)=a,b SELECT(A)=a,d,2019/6/7,Page 23,第5章 自顶向下语法分析方法,5 LL(1)文法的定义,定义 : 一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与 A，满足SELECT(A)SELECT(A)=（无交集）。 LL(1)文法的含义是： 第一个L表示从左到右扫描输入串 第二个L表示分析过程用最左推导 1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。,2019/6/7,Page 24,第5章 自顶向下语法分析方法,例 有文法GS为： SaAS Sb AbA A,SELECT(SaAS)= a,由于SELECT(AbA)SELECT(A)=b， 所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。,SELECT(Sb)= b,SELECT(AbA)= b,SELECT(A)=Follow(A)= a,b,2019/6/7,第5章 自顶向下语法分析方法,Page 25,5.2 LL(1)文法的判别,要判别一个上下文无关文法是否是LL(1)文法 分为五步： 1. 求出能推出的非终结符集 2. 计算每个产生式右部的FIRST()集 3. 计算每个非终结符A的FOLLOW(A)集 4. 计算每个产生式A的SELECT(A)集 5. 按LL(1)文法的定义判别,2019/6/7,Page 26,第5章 自顶向下语法分析方法,1. 求出能推出的非终结符集,步骤： (1)第1次扫描扫描文法中的产生式 对能直接推出的产生式左部的终结符标“是”。 删除所有右部含有终结符的产生式。若以某一非终结符为左部的所有产生式都被删除，则该非终结符不能推出，将其标为“否”。,2019/6/7,Page 27,第5章 自顶向下语法分析方法,1. 求出能推出的非终结符集,例GS： SAB|bC Ab| BaD| CAD|b DaS|c,SAB SbC Ab A BaD B CAD Cb DaS Dc,是,是,否,2019/6/7,Page 28,第5章 自顶向下语法分析方法,1. 求出能推出的非终结符集,(2)第2次扫描扫描产生式右部的符号 对每个产生式p: AX1Xn，如果X1,Xn都被标为“是”(即X1,Xn都能推出)，则A也能推出，将其标为“是”。 如果AY1Yn中，Y1Yn中任一个已被标为“否”，则删掉该产生式，若这么做使得A的所有产生式都被删去，则A不能推出，将其标为“否”。,2019/6/7,Page 29,第5章 自顶向下语法分析方法,1. 求出能推出的非终结符集,例GS： SAB|bC Ab| BaD| CAD|b DaS|c,SAB SbC Ab A BaD B CAD Cb DaS Dc,是,是,否,是,否,能推出的非终结符集为A,B,S,2019/6/7,Page 30,第5章 自顶向下语法分析方法,2. 计算每个产生式右部的FIRST()集,首先对每一文法符号X (XVT VN)，求FIRST(X)的算法: 对每个a VT ：FIRST(a)= a 对每个AVN ：若 A * ， 则 FIRST(A) 对每个AVN ：若Aa, aVT ，则a FIRST(A),2019/6/7,Page 31,第5章 自顶向下语法分析方法,2. 计算每个产生式右部的FIRST()集,若X,Y1,Y2,Yn都VN,有产生式X Y1Y2Yn.当Y1,Y2,Yn-1都*时，FIRST(Y1)-,FIRST(Y2)-, FIRST(Yn-1)-,FIRST(Yn)都包含在FIRST(X)中。 当4中所有Yi*，则FIRST(X)= FIRST(Y1)FIRST(Y2)FIRST(Yn) ,2019/6/7,Page 32,第5章 自顶向下语法分析方法,例GS： SAB S bC Ab A BaD B CAD C b DaS D c,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集为A,B,S,b,a,b,a c,a,a c,b,2019/6/7,Page 33,第5章 自顶向下语法分析方法,利用求出每个文法符号的FIRST集求符号串的FIRST集,设=X1X2Xn 当X1不能=* ，则FIRST()=FIRST(X1) 若对任何j (1jn）都有FIRST(Xj), 则FIRST() =(FIRST(X1) - ) (FIRST(Xj) - ) FIRST(Xj+1) 若对所有i (1in)，都有FIRST(Xi)， 则 FIRST()=FIRST(X1)FIRST(Xn) ,2019/6/7,Page 34,第5章 自顶向下语法分析方法,例 GS SAB|bC Ab| BaD| CAD|b DaS|c,已求出非终结符的First集合如下: First(S)=a,b, First(A)=b, First(B)=a, First(C)=a,b,c First(D)=a,c,产生式右部符号串的开始符集合为: SAB FIRST(AB)= SbC FIRST(bC)= A FIRST()= Ab FIRST(b)= CAD FIRST(AD)= DaS FIRST(aS)=,FIRST(A)FIRST(B)=a,b,b,b,(FIRST(A)-)FIRST(D) =b,a,c,a,2019/6/7,Page 35,第5章 自顶向下语法分析方法,3计算每个非终结符A的FOLLOW(A)集,1.对所有AVN令Follow(A)= ;对开始符S，令Follow(S)=# ,因为S=*S，显然#FOLLOW(S),2. 对每条产生式AxBy，考察产生式右部的每一非终结符B， x,y V*，如果y不能推出 Follow(B)=Follow(B)First(y),否则,若y *， Follow(B)=Follow(B)(First(y)-) Follow(A),3. 重复2，直至对所有AVN，Follow(A)收敛为止。,若aFOLLOW(A) ,则表明S=*Aa， 由于AxBy，且y=*,则有 S=*Aa=xBya=xBa， 即S=*xBa, 所以aFOLLOW(B),2019/6/7,Page 36,第5章 自顶向下语法分析方法,例GS： 1SAB 2SbC 3Ab 4A 5BaD 6B 7CAD 8Cb 9DaS 10Dc,已求出非终结符的First集合如下: First(S)=a,b, First(A)=b, First(B)=a, First(C)=a,b,c First(D)=a,c,#,D,#,C,#,B,a #,A,S,Follow集(2),Follow集(1),Follow集(0),c,2019/6/7,Page 37,第5章 自顶向下语法分析方法,4计算每个产生式A的SELECT(A)集,按定义计算SELECT(A)： 若*，则 SELECT(A)=FIRST() 若=*，则 SELECT(A) =(FIRST()-)FOLLOW(A),2019/6/7,Page 38,第5章 自顶向下语法分析方法,例GS： SAB|bC Ab| BaD| CAD|b DaS|c,部分产生式的select集合 SELECT(SAB)= SELECT(SbC)= SELECT(A)= SELECT(Ab)= SELECT(BaD)= SELECT(CAD)=,(FIRST(AB)-)FOLLOW(S)=b,a,#,FIRST(bC) =b,FIRST(b) =b,FIRST(aD) =a,FIRST(AD) =b,a,c,(FIRST()-)FOLLOW(A)=a,c,#,2019/6/7,Page 39,第5章 自顶向下语法分析方法,5. 按LL(1)文法的定义判别,产生式的select集如下: SELECT(SAB)= b,a,# SELECT(SbC)=b SELECT(A)= a,c,# SELECT(Ab)= b SELECT(B)= # SELECT(BaD)=a SELECT(CAD)= b,a,c SELECT(Cb) =b SELECT(DaS)= a SELECT(Dc)= c,由于 SELECT(SAB)SELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b 所以文法GS不是LL(1)文法,一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与 A，满足SELECT(A)SELECT(A)=,2019/6/7,第5章 自顶向下语法分析方法,Page 40,非LL(1)文法 含有左公共因子的文法 若文法中含有形如：A|r 的产生式，称文法含有左公共因子。 显然, SELECT(A)SELECT(A r),文法不是LL(1)文法,5.3 某些非LL(1)文法到 LL(1)文法的等价变换,2019/6/7,第5章 自顶向下语法分析方法,Page 41,含有左递归的文法 文法中只要含有下列形式的产生式（含有或含有或二者皆有），则称文法含有左递归: AA AB BA 在中含有左递归的产生式，称为直接左递归； 在中虽然没有含左递归的产生式， 但A=B=A 即A=+ A,称为间接左递归.,5.3 某些非LL(1)文法到 LL(1)文法的等价变换,2019/6/7,第5章 自顶向下语法分析方法,Page 42,以直接左递归为例，若有如下产生式 AA | A 其中和为任意语法符号串。 不难证明有下面关系式： Select( AA ) ) First( A )First( ) Select( A ) First( ) 故AA和A的Select集相交，不是LL(1)文法,5.3 某些非LL(1)文法到 LL(1)文法的等价变换,A A A A 不知何时结束 不确定,若*,则SELECT(A)=FIRST() 若=*, 则SELECT(A) =(FIRST()-)FOLLOW(A),2019/6/7,第5章 自顶向下语法分析方法,Page 43,对非LL(1)文法进行等价变换 提取左公共因子 消除左递归 注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。,5.3 某些非LL(1)文法到 LL(1)文法的等价变换,2019/6/7,Page 44,第5章 自顶向下语法分析方法,将产生式A|r 等价变换为: A(|r)， 将括号内用一新引入的非终结符A表示,得 AA，A|r 一般形式：若A1|2|n, 提取左公共因子后变为 A(1|2|n )， 引进新的非终结符A，得： AA，A 1|2|n 若在i中仍含有左公共因子,可再次提取.,1、提取左公因子,2019/6/7,Page 45,第5章 自顶向下语法分析方法,例文法G1： SaSb|aS| 提左因子得:SaS(b|)| 引进新的非终结符S得: SaSS| S b|,1、提取左公因子,2019/6/7,Page 46,第5章 自顶向下语法分析方法,1)消除直接左递归 文法G:SSa|b 可改写成 SbS S aS| 一般情形: 含直接左递归的文法G： AA1|A2|Am|1|2|n 消除左递归后改写成： A1A|2A|nA A1 A|2 A|m A|,2、消除左递归,不难验证，改写前和改写后的文法 都产生语言ban|n0,2019/6/7,Page 47,第5章 自顶向下语法分析方法,2)消除间接左递归 将间接左递归变成直接左递归，再加以消除。 算法步骤： 把文法的所有非终结符按任一顺序排列， 如：A1，A2，An 从A1开始，按以下顺序处理Ai。 首先，消除左部为Ai的产生式的直接左递归； 然后，若左部为Ai的产生式的右部为非终结符Aj(ji)开头，即Ai Aj，则用左部为Aj的所有产生式的右部分别代替Ai Aj 中的Aj； 最后，得到的左部为Ai的产生式若有直接左递归，则消除之。 去掉无用产生式。,2019/6/7,Page 48,第5章 自顶向下语法分析方法,例 文法G：(1)SQc|c (2)QRb|b (3)RSa|a,将非终结符排序 ：R，Q，S 对R：产生式(3)不含直接左递归，所以保持不变 对Q：把(3)代入(2)得(2)QSab|ab|b，无直接左递归 对S：把(2)代入(1)得(1)SSabc|abc|bc|c，有直接左递归，消除直接左递归得 SabcS|bcS|cS S abcS| 处理结果为：RSa|a QSab|ab|b SabcS|bcS|cS S abcS| 由于Q，R是不可到达的非终结符，其产生式应删除。 最终得文法G：SabcS|bcS|cS SabcS|,2019/6/7,Page 49,第5章 自顶向下语法分析方法,示例说明： 当非终结符顺序为R，Q，S，消除左递归的最终结果为： SabcS|bcS|cS S abcS| 若非终结符顺序为S，Q，R，则消除左递归的最终结果为： SQc|c QRb|b RbcaR|caR|aR R bcaR| 结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。,2019/6/7,第5章 自顶向下语法分析方法,Page 50,不确定的自顶向下分析也称带回溯的自顶向下分析 定义： 不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。,5.4 不确定的自顶向下分析思想,2019/6/7,Page 51,第5章 自顶向下语法分析方法,例1 设有文法 SxAy Aab|a，对输入串w=xay，推导树为,由于A的两条产生式：Aab 和Aa 右部First集交集不为空，从而引起回溯,2019/6/7,Page 52,第5章 自顶向下语法分析方法,例2 文法G：SaAS Sb AbAS A 输入串w=ab，推导树为:,由于A的产生式A 右部能=* ，且 Follow(A) First(bAS) =b ，从而引起回溯,2019/6/7,Page 53,第5章 自顶向下语法分析方法,例3 文法G：SSa Sb 输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,2019/6/7,第5章 自顶向下语法分析方法,Page 54,5.5 确定的自顶向下分析方法,确定的自顶向下分析方法有： 递归子程序法(recursive-descent parser) 预测分析法(predictive parser) 两种方法都要求文法是LL(1)文法。,2019/6/7,第5章 自顶向下语法分析方法,Page 55,实现思想： 对应文法中每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配。 当识别到终结符时，与当前输入符号匹配，并读取下一输入符； 当识别到非终结符时，则调用该非终结符相应的过程。,5.5.1 递归子程序法,2019/6/7,第5章 自顶向下语法分析方法,Page 56,5.5.1 递归子程序法,由于递归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复先进后出栈。 优点： 简单直观、易于构造 缺点： 对文法要求高，必须是LL(1)文法 递归调用多，速度慢，占用空间多,2019/6/7,第5章 自顶向下语法分析方法,Page 57,5.5.2 预测分析方法,一个预测分析器由三个部分组成： 预测分析程序：控制分析过程的进行。 分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。 预测分析表：是一张二维表，元素MA,a的内容是当非终结符A面临输入符号a(终结符或句子括号)时应选取的产生式，当无产生式时，元素内容为转向出错处理。,2019/6/7,Page 58,第5章 自顶向下语法分析方法,构造预测分析表 步骤： (1) 把文法转变为LL(1)文法 (2) 求出每条产生式的SELECT集 (3) 依照SELECT集把产生式填入分析表 对每个终结符或用a表示 若a SELECT(A)，则把A放入MA,a中，把所有无定义的MA,a标上出错标记。,2019/6/7,Page 59,第5章 自顶向下语法分析方法,例 算术表达式文法G EE+TT TT*FF F(E)i,（1）消除G的左递归得到文法 G ETE E+TE TFT T*FT F(E)i,2019/6/7,Page 60,第5章 自顶向下语法分析方法,（2）求出每个产生式的select集,G是LL(1)文法 SELECT(ETE ) = (,i SELECT(E+TE ) = + SELECT(E ) = ),# SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) = +,),# SELECT(F(E) ) = ( SELECT(F i ) = i ,F (E),F i,F,T,T ,T*FT,T ,T,T FT,T FT,T,E,E ,E+TE,E,E,#,）,（,*,+,i,ETE,ETE,（3）依照选择集合把产生式填入分析表,注：表中空白处为出错,2019/6/7,Page 61,第5章 自顶向下语法分析方法,预测分析程序,2019/6/7,Page 62,第5章 自顶向下语法分析方法,输入串i+i*i#的分析过程,7,6,5,4,3,2,1,所用产生式,剩