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

1、第四章第四章 语法分析语法分析-自顶向下分析自顶向下分析学习目标学习目标: :掌握：掌握：LL(1)LL(1)文法的判别，预测分析文法的判别，预测分析法，递归子程序的构造方法法，递归子程序的构造方法理解：理解：LLLL（1 1）文法文法了解：不确定的自顶向下分析了解：不确定的自顶向下分析语法分析的任务与分类语法分析的任务与分类l 语法分析的任务：语法分析的任务：对任一给定对任一给定 w VT*，判断，判断 w L（G）l 语法分析器：是一个程序，它按照语法分析器：是一个程序，它按照P，做识别，做识别w的工的工作作词法分析器词法分析器语法分析器语法分析器编译程序后续部分编译程序后续部分符号表符号

2、表源程序源程序单词符号单词符号取下一个取下一个单词符号单词符号语法分析语法分析图图4.1 4.1 语法分析器在编译程序中的地位语法分析器在编译程序中的地位q语法分析的作用是识别由词法分析给出的单词序语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子列是否是给定文法的正确句子q分类分类:语法分析语法分析自顶向下分析自顶向下分析自底向上分析自底向上分析确定的确定的不确定的不确定的算符优先分析算符优先分析LR分析分析q自顶向下的基本思想自顶向下的基本思想:q从文法的开始符出发企图推导出与输入的单从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子词串完全相匹配的句子.4.2确

3、定的自顶向下分析思想确定的自顶向下分析思想4.3LL(1)文法的判别文法的判别4.4某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换4.5不确定的自顶向下分析思想不确定的自顶向下分析思想4.1自上而下分析面临的问题自上而下分析面临的问题4.6确定的自顶向下分析方法确定的自顶向下分析方法4.1、自上而下分析面临的问题、自上而下分析面临的问题1、主旨：从文法开始符号出发，自上而下的为输入、主旨：从文法开始符号出发，自上而下的为输入串建立一棵语法树串建立一棵语法树l 例例4.1 文法文法G1： S cAd A ab|a 输入串：输入串：w=cad，为它建立语法树，为它建立语法

4、树ScAdabaS cAdA abA a输入串输入串w :文法文法G:IP分析过程：分析过程：1）w输入串；输入串； IP c S扩充；扩充； c a d2）=c A d； 与与IPc匹配；匹配；3）IP aA扩展，第一式扩展，第一式ab, IP a与与ab匹配；匹配；IP d,但但d与与b不匹配不匹配;4）报告失败，撤销）报告失败，撤销A的子的子树，回到树，回到A;指针回退到指针回退到IPa;A还有替换式未试过，而又还有替换式未试过，而又可能匹配；可能匹配；语法树的形成语法树的形成2 2、困难和问题、困难和问题l文法的左递归文法的左递归l回溯回溯l用替换符的顺序会影响所接受的语言用替换符的顺

5、序会影响所接受的语言 如：如：A ab|a 改为改为 A a|ab l难以报告出错的确切位置难以报告出错的确切位置l穷举试探法穷举试探法低效的分析方法低效的分析方法3 3、自上而下分析的问题解决、自上而下分析的问题解决消除文法的左递归消除文法的左递归克服回溯问题克服回溯问题4.2 确定的自顶向下分析思想确定的自顶向下分析思想1 确定分析的条件确定分析的条件2 开始符号集开始符号集FIRST()的定义的定义3 后跟符号集后跟符号集FOLLOW(A)的定义的定义4 选择集合选择集合SELECT(A)的定义的定义5 LL(1)文法的定义文法的定义确定分析的条件确定分析的条件 从文法的开始符出发，如能

6、根据当从文法的开始符出发，如能根据当前的输入符号（单词符号）前的输入符号（单词符号）唯一地唯一地确定确定选用哪个产生式进行推导，则分析是确选用哪个产生式进行推导，则分析是确定的。定的。例例1 设有文法设有文法G1S:SpA|qBAcAd|aBdB|b若输入串若输入串W=pccadd。自顶向下的推导过程为自顶向下的推导过程为:SSApcAdcAda=pA =pcAd=pccAdd=pccaddG1S有如下特点：有如下特点： (1) 每个产生式的右部由终结符开头每个产生式的右部由终结符开头; (2) 同一非终结符的不同产生式的右部由不同一非终结符的不同产生式的右部由不同的终结符开头。同的终结符开头

