编译原理课件chap04(陈火旺).ppt

1、第四章 语法分析-自上而下分析,第四章 语法分析自上而下分析,高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法 4.1 语法分析器功能 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 下图表明了语法分析器在编译程序中的地位。,第四章 语法分析-自上而下分析,源程序,词法分析,单词符号,取下一 单词,语法分析,词法,分析树,编译后续,符 号 表,语法分析器在编译程序中地位,第四章 语法分析-自上而下分析,语法分析是编译程序的

2、核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。,常用方法,自顶向下分析,自底向上分析,确定 不确定,算符优先分析 LR分析,第四章 语法分析-自上而下分析,自顶向下语法分析方法,自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。 如果能够推导出，则该输入串是给定文法的句子； 如果不能推导出，则该输入串不是给定文法的句子。,第四章 语法分析-自上而下分析,例：已知符号串S=cad 文法GZ: ZcAd Aab|a 求解 SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配.,2.用Z的右部,符号串去

3、匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,第四章 语法分析-自上而下分析,6,6,3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(GZ),4. 回溯 即砍掉A的子树 改选A的第二右部,Aa 检查 a-a匹配 d-d匹配,建立语法树,末端结点为cad与输入cad相匹配, 建立了推导序列 EcAdcad cadL(G(E),S=cad GZ: ZcAd Aab|a,分析工作要部分地或全部地退回去重做叫回溯,第四章 语法分析-自上而下分析,自顶向下语法分析要解决

4、的关键问题,假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,第四章 语法分析-自上而下分析,1.分析过程是带有预测的，对输入符号串要 预测属于什么语法成分，然后根据该语法 成分的文法建立语法树。,2.分析过程是一种试探过程，是尽一切办法 (选用不同规则) 设法建立语法树的过程， 由于是试探过程，故难免有失败， 所以分析 过程需进行回溯，因此我们也称这种方法是带 回溯的自顶向下分析方法。,第四章 语法分析-自上而下分析,自顶向下分析存在的问题及解决方法,自顶向下分析方法的基本缺点： 不能处理具有左递归性的文法,自顶向下分析为什么不能处理左递归

5、文法？,1 左递归文法：,左递归文法 回溯问题,第四章 语法分析-自上而下分析,10,10,如果我们在匹配输入串过程中，假定正好轮到要用非终结符 U直接匹配输入串，即要用U的右部符号串U去匹配，为 了用U去匹配，又得用U去匹配，这样无限的循环下去 将无法终止。,如果文法具有间接左递归，则也将发生上述问题，只不过 环的圈子兜的更大。,要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。,自顶向下分析为什么不能处理左递归文法？,第四章 语法分析-自上而下分析,11,11, 消除直接左递归:,11,11,规则一（提因子）,i)已知 U

6、xy | xw | | xz 解： Ux ( y | w | | z ) 得： Ux U Uy | w | | z iii)已知 Ux | xy 解： Ux ( y |),使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。,ii)已知 Uxy | xw | | xz y y1y2 wy1w2 解：Ux ( y1 ( y2 | w2 ) | | z ) 得： Ux U U y1 y1 | | z y1 y2 | w2,第四章 语法分析-自上而下分析,12,12,规则二 将左递归规则改为右递归规则,若：PP| 则可改写为：P P P P| ,例2 已知GE

7、： E:= T*F | T/F | F T:=F | T*F | T/F 解：左递归改为右递归得： E := T*F | T/F | F T := FT T := *FT | /FT | ,第四章 语法分析-自上而下分析,一般而言，假定关于P的全部产生式是 PP1| P2| P1m| 1| 2 | | n 其中，每个都不等于，而每个都不以P开头，那末，消除P的直接左递归性就是把这些规则改写成： P | 1 P| 2 P| n P P1P| 2P| | mP| ,第四章 语法分析-自上而下分析,14,14,消除一般左递归,1.把G的非终结符整理成某种顺序A1，A2，An ，使得： A1 := 1

8、|2|k A2 := A1 r A3 := A2u | A1v. .,2. For i:=1 to n do begin for j :=1 to i-1 do 把每个形如AiAj r的规则替换成 Ai (1|2|k) r 其中Aj 1|2|k是当前全部Aj 的规则 消除Ai规则中的直接左递归 end,3.化简由2得到的文法即可。,第四章 语法分析-自上而下分析,例：文法Gs为 S Qc|c Q Rb|b R Sa|a,非终结符顺序 重新排列,RSa|a QRb|b SQc|c,1.检查规则R是否存在直接左递归 RSa|a,2.把R代入Q的有关选择，改写规则Q QSab|ab|b,3.检查Q是

