自上而下语法分析.ppt

1、第四章 自顶向下语法分析方法,自顶向下分析的一般过程和问题 FIRST和FOLLOW集定义和计算 LL(1) 文法定义 LL(1)分析程序实现,4.1 语法分析概述,语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。,语法分析在编译系统中所处的位置,语法分析器的输入 Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列 语法分析器的输出 分析树：表示方法？ 见教材 P89 错误处理信息：定位、继续编译,语法分析的接口设

2、计,语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。 问题 对给定的一个输入串，如何判定它是不是一个句子？ 方法 根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。,G = (E, i, +, *, (, ) , P , E) P： E E + E E E * E E ( E ) E i,解：使用最左推导： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,例1：判定输入串(i+i)*i是否是下述文法的句子？,结论：

3、能够从开始符号出发推导出给定的输入串， 因此，是句子。,7,7,例2：已知符号串S=cad 文法GZ: ZcAd Aab|a 求证：SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配.,2.用Z的右部,符号串去匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,8,8,3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(GZ),4. 回溯 即砍掉A的子树 改选A的第二右部,Aa 检查 a-a匹配 d-d匹配,建立语法树,末端结点为ca

4、d与输入cad相匹配, 建立了推导序列 ZcAdcad cadL(G(Z),S=cad GZ: ZcAd Aab|a,分析工作要部分地或全部地退回去重做叫回溯,常用的语法分析方法：,自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导) ，尽可能使用各种产生式，推导出与输入串匹配的句子，从而建立语法树。 自底向上分析法：从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。 具体分类：,4.2 自顶向下语法分析,自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。 从推导的角度看，从开始

5、符号出发，使用最左推导，试图推导出与输入符号串相同的句子。 从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。 需要反复试探。,句型的推导,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。,复习,自顶向下分析方法特点,1.分析过程是带有预测的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。,2.分析过程是一种试探过程，是尽一切办法(选用不同规则) 设法建立语法树的过程，由于是试探过程，故

6、难免有失败， 所以分析过程需进行回溯，因此我们也称这种方法是带 回溯的自顶向下分析方法。,例1：设有文法 (1) S xAy (2) A |= 现有输入串：x=y 其分析过程如右：,失败，需要退回，重新选取A的侯选式，这时使得分析器的动作不稳定,思考：产生回溯的原因？,问题1：回溯,真正原因是：文法的产生式有问题。,回溯问题,14,14,什么是回溯?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件：,文法中，对于某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。,回溯带来的问题：,严重的效率低，只有在理论上的意义而无实际意义,左

7、递归：文法中存在某个AVn，有A A。 直接左递归：有产生式A A 间接左递归：,例2：设有文法G(E)： (1) E E+T | T (2) T T*F | F (3) F (E) | i 现有输入串i*i+i, 分析过程是：,失败：对左递归文法使用最左推导，出现死循环。,思考：产生左递归的原因？,问题2：左递归,真正原因是：文法的产生式有问题。,结论,1. 左递归和回溯问题的产生直接与描述语言的文法有关 2. 应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析,4.3 问题的解决方法,消除左递归 消除回溯,4.3.1 消除左递归,(1) 直接左递归的消除： 假定产生式为：PP|

8、，将其替换为形式等价的产生式组：,例2：文法 E E+T | T T T*F | F F (E) | i 消去左递归后为：,T FT T *FT | ,E TE E +TE | ,F (E) | i,证明的关键步骤： P-P | P- | | | | P- ( | | | | ) P- P, P- | | | | P- P, P- | P,一般而言，若产生式形式为： AA1|A2|An|1|2|m 将其替换为：,练 习,消去文法GS的左递归,S (T) | a + S | a T T,S | S,例：给定间接左递归文法，请消除左递归,1) 代入 2) 消除直接左递归,S Qc|c Q Rb|b

9、 R Sa|a,解：第1步：为R、S、Q排序 第2步：代入：将R代入Q, Q代入S，得到新的文 法产生式组： R Sa|a Q Sab|ab|b S Sabc|abc|bc|c 第3步：消去S的直接左递归，得到,S abcS|bcS|cS S abcS|,(2) 间接左递归的消除方法,方法是:反复 “提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。,设产生式为：A1|2|n,4.3.2消除回溯,例3：有如下两个产生式： if E then S1 else S2; if E then S1;,提取左因子后： if E then S1 B; B else

10、S2 | ;,练习,提取下述文法的左因子,S (T) | a + S | a T ST T ,ST | ,问题: 如果希望没有回溯，对文法有什么要求？,回溯产生的真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。 如果希望没有回溯，对文法有什么要求？,4.4.1 侯选式的首终结符集的定义,即，由该候选式推导出的所有符号串中的第一个终结符的集合。,4.4 LL(1)文法,SApSBqAaAcABbBdB,练习：求给定文法的每个候选式的First集,(1) S xAy (2) A =|,在右边给定的文法中，A的候选式有两个，其首终结符集为： F

