编译原理(清华)第五章自顶向下语法分析方法.ppt

1、第五章 自顶向下语法分析方法,学习目标: 掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法 理解：LL（1）文法 了解：不确定的自顶向下分析,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子 分类:,自顶向下的基本思想: 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.,5.1确定的自顶向下分析思想 5.2LL(1)文法的判别 5.3某些非LL(1)文法到LL(1)文法的等价变换 5.4不确定的自顶向下分析思想 5.5确定的自顶向下分析方法,5.1 确定的自顶向下分析思想,1 确定分析的条件 2 开始符号集FIRST()的定义 3 后跟符号集FOLL

2、OW(A)的定义 4 选择集合SELECT(A)的定义 5 LL(1)文法的定义,1 确定分析的条件,从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。,例1 设有文法G1S: SpA|qB AcAd|a BdB|b 若输入串W=pccadd。自顶向下的推导过程为:,S,S,=pA,=pcAd,=pccAdd,=pccadd,G1S有如下特点： (1) 每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同的终结符开头。 对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。,

3、例2：设有文法G2S为: SAp|Bq Aa|cA Bb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,该例说明，当 (1) 产生式右部以终结符或非终结符开头（无空产生式）； (2) 同一非终结符的不同产生式的右部由不同的符号开头。 对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定,若输入串W=ccap,自顶向下的推导过程为：,例3：设有文法G3S SaA|d AbAS| 若输入串W=abd，自顶向下的推导过程为：,S,=abd,S,=abAS,=abS,文法的特点是:包含空产生式 对于空产生式左部的非终结符，关键是判断该非终

4、结符的后跟符号（集），分析过程可能是确定的。,=aA,要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法。 先研究三个定义 开始符号集FIRST 后跟符号集FOLLOW 选择集合SELECT,2 开始符号集FIRST()的定义,定义:设G=(VN, VT, P, S)是上下文无关文法， (VNVT)* FIRST() = a VT | * a. 若* 则规定 FIRST() 直观上说文法符号串 的开始符号集是由推导出的开头的终结符（包括）组成。,例文法G2S:,SAp SBq Aa AcA Bb BdB,FIRST(Ap)=a,c FIRST(Bq)=b,d FIRST(a

5、)=a FIRST(cA)=c FIRST(b)=b FIRST(dB)=d,由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析,3 后跟符号集FOLLOW(A)的定义,定义 设G=(VT, VN, P, S)是上下文无关文法，AVN ， FOLLOW(A)=a|S=*Aa，a VT， 若有S=* A，则规定 # FOLLOW(A) （注： # 输入串#，#做为输入串的结束符） 直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,例 文法G3S: Sa

6、A|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,说明： 对于非终结符A的两个产生式 AbAS 和 A， 当输入符号FIRST(bAS)=b时，选AbAS推导， 当输入符号FOLLOW(A)=#,a,d 时，选A推导。 由于FIRST(bAS)FOLLOW(A)=，所以可进行确定的自顶向下分析。,4

7、选择集合SELECT(A)的定义,定义 对给定的上下文无关文法的产生式A，AVN，V*， 若*,则SELECT(A)=FIRST() 若=*, 则SELECT(A) =(FIRST()-)FOLLOW(A),解释 当A面对应输入符a，在自顶向下的分析中应选择这样的产生式A进行推导：First()中包含a； 此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A也是可以的。 直观上说某产生式A的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。,例 G3S: SaA Sd AbAS A,SELECT(SaA)=FIRS

8、T(aA)=a SELECT(Sd)=FIRST(d)=d SELECT(AbAS)=FIRST(bAS)=b SELECT(A)=FOLLOW(A)=#,a,d,若*,则SELECT(A)=FIRST() 若=*, 则SELECT(A) =(FIRST()-)FOLLOW(A),说明： 同一非终结符的不同产生式A与A，若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析 、不能同时=*,5 LL(1)文法的定义,定义 : 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符A的两个不同产生式A与A，满足SELECT(A)SELECT(A)=。 LL(1)

