编译原理 自顶向下语法分析方法

1、第四章第四章 自顶向下语法分析方法自顶向下语法分析方法学习目标学习目标: :掌握：掌握：LL(1)LL(1)文法的判别，预测分析法，文法的判别，预测分析法，递归子程序的构造方法递归子程序的构造方法理解：理解：LLLL（1 1）文法文法了解：不确定的自顶向下分析了解：不确定的自顶向下分析语法分析的作用是识别由词法分析给出的单词序列语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子是否是给定文法的正确句子语法分析语法分析自顶向下分析自顶向下分析自底向上分析自底向上分析确定的确定的不确定的不确定的算法优先分析（第算法优先分析（第六六章）章）LR分析（第五章）分析（第五章）自顶向下基

2、本思想自顶向下基本思想:从文法的开始符出发企图推导出与输入的单词串完从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子全相匹配的句子.分类分类:回顾回顾自上而下的分析方法自上而下的分析方法q定义定义: 从文法的开始符号出发，反复使用文法的从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。产生式，寻找与输入符号串匹配的推导。q语法树的构造：语法树的构造： 将文法的开始符号作为语法树的根，向下将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。号串正好是输入符号串。q自上而下分析的主要问题自

3、上而下分析的主要问题 选定产生式选定产生式例例 文法文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子ScAdab=cabdS =cAd回顾回顾自上而下的分析方法自上而下的分析方法ScA da成功成功不成功不成功=cadS =cAd4.1确定的自顶向下分析思想确定的自顶向下分析思想4.2LL(1)文法的判别文法的判别4.3某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换4.4不确定的自顶向下分析思想不确定的自顶向下分析思想4.5确定的自顶向下分析方法确定的自顶向下分析方法本章内容本章内容4.1 确定的自顶向下分析思想

4、确定的自顶向下分析思想1 确定分析的条件确定分析的条件2 开始符号集开始符号集FIRST()的定义的定义3 后跟符号集后跟符号集FOLLOW(A)的定义的定义4 选择集合选择集合SELECT(A)的定义的定义5 LL(1)文法的定义文法的定义1. 确定分析的条件确定分析的条件 从文法的开始符出发，如能根据当前从文法的开始符出发，如能根据当前的输入符号（单词符号）的输入符号（单词符号）唯一地唯一地确定选用确定选用哪个产生式进行推导，则分析是确定的。哪个产生式进行推导，则分析是确定的。例例1 设有文法设有文法G1S:SpA|qBAcAd|aBdB|b若输入串若输入串W=pccadd。自顶向下的推导

5、过程为自顶向下的推导过程为:SSApcAdcAda=pA =pcAd =pccAdd =pccaddG1S有如下特点：有如下特点： (1) 每个产生式的右部由终结符开头每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同一非终结符的不同产生式的右部由不同的终结符开头。同的终结符开头。对于这种文法，在推导过程可以根据当前的对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。即分析过程是确定的。例例2：设有文法设有文法G2S为为:SAp|BqAa|cABb|dBpAScAcAa=ccapS=c

6、Ap =ccAp=Ap该例说明，当该例说明，当(1)产生式右部以终结符或非终结符开头（无空产产生式右部以终结符或非终结符开头（无空产生式）；生式）；(2)同一非终结符的不同产生式的右部由不同的符同一非终结符的不同产生式的右部由不同的符号开头。号开头。若输入串若输入串W=ccap,自顶向下的推导过程为：自顶向下的推导过程为：对于这种文法，在推导过程选用哪个产生式不直对于这种文法，在推导过程选用哪个产生式不直观，关键是判断观，关键是判断产生式右部推出的开始符号产生式右部推出的开始符号（集）（集），分析过程可能是确定的，分析过程可能是确定的例例3：设有文法设有文法G3SSaA|dAbAS| 若输入串

7、若输入串W=abd，自顶向下的推导过程为：自顶向下的推导过程为：AaSbSA d=abd S=abAS =abS文法的特点文法的特点包含空产生式包含空产生式=aA对于空产生式左部的非终结符对于空产生式左部的非终结符，关键是判断关键是判断该该非终结符的后跟符号（集）非终结符的后跟符号（集），分析过程可，分析过程可能是确定的。能是确定的。要进行确定的自顶向下的分析，文法要满要进行确定的自顶向下的分析，文法要满足一定的限制足一定的限制即文法是即文法是LL(1)文法文法先研究三个定义先研究三个定义开始符号集开始符号集FIRST后跟符号集后跟符号集FOLLOW选择集合选择集合SELECT2. 开始符号集