7、。对于这种文法，在推导过程可以根据当前的对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。即分析过程是确定的。例例2：设有文法：设有文法G2S为为:SAp|BqAa|cABb|dBpAScAcAa=ccapS=cAp =ccAp=Ap该例说明，当该例说明，当(1) 产生式右部以终结符或非终结符开头（无空产生式右部以终结符或非终结符开头（无空产生式）；产生式）；(2) 同一非终结符的不同产生式的右部由不同的同一非终结符的不同产生式的右部由不同的符号开头。符号开头。对于这种文法，在推导过程选用哪个产生式不对于这种文

8、法，在推导过程选用哪个产生式不直观，关键是判断直观，关键是判断产生式右部推出的开始符号产生式右部推出的开始符号（集），（集），分析过程可能是确定分析过程可能是确定若输入串若输入串W=ccap,自顶向下的推导过程为：自顶向下的推导过程为：例例3：设有文法：设有文法G3SSaA|dAbAS| 若输入串若输入串W=abd，自顶向下的推导过程为：自顶向下的推导过程为：AaSbSAd=abd S=abAS =abS文法的特点是文法的特点是:包含空产生式包含空产生式对于空产生式左部的非终结符对于空产生式左部的非终结符，关键是判断关键是判断该该非终结符的后跟符号（集），非终结符的后跟符号（集），分析过程可分

9、析过程可能是确定的。能是确定的。=aAn要进行确定的自顶向下的分析，文要进行确定的自顶向下的分析，文法要满足一定的限制法要满足一定的限制即文法是即文法是LL(1)文法。文法。n先研究三个定义先研究三个定义1.开始符号集开始符号集FIRST2.后跟符号集后跟符号集FOLLOW3.选择集合选择集合SELECT1 . 开始符号集开始符号集FIRST()的定义的定义n定义定义:设设G=(VN, VT, P, S)是上下文无关文法，是上下文无关文法，(VN VT)* FIRST( ) = a VT | * a. 若若* 则规定则规定 FIRST( )直观上说文法符号串直观上说文法符号串 的开始符号集是由

10、的开始符号集是由 推导出的开头的终结符（包括推导出的开头的终结符（包括）组成。组成。 n 例文法例文法G2S: SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d 由于由于同一非终结符的两个产生式的右部推导出来同一非终结符的两个产生式的右部推导出来的开始符号集不相交的开始符号集不相交，因此可根据当前输入符属于，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析进行推导，可以进行确

11、定的自顶向下分析2. 后跟符号集后跟符号集FOLLOW(A)的定义的定义n 定义定义 n设设G=(VT, VN, P, S)是上下文无关文法，是上下文无关文法，AVN ，FOLLOW(A)=a|S=*Aa，a VT，若有若有S=* A，则规定则规定 # FOLLOW(A)（注：（注： # 输入串输入串#，#做为输入串的结束符）做为输入串的结束符） 直观上说直观上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那些终结符（包括后的那些终结符（包括#）组成。）组成。n 例例 文法文法G3S:SaA|d AbAS|由由 S=* S 得得 # FOLLOW(S) 由由S

12、=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)=，所所以可进行确定的自顶向下分析

13、。以可进行确定的自顶向下分析。3. 选择集合选择集合SELECT(A)的定义的定义n 定义定义n对给定的上下文无关文法的产生式对给定的上下文无关文法的产生式A，AVN，V*，若若*,则则SELECT(A)=FIRST()若若=*, 则则SELECT(A)=(FIRST()-)FOLLOW(A)n 解释解释n当当A面对应输入符面对应输入符a，在自顶向下的分析中应选在自顶向下的分析中应选择这样的产生式择这样的产生式A 进行推导：进行推导：First( )中包含中包含a；n此外若此外若 可能导出空串，可能导出空串，A自动获得匹配，输入自动获得匹配，输入符符a有可能与有可能与A后的一个符号匹配，所以当

