编译原理及其习题解答（武汉大学出版社）课件chap5.ppt

1、第五章 自顶向下语法分析方法,要点： 1.了解下推自动机 2.求解First,Follow,Select及LL(1)文法的判断 3.非LL(1)到LL(1)的等价变换； （消除左递归等） 4.预测分析表的构造和分析过程,编译原理,引言,语法分析是编译的核心部分。 语法分析的作用：识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）。 语法分析的常用方法：自顶向下分析和自底向上分析两大类。 自顶向下分析法是指从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。若能找到“匹配”的产生式且最终推导出的句子与输入串一致，则这个输入串是文法给定的句子，否则不是文法的句子

2、。 注意：文法是指上下文无关文法。,5.1 下推自动机(PDA),下推自动机很象不确定的有穷自动机，但是多了一个下推栈。,语言L(M)= anbn| n=1 不是正则集，不能由有限自动机所识别，因为：任何一个有限自动机要想识别类似这样的语言，必须设法记住读了多少个“a”。而有限自动机的唯一的“存储器”是其状态，因此只能用一个状态来表示 “已经读入k个a”类似这样的信息。如下图：,识别anbn的“无限状态自动机”,下推自动机示意图,不能使用无限状态的自动机，因此引入一个下推栈。栈的操作足够简单，能保存的信息量足够大。,下推自动机M是一个七元组(形式定义),定义 不确定的下推自动机M是一个七元组，

3、 M = ( K, , , q0, Z0, F )，其中 K：有限控制器的状态集合； ：有限的输入字母表； ：有限的下推栈字母表； ：转换函数,从K( )到 K*有限子集的映射； q0：初始状态,q0 K ； Z0：下推栈起始符号，Z0 ； F：终止状态的集合。,下推自动机转换函数示意图,转换函数 ( q, a, Z ) = (p, ) ， 其中q,p K, a , Z , *，表示在状态q，输入字符为a且下推栈的顶符为Z时，进入状态p，下推栈的栈顶符号由字符串代替，同时读头右移一位。,约定：字符串的最左符号放在下推栈的栈顶。当= 时，表示下推栈的栈顶符号出栈。当a= 时，表示不考虑当前的输入

4、字符，但控制器的状态和下推栈可以调整，即 转换。,下推自动机 例1,例1：构造一个PDA M，能够识别语言L(M)= anbn| n=1 。,解答：设PDA M = ( K, , , q0, Z0, F )，其中 K= q0, q1, q2 , = a, b = Z0, a F= q0 定义为：,( q0, a, Z0 ) = (q1, aZ0) ( q1, a, a ) = (q1, aa) ( q1, b, a ) = (q2, ) ( q2, b, a ) = (q2, ) ( q2, , Z0 ) = (q0, ) ,下推自动机 例1 的PDA 状态转换图,例1：构造一个PDA M，能

5、够识别语言L(M)= anbn| n=1 。,( q0, a, Z0 ) = (q1, aZ0) ( q1, a, a ) = (q1, aa) ( q1, b, a ) = (q2, ) ( q2, b, a ) = (q2, ) ( q2, , Z0 ) = (q0, ) ,下推自动机 例1 的PDA 工作过程,例1：构造一个PDA M，能够识别语言L(M)= anbn| n=1 。 当输入字符串为aaabbb时，M的工作过程为：,( q0, aaabbb, Z0 ) ( q1, aabbb, aZ0 ) ( q1, abbb, aaZ0 ) ( q1, bbb, aaaZ0 ) ( q2

6、, bb, aaZ0 ) ( q2, b, aZ0 ) ( q2, , Z0 ) ( q0, , ),下推自动机 例2,例2：构造PDA M，识别语言L(M)=cR|a,b* 。,解题思路： (1)从状态q0接受句子 ，将输入保存到栈中，状态不变，直到看到中心标记c； (2)当到达c时，将状态变为q1，栈不变； (3)将输入与栈顶内容匹配，状态不变，退栈，直至栈空。 状态转换图为：,下推自动机 例2 的DPDA M,例2：构造PDA M，识别语言L(M)=cR|a,b* 。,是一个确定的下推自动机。,下推自动机 例3,例3：构造一个PDA M，识别语言L(M)= wwR| wa,b* 。,是一