9、文法的含义是： 第一个L表示从左到右扫描输入串 第二个L表示分析过程用最左推导 1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。,例 有文法GS为： SaAS Sb AbA A,SELECT(SaAS)= a SELECT(Sb)= b SELECT(AbA)= b SELECT(A)=Follow(A)= a,b,由于SELECT(AbA)SELECT(A)=b， 所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。,5.2 LL(1)文法的判别,要判别一个上下文无关文法是否是LL(1)文法

10、分为五步： 1. 求能推出的非终结符集 2.计算每个产生式右部的FIRST()集 3.计算每个非终结符A的FOLLOW(A)集 4.计算每个产生式A的SELECT(A)集 5.按LL(1)文法的定义判别,1. 求出能推出的非终结符集,算法: 用S表示能推出的非终结符集 第一步令S= Aj | Aj 产生式集 对每个产生式p: ApX1.Xn，若X1.XnS，则 S:= S Ap 重复第二步的循环，直至S 收敛（不再变化）为止。,例GS：SAB|bC Ab| BaD| CAD|b DaS|c,非终结符集S,能推出的非终结符集为A,B,S,2.计算每个产生式右部的FIRST()集,首先对每一文法符

11、号X (XVT VN)，求FIRST(X)的算法: 对每个a VT ：First(a)= a 对每个A VN ：若 A * 则 First(A):= 否则 First(A):= 对每个产生式 AX1XjXn 做： First(A)=First(A) SectionFirst(X1XjXn),其中 SectionFirst(X1XjXn) = (First(X1) -) (First(X2)-) (First(Xj) -) First(Xj+1) Xj+1是产生式右部中第一个不能推出的符号 若X1 * 则SectionFirst(X1XjXn)=First(X1) 若X1Xn全可推出 则Sect

12、ionFirst(X1Xn)=FIRST(X1)FIRST(Xn) 重复3直到每个符号的FIRST集合都不再增大为止。,例GS：SAB|bC Ab| BaD| CAD|b DaS|c,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集为A,B,S,b,b,a,b,a c,a,a c,利用求出每个文法符号的FIRST集求符号串的FIRST集,设=X1X2Xn 当X1不能=* ，则FIRST()=FIRST(X1) 若对任何j (1jn）都有FIRST(Xj), 则FIRST() =(FIRST(X1) - ) (F

13、IRST(Xj) - ) FIRST(Xj+1) 若对所有i (1in)，都有FIRST(Xi)， 则 FIRST()=FIRST(X1)FIRST(Xn),例 GSSAB|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,产生式右部符号串的开始符集合为: SABFIRST(AB)=FIRST(A)FIRST(B)=a,b, SbCFIRST(bC)= b AFIRST()= AbFIRST(b)= b CADFIRST(AD)

14、=(FIRST(A)-)FIRST(D) =b,a,c DaSFIRST(aS)= a,3计算每个非终结符A的FOLLOW(A)集,1.对所有AVN令Follow(A)= ;对开始符S，令Follow(S)=# ,因为S=*S，显然#FOLLOW(S),2. 对每条产生式AB，考察产生式右部的每一非终结符B， , V*，如果不能推出 Follow(B)=Follow(B)First() 否则 Follow(B)=Follow(B)(First()-) Follow(A),3. 重复2，直至对所有AVN，Follow(A)收敛为止。,若aFOLLOW(A) ,则表明S=*Aa， 由于AB，且=*

15、,则有 S=*Aa=Ba=xBa， 即S=*Ba, 所以aFOLLOW(B),例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,4计算每个产生式A的SELECT(A)集,按定义计算SELECT(A)： 若*，则 SELECT(A)=FIRST() 若=*，则 SELEC

16、T(A)=(FIRST()-)FOLLOW(A),例GS： SAB|bC Ab| BaD| CAD|b DaS|c,部分产生式的select集合 SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=b,a,# SELECT(SbC)=FIRST(bC) =b SELECT(A)=(FIRST()-）FOLLOW(A)=a,c,# SELECT(Ab)=FIRST(b) =b SELECT(BaD)=FIRST(aD) =a SELECT(CAD)=FIRST(AD) =b,a,c,5.按LL(1)文法的定义判别,产生式的select集如下: SELECT(SAB)= b,a,#

17、SELECT(SbC)=b SELECT(A)= a,c,#SELECT(Ab)= b SELECT(B)= #SELECT(BaD)=a SELECT(CAD)= b,a,cSELECT(Cb) =b SELECT(DaS)= aSELECT(Dc)= c,由于SELECT(SAB)SELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b 所以文法GS不是LL(1)文法,5.3 某些非LL(1)文法到LL(1)文法的等价变换,非LL(1)文法 含有左公共因子的文法 若文法中含有形如：A|r 的产生式，称文法含有左公共因子。 显然, SELECT(A)SELECT(A r),

18、文法不是LL(1)文法,含有左递归的文法 文法中只要含有下列形式的产生式（含有a或含有b或二者皆有）则称文法含有左递归： AA ABBA 在a)中含有左递归的产生式，称为直接左递归； 在b)中虽然没有含左递归的产生式， 但A=B=A 即A=+ A,称为间接左递归,以直接左递归为例，若有如下产生式 AA |A 其中和为任意语法符号串。 不难证明有下面关系式： Select( AA ) First( A )First( ) Select( A ) First( ) 故AA 和A 的Select集相交，不是LL(1)文法。,对非LL(1)文法进行等价变换 提取左公共因子 消除左递归 注意：变换后的文