14、后的一个符号匹配，所以当a应属于应属于Follow(A)时，选择产生式时，选择产生式A 也是可以的也是可以的。 n 直观上说某产生式直观上说某产生式A的选择集合是指遇到哪些输的选择集合是指遇到哪些输入符号（包括入符号（包括#）时选用该产生式向下推导。）时选用该产生式向下推导。l例例 G3S: SaA Sd AbAS ASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=FOLLOW(A)=#,a,d若若*,则则SELECT(A)=FIRST()若若=*, 则则SELECT(A)=(FIRS

15、T()-)FOLLOW(A)说明：说明：同一非终结符的不同产生式同一非终结符的不同产生式A与与A，若若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析则一定可以进行确定的自顶向下分析4 LL(1)文法的定义文法的定义n 定义定义 : n一个上下文无关文法是一个上下文无关文法是LL(1)文法的充分必要条文法的充分必要条件是，对每个非终结符件是，对每个非终结符A的两个不同产生式的两个不同产生式A与与A，满足满足SELECT(A)SELECT(A)=。 n LL(1)文法的含义是：文法的含义是：第一个第一个L表示从左到右扫描输入串表示从左到右扫描输入串第二个第二个L表示分析过

16、程用最左推导表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地进行推导，类似地LL(k)文法需要向前看文法需要向前看K个符号才个符号才可以确定选用哪个产生式。可以确定选用哪个产生式。n 例例 有文法有文法GS为：为：SaAS SbAbAASELECT(SaAS)= aSELECT(Sb)= bSELECT(AbA)= bSELECT(A)=Follow(A)= a,b由于由于SELECT(AbA)SELECT(A)=b，所以文法所以文法GS不是不是LL(1)文法，当文法，当A遇输入符遇输入符b时，不时，不能确定选能确

17、定选AbA还是还是A去推导。去推导。4.3 LL(1)文法的判别文法的判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步： 1. 求能推出求能推出的非终结符集的非终结符集 2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集 3. 计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4. 计算每个产生式计算每个产生式A的的SELECT(A)集集 5. 按按LL(1)文法的定义判别文法的定义判别1. 求出能推出求出能推出的非终结符集的非终结符集 算法算法:用用S表示能推出表示能推出的非终结符集的非终结符集第一步令第一步令S=

18、 Aj | Aj 产生式集产生式集对每个产生式对每个产生式p: ApX1.Xn，若若X1.Xn S，则则 S:= S Ap 重复第二步的循环重复第二步的循环，直至直至S 收敛（不再收敛（不再变化）为止。变化）为止。例例GS：SAB|bCAb|BaD|CAD|b DaS|cA,B,S第一次第一次A,B初值初值A,B,S收敛收敛第二次第二次非终结符集非终结符集S能推出能推出的非终结符集为的非终结符集为A,B,S2. 计算每个产生式右部计算每个产生式右部的的FIRST()集集q首先对每一首先对每一文法符号文法符号X (X VT VN)，求求FIRST(X)的算法的算法:q对每个对每个a VT ：Fi

19、rst(a)= a q对每个对每个A VN ：若若 A * 则则 First(A):= q否则否则 First(A):= q对每个产生式对每个产生式 AX1XjXn 做：做：qFirst(A)=First(A) SectionFirst(X1XjXn)其中其中 SectionFirst(X1XjXn) = (First(X1) -) (First(X2)-) (First(Xj) -) First(Xj+1) Xj+1是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号 若若X1 * 则则SectionFirst(X1XjXn)=First(X1) 若若X1Xn全可推出全可推出

20、则则SectionFirst(X1Xn)=FIRST(X1)FIRST(Xn) l 重复重复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)已求出能推出已求出能推出的非终结符集的非终结符集为为A,B,Sbbaba caa cq利用求出利用求出每个文法符号每个文法符号的的FIRST集求集求符号串符号串的的FIRST集集设设=X1X2Xnl