7、个不确定的下推自动机。,上下文无关文法与下推自动机,上下文无关文法与下推自动机，是描述上下文无关语言的不同方式。给定一个CFG和由它产生的语言L(G)，必存在一个下推自动机M接受语言L(M)，使得L(M)= L(G)，反之亦然。给定CFG G，构造对应PDA M的过程可描述为：,(1)把文法的开始符号放到栈中。 (2)重复下述步骤： a.当栈顶为非终结符A时，则非确定地选择一个关于A的产生式，并且把栈中的栈顶A替换为该产生式右边的符号串。 b.当栈顶为终结符a时，则读输入中的下一个符号，并把它与a比较：匹配则转向(2)，否则该非确定分支被拒绝。 c.栈为空时，输入带上的符号都已经读入完毕，则接

8、受该串。,5.2 确定的自顶向下分析思想,自顶向下分析法又可分为确定的和不确定的两种。确定的分析方法对文法有一定的限制，但实现方法简单、直观，便于手工构成或自动生成语法分析器；不确定的分析方法是一种穷举的试探方法，是带回溯的分析方法。 确定的自顶向下方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号唯一地确定地选用哪个产生式替换相应的非终结符往下推导，或构造一棵相应的语法树。 以下举例说明确定性。,5.2 例,文法G1S: SpA SqB AcAd Aa 对输入串pccadd进行语法分析。 解：自顶向下的分析过程： S = pA= pcAd= pccAdd = pccadd 相应的语

9、法树为：,例对应的语法树,（不断的寻找“匹配”的产生式，使每一步推导与原输入串都更接近一步。）,例文法特点,文法G1S: SpA SqB AcAd Aa （1）每个产生式的右部由终结符号开始； （2）具有相同左部的产生式，其右部由不同的终结符号开始；,5.2 例2,文法G2S: SAp SBq Aa AcA Bb BdB 对输入串ccap进行自顶向下的语法分析。 解：分析过程 S = Ap= cAp=ccAp= ccap 对应的语法树为：,例 语法树,例文法特点,SAp SBq Aa AcA Bb BdB （1）每个产生式的右部不全由终结符号开始； （2）具有相同左部的产生式，其右部由不同的终

10、结符号或非终结符号开始（要求产生式右部的开始终结符不同，如本例中S产生式的右部Ap与Bq的开始终结符号集合不能相交）； （3）不含产生式A,开始符号集合FIRST的定义,定义5.1 设G=( VN, VT, P, S)是上下文无关文法 假定是文法G的任一符号串或 (VTVN)* FIRST()=a | a，aVT， V* 特别的， ，则规定FIRST() 构造FIRST()的算法如下：,构造FIRST(X)算法,构造文法G的每一个文法符号X，X (VTVN) （1）若X VT ，则FIRST(X)=X; （2）若X VN ，且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式，则

11、把也加入到FIRST(X)中； （3）若有产生式XY 且Y VN ，则把FIRST(Y)中所有非-元素都加到FIRST(X)中； 若有产生式XY1 Y2Yk 其中Y1 Y2Yk VN ，且,构造FIRST(X)算法（续）,若有产生式XY1 Y2Yk ,其中Y1 Y2Yk VN,且对任何j(1 ji-1 )，FIRST(Yj)都含有 （即Y1 Y2Yi-1 ），则把FIRST(Yj)中的所有非 -元素都加到FIRST(X)中， FIRST(Yi)中的所有元素都加到FIRST(X)中； 特别地，若对所有的FIRST(Yi) (1 Yik)均含有 ，即Yi ，则把加入到FIRST(X)中。 反复使用

12、13，直到每个符号的FIRST集合不再增大为止。,构造FIRST()算法,若 (VTVN)*， = X1X2Xn，则 （1）若 = ，则FIRST()= ; （2）若 ，X1不能 ，则FIRST(X1) 加入到FIRST()中； （3）若X1 X2Xi-1 ，则FIRST(Xi)-加入到FIRST() 中； 若X1 X2Xn ，则 FIRST() , 即FIRST() = FIRST(X1) U FIRST(X2) FIRST(Xn),例 求FIRST集,例2文法G2S中，求关于S,A,B的FIRST集。 SAp SBq Aa AcA Bb BdB,解： FIRST(S)=FIRST(Ap)

