1、第四章 语法分析自上而下分析,本章内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造预测分析程序LL(1)文法,一、 语法分析的任务与分类 语法分析的任务：对任一给定 w VT*，判断 w L（G） 语法分析器：是一个程序，它按照P，做识别w的工作,词法分析器,语法分析器,编译程序后续部分,符号表,图4.1 语法分析器在编译程序中的地位,二、自上而下分析面临的问题,1、主旨：从文法开始符号出发，自上而下的为输入串建立一棵语法树,S,c,A,d,a,b,a,S cAd,A ab,A a,输入串w :,文法G:,IP,分析过程：,1）w输入串； IP c S扩充；,c a d,2）
2、=c A d； 与 IP c匹配；,3）IP aA扩展，第一式ab, IP a与ab匹配；IP d,但d与b不匹配;,4）报告失败，撤销A的子树，回到A;指针回退到IP a;A还有替换式未试过，而又可能匹配；,语法树的形成,上述分析方法的实现：,每一非终结符对应一个递归子程序，在只生成两个串的文法，过程无须递归，而对生成无数个串的文法，递归是不可避免的；,递归子程序：是一个布尔过程，一旦发现它的某个候选式与输入串匹配，它就按此式扩充语法树，并返回true，指针移过已匹配子串。否则， 返回false，保持原来的语法树和指针不变。,程序实现：,使用记号：input_symbol：当前符号内容inp
3、ut_pointer：输入字符指针使用过程：ADVANCE( )：把input_pointer移到下一输入符号位置，置input_symbol是当前符号内容；,使用两个过程：S( )和A( )，它们送回true or false，决定于它们是否在输入串中找到相应的非终结符所构成的串。,procedure S( );begin if input_symbol =cthen beginADVANCE( );if A( ) then if inputSymbol=d thenbegin ADVANCE( ); return trueend end; return false;end;,procedu
4、re A( );begin isave:= input_pointer; if input_symbol= a then beginADVANCE( );if inputSymbol = b then begin ADVANCE( ); return true; end end/*failure to find ab*/ input_pointer:=isave; if inputSymbol = a thenbegin ADVANCE( ); return true;end else return false;end;,2、困难和问题,文法的左递归回溯用替换符的顺序会影响所接受的语言 如：A
5、 ab|a 改为 A a|ab 难以报告出错的确切位置穷举试探法低效的分析方法,三、自上而下分析的问题解决,消除文法的左递归克服回溯问题,1、区分三种类型的左递归,-直接左递归 即形如：N-N-间接左递归 即形如：N-A A-B B-N,-潜在左递归即形如：N-N 而 ,2、直接左递归的消除,候选式：A-A|, ,A - AA- A | ,消除方法：若：A A| ，其中不以A开头则修改规则为：A A A A|,消去直接左递归后： E TE E +TE| T FT T *FT| F （E）| i,例4.2 文法： E E+T | TT T*F | FF （E）| i,消除方法：若：A A| ，(
6、不以P开头)则修改规则为：A A A A|,3、间接和潜在左递归的消除,代入法 将一个产生式规则右部的中的非终结符N替换为N的候选式。如果N有 n个候选式，右边的重复n次，而且每一次重复都有N的不同候选式来代替N。,例4.3 N-a|Bc|在S-pNq中的代入结果为S-paq|pBcq|pq,间接和潜在左递归通常通过代入能转换为直接左递归,4、消除一个文法的一切左递归算法,对文法G的所有非终结符进行排序按上述顺序对每一个非终结符Pi依次执行:for( j=1； j1|2|m ，那么，要知道哪一个i是获得以a开头的串的唯一替换式。即：选择哪一个i，亦即通过查看第一个（当前）符号来发现合适的替换式
7、i。,怎样选择i？以a为头的i如有多个i以a为头的，这是文法的问题,例如，有产生式：语句-if 条件 then 语句 else 语句 | while 条件 do 语句 |begin 语句表 end,若要寻找一个语句，那么关键字 if，while，begin就提示我们哪一个替换式是仅有可能成功的替换式。,抽象地看问题：若要求不得回溯，文法G（当然G不含左递归）的必要条件是什么，也即对文法有什么要求？,若由i a，选该必中，但若j a，就会导致无法百发百中，解决办法是对文法本身提出要求：“不会出现以上情况”，把这些阐明清楚是用一个FIRST()。,定义FIRST()：FIRST()= a | a,
8、aVT 若 ，规定FIRST(),定理,若一个 AVN，就有许多FIRST(i )，如果A的任何两个候选式i和j，均有FIRST(i ) FIRST(j ) = 意味着，A的每一候选式推导后所得的字符串第一个VT均不同。于是，对输入符号a，如果aFIRST(i )，则a notFIRST(j )，( ji )，因此，对A的展开无疑应选候选式i ，才有可能命中。,消除回溯目的：非终结符A的所有侯选式的首符集两两不相交方法：提取公共左因子,若：A 1|2|n|1|2|m (其中,每个不以开头)那么,可以把这些规则改写成 A A|1| 2|m A1|2|n,四、递归下降分析程序构造,在不含左递归和每
9、个非终结符的所有候选式的终结首符集都两两不相交条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。,1 例4.4 文法 G ：,PROCEDURE E;BEGIN T;EEND;,PROCEDURE T;BEGIN F;TEND;,PROCEDURE E;IF SYM=+THEN BEGIN ADVANCE; T;EEND;,E TE,E +TE|,T FT,PROCEDURE T;IF SYM=*THENBEGIN ADVANCE; F;TEND;,PROCEDURE F;IF SYM=iTHEN A
10、DVANCEELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,面临输入：i1+i2*i3时的分析步骤如下：,T *FT|F （E）| i,i1 + i2 * i3 分析过程：,E,T,E,F,T,i1,PROCEDURE E;BEGIN T;EEND;,PROCEDURE T;BEGIN F;TEND;,PROCEDURE F;IF SYM=iTHEN ADVANCEELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVAN
11、CE ELSE ERROR END ELSE ERROR;,PROCEDURE T;IF SYM=*THENBEGIN ADVANCE; F;TEND;,i1 + i2 * i3 分析过程：,E,T,E,F,T,+,E,T,F,T,*,F,T,i1,i2,i3,PROCEDURE E;IF SYM=+THEN BEGIN ADVANCE; T;EEND;,PROCEDURE T;IF SYM=*THENBEGIN ADVANCE; F;TEND;,2、注意：,有，自动匹配，不会失败无成功/失败消息返回出错位置不确切,五、预测分析程序,问题：用递归子程序描写递归下降分析器，要求实现该编译系统的语
12、言允许递归。,改进：使用一张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程序叫预测分析程序。,1、预测分析程序的工作过程,预测分析程序有四部分,分析程序的动作,程序测定栈顶有X和当前输入符a，由（X，a）决定程序动作，三种可能:1）若X=a=#，分析停止，宣告成功地完成分析；2）若X=a#，则X弹出栈，下移输入指针；3）若XVN，则去查分析表M的元素MX，a，该元素或为X的产生式，或为一个出错元素。,如：MX，a=XUVW,就用WVU（U在顶）替换栈顶的X作为输出；如：MX，a=error，则调用error程序。,对第3）条， XVN，查分析表M的元素MX，a,分析表格式,E
13、 TE E +TE|T FT T *FT |F （E）|i,例4.5 按预测分析程序，对于输入 id+id*id 所作动作如下所示：,1 #E id+id*id#2 #ET id+id*id# ETE3 #ETF id+id*id# TFT4 #ETid id+id*id# Fid5 #ET +id*id# 6 #E +id*id# T7 #ET+ +id*id# E +TE#ET id*id#ETF id*id# T FT,M E, id = E TE,M T, id = T FT,MF, id = F id,匹配，id出栈输入串指针后移,E,id,T,id,F,id,id,id,10 #E
14、Tid id*id# Fid11 #ET *id# 12 #ETF* *id# T*FT13 #ETF id#14 #ETid id# F id15 #ET #16 #E # T # # E 有: X=a=#，分析成功。,id,id,T ,id,*,*,F,id,id,id,T,#,E,#,#,#,结论：输出的产生式就是最左推导的产生式。栈中放右部，等待与匹配；表指出（栈顶，a）时，如何扩充树，出错马上发现。实质：栈：残缺规范句型表：指出VN按哪一条扩充，依赖于VT,上述分析过程生成的语法树：,F (E),F id,F,T ,T ,T *FT,T ,T,T FT,T FT,T,E ,E ,E
15、+TE,E,E TE,E TE,E,#,),(,*,+,id,id + id * id # ：,+,E,T,F,T,*,F,T,id,id,E,T,E,F,T,id,2、分析表的构造,分析表格式：,思路：1）把产生式填到何处？2）按 ? 将产生式分为两种：一种是： a另种是： ,先要构造两个与G有关的集合：FIRST()和FOLLOW(A)；1）定义：若G，V*，S，AVN,2）构造FIRST()先构造FIRST(X),XV。,连续使用以下规则，直至再无终结符，或加入任一FIRST集为止, 若XVT，则 FIRST(X)是X 若XVN ,且X-a，则 a FIRST(X) X-， 则 FIRS
16、T(X) 若XVN ,X-Y,YVN ,则 FIRST(Y) FIRST(X),进而：X-Y1Y2Yi-1YiYk ,YjVN ,1ji-1 FIRST(Yj )，即Y1Y2Yi-1 ，则 当 则 FIRST(X),再进而构造FIRST(X1X2Xn), FIRST(X1)的非终结符加入FIRST()若FIRST(X1)，则FIRST(X2)的所有非终结符加入FIRST()若FIRST(X1), FIRST(X2)，则FIRST(X3)的所有非终结符加入FIRST()最后，若 FIRST(Xi), i=1.n，则 加入FIRST(),3）构造FOLLOW(A)应用下列规则，直到再没有什么加进任
17、一FOLLOW为止, #属于FOLLOW(S)若存在A-B，则FIRST() FOLLOW(B)，除外若有A-B，或 A-B 且FIRST()，则 FOLLOW(B) FOLLOW(A),4）例4.6 已知文法G：E TE T *FT|E +TE| F （E）| iT FT求它的FIRST(),FOLLOW(A),FIRST集的构造：FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E) = + , FIRST(T) = * , , #属于FOLLOW(S),若存在A-B，则FIRST() FOLLOW(B),除外,由得： FOLLOW(E) = # 由
18、得：E TE则 FIRST(E) FOLLOW(T)，即 FOLLOW(T) = + T FT则 FIRST(T) FOLLOW(F) ,即 FOLLOW(F) = * F （E）则 FIRST( ) ) FOLLOW(E) ,即 FOLLOW(E) = # , ) ,FOLLOW集的构造：,FIRST(T) = * , ,FIRST(E) = + , ,即 FOLLOW( F ) = * , , , ,若有A-B，或 A-B 且FIRST(),则FOLLOW(B) FOLLOW(A),FOLLOW( E ) = ) , # FOLLOW( T ) = + FOLLOW( F ) = * ,由
19、得：,E TE得 FOLLOW(E) FOLLOW(E)，,即 FOLLOW( E ) = , ,),#,E TE且 E 得 FOLLOW(E) FOLLOW(T)，,即 FOLLOW( T ) = + , , ,),#,T FT得 FOLLOW(T) FOLLOW(T),即 FOLLOW( T ) = , , ,T FT且 T 得 FOLLOW(T) FOLLOW(F),),#,+,),#,+,FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E) = + , FIRST(T) = * , FOLLOW(E) = FOLLOW(E) = ) , # F
20、OLLOW(T) = FOLLOW(T) = + ，) ，# FOLLOW(F) = * , + , ) , # ,最终构造结果：,注意：FIRST集针对终结符，非终结符，候选式而构造；FOLLOW集只对非终结符构造。,5）构造分析表算法：输入G1文法，输出分析表M,对文法的每一个A- ,做和；对于任aFIRST(),把A- 加进MA，a若FIRST()，则把A- 加进 MA ,b ,b FOLLOW(A)； 若FIRST()，$ FOLLOW(A),则把A-加进 MA ,$,6)例4.7 算法应用于文法G,E TE 填法：FIRST(TE)=FIRST(T)= ( , id M E , (
21、= E TE M E ,id = E TE,E +TE 填法：M E, + = E +TE,E 填法：FOLLOW(E)= ), # M E, ) = E M E , # = E ,六、LL（1）分析法,LL：第一个L表示从左到右扫描输入串， 第二个L表示最左推导（1）：表示分析时每一步只需向前查看一个符号,2、LL（1）文法的条件,1、LL（1）文法一个文法G，若它的分析表M不含多重定义入口，则称它是一个LL（1）文法。,（1）FIRST(） FIRST() = （2）若 ，则 FIRST（） FOLLOW（A）=,文法G是LL(1)的，则对于G的每一个非终结符A的任何两个不同产生式 A -
22、 | ,有：,说明,使用LL(1)文法，一定可以实现不带回溯的自上而下分析；, 对 A- | ，若条件（1）不成立，则FIRST(） FIRST() ，假设， FIRST(） FIRST() = a ,那么，当A面临输入符号a，而a同时属于FIRST(）和 FIRST() ，则分析无法继续进行下去，因为不能确定用哪一个候选式可以保证一定能够得到匹配而不进行回溯。,实质就是分析表的MA, a中包含两条候选式A - A - ,反之，分析表的MA, a中只包含一条候选式则意味着可以进行确定性的无回溯的分析。,对 A- | ，若 ，且条件（2）不成立，则 FIRST（） FOLLOW（A） 假设， F
23、IRST(） FOLLOW(A) = a ,那么，当A面临输入符号a时，若选候选式A - ，则由于a FIRST(）可以使a一定得到匹配；同时，若选候选式A - 也可以满足要求，这是由 ，而a FOLLOW(A)。,实质同样是由于分析表的MA, a中包含两条候选式：A - A - 而这与LL(1)文法的定义互相矛盾。,综上所述，若某文法为LL(1)文法，则该文法一定满足这两个条件，它意味着进行自上而下分析时可以对候选式进行不带回溯的确定性的选择。,因此，不能确定用哪一个候选式可以保证一定能够得到a的后续匹配而不进行回溯。,但是，条件语句文法不能改造成LL(1)文法语句 if 条件 then 语
24、句 else 语句|if 条件 then 语句,例4.8S iCtS|iCtSeS|a C b提公因子后，文法成为：S iCtSS|a SeS| C b, 计算该文法的FIRST集和FOLLOW集为：,FIRST( S ) = i，a FIRST( S)= e，FIRST( C ) = b FOLLOW( S ) = #，e FOLLOW( S)= #，e FOLLOW( C ) = t , 按构造分析表算法，该文法的分析表M为：,文法：S iCtSS|a SeS| C b, FIRST( S) = e，而：FOLLOW(S)= #, e S-填入 M S, # 和 M S, e ，即,候选式 S-填法（SeS| ）：,由上表可见，改造后的文法仍然是非LL(1)文法。（这是因为， M S, e 含有多个候选式;或说：FIRST(eS)FOLLOW(S) = e ）因此，,强制令 M S, e = S-eS （即：坚持把e和最近的t相结合。）从程序语言来看，相当于规定ELSE坚持与最近的THEN相结合。,参考资料,陈火旺，程序设计语言编译原理（第三版）,国防工业出版社，6683冯博琴译，现代编译程序设计，邮电出版社2.2.3，2.2.4Kenneth C. Louden,冯博琴 等译，编译原理与实践，机械工业出版社,