21、当当X1不能不能=* ，则，则FIRST()=FIRST(X1)l 若对任何若对任何j (1jn）都有都有FIRST(Xj), 则则FIRST()=(FIRST(X1) - ) (FIRST(Xj) - ) FIRST(Xj+1) l 若对所有若对所有i (1in)，都有都有FIRST(Xi)， 则则 FIRST()=FIRST(X1)FIRST(Xn) 例例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

22、)=a,c 产生式右部产生式右部符号串符号串的开始符集合为的开始符集合为:SAB FIRST(AB)=FIRST(A)FIRST(B)=a,b,SbC FIRST(bC)= bAFIRST()= AbFIRST(b)= bCADFIRST(AD)=(FIRST(A)-)FIRST(D) =b,a,cDaSFIRST(aS)= a3计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集1.对所有对所有A VN令令Follow(A)= ;对开始符对开始符S，令令Follow(S)=# 因为因为S=*S，显然，显然#FOLLOW(S)2. 对每条产生式对每条产生式AxBy，考察产生式右部的每一

23、非终考察产生式右部的每一非终结符结符B， x,y V*，如果如果y不能推出不能推出Follow(B)=Follow(B) First(y) 否则否则 Follow(B)=Follow(B) (First(y)-) Follow(A)3. 重复重复2，直至对所有，直至对所有A VN，Follow(A)收敛为止。收敛为止。若若aFOLLOW(A) ,则表明则表明S=*Aa， 由于由于AxBy，且且y=*,则有则有 S=*Aa=xBya=xBa，即即S=*xBa, 所以所以aFOLLOW(B)例例GS：1SAB2SbC3Ab4A5BaD6B7CAD8Cb9DaS10Dc已求出已求出 非终结符的非终结

24、符的First集合如下集合如下:First(S)=a,b, First(A)=b, First(B)=a, First(C)=a,b,cFirst(D)=a,c #D#C#Ba #A#a # cSFollow集集(2)Follow集集(1)Follow集集(0)c4计算每个产生式计算每个产生式A的的SELECT(A)集集按定义计算按定义计算SELECT(A)：若若*，则则SELECT(A)=FIRST()若若=*，则则SELECT(A)=(FIRST()-)FOLLOW(A)例例GS：SAB|bC Ab| BaD| CAD|b DaS|c是否是否=* First集集Follow集集S是是a,

25、b,#A 是是 b,a, c, # B 是是 a,#C 否否a,b,c#D 否否a,c#部分产生式的部分产生式的select集合集合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(CAD)=FIRST(AD) =b,a,c5. 按按LL(1)文法的定义判别文法的定义判别产生式的产生式的select集如下集如下:SELECT(SAB)= b,a,

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

27、式，的产生式，称文法含有左公共因子。称文法含有左公共因子。显然显然,SELECT(A)SELECT(A r),文法文法不是不是LL(1)文法文法含有含有左递归左递归的文法的文法文法中只要含有下列形式的产生式（含有文法中只要含有下列形式的产生式（含有a a或含有或含有b b或二者皆有）则称文法含有左递归：或二者皆有）则称文法含有左递归：nA AA AnABABBABA在在a)a)中含有左递归的产生式，称为中含有左递归的产生式，称为直接左递直接左递归归；在在b)b)中虽然没有含左递归的产生式，中虽然没有含左递归的产生式，但但A A=B B=AA 即即A A=+ + A A,称为称为间接左间接左递归

28、递归以直接左递归为例，若有如下产生式以直接左递归为例，若有如下产生式AA | A 其中其中 和和 为任意语法符号串。为任意语法符号串。不难证明有下面关系式：不难证明有下面关系式：Select( AA ) ) First( A ) First( )Select( A ) First( )故故AA 和和A 的的Select集集相交，不是相交，不是LL(1)文法。文法。n对非对非LL(1)文法进行等价变换文法进行等价变换提取左公共因子提取左公共因子消除左递归消除左递归注意：变换后的文法不一定是注意：变换后的文法不一定是LL(1)文文法，文法不含左递归和左公共因子只是法，文法不含左递归和左公共因子只是

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