9、否直接左递归,4.把Q代入S的右部选择 SSabc|abc|bc|c,5.消除S的直接左递归 S(abc|bc|c)S S abc S|,最后得到文法为:,S(abc|bc|c)S S abc S|,QSab|ab|b RSa|a,第四章 语法分析-自上而下分析,16,16,最后得到的文法:,S(abc|bc|c)S S abc S| QSab|ab|b RSa|a,可以看出其中关于Q和R的规则是多余的规则 经过压缩后 S(abc|bc|c)S S abc S| 可以证明改写前后的文法是等价的,应该指出,由于对非终结符的排序不同,最后得到的文法在形 式上可能是不一样的,但是不难证明它们的等价.

10、,第四章 语法分析-自上而下分析,自顶向下语法分析方法,自顶向下分析法分确定性和不确定性两种。 自顶向下的确定性分析法对文法有一定的限制，但实现简单直观，便于手工或自动构造； 自顶向下的不确定性分析法是带有回溯的分析方法，效率低，代价高，极少使用。,第四章 语法分析-自上而下分析,一、确定的自顶向下分析思想 1、方法：从开始符号出发，不断替换非终结符，根据当前的单词符号就可以唯一选定要替换的产生式。,例1：文法G(S)：SpA SqB AcAd Aa 输入串 W=pccadd 自顶向下的推导过程为:,第四章 语法分析-自上而下分析,a,相应的语法树：,SpA pcAd pccAdd pccad

11、d,SpA SqB AcAd Aa 输入串 W=pccadd,第四章 语法分析-自上而下分析,例1：文法G(S)：SpA SqB AcAd Aa 该文法的特点： （1）每个产生式的右部都由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符开始。 对于这样的文法，其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导，因此，分析过程是唯一确定的。,第四章 语法分析-自上而下分析,例2：文法G(S)为： S Ap S Bq A acA BbdB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或

12、非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？,第四章 语法分析-自上而下分析,例2：文法G(S)为： S Ap S Bq A acA BbdB 当输入W=ccap推导： 自顶向下的推导过程为：,第四章 语法分析-自上而下分析,例2：文法G(S)为： S Ap S Bq A acA BbdB 当输入W=ccap推导： 自顶向下的推导过程为： S Ap cAp ccAp ccap 语法树为：,a,第四章 语法分析-自上而下分析,例2：文法G(S)为： S Ap S Bq A acA BbdB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2

13、 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？,第四章 语法分析-自上而下分析,2、开始符号集合的定义：,设G=（VT，VN， P ，S ）是上下文无关文法， 开始符号集合为First()= a | a，aVT， 、V* 规则右部的开始符号集包括所有终结符 a，使得规则右部经过若干推导后得到的字符串以a为起始。 若 ，则规定First() 。,*,*,例3：上例中文法是： SAp|Bq A a | cA B b | dB 则：FIRST(Ap)=？； FIRST(Bq)=？,针对产生式规则的右

14、部产生开始符号集合,第四章 语法分析-自上而下分析,2、开始符号集合的定义：,设G=（VT，VN， P ，S ）是上下文无关文法， 开始符号集合为First()= a | a，aVT， 、V* 规则右部的开始符号集包括所有终结符 a，使得规则右部经过若干推导后得到的字符串以a为起始。 若 ，则规定First() 。,*,*,例3：上例中文法是： SAp|Bq A a | cA B b | dB 则：FIRST(Ap)=a，c； FIRST(Bq)=b，d,针对产生式规则的右部产生开始符号集合,第四章 语法分析-自上而下分析,如何根据输入串的第1个符号来确定产生式呢？ 根据当前输入符号属于哪个产

15、生式右部的开始符号集合而决定选择相应产生式进行推导。,第四章 语法分析-自上而下分析,例3：文法GS ： S aA | d A bAS| 若输入W=abd，则推导过程为：,第四章 语法分析-自上而下分析,例3：文法GS ： S aA | d A bAS| 若输入W=abd，则推导过程为： S aA abAS abS abd 当非终结符A面临输入符号d，且d不属于A的任何候选首符集，但A的候选首符集包含,第四章 语法分析-自上而下分析,当某一非终结符的产生式中含有空产生式时，第二步推导的产生式该如何确定呢？根据后跟符号集合确定,3、后跟符号集合的定义：,设G=（VT，VN，P，S）是上下文无关文

