ch4自顶向下语法分析.ppt

第四章 语法分析,自顶向下语法分析,自顶向下语法分析,4.1 语法分析概述 4.2 自顶向下分析方法 4.2.1 自顶向下分析的一般过程 4.2.2 自顶向下分析存在的问题 4.2.3 LL(1)分析法 4.2.4 递归子程序法（递归下降分析法）,4.1 语法分析概述,高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。 语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。,图4.1 语法分析程序的作用及其在编译程序中的位置,语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。规则是用文法的产生式来定义的。 根据文法的产生式规则，从开始符号出发，看能否推导出这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。 语法分析器的输出 分析树 错误处理信息,语法分析的方法： 自上而下分析法(Top-down) 基本思想：从文法的开始符号出发，向下推导，尽可能使用各种产生式，推导出与输入串匹配的句子。 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。,4.2.1自顶向下分析的一般过程,给定符号串S，若预测是某一语法成分， 那么可根据该语法成分的文法,设法为S构造一棵语法树. 若成功,则S最终被识别为某一语法成分,即 SL(GZ)其中GZ为某语言成分的文法. 若不成功,则 SL(GZ),8,8,例：已知符号串S=cad 文法GZ: ZcAd Aab|a 求解 SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配.,2.用Z的右部,符号串去匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,9,9,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,分析工作要部分地或全部地退回去重做叫回溯,自顶向下分析方法特点 1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。 2.分析过程是一种试探过程，是尽一切办法(选用不同规则) 设法建立语法树的过程，由于是试探过程，故难免有失败， 所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。,4.2.2 自上而下分析面临的问题,问题1：回溯,什么是回溯?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件：,文法中，对于某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。,回溯带来的问题：,严重的效率低，只有在理论上的意义而无实际意义,问题2：左递归 左递归：是左递归的，如果一个文法中存在某个非终结符号A，使A A。 如果是A A，则称为直接左递归，否则称为间接左递归。,自顶向下分析方法的基本缺点： 不能处理具有左递归性的文法,自顶向下分析为什么不能处理左递归文法？,例：设有文法： E-E+T|T T-T*F|F F-(E)|i 现有输入串i*i+i, 其分析过程是：,失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。,结论 左递归和回溯问题的产生直接与描述语言的文法有关。 因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。,左递归的消除,消除直接左递归： 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： PP PP|,证明的关键步骤： P-P | P- | | | | P- ( | | | | ) P- P, P- | | | | P- P, P- | P,文法 E-E+T | T T-T*F | F F-(E) | i,消除左递归后： E-TE, E-+TE | T-FT, T-*F T| F-(E) | i,文法 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 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P1P | 2P | | nP P1P | 2P | | mP | ,练习：消除下列文法的直接左递归 1.设文法G(S)： S(L)|a S|a LL，S|S 2. G(S)： SSaP|Sf|P PQbP|Q QcSd|e,消除一般左递归,一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。,消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k ; (其中Pj1|2|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,22,22,例：文法Gs为 S Qc|c Q Rb|b R Sa|a,1.检查规则R是否存在直接左递归 RSa|a,2.把R代入Q的有关选择，改写规则Q QSab|ab|b,3.检查Q是否直接左递归,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,23,23,最后得到的文法:,S(abc|bc|c)S S abc S| QSab|ab|b RSa|a,可以看出其中关于Q和R的规则是多余的规则 经过压缩后 S(abc|bc|c)S S abc S| 可以证明改写前后的文法是等价的,应该指出,由于对非终结符的排序不同,最后得到的文法在形 式上可能是不一样的,但是不难证明它们的等价.,消除回溯,消除回溯的思路：假设轮到用A去执行匹配任务, A1| 2|n,若能根据面临的输入符从产生式的多个候选式中选出一个作为全权代表,使得若该候选式与输入串匹配成功,则A与输入串匹配成功, 若该候选式与输入串匹配不成功,则A与输入串匹配不成功, 这样就可以消除回溯。,如何从多个候选式中选出一个全权代表? 例如, AaA | bB | cC a A1| 2|n a 若A的n个候选式中只有一个推出的终结符串的首字符包含a (设为i), 则候选式i可作为A的全权代表。 这就要求匹配前先求出各个候选式所能推出的所有终结符串的首字符, 即候选式的终结首符集FIRST()。,终结首符集FIRST() 令G是一个无左递归文法, 对G的所有非终结符的每个候选式, 定义 FIRST() = a | a， a Vt ， , V* 若 ，则规定 FIRST(),*,*,A1| 2|n FIRST(A)=FIRST(1)FIRST(2),不产生回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai) First(aj) = 当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。,例：设有文法GS: S-Aa|Bb A-d|cA B-b|aB,对S: FIRST(Aa)=d,c, FIRST(Bb)=a,b, FIRST(Aa) FIRST(Bb)= 对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,例如, AabA | aB | ab 改写文法: AaA AbA | B | b,改写第2式: AbA | B AA |,如何使每个非终结符的候选终结首符集互不相交? 方法是提取公共左因子。,提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成 AA | 1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,例：有如下两个产生式： if E then S1 else S2 | if E then S1 提取左因子后： if E then S1 B B else S2 |,文法的两个条件,2、 对文法的任一终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。,1、文法是非左递归的；,练习： 消除文法GS 的左递归和回溯。 GS： SSAe|Ae AdbA|de|d,4.2.3 LL(1)文法,当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件，是不是就一定能进行有效的自上而下分析了？ 回答：若不属于任一非终结符的候选终结首符集, 则可进行有效的LL(1)分析了。然而,消除左递归和提取左因子后, 文法中引进了大量-生成式, 这就引出自动匹配问题。,自动匹配问题 对于文法GE: ETE E+TE | TFT T*FT | F(E) | i 考虑输入串i+i,i + i,IP,E,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,i + i,IP,E,T,E,F,T,i,+,T,E,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,当A面临输入符a时, 若aFIRST(A)且FIRST(A), 则考虑自动匹配问题。 对于上述算术表达式文法,若输入串为i/i, 即使让T自动匹配, “/”仍不能与后面符号匹配, 此时没必要让T自动匹配。,结论: 只有在当前输入符能与A后的第一个终结符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符, 即FOLLOW(A)。,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,特别是，若 ，则规定 FOLLOW(A),即FOLLOW(A)是所有句型中紧跟在 A之后的终结符 或 # 。,FOLLOW(A)的定义,自动匹配条件 当A面临输入符a时,若aFIRST(A)且FIRST(A), 则只有当aFOLLOW(A)时,才使A自动得到匹配。缺少任一条件,均不自动匹配。,若输入符aFIRST(A)且aFOLLOW(A), 则当FIRST(A)时仍需进行试探(回溯)。因此,对于存在-生成式的非终结符A,若要进行不带回溯的自上而下分析,则FIRST(A)与FOLLOW(A)应互不相交。,构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1| 2| n 则 FIRST( i)FIRST( j) (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST(i)FOLLOW(A)= i=1,2,.,n 如果一个文法G满足以上条件，则称该文法G为 LL(1)文法。,对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A 1 | 2 | | n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。,练习：判断文法G是不是LL(1)文法？ G: SaAS|b A-bA|,FIRST集的求法,设XVn Vt，构造FIRST(X)算法如下： (1)若XVt，则 FIRST(X) = X； (2)若X Vn，有Xa,把a加入FIRST(X); 若有X,把加入FIRST(X); (3)若X Vn, 有XY,Y Vn,把FIRST(Y)的 所有非元素都加入FIRST(X); 若有XY1Y2Yk,而Y1Yi1都有, 则把FIRST(Yj) (j=1,2,i)的所有非元素都加入FIRST(X); 特别地,若Y1Yk均有产生式, 则把也加入到FIRST(X)。 (4)重复执行上述过程，直到first(X)不再增大,例：求下题的FIRST集 S-Ap S-Bq A-a A-cA B-b B-dB,first(S) = first(A) first(B)= a,c,b,d first(A) = a,c first(B) = b,d,例：求下题的FIRST集 E -TE E-+TE E- T -FT T-*FT T- F- (E) F- i,例：求下题的FIRST集 E -TE E-+TE E- T -FT T-*FT T- F- (E) F- i,first(E) = first(T)=first(F)= ( ，i first(E) = +， first(T) = ( ，i first(T) = *， first(F) = ( ，i ,求非终结符A的FOLLOW集的算法,对文法中每一A, Vn 1.如果A是开始符号，FOLLOW(A) 2.若有AB (可为空), 则将FIRST()加入FOLLOW(B)。 3.若有AB或AB且 , 则把 FOLLOW(A)加入到FOLLOW(B)。 连续使用上述规则，直到follow(A)不再增大。,例:求下题的FOLLOW集,S-Ap S-Bq A-a A-cA B-b B-dB,Follow(S)=# Follow(A)=p Follow(B)=q,例:求下题的FOLLOW集,1.E -TE 2.E-+TE 3.E- 4.T -FT 5.T-*FT 6.T- 7.F-(E) 8.F-i,例:求下题的FOLLOW集,1.E -TE 2.E-+TE 3.E- 4.T -FT 5.T-*FT 6.T- 7.F-(E) 8.F-i,follow(E) =#，) follow(E) = follow(E) = #，) follow(T) =follow(E)(first(E)-) =#,),+ follow(T) =follow(T) =#，)，+ follow(F) =(first(T)-)follow(T) =*,#,),+,1.如果A是开始符号，FOLLOW(A) 2.若有AB (可为空), 则将FIRST()加入FOLLOW(B)。 3.若有AB或AB且 , 则把 FOLLOW(A)加入到FOLLOW(B)。 连续使用上述规则，直到follow(A)不再增大。,练习：已知文法GS如下，试求出各非终结符的FIRST和FOLLOW集 。 GS：SaD DSTe| TbH HT|,4.4 递归下降分析程序构造,递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过程则通过自上而下一级一级地调用子程序来实现，所以称为递归下降分析法。 思想:对文法中的每个非终结符编写一个处理子程序，处理子程序的代码结构由相应的非终结符的规则右部来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。,限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。尽管这样,它还是许多高级语言的编译系统经常采用的语法分析方法。,基本架构,对于每个非终结符号的产生式Uu1|u2|un处理的方法如下： U( ) ch=当前符号; if(ch是u1符号串的第一个符号) 处理u1 else if(ch是u2符号串的第一个符号) 处理u2 else error() ,对于U的每个右部ui=x1x2xn的处理架构如下： 处理x1的程序； 处理x2的程序； 处理xn的程序； 如果右部为空，则不处理。,对于右部中的每个符号xi 如果xi为终结符号： if(x= 当前输入符号串中的符号) NextCh()；return; else 出错处理 如果xi为非终结符号，直接调用相应的过程： xi(),例:文法G(E): ETE E+TE | TFT T*FT | F(E) | i 几个全局过程和变量： ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号 SYM，IP当前所指的输入符号 ERROR，出错处理子程序,主程序: PROGRAM PARSER; BEGIN ADVANCE; E; IF SYM # THEN ERROR END;,ETE 对应的递归下降子程序为:,PROCEDURE E； BEGIN IF SYM FIRST(TE) THEN T；E ELSE ERROR END；,ETE E+TE | TFT T*FT | F(E) | i,E+TE | 对应的递归下降子程序为:,PROCEDURE E； IF SYM=+ THEN BEGIN ADVANCE； T；E END ELSE IF SYM# AND SYM) THEN ERROR follow(E) = follow(E) = #，),ETE E+TE | TFT T*FT | F(E) | i,TFT对应的递归下降子程序为:,PROCEDURE T； BEGIN IF SYM FIRST(FT) THEN F；T ELSE ERROR END；,ETE E+TE | TFT T*FT | F(E) | i,T*FT | 对应的递归下降子程序为:,PROCEDURE T； IF SYM=* THEN BEGIN ADVANCE； F；T END ELSE IF SYM# AND SYM) AND SYM+ THEN ERROR follow(T) =follow(T) =#，)，+,ETE E+TE | TFT T*FT | F(E) | i,F(E) | i对应的递归下降子程序为:,ETE E+TE | TFT T*FT | F(E) | i,PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,例：已知文法GS如下，用描述语言编写它的递归向下分析程序。 S - aBc |bAB A - aAb |b B - b |,S的递归子程序 void S() if (sym=a) sym=getnext(); B(); if (sym=c) sym=getnext(); else error(); else if (sym=b) sym=getnext(); A();B(); else error(); ,S - aBc |bAB,A的递归子程序 void A() if (sym=a) sym=getnext(); A(); if (sym=b) sym=getnext(); else error(); else if (sym=b) sym=getnext(); else error(); ,A - aAb |b,B的递归子程序 void B() if (sym=b) sym=getnext(); else if (sym!=c ,B - b |,主程序为： Void main() sym=getnext(); S(); if (sym!=#) error(); ,4.5 预测分析程序（LL(1)分析法),一、预测分析程序工作原理 LL(1)分析法又称预测分析法, 是一种不带回溯的非递归自上而下分析法。 LL(1)分析法的基本思想: 从左向右扫描源程序(第一个L),同时从开始符号起生成句子的最左推导(第二个L),并且只需要向前查看一个输入符号,便能唯一确定当前推导应选用的产生式。 一个LL(1)分析器由一张LL(1)分析表(预测分析表)、一个先进后出分析栈和一个控制程序(表驱动程序)组成。,对上图的LL(1)分析器说明如下： (1)输入串是待分析的符号串,它以“#”作为结束标志。(注: #VT但不是文法符号, 是由分析程序自动添加的) (2)分析栈存放分析过程中的文法符号。分析开始时栈底先放一个“#”,再压入文法开始符; 当分析栈中仅剩“#”且输入串指针指向串尾的“#”时, 分析成功。,(3)分析表用一个矩阵M(二维数组) 表示,它概括了文法的全部信息。矩阵的每一行与文法的一个非终结符相关联,而每一列与文法的一个终结符或“#”关联。分析表元素MA,a中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。,Ai iV* MA,a= error,MA,a = Ai 表示当要用A去匹配输入串时，且当前输 入符号为a时，可用A的第i个选择去匹配。 即 当i时，有i a; 当i时，则a为A的后继符号。,MA,a=error 表示当用A去匹配输入串时，若当前输入符号为a， 则不能匹配，表示无Aa,或a不是A的后继符号.,(4) 控制程序根据分析栈栈顶符号x和当 前输入符a决定分析器的动作: 若xa“#”,则分析成功。 若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移, 继续对下一个字符进行分析。 若x为非终结符A,则查分析表MA,a: i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号逆序压栈;若MA,a为A,则只将A自栈顶弹出。 ii.若MA,a为空,则发现语法错误,调用出错处理程序进行处理。,预测分析程序的框图,例：文法GE E:= E +T | T T:= T * F | F F:=(E)|i 请用自顶向下的方法分析是否字符串i+i*iL(GE)。,消除左递归,E:=TE E:=+TE| T :=FT T:=*FT| F:=(E)|i,注：矩阵元素空白表示Error,输入串为: i+i*i#,5. ET TE# + i*i# (出栈，读下一个符号）,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A) 构造分析表MA，a,例4.6 对于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 构造每个非终结符的FIRST和FOLLOW集合：,FIRST(TE) =(,i FIRST(+TE )=+ FIRST(FT ) =(,i FIRST(*FT )=*, FIRST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F)=*,+,),#,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。 1. 对文法G的每个产生式A执行第2步和第3步； 2. 对每个终结符a FIRST()，把A加至MA，a中； 3. 若FIRST()，则对