13、FIRST(Bq)=a,c b,d FIRST(A)=FIRST(a)FIRST(cA)=a,c FIRST(B)=FIRST(b)FIRST(dB)=b,d,练习题,1. 文法GE: ETE1 E1+T E1 | TFT1 T1*F T1 | F(E) | a 求G中的每一个符号的FIRST集合。,解：FIRST(E)=FIRST(T)=FIRST(F)=(, a FIRST(E1)=+, FIRST(T1)=*, ,空产生式引起的问题,文法规则中允许有空产生式的情况，若文法中含有空产生式，会给自顶向下的分析带来一些不同的考虑方面。 例3 文法G3S: SaA Sd AbAS A 对输入串a

14、bd进行分析。 解：S aA abAS abS abd 分析：当面临输入符号d时，d不在FIRST(A)中，但 FIRST(A)，因此对于d的匹配就依赖于在可能推导过程中A后面的符号S。为此，需定义一个文法符号的后跟符号的集合。,FIRST(S)=a,d FIRST(A)=b, ,FOLLOW集合定义,假定S是文法的开始符号，对于任何非终结符A（即A VN） FOLLOW(A)=a | S Aa ，aVT 特别地，若S A，则规定FOLLOW(A)。 FOLLOW(A)就是所有在某个句型中出现，且紧跟在A后的终结符或“”（约定为输入串的结束符或称句子的括号，或用“$”表示）。 FOLLOW集不

15、含元素。,构造FOLLOW(B)的算法,反复使用如下规则，直到每个FOLLOW集不再增大为止： （1）对于文法的开始符号S，置“”于FOLLOW(S)中； （2）若AB是一个产生式，则把FIRST()-(即非空元素)加至FOLLOW(B)中； （3）若AB是一个产生式，或AB是一个产生式而 （即 FIRST()），则把FOLLOW(A)加到FOLLOW(B)中。 原因如下：,证明, 当有形为 ： D 1A1 AB 且 可 ，或者AB 的产生式，其中A,B,D VN，1,1, , (VN VT)* 时，在推导过程中可能出现这样的句型序列： S 1A1 1B1 1B1 由定义可知，FIRST(1)

16、 FOLLOW(A)和FIRST(1) FOLLOW(B)，所以也就有FOLLOW(A) FOLLOW(B),例 求 FOLLOW 集,例2文法G2S中，求关于S,A,B的FOLLOW集。 SAp SBq Aa AcA Bb BdB,解：FOLLOW(S)=# FOLLOW(A)=p FOLLOW(B)=q,练习题,1.文法GE如下，求G中每一非终结符的FOLLOW集。 ET E1 E1+T E1 | TFT1 T1*F T1 | F(E) | a,解： FOLLOW(E)=#,) FOLLOW(E1)=FOLLOW(E) =#,) FOLLOW(T)=FIRST(E1) FOLLOW(E)=

17、+,#,) FOLLOW(T1) =FOLLOW(T)=+,#,) FOLLOW(F)= FIRST(T1) FOLLOW(T) FOLLOW(T1) =*, +,#,),LL(1)文法的含义 LL：指从左(L)到右的左(L)分析器。也可以说，从左到右地扫描输入串并建立它的最左推导。 “1”：表明只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导） 类似的也有LL(k)文法，k的意思就是选择同一个非终结符的不同产生式时，是通过向前（右）看k个符号决定的。LL(1)文法只需向前看一个符号即可选择，例如A | 产生式，那么只要FIRST() FIRST()=就可决定用哪个产生式。,5.2

18、 LL(1)文法的判别,Select集合的定义,给定上下文无关文法的产生式A，AVN, V*： 若 ，则Select(A)=First() 若 ，则Select(A)=(First()-) Follow(A),一个文法G是LL(1)文法，当且仅当对文法中的每个非终结符A的任两个不同的产生式A，A，总满足 SELECT(A) SELECT(A )= 其中、不同时能 ,LL(1) 文法的定义,LL(1) 文法的判别,判别一个文法是否是LL(1)文法，只要判别文法是否满足LL(1)条件即可。 判别文法是否是LL(1)文法，还可以用预测分析表来判别，有关内容在后面介绍。,5.2 LL(1) 文法判别步

19、骤, 求出能推出的非终结符 求FIRST集合； 求FOLLOW集合； 计算SELECT集合。 对同一非终结符的不同产生式求Select交集,文法GS: SAB SbC A Ab B BaD CAD Cb DaS Dc 判断是否是LL(1)文法。,LL(1) 文法判别 之 例,文法GS: SAB SbC A Ab B BaD CAD Cb DaS Dc,例解：（1）求出能推出的非终结符,SAB SbC A Ab B BaD CAD Cb DaS Dc 各非终结符的FIRST集为：,例解：（2）计算FIRST集-1,FIRST(S)=(FIRST(A)-)(FIRST(B)-)b=b,a, ,FI

20、RST(A)=b =b, ,FIRST(B)=a =a, ,FIRST(C)=(FIRST(A)-)FIRST(D) b=b,a,c,FIRST(D)=ac =a, c,SAB SbC A Ab B BaD CAD Cb DaS Dc 每个产生式的右部符号串的开始符号集为：,例解：（2）计算FIRST集-2,FIRST(AB)=a,b, ,FIRST(bC)=b,FIRST()= ,FIRST(b)= b,FIRST(aD)=a,FIRST(AD)=a,b,c,FIRST(aS)=a,FIRST(c)=c,SAB SbC A Ab B BaD CAD Cb DaS Dc 各非终结符的FOLLO

21、W集为：,例解：（3）计算FOLLOW集,FOLLOW(S)=#FOLLOW(D),FOLLOW(A)=(FIRST(B)-)FOLLOW(S)FIRST(D),FOLLOW(B)= FOLLOW(S),FOLLOW(C)= FOLLOW(S),FOLLOW(D)= FOLLOW(B) FOLLOW(C),FOLLOW(S)=# FOLLOW(A)=a,c,# FOLLOW(B)=# FOLLOW(C)=# FOLLOW(D)=#,例解: （4）计算SELECT集,解：SELECT(SAB)=FIRST(AB)-FOLLOW(S)=a,b,# SELECT(SbC)=FIRST(bC)=b S

22、ELECT(A )=FIRST() - FOLLOW(A)=a,c,# SELECT(Ab)=b SELECT(B )=FIRST() - FOLLOW(B)=# SELECT(BaD)= FIRST(aD)=a SELECT(CAD)=FIRST(AD)=b,a,c SELECT(Cb)=FIRST(b)=b SELECT(DaS)=FIRST(aS)=a SELECT(Dc)=c,例解: (5)同一非终结符的不同产生式求Select交集, SELECT(SAB)SELECT(SbC)=b SELECT(A )SELECT(Ab)= SELECT(B ) SELECT(BaD)= SELEC

23、T(CAD) SELECT(Cb)=b SELECT(DaS) SELECT(Dc) = 该文法不是LL(1)文法。,LL(1) 文法判别之例2 课本P124例5.10,文法GE: ET E1 E1+T E1 | TFT1 T1*F T1 | F(E) | a 判断是否是LL(1)文法。,解： SELECT(E1+T E)SELECT(E1)=+,),#= SELECT(T1*FT1)SELECT(T1)=*,+,),#= SELECT(F(E)SELECT(Fa)=(a= 该文法是LL(1)文法,5.3 某些非LL(1)文法到LL(1)文法的等价转换,确定的自顶向下的语法分析要求对给定语言的