8、开始符号集FIRST( )的定义的定义定义定义:设设G=(VN, VT, P, S)是上下文无关文法，是上下文无关文法， (VN , (VN VT)* )FIRST( ) = a | a VT 且且* a. （若若* 则规定则规定 FIRST( )）直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推推导出的所有的终结符开头和可能的导出的所有的终结符开头和可能的组成。组成。 例文法例文法G2S: SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d结论一结

9、论一 针对无空产生式的文法针对无空产生式的文法G，同一非终结符的任两，同一非终结符的任两个产生式的右部串的个产生式的右部串的First集无交集，即可进行确定的集无交集，即可进行确定的自顶向下分析。自顶向下分析。3. 后跟符号集后跟符号集FOLLOW(A)的定义的定义定义定义 设设G=(VT, VN, P, S)是上下文无关文法，是上下文无关文法， Bx xAy y (A,B VN x,yx,y (VN VT)* )FOLLOW(A)=a|S=*Aa，a VT，若有若有S=* A，则规定则规定 # FOLLOW(A)（注：（注： # 输入串输入串#，#做为输入串的结束符）做为输入串的结束符）直观

10、上说直观上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那后的那些终结符（包括些终结符（包括#）组成。）组成。例 文法G3S: SaA|d AbAS|由由 S=* S 得得 # FOLLOW(S) 由由S=aA=abAS=abbASS =abbASaA 得得 a FOLLOW(S) =abbASd 得得 d FOLLOW(S) FOLLOW(S)=#,a,d 由由S=* aA 得得 # FOLLOW(A) 由由S=* abAS =* abAaA 得得 a FOLLOW(A) =* abAd 得得 d FOLLOW(A) FOLLOW(A)=#,a,dFOLLO

11、W(A)FOLLOW(S)解释解释当当A面对应输入符面对应输入符a，在自顶向下的分析中应选择这在自顶向下的分析中应选择这样的产生式样的产生式A i( i可导出空串可导出空串)进行推导：进行推导：若若a First( i),则则 A i 可可选选因因 i 可能导出空串，可能导出空串，A自动获得匹配，输入符自动获得匹配，输入符a有可能与有可能与A 后的一个符号匹配，故当后的一个符号匹配，故当 a Follow(A) 时，产生式时，产生式A i 亦可亦可选选结论一结论一 针对无空产生式的文法针对无空产生式的文法G，同一非终结符的任两个，同一非终结符的任两个产生式的右部串的产生式的右部串的First集

12、无交集，即可进行确定的集无交集，即可进行确定的自顶向下分析。自顶向下分析。结论二结论二例 文法G3S: SaA|d AbAS|SaA =Sd =AbAS =A =First(aA) = a First(d) = d First(bAS) = b First() + Follow(A) = + #,a,d = , # , a , d = # , a , d 回顾回顾开始符号集开始符号集FIRST( )的定义的定义定义定义:设设G=(VN, VT, P, S)是上下文无关文法，是上下文无关文法，A (AVN , (VN VT)* )FIRST( ) = a | a VT 且且* a. （若若 *,

13、 则规定则规定FIRST( )）直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推推导出的所有的终结符开头和可能的导出的所有的终结符开头和可能的组成。组成。 回顾回顾后跟符号集后跟符号集FOLLOW(A)的定义的定义定义定义 设设G=(VT, VN, P, S)是上下文无关文法，是上下文无关文法， Bx xAy y (A,B VN x,yx,y (VN VT)* )FOLLOW(A)=a|S=*Aa，a VT，若有若有S=* A，则规定则规定 # FOLLOW(A)（注：（注： # 输入串输入串#，#做为输入串的结束符）做为输入串的结束符）直观上说直观上说,非终结符非终