30、G：AA1|A2|Am|1|2|n消除左递归后改写成：消除左递归后改写成： A1A|2A|nA A1 A|2 A|m A| 消除直接左递归消除直接左递归文法文法G:SSa|b可改写成可改写成 SbS S aS|n消除间接左递归消除间接左递归将将间接左递归变成直接左递归间接左递归变成直接左递归，再消除，再消除n算法步骤：算法步骤：n把文法的所有非终结符按任一顺序排列，把文法的所有非终结符按任一顺序排列，n如：如：A1，A2，Ann从从A1开始，按以下顺序处理开始，按以下顺序处理Ai。首先，消除左部为首先，消除左部为Ai的产生式的直接左递归的产生式的直接左递归然后，若左部为然后，若左部为Ai的产生

31、式的右部为非终结的产生式的右部为非终结符符Aj(j* ，且，且Follow(A) First(bAS) =b ，从而引起，从而引起回溯回溯例例3 文法文法G：SSa Sb输入串输入串w=baa，推导树为推导树为:SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯由于文法含有左递归而引起回溯4.6 确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：递归子程序法递归子程序法(recursive-descent parser)预测分析法预测分析法(predictive parser)两种方法都要求文法是两种方法都要求文法

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

33、。相应的过程。n例例 算术表达式文法算术表达式文法G EE+TT TT*FFF(E)i1）消除左递归得消除左递归得 G: ETE E+TE TFT T*FT F(E)iG是是LL(1)文法文法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 1 判断是否可以应用递归子程序法判断是否可以应用递归子程序法2 构造文法构造文法G的

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

35、责读入下一个负责读入下一个TOKEN字字过程过程ERROR负责报告语法错误负责报告语法错误约定：约定：变量变量TOKEN存放已读入的存放已读入的TOKEN字字过程进入时变量过程进入时变量TOKEN存放了一个待匹配的存放了一个待匹配的TOKEN字字退出过程时，变量退出过程时，变量TOKEN中仍存放着一个待匹中仍存放着一个待匹配的配的TOKEN字。字。 (1) program MAIN; /* 主程序主程序 */ begin GETNEXT (TOKEN); E (TOKEN); /* 转匹配转匹配ETE */ if TOKEN # then ERROR end. 构造文法构造文法G：ETE E+

36、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) /*转匹配转匹配

37、E+TE*/ end else /*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 TO

38、KEN) 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); /* 转匹配转匹配ETE */ if TOK

39、EN=) then GETNEXT (TOKEN) /* 匹配匹配), 读下一读下一TOKEN字字 */ else ERROR end else /* 选择产生式选择产生式Fi */ if TOKEN=i then GETNEXT (TOKEN) else ERROR end; n特点：特点：优点：简单直观、易于构造优点：简单直观、易于构造缺点：缺点：对文法要求高，必须满对文法要求高，必须满足足LL(1)文法；文法；递归调用多，速度慢，占用递归调用多，速度慢，占用空间多空间多实用性：许多高级语言，如实用性：许多高级语言，如Pascal、c等编译系统常常采用此方法。等编译系统常常采用此方法。i1

40、 + i2 * i3 分析过程：分析过程：ETEFTi1PROCEDURE E;BEGIN T;EEND;PROCEDURE T;BEGIN F;TEND;PROCEDURE F;IF SYM=iTHEN ADVANCEELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;PROCEDURE T;IF SYM=*THENBEGIN ADVANCE; F;TEND;else /* T对应的语句对应的语句*/ if TOKEN+ and TOKEN) and TOKEN# then E

41、RROR endi i1 1 + i+ i2 2 * * i i3 3 分析过程：分析过程：ETEFT+ETFT*FTi i1 1i i2 2i i3 3PROCEDURE EPROCEDURE E; ;IF SYM=+THEN IF SYM=+THEN BEGINBEGIN ADVANCE; ADVANCE; T;E T;EEND;END;PROCEDURE TPROCEDURE T; ;IF SYM=IF SYM=* *THENTHENBEGINBEGIN ADVANCE; ADVANCE; F;T F;TEND;END;4.4.2 预测分析方法预测分析方法一个预测分析器由四个部分组成：一