24、文法必须是LL(1)，对一个非LL(1)文法是否能变换为等价的LL(1)形式一个如何变换？主要要解决以下问题： 直接或间接的递归：如AA 或 A A 左公共因子:如AB和AC 必须想办法消除以上形式的产生式。原因：,LL(1)文法的分析过程消除了回溯,消除左公共因子的原因： A有n个候选式 A1| 2| |n，由于LL(1)文法对相同左部的产生式其右部的FIRST集必两两不相交，即SELECT(Ai) SELECT(Aj)=。所以当非终结符A执行匹配任务，A所面临的输入符号为a。A能根据不同的a选用相应的候选式i执行匹配（否则报错）。 问题： 解决了以上问题后，是否一定可以变换为LL(1)文法

25、呢？,提取左公共因子,假定关于A的规则是 A1| 2 | n 变换为：A(1| 2 | n) 于是，可把这些规则改写为： AA A1| 2 | n 反复提取左公共因子，就能够把每个非终结符（包括新引进者）的所有候选首字符集合变成两两不相交的。为此付出的代价是：引进新的非终结符和-产生式。,提取左公共因子 之 例和例,例1：文法G1S: ScAd A ab | a 提取左公共因子，将该文法改写为： ScAd A aA A b | 且改写后的文法G1S是LL(1)文法。,例2：文法G2S: (1)SaSb (2)SaS (3)S 对(1)、(2)提取左公共因子后将文法变换为文法G2S： SaSS|