14、结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那后的那些终结符（包括些终结符（包括#）组成。）组成。4. 选择集合选择集合SELECT(A )的定义的定义定义定义对给定的上下文无关文法的产生式对给定的上下文无关文法的产生式 A (AVN， V*)若若 *,则则SELECT(A )=FIRST( )若若 =*, 则则SELECT(A )=(FIRST( )-)FOLLOW(A)解释解释 A的产生式的产生式A 1 | 2 | 3 | (A面对应输入符面对应输入符a)在自顶向下的分析中：在自顶向下的分析中：对于对于A i且且 i *, 若若a First( i ), 则则A i可可

15、选选对于对于A j且且 j =*, 若若a (First( j)-)Follow(A),则则A j可可选选 例例 G3S: SaA Sd AbAS ASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A) =(FIRST()-)+ FOLLOW(A)=#,a,d若若 *,则则SELECT(A )=FIRST( )若若 =*, 则则SELECT(A )=(FIRST( )-)FOLLOW(A)结论三结论三同一非终结符的不同产生式同一非终结符的不同产生式A与与A，若若SELECT(A)SELECT

16、(A)=，则一定可则一定可以进行确定的自顶向下分析以进行确定的自顶向下分析5. LL(1)文法的定义文法的定义定义定义 : 上下文无关文法为上下文无关文法为LL(1)文法的充分必要条件是，对文法的充分必要条件是，对每个非终结符每个非终结符A的两个不同产生式的两个不同产生式A与与A，满满足足SELECT(A)SELECT(A)=LL(1)文法的含义是：文法的含义是：第一个第一个L从左到右扫描输入串从左到右扫描输入串第二个第二个L分析过程用最左推导分析过程用最左推导(1)表明只需向前看表明只需向前看 1 个输入符号便可以决定选个输入符号便可以决定选哪个产生式进行推导（类似地，哪个产生式进行推导（类

17、似地，LL(k) 文法则需要文法则需要向前看向前看 k 个输入符号才可以确定选用哪个产生式）个输入符号才可以确定选用哪个产生式）例例 有文法有文法GS为：为：SaAS SbAbAASELECT(SaAS)= aSELECT(Sb)= bSELECT(AbA)= bSELECT(A)= a,b由于由于SELECT(AbA)SELECT(A)=b，所以所以文法文法GS不是不是LL(1)文法，当文法，当A遇输入符遇输入符b时，不能确时，不能确定选定选AbA还是还是A去推导。去推导。4.2 LL(1)文法的判别文法的判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为

18、五步：分为五步： 1. 求能推出求能推出的非终结符集的非终结符集 2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集 3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4. 计算每个产生式计算每个产生式A的的SELECT(A)集集 5. 按按LL(1)文法的定义判别文法的定义判别1. 求出能推出求出能推出的非终结符集的非终结符集算法描述算法描述:用用T表示能推出表示能推出的非终结符集的非终结符集令令T= Aj | (Aj) 产生式集产生式集对于产生式对于产生式ApA1.An 若若A1.An T，则则 T = T Ap 重复重复，直至，直至T 收敛（不再变化）为止

19、收敛（不再变化）为止例例GS：SAB|bCAb|BaD|CAD|b DaS|cA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集T T能推出能推出的非终结符集的非终结符集T为为A,B,S2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集对每个对每个a VT ：First(a)= a 对每个对每个A VN ：若若 A * 则则 当前当前First(A)= 否则否则 当前当前First(A)= 对每个产生式对每个产生式 AX1XjXn ：First(A)=First(A) SectionFirst(X1XjXn) S

20、ectionFirst(X1XjXn) = (First(X1) -) (First(X2)-) (First(Xj) -) First(Xj+1) Xj+1是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号首先对首先对文法符号文法符号X (X VT VN)，求求FIRST(X) :对每个产生式对每个产生式 AX1XjXn 做：做：First(A)=First(A) SectionFirst(X1XjXn )其中其中 SectionFirst(X1XjXn) = (First(X1) -) (First(X2)-) (First(Xj) -) First(Xj+1) Xj+1

21、是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号 若若X1 * 则则SectionFirst(X1XjXn)=First(X1) 若若X1Xn全可推出全可推出 则则SectionFirst(X1Xn)= (First(X1) -)(FIRST(Xn)-)重复重复3直到每个符号的直到每个符号的FIRST集合都不再增大为止集合都不再增大为止例例GS: SAB|bC Ab| BaD| CAD|b DaS|cbaa cb a c a b b aFirst集集(3)baa cb a b bFirst集集(2)ba First集集(1)ABCDabSabFirst集集(0)已求出能推出