42、个预测分析器由四个部分组成：n预测分析程序：预测分析程序：控制分析过程的进行。控制分析过程的进行。n分析栈：分析栈：存放从文法开始符号出发的自顶向下存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。和文法开始符，结束时栈应是空的。n预测分析表：预测分析表：是一张二维表，元素是一张二维表，元素MA,a的内的内容是当非终结符容是当非终结符A面临输入符号面临输入符号a（终结符或句终结符或句子括号）时应选取的产生式，当无产生式时，子括号）时应选取的产生式，当无产生式时，元素内容为转向出错处理。元素内容为转向

43、出错处理。输出：输出：根据分析表内元素做规定的语义动作根据分析表内元素做规定的语义动作n 构造预测分析表方法构造预测分析表方法1步骤：步骤：(1) 把文法转变为把文法转变为LL(1)文法文法(2) 求出每条产生式的求出每条产生式的SELECT集集(3) 依照依照SELECT集把产生式填入分析表集把产生式填入分析表对每个终结符或对每个终结符或用用a表示表示若若a SELECT(A )，则把则把A 放入放入MA,a中，把所有无定义的中，把所有无定义的MA,a标上标上出错标记。出错标记。预测分析表构造算法预测分析表构造算法2 21.对文法对文法G的每个产生式的每个产生式 执行第二步执行第二步 和第三

44、步；和第三步；2.对每个终结符对每个终结符a FIRST( )，把，把 加加 至至A,a中，中，3.若若 FIRST( )，则对任何则对任何b FOLLOW(A) 把把 加至加至A,b中，中，4.把所有无定义的把所有无定义的A,a标上标上“出错标志出错标志”。可以证明，一个文法可以证明，一个文法G的预测分析表不含多重的预测分析表不含多重入口，当且仅当该文法是入口，当且仅当该文法是LL(1)的的例例 算术表达式文法算术表达式文法G EE+TTTT*FFF(E)i（1）消除）消除G的左递归得到文法的左递归得到文法 GETE E+TE TFT T*FTF(E)i（2）求出每个产生式的求出每个产生式的

45、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 iFT T T* FTT TT FTT FTTE E E+TEEE#）（*+iETEETE（3）依照选择集合把产生式填入分析表）依照选择集合把产生式填入分析表注：表中空白处为出错注：表中空白处为出错2 预测分析程序预测分析程序上托栈顶符放入上托栈顶符放

46、入XNYYNNNN YY Y把把#和和文法开始符文法开始符压入分析栈；压入分析栈； 当前输入符送当前输入符送a把产生式右部把产生式右部反序反序进栈进栈XVT ?X=# ? X=a ?X=a?读下一输入读下一输入符到符到aMX,a有产有产生式？生式？出错出错结束结束出错出错预测分析程序工作过程预测分析程序工作过程分析算法分析算法 BEGIN 首先把首先把#然后把文法开始符号推入栈；把第然后把文法开始符号推入栈；把第一个输入符号读进一个输入符号读进a; FLAG：=TRUE；WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中； IF X Vt THEN