26、 Sb | ,该文法是LL(1)文法吗？,答：不是。,提取左公共因子 之 例,文法G3A: (1)Aad (2)ABc (3)BaA (4)BbB,解：这是一种隐式的左公共因子。 将(3)、(4)代入(2)，就可得 (1)Aad (2)AaAc (3)AbBc (4)BaA (5)BbB 因此，提取左公共因子后的文法G3A为： AaA| bBc Ad| Ac BaA|bB,提取左公共因子 之 课堂练习,文法G4S: SaSd SAc AaS A b,解：这是一种隐式的左公共因子。 （1）将关于A的产生式代入关于S的产生式中： S aSd S aSc | bc AaS A b （2）提取左公共因

27、子 S - aS ( d | c ) （3）删除无用产生式,提取左公共因子 之 例4,文法G5S: SAp| Bq AaAp| d BaBq| e,解：这是一种隐式的左公共因子。 （1）将关于A、B的产生式代入关于S的产生式中： SaApp | aBqq Sdp | eq AaAp | d BaBq | e,提取左公共因子 之 例4（续）,提取左公共因子： SaS| dp | eq SApp | Bqq AaAp | d BaBq | e （2）第二次将关于A、B的产生式代入关于S的产生式中： SaS| dp | eq SaAppp | aBqqq | dpp | eqq AaAp | d B

28、aBq | e 提取左公共因子： SaS| dp | eq SaS | dpp | eqq S Appp | Bqqq AaAp | d BaBq | e（3）,对提取左公共因子的说明,（1）文法中不含左公共因子是LL(1)文法的必要条件； （2）注意隐式左公共因子的提取； （3）删除新文法中的无用产生式； 删除那些不可到达的非终结符或不可终止的非终结符，对文法重新压缩（或化简）。 （4）存在某些文法不能在有限步内提取完左公共因子； 并不是所有处理回溯问题都需采用提取左公共因子的方法。,左递归在分析中存在的问题,自上而下分析中常会出现“无限循环”的问题，即一个文法是含有左递归的，存在非终结符P

29、： P P 对这种文法，当试图用P去匹配输入串时会发现，在没有吃进任何输入符号的情况下，又得重新要求P进行新的匹配。,例如 文法GS: SSa Sb，输入串为baaaa。 分析过程：S =Sa=Saa=Saaa （没有对当前输入符号匹配就又进入对S进行递归调用，这样就会出现死循环） 左递归：直接左递归和间接左递归,直接左递归的消除,假定P的全部产生式是： PP1| P2| | Pm| 1| 2| | n 其中每个都不等于，每个都不以P开头。 改造规则： 消除P的直接左递归性就是把这些规则改写成 P 1P| 2 P| | n P P 1 P | 2 P | | m P | ,消除直接左递归之例

30、1,例如 文法GE：S Sa S b 经消除直接左递归后变成： S bS SaS | ,消除直接左递归之例 2,例如 文法GE：E E+T | T T T*F | F F (E) | i 经消除直接左递归后变成： E TE E +TE | T FT T *FT | F (E) | i,消除间接左递归 之 例1,先将间接左递归变成直接左递归，然后再消除直接左递归。 例1 文法GS：SAa | b AAc | Sd | e 解：先将关于S的产生式代入关于A的产生式中： SAa | b AAc | Aad | bd |e 消除关于A产生式的左递归 SAa | b AbdA | eA AcA | ad

31、A| ,消除间接左递归 之 例2,先将间接左递归变成直接左递归，然后再消除直接左递归。 例2 文法GA: (1) AaB (2) AB b (3) BAc (4) Bd 解：先将(1)、(2)的右部代替产生式(3)中的非终结符A： BaBc BBbc 于是有：B - aBc|Bbc|d 。消除关于B产生式的左递归 B - (aBc|d) B B - bcB| ,消除文法中一切左递归的算法（1/2）,条件：文法必须是不含回路（形如P P的推导）和无产生式。 算法：分步 （1） 把文法G中的所有非终结符按任一顺序排列成P1,P2,Pn；按此顺序执行 （2）FOR I:=1 TO n DO BEGI