11、irst(A1) = First(A2) = 相交,就会产生回溯,因此，只要存在某个非终结符的多个候选式的首终结符集相交，就会在推导的某时刻产生回溯。从而导致语法分析器选择了错误的侯选式。,因此，不产生回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai) First(aj) = 当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。,32,32,例子,设有文法GS: S-Aa | Bb A-d | cA B-b | aB,对S: FIRST(Aa)=d,c, FIRST(Bb)=a,b, FIRST(Aa) FIRST(Bb)= 对

12、A: FIRST(d)=d, FIRST(CA)=c, FIRST(d) FIRST(Ca)= 对B: FIRST(b)=b, FIRST(aB)=a, FIRST(b) FIRST(aB)= 若给定 w=abb 则自顶而下分析对应的推导为: S=Bb=aBb=abb,求非终结符A的First集的算法,求某一非终结符A的首终结符集First(A)的算法为： 1.若有产生式Aa,aVT，把a加到First(A)中； 2.若有产生式A, 把加到First(A)中； 3.若有产生式AX，XVN，把First(X)中非元素加到First(A)中； 4.若有产生式AX1X2X3.Xk,其中X1X2.Xk

13、VN。则 当X1X2X3.Xi =(1ik)时，把First(Xi+1.Xk)的非元素加到 First(A)中； 当X1X2X3.Xk=时，把First()加入First(A)中 5.重复执行上述过程，直到First(A)不再增大,*,*,SApSBqAaAcABbBdB,例：用算法求下述文法的每个非终结符的First集,E TEE +TEE T FTT *FTT F (E)F i,First(F) = ( ，i First(T) = *， First(E) = +，First(T) = First(F) = ( ，i First(E) = First(T) = ( ，i ,练 习,求下列文法

14、的每个非终结符的First集,是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条件，就一定能进行有效的自顶向下分析呢？,思考题,确定的自上而下的分析 举例1：对于文法G1S：SpA SqB AcAd Aa 对输入串pccadd，自上而下的推导过程是： S = pA = pcAd = pccAdd = pccadd 对应的分析树：,例2：对于文法G2S：,SAp SBq Aa AcA Bb BdB,输入串ccap，自上而下的推导过程是： S = Ap = cAp = ccAp = ccap,4.4.2 后随符号集的定义,假定S是文法的开始符号，对于AN： Follow(A)=a|SAa，

15、aT 特别，若 SA，则，# FOLLOW(A) 当非终结符A面临a时， a不属于A的任何侯选首终结符集，但A的某个候选首终结符集中含，只有当a FOLLOW(A)时才能自动进行匹配。,*,*,注：FOLLOW集合中不能有,对右边给定的文法，求A的后随符号集follow(A),SApAa |AcA AaA,follow(A) = p,求非终结符A的Follow集的算法,1.如果A是开始符号，Follow(A) 2.若有产生式BAa,aVT，则 把a加入到Follow(A)中； 3.若有产生式BAX，XVN，则 把First(X)中非元素加入Follow(A)中； 4.若BA 或 BA， =，则

16、 把Follow(B)加入到Follow(A)中； 5.连续使用上述规则，直到Follow(A)不再增大。,*,例:求下题的Follow集,SApSBqAaAcABbBdB,解：Follow(S)=# Follow(A)=p Follow(B)=q,规则1,规则2,规则2,练 习,1.E TE2.E +TE3.E 4.T FT5.T *FT6.T 7.F (E)8.F i,follow(E) =#，) follow(E) = follow(E) = #，) follow(T) = (first(E)-) follow(E) =#,),+ follow(T) =follow(T) =#，)，+

17、follow(F) =(first(T)-)follow(T) =*,#,),+,E是开始符号，应用规则1， 根据产生式7，应用规则2,根据产生式1，应用规则4,根据产生式2，应用规则3， 根据产生式2，3，应用规则4,根据产生式4，应用规则4,根据产生式4，应用规则3 根据产生式4，6，应用规则4,求下题的Follow集,例： 仍讨论文法GS: S AB | bC A b | B aD | CAD | b D aS | c 所有非终结符求FOLLOW集过程如下： FOLLOW(S)=#FOLLOW(D) FOLLOW(A)=aa,cFOLLOW(S) FOLLOW(B)=FOLLOW(S)

18、FOLLOW(C)=FOLLOW(S) FOLLOW(D)=FOLLOW(B)FOLLOW(C) 从FOLLOW(S)=#开始，不断循环求解直到所有 FOLLOW集不再增大，最后可得： FOLLOW(S)= # FOLLOW(A)= a, c,#$ FOLLOW(B)= # FOLLOW(C)= # FOLLOW(D)= #,4.4.3 LL(1)分析方法,所谓LL(1)分析方法。如此命名该分析方法的原因在于相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。至于括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的

19、产生式（规则）。因此，我们通常把按上述方法执行语法分析任务的程序称为LL(1)分析程序或LL(1)分析器。,(对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。 (1) 文法不含左递归 (2) 对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交(是否有回溯) ，即：若 A1|2|n ，则 First(ai) First(aj) = ( i j ) (3) 对文法中的每个非终结符A,若它的某个首终结符集含有，则 First(A) Follow(A) = ,LL(1)文法的判别,例：判断下述文法是否是LL(1)文法： S aASS bA bAA ,解：(1)

20、该文法不含左递归 (2) First(SaAS)=a First(Sb)=b First(AbA)=b First(A)= S和A的侯选式的first集都不相交，满足条件2 (3) 由于 First(A) Follow(A)=First(S)=a,b Follow(A) First(A bA) ) 不满足条件3，则不是LL(1)文法,练 习,判断给定的文法是否为LL(1)文法，若不是，进行改造,解答：First(Aab)=a ; First(Aa)=a ; 不满足条件2，故不是LL(1)文法,改造方法：(消除回溯提取公因子) SxAy ; Aa(b|) = SxAy ; AaA ; A b|,

21、S xAyA ab|a,例3：使用下述文法对 i + i 进行分析：,E TE E +TE| T FT T *FT | F (E)|i,第一步：iFirst(TE) iFirst(FT) iFirst(F),第三步：+First(E) ,第二步：+first(T) First(T)，+ Follow(T) 自动匹配, 不读输入符号,LL(1)分析过程,follow(E) =#，) follow(E) = follow(E) = #，) follow(T) =follow(E)(first(E)-) =#,),+ follow(T) =follow(T) =#，)，+ follow(F) =(f

22、irst(T)-)follow(T) =*,#,),+,LL(1)文法的分析过程,假设要用非终结符A进行匹配，面临输入符号a，A的所有侯选式为： A1|2|n 分析过程为：(总结) 若a First(Ai),使用i去匹配。 若a不属于任何一个产生式的首终结符集， (1)若不属于任何一个 First(Ai)，则出错。 (2)若属于某个First(Ai),同时a Follow(A), 则让A 与自动匹配；否则，a的出现是一种语法错误。,4.5 递归下降分析方法,是进行语法分析的一种方法 要求文法是LL(1)文法 实现思想： 为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出

23、的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为，认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。,基本架构,(1)对于每个非终结符号的产生式Uu1|u2|un处理的方法如下： U( ) ch=当前符号; if(ch是u1符号串的第一个符号) 处理u1 else if(ch是u2符号串的第一个符号) 处理u2 elseerror() ,由于无回溯的文法保证选择是唯一的。 当存在时，可以用error()替代为return;这样可以较晚发现错误。 约定：进入这个过程时，已读入U的第一个符号。离开这个过程时，下一个符号已

24、经被读到当前符号。,基本架构,(2)对于U的每个右部ui=x1x2xn的处理架构如下： 处理x1的程序； 处理x2的程序； 处理xn的程序； 如果右部为空，则不处理。,基本架构,(3)对于右部中的每个符号xi 如果xi为终结符号： If (x = 当前输入符号串中的符号) NextCh()；return; else 出错处理 如果xi为非终结符号，直接调用相应的过程： xi(),基本架构,（4）对于形如Xi的产生式，在相应的子程序Pi( )中，应该能够判断当前输入符号a是否属于集合FOLLOW(Xi)，从而决定是从Pi( )返回还是报错。,在给定的语法定义中选择与IF语句有关的产生式。 :=

25、if then else := := | | = | = := := := := | :=0|1|2|3|9,如：对应于产生式 := if then 的过程的算法描述为：,ifs() gettoken(); If (token !=“if”) error; getnexttoken(); bool_expr(); getnexttoken(); If (token !=“then”) error; getnexttoken(); exe_sentence(); ,相应于产生式： := 的过程：,bool_expr() gettoken(); handle_varible(); Getnextt

26、oken(); If (token not in ! ( | | = | = ) error; Getnexttoken(); handle_varible(); ,思考 请写出for语句的递归下降的分析程序：,:= for := to do :=| := *|/| := :=| := := := .,例：为下列表达式文法GE编写递归下降识别程序。 E E+T | T T T*F | F F (E) | i,解： 步骤1：消除左递归： E TE E +TE | T FT T *FT | F (E) | i 步骤2：编写递归下降识别子程序，这里使用C语言形式。见下页图。,步骤3：编写递归下降识别

27、主程序,使用该识别程序识别输入串：i * i + i，首先读入符号i，然后调用子程序E，在E中调用子程序T，在T中调用子程序F，匹配i，读入下一符号*，子程序F调用完毕，回到T。在T中继续调用子程序T，匹配*，读入下一符号i。在T中继续调用子程序F，匹配i，读入下一符号+，回到子程序T。在T中递归调用子程序T，不执行任何操作返回T，进而返回T，进而返回E。在E中继续调用子程序E，匹配+，读入下一符号i，调用子程序T。在T中调用子程序F，匹配i，读入下一符号，为输入串结束符$，返回E。在E中递归调用E，不执行任何操作返回E，进而返回E。至此子程序E调用完毕，回到主程序，检查到达输入串末尾，从而识

28、别成功。 由于有些信息需要保留，通常在入口处需保留某些信息，出口时需要恢复。由于递归过程是遵循先进后出 规律，所以通常需要开辟先进后出栈来处理。,递归分析程序的优点,实现思想简单明了。程序结构和语法规则直接对应。 因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。,4.6 预测分析程序,递归下降分析法：采用递归过程。因此实现分析程序所使用的高级语言必须支持递归过程才行。 预测分析法是自顶向下分析的另一种方法。 使用下推自动机的方式实现。 使用一个二维分析表和栈联合进行控制来实现分析。,预测分析器模

29、型,分析表M: 是一个从VN(VT#)到产生式的映射。在分析时遇到A和a时，应该选择MA,a中存放的产生式。如果MA,a为空，表示出现语法错误。 分析表格式:,第1列为非终结符,第1行为终结符+#,每个元素为产生式或空,E TEE +TE |T FTT *FT |F (E) |i,总控程序:,将#压入堆栈中，将开始符号S压入堆栈中 读取第一个输入符号到a； 循环执行下述操作： 栈顶符号弹出放入X中； 如果X为终结符号： 如果X = a != #，表明成功匹配a符号; 读取下一个符号到a，否则出错； 如果X = # 如果X = a ，分析结束，接受句子。 如果 X!= a ，出错处理。 如果X为

30、非终结符号, 则查分析表M: 如果MX,a为空，出错处理。 如果MX,a=X1 X2Xn , 则: 将右部Xn X2 X1反序压入堆栈中。,预测分析过程,下面用预测分析方法对输入串i+i*i # 进行分析，给出栈的变化过程如下：,构造预测分析表,预测分析过程的总控程序是固定的。对于某个文法，分析表是分析过程的核心。 表中MA,a= AX1X2Xn 表示对应于X1X2Xn字的首终结符可以是a。就是说X1X2Xn=aw。可以通过这个方式来确定分析表中的值。(即：求首终结符),*,预测分析表的构造算法,对文法的每个文法符号X构造First(X) 对于每一产生式 A, 对于每个终结符aFirst(),

31、将A填入 MA,a； 如果First()，则构造Follow(A)，对任何元素 bFollow(A)，将A填入MA,b； 将所有无定义的 MA,a 标上错误标志。,如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。,例：求对应于下述文法的预测分析表：,1.首先求first集,E TEE +TE |T FTT *FT | F (E) |i,First (E) = ( ，i First (E) = +，First (T) = ( ，i First (T) = *， First (F) = ( ，i ,2.由于 First (E), First (T) 求E和T的Fol

32、low集,Follow (E) = #，) Follow (T) =#，)，+,E TEE +TE E T FTT *FT T F (E) F i,3.根据集合的值填表，得到,综合练习,设文法G(S)： S(L) | aS | a LL，S | S (1) 消除左递归和回溯； (2)计算每个非终结符的First和Follow集； (3) 构造预测分析表。,预测分析表,First (S) (, a Follow (S)# , ， , ) First (S)(, a , Follow (S)# , ，, ) First (L)(, a Follow (L) ) First (L)，,Follow

33、(L) ),S(L) | aS S S | LSL L ,SL |,4.6自上而下语法分析程序的设计,实现的语法成分包括： (1)带类型的简单变量的说明语句； (2)算术表达式和布尔表达式； (3)简单赋值语句； (4)各种控制语句：如if语句、while语句、 repeat语句、for语句,源程序举例：,program example; const i5； var a,b,c:integer; x:char; begin if(a+c*3b) and (b3) then c:=3; x:=2+(3*a)-b*c*8; for x:=1+2 to 3 do b:=100; while ab do c:=5; repeat a:=10; until ab; end.,总控程序的框架,void paser( ) /*语法分析总控程序*/ token = getnexttoken(); if (token 不是 “program” ) error()；/*程序中缺少progr