47、IF X=a THEN 把下一把下一个输入符号读进个输入符号读进a ELSE ERRORELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,a=X X1X2.XK THEN 把把XK，X K-1,.,X1一一推进栈一一推进栈 ELSEERROR END OF WHILE;STOP/*分析成功，过程完毕分析成功，过程完毕*END3 输入串输入串i+i*i#的分析过程的分析过程i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT T* FTFTT T FF i iF (E)(E)+匹配匹配+i*i#ET+

48、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 iF (E)(E)本章小结本章小结q两种自顶向下分析方法：两种自顶向下分析方法

49、：递归子程序法递归子程序法预测分析法预测分析法q一种文法：一种文法：LL(1)文法文法判别方法判别方法非非LL(1)到到LL(1)的转换的转换第第4章习题章习题第第1题：题：对文法对文法GS Sa|(T)TT,S|S 给出给出(a,(a,a)和和(a,a),(a),a)的最左推导。的最左推导。对文法对文法G，进行改写，然后对每个非终结符写出不带回溯，进行改写，然后对每个非终结符写出不带回溯 的递归子程序。的递归子程序。 (3) 经改写后的文法是否是经改写后的文法是否是LL(1)的的?给出它的预测分析表。给出它的预测分析表。(1) (4) 给出输入串给出输入串(a,a)#的分析过程，并说明该串是

50、否为的分析过程，并说明该串是否为G的的句子句子S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) S(T) (T,S) (T,S) (S,S) (T),S) (T,S),S)(T,S,S ),S) (S,S,S ),S) (T),S,S ),S) (T,S),S,S ),S) (S,S),S,S ),S) (a,S),S,S ),S) (a,a),S,S ),S) (a,a), , S ),S) (a,a), , (T) ),S) (a,a), , (S) ),S) (a,a), , (a) ),S) (a,a),

51、 , (a) ),a) (1)GS Sa|(T)TT,S|S 消除左递消除左递归得等价文法归得等价文法GGS Sa|(T)TST T,ST| GS Sa|(T)TST T,ST| Select(Sa)=aSelect(S )=Select(S (T)= ( Select(T ST)=First(ST)=a , ( Select(T, ST)=,Select(T )=Fllow(T)=)该文法是该文法是LL(1)文法。文法。TT,ST T STTS#）,(aS SaSelect(Sa)=aSelect(S )=Select(S (T)= ( Select(T ST)=First(ST)=a ,

52、( Select(T, ST)=,Select( T )=Fllow(T)=)S (T)T STT STT(2)递归子程序的写法：递归子程序的写法：若关于一个非终结符的产生式只有一条，直接按产生式右部若关于一个非终结符的产生式只有一条，直接按产生式右部写程序，右部是终结符就进行匹配，是非终结符就调用相应的写程序，右部是终结符就进行匹配，是非终结符就调用相应的子程序，如子程序，如T ST若关于一个非终结符的产生式不只一条，按若关于一个非终结符的产生式不只一条，按select集合写成集合写成if条件语句，如：条件语句，如： S a， S， S (T) SELECT(S a ) = a SELECT

53、(S) = SELECT(S (T) = ( 若产生式右部为空串若产生式右部为空串可以不生成任何语句，或者按可以不生成任何语句，或者按select集合，生成一条判断语句集合，生成一条判断语句如：如：SELECT(T ) = ) 生成：生成：if Token ) then Error;procedure S； /* S a | | (T)对应的程序对应的程序 */begin If TOKEN=a then GETNEXT(TOKEN) else if TOKEN= then GETNEXT(TOKEN) else if TOKEN=( then begin GETNEXT(TOKEN); T;

54、if TOKEN=) then GETNEXT(TOKEN) else ERROR; end else ERROR; end; If Token ) then ERROR;（错误）错误）没有被读掉，变量）没有被读掉，变量Token=)，S后续的过后续的过程处理的第一个字为程处理的第一个字为），导致出错，导致出错procedure T ； /*T ,ST|对应的程序对应的程序*/begin if TOKEN=, then begin GETNEXT(TOKEN); （容易出错）容易出错） S; T; end else if TOKEN ) then ERROR; end;可以不写，但写成可以不写

55、，但写成else ERROR;是错误的是错误的也可以写成：也可以写成：else if TOKEN ) then return else ERROR;但是不能写成但是不能写成 else if TOKEN ) then GetNext(Token) else ERROR;（3）经改写后的文法是否是）经改写后的文法是否是LL(1)的？给出它的预测分的？给出它的预测分析表。析表。已求得产生式的已求得产生式的SELECT集集SELECT(S a ) = a SELECT(S) = SELECT(S (T) = ( SELECT(T ST ) = a, ,( SELECT(T ,ST ) = , SELECT(T ) = ) 是是LL(1)文法，构造预测分析表如下：文法，构造预测分析表如下：a(),#SSaS S(T)TTSTTSTTSTTT T ,ST （4）给出输入串）给出输入串(a,a)#的分析过程，并说明该串是否为的分析过程，并说明该串是否为G的句子。的句子。a(),#SSa