22、已求出能推出的非终结符集的非终结符集T为为A,B,Sbbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）ccccbaa cb a c a b b aFirst集集(3)baa cb a b bFirst集集(2)ba First集集(1)ABCDabSabFirst集集(0)bbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）cccc结论：文法符号的结论：文法符号的First集合如下集合如下:First(S)=a,b, First(A)=b, First(B)

23、=a, First(C)=a,b,c First(D)=a,c First(a)=a First(b)=b First(c)=c 利用求出利用求出每个文法符号每个文法符号的的FIRST集求集求符号串符号串的的FIRST集集设右部串设右部串=X1X2Xn1. 当当X1* ，则，则FIRST()=FIRST(X1)2. 若对任何若对任何j (1jn）都有都有FIRST(Xj) ， Xj+1为为X1X2Xn中第一个推不出中第一个推不出的符号的符号，则，则 FIRST()= (FIRST(X1) - ) (FIRST(Xj) - ) FIRST(Xj+1) 3. 若对所有若对所有i (1in)，都有都

24、有FIRST(Xi)，则则 FIRST()=FIRST(X1)FIRST(Xn) FIRST(AB)= FIRST(A)FIRST(B)=a,b, FIRST(bC)= FIRST(b)=b FIRST()= FIRST( b )= b FIRST(AD)= (FIRST(A)-)FIRST(D) =b,a,c FIRST(aS)= FIRST(a)=a例例GS SAB|bC Ab| BaD| CAD|b DaS|c已求出非终结符的已求出非终结符的First集合如下集合如下:First(S)=a,b, First(A)=b, First(B)=a, First(C)=a,b,cFirst(D)

25、=a,c 产生式右部产生式右部符号串符号串的开始符集合为的开始符集合为:SABSbCAAbCADDaS要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步： 1. 求能推出求能推出的非终结符集的非终结符集T 2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集 3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4. 计算每个产生式计算每个产生式A的的SELECT(A)集集 5. 按按LL(1)文法的定义判别文法的定义判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步： 1

26、. 求能推出求能推出的非终结符集的非终结符集T 2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集 3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4. 计算每个产生式计算每个产生式A的的SELECT(A)集集 5. 按按LL(1)文法的定义判别文法的定义判别3计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集1.对所有对所有A VN ，令令Follow(A)= (对开始符对开始符S，令令Follow(S)= # )因为因为S=*S，显然，显然#FOLLOW(S)2. 对每条产生式对每条产生式BxAy，考察产生式右部的每一非终考察产生式右部的每一非终

27、结符结符A， x,y V*，若若y *, 则则Follow(A)=Follow(A) First(y) 否则否则 Follow(A)=Follow(A) (First(y)-) Follow(B)3. 重复重复2，直至对所有，直至对所有A VN，Follow(A)收敛为止收敛为止若若aFOLLOW(B) ,则表明则表明S=*Ba， 由于由于BxAy，且且y=*,则有则有 S=*Ba=xAya=xAa，即即S=*xAa, 所以所以aFOLLOW(A)例例GS：1SAB2SbC3Ab4A5BaD6B7CAD8Cb9DaS10Dc已求出已求出 非终结符的非终结符的First集合如下集合如下:Firs

28、t(S)=a,b, First(A)=b, First(B)=a, First(C)=a,b,cFirst(D)=a,c #D #C #Ba #A # # #a # c # # #SFollow集集(2)Follow集集(1)Follow集集(0)c敛敛敛敛敛敛敛敛敛敛结论：结论：Follow(S)=# Follow(A)=a, c , # Follow(B)=# Follow(C)=# Follow(D)=#4计算每个产生式计算每个产生式A的的SELECT(A)集集按定义计算按定义计算SELECT(A)：若右部串若右部串 *，则则SELECT(A )=FIRST()若右部串若右部串 =*，则

29、则SELECT(A )=(FIRST()-)FOLLOW(A)SELECT(SAB) SELECT(SbC)SELECT(A)SELECT(Ab)SELECT(BaD)SELECT(B)SELECT(CAD)SELECT(Cb)SELECT(DaS)SELECT(Dc)例例GS：SAB|bC Ab| BaD| CAD|b DaS|c=*否？否？Follow集集S是是#A是是 a, c, # B是是 #C否否#D否否#SELECT(SAB) =(FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC) =FIRST(bC) =bSELECT(A) =(FIRST()-）FOLL

30、OW(A)=a,c,#SELECT(Ab) =FIRST(b) =bSELECT(BaD) =FIRST(aD) =aSELECT(B) =(FIRST()-）FOLLOW(B)=#SELECT(CAD) =FIRST(AD) =b,a,cSELECT(Cb) =FIRST(b) =bSELECT(DaS) =FIRST(aS) =aSELECT(Dc) =FIRST(c) =cFIRST(AB)= a,b,FIRST(bC)= bFIRST()= FIRST(b)= bFIRST(aD)= aFIRST(AD)=b,a,cFIRST(aS)= a5. 按按LL(1)文法的定义判别文法的定义判

31、别产生式的产生式的select集如下集如下:SELECT(SAB)= b,a,# SELECT(SbC)=bSELECT(A)= a,c,# SELECT(Ab)= bSELECT(B)= # SELECT(BaD)=aSELECT(CAD)= b,a,c SELECT(Cb) =bSELECT(DaS)= a SELECT(Dc)= c 由于由于SELECT(SAB)SELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b所以文法所以文法GS不是不是LL(1)文法文法对每个非终结符对每个非终结符A的任两个产生式的任两个产生式A与与A，满足满足SELECT(A)SELECT(

32、A)=要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步： 1. 求能推出求能推出的非终结符集的非终结符集T 2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集 3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4. 计算每个产生式计算每个产生式A的的SELECT(A)集集 5. 按按LL(1)文法的定义判别文法的定义判别gogo由每个产生式的由每个产生式的select集构造集构造LL(1)分析表分析表 例例GS： SAB|bC Ab| BaD| CAD|b DaS|c 试判断该文法是否为试判断该文法是否为LL(1)

33、文法文法?backbackA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集T T能推出能推出的非终结符集的非终结符集T为为A,B,S1. 求能推出求能推出的非终结符集的非终结符集Tbackback2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集FIRST(AB)=FIRST(A)FIRST(B)=a,b, FIRST(bC)= bFIRST()= FIRST(b)= bFIRST(AD)=(FIRST(A)-)FIRST(D) =b,a,cFIRST(aS)= aFIRST(aD)= abackbackbaa

34、 cb a c a b b aFirst集集(3)baa cb a b bFirst集集(2)ba First集集(1)ABCDabSabFirst集集(0)bbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）cccc3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集backback #D #C #Ba #A # # #a # c # # #SFollow集集(2)Follow集集(1)Follow集集(0)c敛敛敛敛敛敛敛敛敛敛4. 计算每个产生式计算每个产生式A 的的SELECT(A )集集backback

35、SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC) =bSELECT(A)=(FIRST()-）FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b) =bSELECT(BaD)=FIRST(aD) =aSELECT(B)=(FIRST()-）FOLLOW(B)=#SELECT(CAD)=FIRST(AD) =(FIRST(A)- )FIRST (A)=b,a,cSELECT(Cb)=FIRST(b) =bSELECT(DaS)=FIRST(aS) =aSELECT(Dc)=FIRST(c) =cSELECT(

36、SAB)= b,a,# SELECT(SbC)=bSELECT(A)= a,c,# SELECT(Ab)= bSELECT(B)= # SELECT(BaD)=aSELECT(CAD)= b,a,c SELECT(Cb) =bSELECT(DaS)= a SELECT(Dc)= c 由每个产生式的由每个产生式的select集构造集构造LL(1)分析表分析表 abc#SABCDSAB SABSABSbCAAAAbBaDBCADCADCbCADDaSDc5. 按按LL(1)文法的定义判别文法的定义判别backback根据根据LL(1)文法的定义判别文法的定义判别,由于由于 SELECT(SAB)S