32、N FOR J:=1 TO I-1 DO 把形如PiPj的规则改写成 Pi1 | 2 | |k，其中Pj1 | 2 | |k是关于Pj的所有产生式； 消除关于Pi的产生式的直接左递归性 END,消除文法中一切左递归的算法（2/2）,（3）化简由(2)所得的文法，即去除那些从开始符号出发永远无法达到的非终结符的产生式规则。 例子如下：,消除全部左递归的 例子,文法GS： SQc | c QRb | b RSa | a 解：令文法的非终结符排序为R,Q,S。对于R不存在直接左递归，把R代入到Q的有关候选后，Q的规则变为： QSab | ab | b现在Q同样不含直接左递归，把它代入到S的有关候选后

33、，S变成： SSabc | abc | bc | c 消除S的直接左递归后，得到整个文法为： SabcS | bcS | cS S abcS | Q Sab | ab | b R Sa | a,例（续）,显然，其中关于Q和R的产生式是多余的，经过化简后最后所得的文法是 SabcS | bcS | cS S abcS | 注意：由于对非终结符排序的不同，最后所得的文法在形式上可能是不一样的，但它们是等价的。例如，排列顺序为S、Q、R时：,例（续）,令文法的非终结符排序为S、Q、R。对于S不存在直接左递归， Q同样不含直接左递归。把S代入到R的有关候选后，R的规则变为： RQca | ca | a

34、现在Q同样不含直接左递归，把它代入到R的有关候选后，R变成： RRbca | bca | ca | a 消除R的直接左递归后，得到整个文法为： SQc | c Q Rb | b R( bca | ca | a)R R bcaR | ,5.4不确定的自顶向下分析思想,1. 当文法不是LL(1)文法时，不能用确定的自顶向下的分析，可采用不确定的自顶向下的分析方法，即带回溯的自顶向下的分析方法。 2. 带回溯的自顶向下的分析是一个试探的过程，当分析不成功时，退回到适当的位置，再重新试探其余候选的产生式。 这种方式，需要记录已经选过的产生式，直到都试探完毕仍不成功，才能确定输入串不是该文法的句子。 3

35、. 编译程序实现时，一般是边分析边插入语义动作。带回溯的分析代价很高，效率很低，不实用。,5.4不确定的自顶向下分析思想,引起回溯的原因： 1. 由于相同左部产生式的右部FIRST集交集不为空； 例如文法GS： S xAy A ab | a 分析输入串xay#。 2. 由于相同左部的非终结符的右部能 ，且该非终结符FOLLOW集中含有其右部FIRST集中的元素； 例如文法GS： S aAS | b A bAS | 分析输入串ab# 3. 由于文法含有左递归而引起的回溯,5.5 确定的自顶向下的分析方法,一、递归子程序法: 在源程序的编译过程中，对于每一个语法成份（非终结符）用相应的子程序处理。

36、而子程序又分为简单子程序（不调用任何子程序）、嵌套子程序（调用其它子程序，但不调用它自身）、递归子程序（直接或间接调用它自身）。 由于程序设计语言的许多语法成份是递归定义的，因此处理它的相应子程序也是递归子程序，这种分析方法的名称也由此而得名。,递归子程序法的编译思想,从文法的识别符号开始，在语法规则支配下进行语法分析。逐个扫描单词符号序列，根据文法和当前输入符号预测到下一个语法成份v时，便确定v为目标，并调用和识别v的子程序，在分析v的过程中，又可能确立其它（或自身）子目标并调用相应的子程序，如此继续下去。,递归子程序法设计的注意点,由于递归子程序在退出之前又可能再次进入程序，因此不用一个固

37、定单元来存放返回地址，而是需要开辟一个栈存放返回地址。因此，在编译写递归子程序时，应注意处理程序的入口和出口（所谓入口是应将返回地址送至地址栈栈顶；出口是应从返回地址栈栈顶取返回地址）。,子程序,设aVT，P(a)代表语句：if ch=a then READ(ch) else error 设=x1x2xn，x1(VNVT), P()代表语句：P(x1); P(x2); P(xn); 设UVN，产生式U1|2|m, 定义P(U): read(ch); if ch First(1) then P(1) else if ch First(2) then P(2) else if ch First(m

38、) then P(m) else error,全局变量ch，代表输入符号的当前符号；read(ch)函数，读入符号串的下一个符号并存入ch中。,子程序(续),设UVN，产生式U1|2|m|, 定义P(U): read(ch); if ch First(1) then P(1) else if ch First(2) then P(2) else if ch First(m) then P(m) else if ch Follow(U) then return else error,递归下降分析程序 之 例,考虑文法GE： EE+T | T T T*F | F F (E) | i 消去左递归后变