16、法，AVN，S是开始符号， Follow(A)=a | S uA且aVT，a First()，uVT*，V+。针对非终结符 若S uA，且 ，则#Follow(A) （#表示输入串的结束符，或句子括号）,可写成为： Follow(A)a|SAa， aVT 若SA，则#Follow(A)。,*,*,*,*,*,第四章 语法分析-自上而下分析,Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。,例4：在例2中文法GS为：S Ap | Bq A a | cA B b | dB 求Follow集。,解：Follow(S)=？ Follow(A)=？ Follow(B)=？,第四章 语法分

17、析-自上而下分析,换句话说： Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。,例4：在例2中文法GS为：S Ap | Bq A a | cA B b | dB 求Follow集。,解：Follow(S)=# Follow(A)=p Follow(B)=q,第四章 语法分析-自上而下分析,自上而下语法分析要解决的关键问题,假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？ 根据规则的选择集合来确定。,第四章 语法分析-自上而下分析,4、选择集合的定义 给定上下文无关文法的产生式A，AVN， V*，若，则Select（A）=Fir

18、st()， 若，则Select(A)=（First()-）Follow(AA),*,*,给定输入串，根据产生式规则的选择集合选择产生式进行推导。,第四章 语法分析-自上而下分析,5、LL(1)文法的定义： 文法不含左递归； 对于文法中每个非终结符A的各个产生式的候选首 符集两两不相交。即，若Ax1| x2| xn 如果： FIRST(xi)FIRST(xj) = (ij,i,j=1,2,n) 而当FIRST(xi)时，有 FIRST(xi) FOLLOW(U) = 一个文法若满足以上条件，则称该文法为LL(1)文法。 只有对满足LL(1)文法的句子，才能进行确定的自顶向下分析： 给定输入串，就

19、可以根据产生式规则的选择集合确定唯一的产生式进行推导。,第四章 语法分析-自上而下分析,LL(1)的含义：从左L向右扫描输入串，分析过程中采用最左L推导，只需向右看1个符号就可确定如何推导（选择哪个产生式进行推导）。,第四章 语法分析-自上而下分析,例5：上例3文法： SaA|d AbAS| 证明该文法为LL(1)文法。,第四章 语法分析-自上而下分析,例5：上例3文法： SaA|d AbAS| 证明该文法为LL(1)文法。 不难看出：Select(Sa A)=First(aA)a Select (Sd)= First(d)=d Select (AbAS)=b Select (A)=（firs

20、t()- ）follow(A)=a,d,# Select (S aA) Select(Sd) ad= Select(AbAS) Select(A) ba,d,#= 所以上述文法是LL(1)文法。,SAa aA ,*,SaA abAS abAd S aA abAS abAaA 所以Follow(A)=a,d,#,第四章 语法分析-自上而下分析,例：设文法GS为： S aAS | b A bA | 判别是否是LL(1)文法。,第四章 语法分析-自上而下分析,解：Select(S aAS)=first(aAS)=a Select ( S b ) =b Select ( A bA ) =b Selec

21、t ( A ) =（first()-）follow(A)=a,b Select( SaAS ) Select(Sb ) a b = Select(A bA) Select(A )ba,b 因此，该文法不是LL（1）文法，因而也就不可能用确定的自顶向下分析。,第四章 语法分析-自上而下分析,当需要选用自顶向下分析技术时，首先必须判定所给的文法是否是LL(1)文法。,第四章 语法分析-自上而下分析,4.4 递归下降分析程序构造（见P75） 当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的自上而下分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样一个分析程序称