37、ELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b所以文法所以文法GS不是不是LL(1)文法文法习题习题判别文法判别文法GS是否为是否为LL(1)文法文法SaSb|P PbP PPc|Qc QaQ QaQ|First(2)First(1)PPQQSFirst(0)aFirst(P)(敛敛)b (敛敛)bFirst(Q)(敛敛)a (敛敛) a (敛敛) (1)(2)a b (敛敛)b (敛敛)a b (敛敛)a (敛敛) a (敛敛) a b (敛敛)a b (敛敛)First集集Sa b PbP a b QaQ a习题习题判别文法判别文法GS是否为是否为LL(1)文法文

38、法SaSb|P PbP PPc|Qc QaQ QaQ|(2)FIRST(aSb) = FIRST(a)=a FIRST(P) = bFIRST(bP) = FIRST(b) = bFIRST(Pc) = FIRST(P) = bFIRST(Qc) = FIRST(Q) = aFIRST(aQ) = FIRST(a) = aFIRST(aQ) = FIRST(a) = aFIRST() = First集集Sa b PbP a b QaQ aFollow(2)Follow(1)PPQQS#Follow(0)# b (收敛收敛)# b c# b cc (收敛收敛) c(收敛收敛)(收敛收敛)(收敛收

39、敛)习题习题判别文法判别文法GS是否为是否为LL(1)文法文法SaSb|P PbP PPc|Qc QaQ QaQ|(3)Follow集集S# b P# b cP # b cQcQ cFirst集集Sa b PbP a b QaQ a SELECT(SaSb)= a SELECT(SP)=b SELECT(PbP )= b SELECT(PPc)= b SELECT(PQc)= a SELECT(QaQ)=a SELECT(QaQ)= a SELECT(Q)= c 构造构造LL(1)分析表分析表根据根据LL(1)定义判断定义判断, 文法文法GS是是LL(1)文法文法FIRST(aSb) = FI