19、法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。,1 提取左公共因子,将产生式A|r 等价变换为: A(|r)， 将括号内用一新引入的非终结符A表示,得 AA，A|r 一般形式：若A1|2|n, 提取左公共因子后变为AA， A 1|2|n 若在i中仍含有左公共因子,可再次提取.,例文法G1： SaSb|aS| 提左因子得:SaS(b|)| 引进新的非终结符得: SaSS| S b|,2.消除左递归,消除直接左递归 文法G:SSa|b 可改写成 SbS S aS| 一般情形: 含直接左递归的文法G： AA1|A2|Am|1|2|n 消除左递归后改写成： A1A|

20、2A|nA A1 A|2 A|m A|,消除间接左递归 将间接左递归变成直接左递归，再消除 算法步骤： 把文法的所有非终结符按任一顺序排列， 如：A1，A2，An 从A1开始，按以下顺序处理Ai。 首先，消除左部为Ai的产生式的直接左递归 然后，若左部为Ai的产生式的右部为非终结符Aj(ji)开头，即Ai Aj，则用左部为Aj的所有产生式的右部分别代替Ai Aj 中的Aj 最后，得到的左部为Ai的产生式若有直接左递归，则消除之 去掉无用产生式。,例 文法G：(1)SQc|c(2)QRb|b (3)RSa|a,将非终结符排序 ：R，Q，S 对R：产生式(3)不含直接左递归，所以保持不变 对Q：把