22、为递归下降分析器。 在本节中我们对巴科斯范式进行了扩充： （1）用花括号表示闭包运算* ( 2）用0n表示可以任意重复0次至n 次， 00=。 （3）用方括号表示01，即表示的出现可有可无。 4.5 预测分析程序 使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。我们现在介绍的预测分析程序就是属于这种类型的LL(1)分析器。 本节要 掌握对给定文法构造出每个非终结符的FIRST和FOLLOW集合。,第四章 语法分析-自上而下分析,2、预测分析方法： 自顶向下分析的另一种方法 预测分析

23、器的组成：,预测分析程序 先进后出栈 预测分析表与文法有关,第四章 语法分析-自上而下分析,预测分析表可用一个矩阵表示。矩阵元素MA,a中的A表示非终结符， a表示终结符或句子结束符#，矩阵元素MA,a中的内容是一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理。 如何构造预测分析表？,第四章 语法分析-自上而下分析,45,45,() 构造分析表,基本思想是: 当文法中某一非终结符呈现在栈顶时,根据当前的输入符号,分析表应指示要用该非终结符里的哪一条规则去匹配输入串

24、(即进行下一步最左推导) 根据这个思想,我们不难把构造分析表算法构造出来!,终结符号,非终结符号,第四章 语法分析-自上而下分析,表驱动的预测分析程序模型（P77）,第四章 语法分析-自上而下分析,(2)分析过程：,#S进栈，当前终结符送a,上托栈顶符号放入X,XVT？,Xa？,X=#？,END,error,M(X,a)是 产生式吗？,Xa？,error,若产生式为 Xx1x2xn 按逆序即 xnx2x1入栈,读下一 个符号,y,y,y,n,n,n,y,y,n,n,第四章 语法分析-自上而下分析,48,48,执行程序主要实现如下操作:,1.把#和文法识别符号E推进栈,并读入输入串的第一 个符a

25、,重复下述过程直到正常结束或出错.,2.测定栈顶符号X和当前输入符号a,执行如下操作:,(1)若X=a=#，分析成功，停止。E匹配输入串成功. (2)若X=a#，把X推出栈，再读入下一个符号。 (3)若XVn，查分析表M（详细步骤见下页）,第四章 语法分析-自上而下分析,49,49,(3)若XVn，查分析表M。 a) MX,a= X=UVW 则将X弹出栈，将UVW压入 注：U在栈顶 （最左推导） b) MX, a = error 转出错处理 c) MX, a = X:= -a为X的后继符号 则将X弹出栈 （不读下一符号） 继续分析。,第四章 语法分析-自上而下分析,分析算法,BEGIN 首先把

26、#然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,b=X X1X2.XK THEN 把XK，X K-1,.,X1一一推进栈 ELSEERROR END OF WHILE; STOP/*分析成功，过程完毕* END,第四章 语法分析-自上而下分析,预测分析表构造算法,1.对文法G的每

27、个产生式 执行第二步 和第三步； 2.对每个终结符aFIRST()，把 加 至A,a中， 3.若 FIRST()，则对任何bFOLLOW(A) 把 加至A,b中， 4.把所有无定义的A,a标上“出错标志”。 可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的,第四章 语法分析-自上而下分析,(3)实例分析：给定文法，构造预测分析表，并针对输入串i+i*i#构造预测分析过程。,例：文法为：E E+T | T T T*F | F F i | (E) 步骤：,（1） 判断文法是否为LL(1)文法。 如果文法中含有左递归，必须先消除左递归： （2）构造预测分析表 ： Selec

28、t(A ) （3）列出预测分析过程,第四章 语法分析-自上而下分析,S Sa S bS S b SaS| E E+T E T,(3)实例分析：给定文法，构造预测分析表，并针对输入串i+i*i#构造预测分析过程。,例：文法为：E E+T | T T T*F | F F i | (E) 构造步骤有：, 判断文法是否为LL(1)文法。 由于文法中含有左递归，所以必须先消除左递归：,E E+T | T,E TE E +TE|,第四章 语法分析-自上而下分析,T T*F | F,TFT T*FT|,ETE E+TE| TFT T*FT| F i | (E),文法变为：,第四章 语法分析-自上而下分析,

29、求First集合： First(E)= ( ，i First(E )= + ， First(T)= ( ，i First (T )= * ， First (F)= ( ，i ,ETE T不， E不 First(E)=first(T) =first(F)= ( , i ,求Follow集： Follow (E)= ，# Follow (E )= ，# Follow (T)= + ， ，# Follow (T )= + ， ，# Follow (F)=* ，+ ， ，#,ETE FTE (E)TE,ETE FTE (E)TE (TE)TE,ETE T+TE T+T T+FTT+(E)T T+(TE

30、)TT+(T)T,ETE FTE FT F*FT F*(E)T F*(TE)TF*(FTE)T F*(FT)T,第四章 语法分析-自上而下分析,求Select集： Select (ETE)= ( ，i Select (E +TE)=+ Select (E )=， ，# Select (T FT )=(，i Select (T *FT)=* Select (T )=，+，# Select (F i)=i Select (F (E)=(,由上可知有相同左部产生式的Select集合的交集为空，所以文法是LL (1),第四章 语法分析-自上而下分析,构造预测分析表 ： 方法：对每个终结符或#用a表示。

31、 若aSelect(Aa)，则Aa放入MA,a中。,第四章 语法分析-自上而下分析,对于某句子的分析过程： 下面用预测分析程序，栈和预测分析表对输入串i+i*i#进行分析，给出栈的变化过程如下：,第四章 语法分析-自上而下分析,第四章 语法分析-自上而下分析,表驱动的预测分析程序模型,第四章 语法分析-自上而下分析,第四章 语法分析-自上而下分析,62,62,设=X1X2.Xn, XiVn Vt 求FIRST()=? 首先求出组成的每一个符号Xi的FIRST集合,若XiVt，则 FIRST(Xi) = Xi,(2) 若Xi Vn 且 Xia.|， a Vt 则 FIRST(Xi)=a，,()

32、集合FIRST的算法,第四章 语法分析-自上而下分析,63,63,第四章 语法分析-自上而下分析,64,64,() 构造集合FOLLOW的算法,若S为识别符号,则把“#”加入FOLLOW(S)中,(2)若AB (),则把FIRST()-加入FOLLOW(B),注：FOLLOW集合中不能有,设S, A, BVn , 算法：连续使用以下规则，直至FOLLOW集合不再扩大,第四章 语法分析-自上而下分析,65,65,解：1）求FIRST： FIRST(F)= (，i FIRST(T)=*, FIRST(T)=FIRST(F)-= (，i FIRST(E)=+, FIRST(E)= FIRST(T)-

33、=(，i FIRST(TE)=FIRST(T)-=(，i FIRST(+TE)=+ FIRST()= FIRST(FT)= FIRST(F)-=(，i FIRST(（E）)=( FIRST(i)=i,例：GE分析表的构造 ETE E+TE| TFT T*FT| F(E)|i,构造过程： 1）求FIRST： 2）求FOLLOW 3）构造分析表,第四章 语法分析-自上而下分析,66,66,ETE E+TE| TFT T*FT| F(E)|i,2）求FOLLOW,FIRST(F)=(,i FIRST(T)=*, FIRST(T)=(,i FIRST(E)=+, FIRST(E)=(,i,第四章 语法

34、分析-自上而下分析,例题,例：已知文法GS：S aH H aMd | d M Ab | A aM | e （1）判断该文法是否是LL(1)文法，若是，请构造相应的LL(1)预测分析表 （2）给出对输入串aaabd#的预测分析过程，并说明该输入串是否是该文法的句子。,第四章 语法分析-自上而下分析,掌握LL(1)预测分析表的构造，请参看4。5。1 预测分析程序的工作过程（P76）和 4。5。2预测分析表的构造（P78）。 现在举一些例子帮助同学们理解： 例4。7 对于文法 ETE E +TE| T FT T *FT| F (E)| i 我们构造每个非终结符的FIRST和FOLLOW集合 解：FI

35、RST(E) = (, i FOLLOW(E) = ), # FIRST(E) = +, FOLLOW(E) = ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T) = *, FOLLOW(T) =+ , ), # FIRST(F) = (, i FOLLOW(F) =*, +, ) , # 在这里我们要注意FOLLOW(F)的求解过程其中： FOLLOW(F)=FIRST(T)=*; 因为T ,所以将FOLLOE(T)加到FOLLOW(F)中 （由于TFT), 则：FOLLOW(F)=FOLLOW(T)=FIRST(E)=+,第四章 语法分析-自上而下分析,构造分析表M的算法是： （1）对文法G的每个产生式A执行第二步和第三步； （2）对于每个终结符aFIRST()，把A加到MA,a中； （3）若FIRST() ，则对任何的b FOLLOW(A)把A加至Ma,b中； （4）把所有无定义的MA,a标上“出错标志” 4.6 LL(1) 分析中的错误处理,第四章 语法分析-自上而下分析,例题与习题解答,例1试构造与下列文法GS等价的无左递归文法。 GS: SSa|Nb|c (1) N Sd|Ne|f (2