40、RST(a)=a FIRST(P) = bFIRST(bP) = FIRST(b) = bFIRST(Pc) = FIRST(P) = bFIRST(Qc) = FIRST(Q) = aFIRST(aQ) = FIRST(a) = aFIRST(aQ) = FIRST(a) = aFIRST() = Follow集集S# b P# b cP# b cQcQc(4)(5)abc#SSaSbSPPPbP PPQcPPcQQaQQQaQQLL(1)分析表分析表4.3 非非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换非非LL(1)文法文法含有含有左公共因子左公共因子的文法的文法若文法中

41、含有形如：若文法中含有形如：A|r 的产生式，称文法的产生式，称文法含有左公共因子。含有左公共因子。显然显然,SELECT(A)SELECT(A r),文法文法不是不是LL(1)文法文法stmt if expr then stmt | if expr then stmt else stmt | other 句型句型 if e1 then if e2 then s1 else s2推导一推导一stmt if e1 then stmt if e1 then if e2 then s1 else s2悬空悬空 else 问题问题推导二推导二stmt if e1 then stmt else s2 i

42、f e1 then if e2 then s1 else s2stmt if expr then stmt | if expr then stmt else stmt | other stmt matched _stmt | unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt含有含有左递归左递归的文法的文法文法中只要含有下列形式的产

43、生式文法中只要含有下列形式的产生式,则称文法含有则称文法含有左递归：左递归：a)AAb)AB BA在在a)中含有左递归的产生式，称为中含有左递归的产生式，称为直接左递归直接左递归在在b)中虽然没有含左递归的产生式，中虽然没有含左递归的产生式，但但A=B=A 即即A=+ A,称为称为间接左递归间接左递归以直接左递归为例，若有如下产生式以直接左递归为例，若有如下产生式AA |A 其中其中 和和 为任意语法符号串。为任意语法符号串。不难证明有下面关系式：不难证明有下面关系式：Select( AA ) ) First( A ) First( )Select( A ) First( )故故AA 和和A

44、的的Select集集相交相交，不是不是LL(1)文法文法对非对非LL(1)文法进行等价变换文法进行等价变换提取左公共因子提取左公共因子消除左递归消除左递归注意：变换后的文法不一定是注意：变换后的文法不一定是LL(1)文法，文文法，文法不含左递归和左公共因子只是法不含左递归和左公共因子只是LL(1)文法的文法的必要条件必要条件1 提取左公共因子提取左公共因子将产生式将产生式A|r 等价变换为等价变换为:A(| r)，(| r)引入一新非终结符引入一新非终结符A表示表示, 即得即得 A A A| r一般形式：若一般形式：若A1|2|n|提取左公共因子提取左公共因子, 即得即得 A A | A 1|

