第5章 自顶向下语法分析方法ppt课件.ppt

第5章 自顶向下语法分析(Top-down Syntax Analysis),语法分析的主要工作： 是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。,语法分析常用的方法： 自顶向下的语法分析和自底向上的语法分析两大类。,自顶向下分析思想,自顶向下的方法： 从文法的开始符号（设为程序）开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。,自顶向下的主要思想： 从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。,自顶向下方法的关键： 是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。,自顶向下的缺点:,在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。 所以自顶向下分析法又分为确定的和不确定的两种：,确定的分析方法需对文法有一定的限制，但由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因此仍是目前常有的方法之一。,不确定的方法即回溯的分析方法。这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因此极少使用。,5.1 确定的自顶向下分析思想,例5.1若有文法GS： S pA S qB A cAd A a 若有输入串w = pccadd.,解：推导过程为：,其相应的语法树见右图：,这个文法的特点： 1每个产生式的右部都由终结符号开始。 2如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。,考察自顶向下的推导过程。,例5.2：,解：自顶向下的推导过程为：,其相应的语法树见右图：,这个文法的特点： 1产生式的右部不全是由终结符号开始。 2如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。 3文法中无空产生式。,小结：,在上述推导过程中，对于产生式中相同左部含有非终结符打头的右部时，在推导中选用哪个产生式是不能直接知道的。,对输入串W=ccap为输入串时，其第一个符号为c，这时从S出发选择S Ap，还是选择S Bq。其根据是要知道 A或B它们是否能推导以c打头的符号串，即它们的首符集是什么。若c是Ap的首符集的元素，且不在Bq的首符集中，则选择S Ap往下推导。反之，若c在Bq的首符集中，不在Ap的首符集中，则选择S Bq往下推导。其它情况为不确定推导或出错。,因此，在推导前有必要求出每个文法符号的首符集。,一.首符集，后继符集与选择集的定义：,定义4-1（首符集定义）：,设G=(VN ，VT ，P，S）是上下文无关文法，是G的任一符号串，则有：,即： FIRST()是从出发推导出的所有符号串首终结符或可能的构成的集合。,这样在文法 G2中，关于S的两个产生式虽然都以非终结符开始，但它们右部符号串可以推导出首符集合互不相交，因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。,例5.3:,若有文法G3S:SaAS dA bASA若有输入串W=abd。考察自顶向下的推导过程。,解：,相应语法树为右图：,当文法中有空产生式时,如例：,小 结：,由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合为： （定义5.2）,定义5.2:,设G=(VN , VT ,P,S)是上下文无关文法，AVN的后继符集合为：,定义5.3：,定义选择符集合SELECT如下： 对于给出上下文无关文法的产生式A,AVN,V*，则,（一） 求FIRST(X)的算法 对每一文法符号X(VNVT），求FIRST(X).(a)若XVT,则令FIRST(X)=X;(b)若XVN,且有产生式Xa.,(aVT)，则令aFIRST(X);(c) 若XVN,有X，则令 FIRST(X);(d)若 XVN, y1, y2,.yi都VN,且有产生式X y1 y2.yn,三种集合的构造算法：,注：三种集合均为终结符集,（二）求 FIRST()的算法（= x1 x2 . xn):,1.若n=0,即=,则令FIRST()=;2.否则，对1in,求FIRST(xi)3.若n=1,则令 FIRST()=FIRST(x1);4.若n2且对一切j=1,2,.,i-1都有FIRST(xj). 则令FIRST(xi )- FIRST(),其中2in; 若对一切 j=1,2,n都有FIRST(xj),则令FIRST(),或：1.把FIRST(x1)中所有非元素加入到FIRST()中，即 FIRST( )=FIRST(x1)- ; 若FIRST(x1)包含有，则把FIRST(x2)的所有非元素加入到 FIRST()中，即FIRST()=FIRST() (FIRST(x2)-); 若FIRST(x1)和FIRST(x2)都包含有 ，则把FIRST(x3)的所有 非元素加到FIRST()中； 照此方法继续，一直到考察到xn。 2.若FIRST(xi ),i= 1,2,n;即每个FIRST(xi )中都有。则将加 到FIRST()中。特别地， 若 = ，则FIRST()=.,(三) 求FOLLOW(A)的算法(A VN):,(a)对文法开始符号S，令# FOLLOW(S).(b)若BA是一个产生式，则令FIRST()- 属于FOLLOW(A);(c) 若BA是一个产生式，或BA是一个产生 式且有FIRST()，则令FOLLOW(B)是 FOLLOW(A)的子集。即把FOLLOW(B)的所有元素 加入到FOLLOW(A)中。(d)反复使用(b)直到每个非终结符的 FOLLOW集合 不再增加为止。,(四) 求SELECT(A)的算法：,例：有文法：ETE E+TE | TFT T*FT | Fi | ( E )求其三种集合。,解：,FIRST(E)=FIRST(T)=FIRST(F)=i, ( FIRST(E)=+,FIRST(T)=*,FOLLOW(E)=FOLLOW(E)= ),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#SELECT(ETE)=FIRST(T)=i,( SELECT(E+TE)=FIRST(+TE)=+SELECT(E)=FIRST()FOLLOW(E)=),#SELECT(TFT)=FIRST(F)=i,(SELECT(T*FT)=FIRST(*FT)=*SELECT(T)=FIRST()FOLLOW(T)=+,),#SELECT(Fi)=FIRST(i)=iSELECT(F（E)=FIRST(i) =(,例：有文法：ETE E+TE| TFT T*FT| Fi| (E)求其三种集合。,例：设有文法GS：SaAS ， Sb ， AbA ， A ,5.2 LL(1)文法的判别,SELECT(SaAS)=FIRST(aAS)=a,SELECT(Sb)=b,SELECT(AbA)=b,SELECT(A)=FIRST()- FOLLOW(A)=a,b ,SELECT(SaAS)SELECT(Sb)=ab= SELECT(AbA)SELECT(A)=ba,b 故文法 GS不是LL(1)文法。,当一个文法是LL(1)文法时，则该文法一定能够采用确定的自顶向下的分析方法进行分析。,5.3文法的等价变换,确定的自顶向下分析要求给定语言的文法必须是 LL(1)形式，然而，不一定每个语言都是LL(1)文法，对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是我们讨论的主要问题。由LL(1)文法的定义可知若文法中含有左递归或含有左公共因子，则该文法肯定不是LL(1)文法，因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换。,更不一般地:,对A 1| 2 | | n提取左公因子为：A A A 1| 2 | | n若在i , j , k中仍含有左公共因子，可再进行提取，这样反复进行提取直到所引进的新非终结符的有关产生式均无左公共因子为止。,结论：1）不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。2）一个文法提取了左公共因子后，只解决了相同左部产生式的右部FIRST集不相交问题。当改写后的文法不含有空产生式，且无左递归时，则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方法进行判断才能确定是否为LL(1)文法。,(2).消除左递归,一个文法含有下列形式的产生式之一时：1)AA , AVN, V*2)AB , BA , A,BVN, ,V*则称该文法是左递归的。然而，一个文法是左递归时，不能采取自顶向下分析法。,消除左递归方法有：a)把直接左递归改写为右递归： 设有文法产生式： AA|. 其中非空， 不以A打头。 可写为：AA AA | 一般情况下，假定关于A的产生式是： AA 1| A 2 | | A m| 1| 2 | | n 其中， i(1im)均不为空， j(1jn)均不以A打头。 则消除直接左递归后改写为： A 1 A | 2 A | | n A A 1 A | 2 A | | m A | ,例：,有文法G(E)：EE +T |T TT*F | F Fi| (E)消除该文法的直接左递归。,解： ETE E+TE| TFT T*FT| Fi| (E),AA|改写为： AA AA | ,b)消除间接左递归：,对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按a)清除左递归。,以文法G6为例： (1)AaB (2)ABb (3)BAc (4)Bd,用产生式(1)，(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式: (1)BaBc (2)BBbc (3)Bd,消除左递归后得到： BaBcB |dB BbcB |再把原来其余的产生式AaB,ABb加入，最终得到等价文法为:(1) AaB(2) ABb(3) B(aBc|d)B(4) BbcB|,c)消除文法中一切左递归的算法,设非终结符按某种规则排序为A1, A2, An 。For i:=1 to n do begin For j:=1 to i-1 do begin 若Aj的所有产生式为： Aj 1| 2 | | n 替换形如Ai Aj 的产生式为： Ai 1 |2 | |n end 消除Ai中的一切直接左递归 end,5.4 不确定的自顶向下分析思想,当文法不满足 LL(1)时，则不能用确定的自顶向下分析，但有时可用不确定的自顶向下分析法，也就是带回溯的自顶向下分析法。 引起回溯的原因是在文法中当关于某个非终结符的产生式有多个候选时，而面临当前的输入符无法确定选用唯一的产生式，从而引起回溯，有三种情况：,带回溯的自顶向下分析是一个试探过程，当分析不成功是则推翻分析退回到适当位置再重新试探其余候选可能的推导。这样需要记录推导每步所选过的产生式，直到把所有可能的推导序列都试空仍不成功才能确定输入串是不是该文法的句子而报错。 由于在编辑程序真正实现时往往是边分析边插入语义动作，因而带回溯的分析代价高，效率很低，在实用编译程序中几乎不用。,(1) 由于相同左部的产生式的右部 FIRST集交集不为空而引起回溯。,(3)由于文法含有左递归而引起回溯。,5.5 确定的自顶向下分析方法,5.5.1 递归下降法（递归子程序法） (Recursive-dewscent parsing) 在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。,(1) 递归下降法的主要思想是：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。,(2) 用程序表示递归子程序的内部结构： 设A是一个非终结符：A1 A2 An,则写 (A) if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示调用处理符号串i的子程序。,对文法加限制：1。任一非终结符B都不是左递归的，否则会产生死循环。2。对A的任意两个右部i , j ,有：first(i)first(j)= First(i)表示i所能导出串的第一个符号的集合。显然，每个i的first(i)是互不相同的，否则则无法判断应执行哪个(i )。,对A的任一右部i 设为： i = y1 y2 yn则定义( i) begin(y1);(y2);(yn) end其中yj可分为下列两种情况（j=1,n):1) yjVT,则 ( yj) if char yj then ERROR else READ(char)2) yjVN,则(yj)表示调用关于yj的递归子程序。,A1 A2 An,例1.,设有文法G: A aBa BbBb | a则有(A) if char=a then (aBa) else ERROR if char=a then begin(a);(B);(a) end else ERROR if char=a then begin if chara then ERROR else READ(char); (B); if chara then ERROR else READ(char) end else ERROR,(B) if char = b then (bBb) else if char=a then (a) else ERROR, if char=b then begin if charb then ERROR else READ(char); (B); if charb then ERROR else READ(char) end else if char=a then if char a then ERROR else READ(char) else ERROR, if char =b then begin (b); (B); (b) end else if char=a then (a) else ERROR,BbBb | a,关于表达式的处理： =| + =| * =| () = i | i(),例2：,E: procedure E; begin T; while char=+ do begin READ(char); T end end,即：ET | E +T TF | T *F FP | (E) P i | i (E),为了处理方便，把上述文法变为： ET+T TF*F FP| (E) Pi| i(E),T: procedure T; begin F; while char = * do begin READ(char); F end end,E: procedure E; begin T; while char=+ do begin READ(char); T end end,F: procedure F; begin if char =( then begin READ(char); E; if char ) then ERROR else READ(char) end else P end,ET+TTF*FFP| (E)P i| i(E),P: procedure P begin if char i then ERROR else begin READ(char); if char =( then begin READ(char); E; if char ) then ERROR else READ(char) end end end,ET+TTF*FFP| (E)P i| i(E),5.5.2 预测分析方法（LL(1) Method）,LL(k)文法是采取确定的自左至右扫描（输入串）和自顶向下分析技术的最大一类文法。LL系指：自左向右扫描（输入串），自上而下进行最左推导。 一般来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下方法进行分析的过程中，如果每步仅利用当前的非终结符（事实上此时它已位于分析栈顶）和至多向前查看k个输入符号就能唯一 决定采取什么动作，那么这个文法称为LL(K)文法。 对于大多数程序设计语言而言。K=0或1就足够了。因此我们将主要讨论k1的情形。,一、LL(1)方法的分析过程,从实现的角度来说，上述替换过程需要花较多的时间，因为它除了把一个候选式替换掉x1,还需要x2 xn统统进行移位处理,这时很麻烦的。我们的处理方法是用栈来保存x1x2 xn,而且是把xn作为栈底， x1作为栈顶，那么上述的替换动作就简单了，只需在栈顶进行替换。即去掉x1把候选式的符号串按逆序方式压入栈中即可。,设分析的当前格局为（x1x2 . xn#, y1y2 . ym#)，其中xi表示句型的前端部分，诸yj表示输入流的后端部分（终结符串）。则可能有下述动作之一：1.替代：当x1VN时，则选相应的候选式去替换x1 。2.匹配：当x1VT时，它与y1进行匹配，其结果为两种可能，如 果匹配成功，则去掉x1和y1（即只指针后移一位）否则报错。3.接受：当格局为(#, #）时，报告分析成功结束。,例：,设有文法：SaBc|bB BbB|d 且给定输入串abbbdc，看其自顶向下的分析过程。,接受,结束,二、LL(1)方法的实现：,LL(1)方法在实现时用到一个LL(1)分析矩阵和一个分析栈以及预测分析总控程序。 分析矩阵的元素MA,a中的下标A为非终结符，a为终结符或句子结束标记#，矩阵元素MA,a的内容为一条关于A的产生式。 它表明当用非终结符A向下推导而当前输入符为a时，所应采用的候选式。当矩阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配。因此应该转向出错处理。 预测分析程序见下图：,流程图：,例：现以表达式文法为例构造预测分析表。,GE: EE+T | T TT*F | F Fi |(E),SELECT(ETE)=(, i SELECT(E+TE)=+ SELECT(E=),# SELECT(TFT)=(, i SELECT(T*FT)=* SELECT(T)=+, ), # SELECT(Fi)=i SELECT(F(E)=( 可知具有相同左部的产生式的SELECT集合互不相交，所以该文法是LL(1)文法。,解：(1)判断GE是否为LL(1)文法,因文法中含有左递归，故必须先消去左递归，使文法 变为： ETE E+TE| TFT T*FT| Fi|(E)求三种集合（前面已举例，图略）最后得到：,（2）构造预测分析表,对每个终结符或#号用a表示，则若aSELECT(A)。令MA,a=A(一般为了简化，取MA,a=)把所有无定义的MA,a标上ERROR（一般在表中用空白表示）。上例的分析表为：,SELECT(ETE)=(,i SELECT(E+TE)=+ SELECT(E=,),# SELECT(TFT)=(, i SELECT(T*FT)=* SELECT(T)=,+,),# SELECT(Fi)=i SELECT(F(E)=(,下面采用预测分析法对输入串i+i*i#进行分析。,1 #E i+i*i# 替代 ETE #ET i+i*i# 替代 TFT #ETF i+i*i# 替代 Fi #ETi i+i*i# 匹配 #ET +i*i# 替代 T #E +i*i# 替代 E+TE,步骤 分析栈 输入队列 动作 所用产生式,步骤 分析栈 输入队列 动作 所用产生式,7 #ET+ +i*i# 匹配 8 #ET i*i# 替代 TFT9 #ETF i*i# 替代 Fi10 #ETi i*i# 匹配 11 #ET *i# 替代 T*FT12 #ETF* *i# 匹配 13 #ETF i# 替代 Fi14 #ETi i# 匹配 #ET # 替代 T16 #E # 替代 E17 # # 接受,实验题目 实验题目：赋值语句的翻译程序设计 作业99页练习：1题,