21、(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|,示例说明： 当非终结符顺序为R，Q，S，消除左递归的最终结果为： SabcS|bcS|cS S abcS| 若非终结符顺序为S，Q，R，则消除左递归的最终结果为： SQc|c QRb|b RbcaR|caR|aR

22、 R bcaR| 结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。,5.4 不确定的自顶向下分析思想,不确定的自顶向下分析也称带回溯的自顶向下分析 定义： 不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。,例1 设有文法 SxAy Aab|a，对输入串w=xay，推导树为,由于A的两条产生式：Aab 和Aa 右部First集交集不为空，从而引起回溯,例2文法G：SaASSbAbASA

23、 输入串w=ab，推导树为:,由于A的产生式A 右部能=* ，且 Follow(A) First(bAS) =b ，从而引起回溯,例3文法G：SSaSb 输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,5.5 确定的自顶向下分析方法,确定的自顶向下分析方法有： 递归子程序法(recursive-descent parser) 预测分析法(predictive parser) 两种方法都要求文法是LL(1)文法。,5.5.1 递归子程序法,实现思想： 对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集

24、可唯一确定选择哪个产生式进行匹配。 当识别到终结符时，与当前输入符号匹配，并读取下一输入符； 当识别到非终结符时，则调用该非终结符相应的过程。,例 算术表达式文法G EE+TT TT*FF F(E)i,1）消除左递归得 G: ETE E+TE TFT T*FT F(E)i,2）求出G的选择集合 SELECT(ETE ) = (,i SELECT(E+TE ) = + SELECT(E ) = ),# SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) = +,),# SELECT(F(E) ) = ( SELECT(F i ) = i ,G是LL(1

25、)文法,1 判断是否可以应用递归子程序法,2 构造文法G的递归下降分析器 定义： 当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。,组成： 递归下降分析器由一个主程序MAIN和每个非终结符对应的一个递归过程组成。 用到的一些子过程： 过程GETNEXT负责读入下一个TOKEN字 过程ERROR负责报告语法错误 约定： 变量TOKEN存放已读入的TOKEN字 过程进入时变量TOKEN存放了一个待匹配的TOKEN字 退出过程时，变量TOKEN中仍存放着一个待匹配的TOK

26、EN字。,非终结符相应的分析子程序的构造方法 对于每个非终结符U，编写一个相应的子程序P(U); 对于产生式Ux1 | x2 |xn，x1,.xn都 关于U的子程序P(U)按如下方法构造： if TOKEN in first(x1) then p(x1) else if TOKEN in first(x2) then p(x2) else . if TOKEN in first(xn) then p(xn) else ERROR,如果U还有空产生式U ,则算法中的语句： if TOKEN in first(xn) then p(xn) else ERROR 改写为 if TOKEN in fi

27、rst(xn) then p(xn) else if TOKEN not in follow(U) then ERROR 对于符号串x=y1y2yn；p(x)的含义为： begin p(y1);p(y2);p(yn) end 如果yiVN，则P(yi)就代表调用yi的子程序；yiVT，则P(yi)为形如下述语句的一段程序 if TOKEN=yi then GETNEXT(TOKEN) else ERROR,(1) program MAIN; /* 主程序 */ begin GETNEXT (TOKEN); E (TOKEN); /* 转匹配ETE */ if TOKEN # then ERRO

28、R end.,构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(2) procedure E (TOKEN); /*匹配ETE*/ begin T (TOKEN); /*转匹配TFT*/ E (TOKEN) /*转匹配E+TE*/ end;,(3) procedure E (TOKEN); /*匹配E+TE*/ begin if TOKEN=+ then /*选择产生式E+TE*/ begin GETNEXT (TOKEN); /*匹配+,读下一个TOKEN字*/ T (TOKEN); /*转匹配TFT*/ E (TOKEN) /*转匹配E+TE*/ end else

29、 /*E对应的语句*/ if TOKEN) and TOKEN# then ERROR end;,(5) procedure T (TOKEN); /* 匹配T*FT */ begin if TOKEN = * then /* 选择产生式T*FT */ begin GETNEXT (TOKEN); /* 匹配*，读下一TOKEN字 */ F (TOKEN); /* 转匹配F(E)i */ T (TOKEN) /* 转匹配T*FT */ end else /* T对应的语句*/ if TOKEN+ and TOKEN) and TOKEN# then ERROR end;,(4) procedure T (TOKEN); /*匹配TFT */ begin F (TOKEN); /*转匹配F(E)i*/ T (TOKEN) /*转匹配T*FT*/ end;,(6) procedure F (TOKEN); /* 匹配F(E)i */ begin if TOKEN = ( then /*选择产生式F(E) */ begin GETNEXT (TOKEN); /* 匹配(，读下一TOKEN字 */ E (TOKEN); /* 转