45、2|n若在若在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.例例文法文法G1：SaSb|aS| 提取左因子得提取左因子得: SaS(b|)| 引进新非终结符引进新非终结符S, 得得:SaSS|S b|2. 消除左递归消除左递归1)消除直接左递归消除直接左递归文法文法G: SSa|b可改写成可改写成 S bSS aS|一般情形一般情形:含直接左递归的文法含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：消除左递归后改写成： A1A|2A|nA A1 A|2 A|m A| 2)消除间接左递归消除间接左递归 将间接左递归变成直接左递归，再消除将间接左递归变成直接

46、左递归，再消除算法步骤：算法步骤：1.把文法的所有非终结符按任一顺序排列，把文法的所有非终结符按任一顺序排列，如：如：A1，A2，Ai， ，Ak， ，An2.从从A1开始，按以下顺序处理开始，按以下顺序处理Ak消除左部为消除左部为Ak的产生式的直接左递归的产生式的直接左递归若左部为若左部为Ak的产生式的右部为非终结符的产生式的右部为非终结符Ai(i* ，且，且Follow(A) First(bAS) =b ，从而引起回溯，从而引起回溯例例3文法文法G：SSaSb输入串输入串w=baa，推导树为推导树为:SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯由于文法

47、含有左递归而引起回溯4.5 确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：LL(1)预测分析器预测分析器 (predictive parser)LL(1)递归子程序分析器递归子程序分析器(recursive-descent parser)两种方法都要求文法是两种方法都要求文法是LL(1)文法文法4.5 确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：LL(1)预测分析器预测分析器 (predictive parser)LL(1)递归子程序分析器递归子程序分析器(recursive-descent

48、parser)两种方法都要求文法是两种方法都要求文法是LL(1)文法文法4.5.1 LL(1)预测分析器预测分析器一个预测分析器由三个部分组成：一个预测分析器由三个部分组成：预测分析程序：预测分析程序：控制分析过程的进行。控制分析过程的进行。分析栈：分析栈：存放从文法开始符号出发的自顶向下推存放从文法开始符号出发的自顶向下推导过程中导过程中等待匹配等待匹配的文法符号。开始时放入的文法符号。开始时放入#和文法开始符，结束时栈应是空的。和文法开始符，结束时栈应是空的。预测分析表：预测分析表：是一个二维表，元素是一个二维表，元素MA,a的内容的内容是当非终结符是当非终结符A面临输入符号面临输入符号a

49、（终结符或）时终结符或）时应选取的应选取的产生式产生式；当无产生式时，元素；当无产生式时，元素MA,a为为出错处理出错处理(error)。1.构造预测分析表构造预测分析表步骤：步骤：(1) 把文法转变为把文法转变为LL(1)文法文法(2) 求出每条产生式的求出每条产生式的SELECT集集(3) 依照依照SELECT集把产生式填入分析表集把产生式填入分析表l横坐标横坐标终结符与终结符与l纵坐标纵坐标非终结符非终结符l交点交点MA,an(A )放入放入MA,a若若a SELECT(A )n无产生式的无产生式的MA,a标记出错标记出错例例 算术表达式文法算术表达式文法G EE+TTTT*FFF(E)

50、i（1）消除）消除G的左递归得到文法的左递归得到文法 GETE E+TE TFT T*FTF(E)i（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)(E)F i iFT T T* FTFTT TTFTFTT FTFTTE E E+TEEE#）（*+iETEETE（3

51、 3）依照选择集合把产生式填入分析表）依照选择集合把产生式填入分析表注：表中空白处为出错注：表中空白处为出错2.预测分析程序预测分析程序上托栈顶符放入上托栈顶符放入XNYYNNNN YY Y把把#和和文法开始符文法开始符S压入分析栈；压入分析栈； 当前输入符送当前输入符送a把产生式右部把产生式右部反序反序进栈进栈XVT ?X=# ? X=a ?X=a?读下一输入读下一输入符到符到aMX,a有产生式？有产生式？出错出错结束结束出错出错预测分析程序工作过程预测分析程序工作过程3. 输入串输入串i+i*i#的分析过程的分析过程i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT

52、 T* FTFTT T FF i iF (E)(E)+匹配匹配+i*i#ET+7E+TE+i*i#E6T +i*i#ET5i匹配匹配i+i*i#ETi4Fii+i*i#ETF3TFTi+i*i#ET2ETEi+i*i#E1所用产生式所用产生式剩余输入串剩余输入串分析栈分析栈步骤步骤TFTi*i#ET8Fii#ETF13i匹配匹配i#ETi14T #ET15E #E16接受接受#17*匹配匹配*i#ETF*12T * *FTFT*i#ET11i匹配匹配i*i#ETi10Fii*i#ETF9i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT T* FTFTT T FF i

53、iF (E)(E)4.5.2 递归子程序法递归子程序法(第三次实验第三次实验)1 实现思想实现思想 对文法中的每个非终结符编写一个递归过程，对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多个识别由该非终结符推出的串。当非终结符有多个产生式时，按当前输入符属于哪个产生式的产生式时，按当前输入符属于哪个产生式的SELECT集可唯一确定选择哪个产生式进行匹配。集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一当识别到终结符时，与当前输入符号匹配，并读取下一输入符；输入符；当识别到非终结符时，则调用该非终结符相应的过程。当识别到非终结符

54、时，则调用该非终结符相应的过程。定义定义当一个文法满足当一个文法满足LL(1)条件时，就为它构造条件时，就为它构造一个不带回溯的自顶向下的分析程序一个不带回溯的自顶向下的分析程序u这个分析程序由一组这个分析程序由一组递归过程递归过程组成组成u每个过程对应文法的一个非终结符每个过程对应文法的一个非终结符 这样的一个分析程序称为这样的一个分析程序称为递归下降分析器递归下降分析器2 构造文法构造文法G的递归下降分析器的递归下降分析器组成：组成： 递归下降分析器由一个主程序递归下降分析器由一个主程序main和每个非终结符和每个非终结符对应的一个递归过程组成。对应的一个递归过程组成。用到的一些子过程：用

55、到的一些子过程：过程过程getnext负责读入下一个负责读入下一个TOKEN字字过程过程error( )负责报告语法错误负责报告语法错误约定：约定：变量变量TOKEN存放已读入的存放已读入的TOKEN字字过程进入时变量过程进入时变量TOKEN存放了一个待匹配的存放了一个待匹配的TOKEN字字退出过程时，变量退出过程时，变量TOKEN中仍存放着一个待匹配的中仍存放着一个待匹配的TOKEN字。字。 非终结符相应的分析子程序的构造方法非终结符相应的分析子程序的构造方法 对于每个非终结符对于每个非终结符U，编写一个相应的子程序编写一个相应的子程序P(U)对于产生式对于产生式Ux1 | x2 |xn (

56、 x1,.,xn ) 关于关于U的子程序的子程序P(U)按如下方法构造：按如下方法构造： if (TOKEN first(x1) ) p(x1); else if (TOKEN first(x2) ) p(x2); else if (TOKEN first(xn) ) p(xn); else ERROR();ERROR();3)如果如果U还有空产生式还有空产生式U ,则算法中的语句：则算法中的语句：if (TOKEN first(xn) ) p(xn) else ERROR();ERROR(); 改写为改写为if (TOKEN first(xn) ) p(xn); else if (TOKEN

57、 follow(U) ERROR ();ERROR ();4)对于符号串对于符号串x=y1y2yn p(x)的含义为：的含义为：main( )p(y1);p(y2);p(yn); 如如yiVN，则则P(yi)就代表调用就代表调用yi的子程序；的子程序； 如如yiVT，则则P(yi)为如下述代码为如下述代码if (TOKEN=yi ) getnext(TOKEN); else ERROR();ERROR();例例 算术表达式文法算术表达式文法G EE+TTTT*FFF(E)i1 1）消除左递归得）消除左递归得 G: G: ETE ETE E+TEE+TE TFT TFT TT* *FTFTF(E

58、)iF(E)i2）求出）求出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)文法文法1 判断是否可以应用递归子程序法判断是否可以应用递归子程序法(1)ch TOKEN; main( ) /* 主程序主程序 */ getnext (TOKEN); E (TOKEN); /* 转匹配转匹配ETE */ if (TOKEN != # ) ERROR();ERROR(); 构造文法构造文法G：ETE E