39、成： E TE E +TE | T FT T *FT | F (E) | i,递归下降分析程序,PROCEDURE E BEGIN T ; E END,PROCEDURE T BEGIN F ; T END,PROCEDURE E IF SYM=+ THEN BEGIN ADVANCE; T ; E END,PROCEDURE T IF SYM=* THEN BEGIN ADVANCE; F ; T END,递归下降分析程序（续）,PROCEDURE F IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E ; IF SYM=) T

40、HEN ADVANCE ELSE ERROR END ELSE REEOR 为了程序更加清晰好写，也可先画出程序框图：,例5.16 文法G35S:S(A)|aAb AeA|dSA AdA|,Read(ch),ch=( ?,ch=a ?,ch=b ?,Read(ch),P(A),Read(ch),Read(ch),error,P(A),ch=) ?,Y,N,N,Y,N,P(S):,N,Y,Y,例5.9（续） AeA|dSA,ch=e ?,ch=d ?,P(S),P(A),Read(ch),error,Y,N,P(A):,例5.9（续） AdA|,ch=d ?,chFollow(A)?,Read(

41、ch),error,Y,N,P(A):,N,Y,对递归下降分析程序的说明,ADVANCE : 把输入串指示器IP调至下一个输入符号； SYM : 当前所指的输入符号； ERROR : 出错诊察处理程序。,假定在开始工作前，输入串指示器IP指向第一个输入符号。当每个子程序工作完毕之后，IP总是指向下一个未处理的符号。注意避免递归子程序E，我们知道关于E的产生式是： E +TE | 即E只有两个候选。第一个候选的开头终结符为，第二个候选为。也就是说，当E面临输入符号时就令第一个候选进入工作，当面临任何其它输入符号时，E就自动认为获得了匹配。递归过程E就是根据这一原则设计的。,递归子程序的优缺点,优

42、点： 可以根据文法的规则直接写出相应的识别程序，而且那样的直观、明了、易于掌握。由于识别程序与文法之间的紧密结合，使出错的可能性大为减少，至少不会出现很严重的问题。 缺点： （1）大量的相互嵌套递归子程序的频繁调用，使分析器的速度相当慢； （2）分析器自身的程序量要比表驱动类型的分析器大，对文法的要求较高，必须满足LL(1)文法。 因此，一些规模较小的语言仍宜于采用这种方法。,二、预测分析方法,实现递归下降分析的另一种有效方法是使用一张分析表和一个栈进行联合控制从而产生预测分析程序，这种方法就是预测分析方法。 整个分析过程由符号栈STACK栈顶元素X和输入串R中当前元素a确定下一步骤，而下一步

43、骤又常常是通过查阅预测分析表MX,a获得应有信息。 分析方法的核心是预测分析表。,预测分析方法的工作图,输入的字符串,#,总控程序,预测分析表,stack,S #,asdf,预测分析总控程序的工作流程,预测分析程序中的栈STACT,栈STACT用于存放文法符号。分析开始时，栈底首先放一个“”，然后放进文法开始符号，同时，假定输入串之后也总有一个“”，标志输入串的结束。,#S,预测分析程序的总控程序,对于不同的文法G，会有不同的分析表。但这种自顶向下的语法分析的总控程序却是一样的。预测分析程序的总控程序在任何时候都是按STACT栈顶符号X和当前输入符a行事的。 对任何(X,a)，总控程序每次都执

44、行下述三种可能的动作之一： (a) 若X= a =#，则宣布分析成功，停止分析过程； (b) 若X= a #，则把X从STACT栈顶退出，让a指向下一个输入符号；,预测分析程序的总控程序（续）,(c) 若X是一个非终结符，则查看分析表M： 若MA,a中存放着关于X的产生式，则首先把X退出栈顶，然后把产生式的右部符号串按逆序一一推进STACT栈（若为 则意味着什么也不进栈）。在把产生式符号推进栈的同时，应做这个产生式相应的语义动作。 若MA,a中值为“出错标志”，则调用出错诊察程序ERROR。,预测分析程序总控程序的描述,BEGIN 首先把“#”、文法的开始符号推进栈； 把第一个输入符号读进a；

45、 FLAG := TRUE; WHILE FLAG DO BEGIN 把STACT栈顶符号上托出去并放在X中； IF XVT THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE,IF X=# THEN IF X=a THEN FLAG := FALSE ELSE ERROR ELSE IF MA,a=XX1 X2 Xk THEN 把Xk Xk-1 X2 X1一一推进栈； /*若X1 X2 Xk = ，则不推进什么进栈*/ ELSE ERROR END OF WHILE； STOP /*分析成功，过程完毕*/ END.,预测分析程序总控程序的描述,预测分析表

46、的构成,预测分析表与给定的文法G有关，它是一个MA,a形式的矩阵，其中A为非终结符，a为终结符或“#”（注意，“#”约定为输入串的结束标记，而不是文法的终结符）。 若该文法有n个非终结符，m个终结符，则该矩阵是n行m+1列的矩阵。 分析表M的元素MA,a为关于非终结符A的一条产生式，指出当该非终结符A面临输入符号a时应选择的规则。MA,a也可能是“出错标志”，指出非终结符号A不能面临终结符号a。,分析表M的构造思想,假定有产生式A， （1）aFIRST()，那么当A出现在STACT栈栈顶，且a是当前输入符号时，应被当作是A唯一的全权代表，因此，MA,a中应填入产生式A； （2）当或 时，如果当

47、前面临的输入符号aFOLLOW(A)，那么A就认为已自动获得匹配，因此，MA,a中应填入产生式A；,分析表M的构造算法,（1）对文法G中的每个产生式A执行第2步和第3步； （2）对每个终结符aFIRST()，把A加至MA,a中； （3）若FIRST()，则对任何bFOLLOW(A)把A加至MA,a中； （4）把所有无定义的MA,a标上“出错标志”。,预测分析方法 之 例1 (1)判断是否LL(1)文法,解：FIRST(E)=FIRST(T)=FIRST(F)=( , i FIRST(E)=+ , FIRST(T)=* , FOLLOW(E)=FOLLOW(E)=# , ) FOLLOW(T)=

48、FOLLOW(T)=# , ) , + FOLLOW(F)=* , + , ) , #,文法GE: E TE E +TE | T FT T *FT | F (E) | i 构造其预测分析表。,预测分析方法 之 例1 求出SELECT集,解：SELECT(E-TE)= (, i SELECT(E-+TE)= + SELECT(E- )=), # SELECT(T- FT)= (, i SELECT(T-*FT)= * SELECT(T- )=+, ), # SELECT(F- (E) )= ( SELECT(F- i)= i ,预测分析方法 之 例1 (2)构造预测分析表,文法GE的预测分析表：

49、,对预测分析表的说明,上述算法可适用于任何文法G以构造它的分析表M，但对某些文法其分析表MA,a可能持有若干个产生式，或者说有些MA,a可能是多重定义的。如果G是左递归或二义的，那么M至少含有一个多重定义入口。因此也可用分析表来判断LL(1)文法： 一个文法G，若它的分析表M不含多重定义入口，则称它是一个LL(1)文法。 为了节省存储空间和运行效率，可以将上述M进一步简化。实际上，只要将产生式右部存放便行。,预测分析方法 之 例2,解：提取左公共因子后将文法改写成G： SiCtSS| a SeS | C b 该文法的FIRST、FOLLOW集合为： FIRST(S) = i , a FIRST(S)=e , FIRST(C)=b FOLLOW(S)=FOLLOW(S)=#, e FOLLOW(C)=t,文法GS： SiCtS | iCtSeS | a C b 判断是否为LL(1)文法。,例2的预测分析表M,其中MS,e是二重的， 此文法是二义的，非LL(1)文法。,由于FOLLOW(S)=#, e导致了MS,e是二重定义，从而无法改为LL(1)文法。但是如果令MS,e只含SeS，则意味着坚持把else和最近的then相结合。,说明,为了总控工作的方便，还可以把分析表的元素