第四章语法分析自上而下优秀课件.ppt

《第四章语法分析自上而下优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析自上而下优秀课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章语法分析自上而下第1页，本讲稿共60页 一、一、语法分析的任务与分类语法分析的任务与分类l 语法分析的任务：语法分析的任务：对任一给定对任一给定 w Vw VT T*，判断，判断 w Lw L（G G）l 语法分析器：是一个程序，它按照语法分析器：是一个程序，它按照P P，做识别，做识别ww的工作的工作词法分析器词法分析器语法分析器语法分析器编译程序后续部分编译程序后续部分符号表符号表源程序单词符号取下一个单词符号语法分析图图4.1 4.1 语法分析器在编译程序中的地位语法分析器在编译程序中的地位第2页，本讲稿共60页二、自上而下分析面临的问题二、自上而下分析面临的问题1 1、主旨：主旨

2、：从文法开始符号出发，从文法开始符号出发，自上而下自上而下的为输入的为输入串建立一棵语法树串建立一棵语法树l 语法分析的分类：自下而上 自上而下l 例例4.1 4.1 文法文法G1G1：S cAdS cAd A ab|a A ab|a 输入串：输入串：w=cadw=cad，为它建立语法树，为它建立语法树第3页，本讲稿共60页ScAdabaS cAdS cAdA abA abA aA a输入串输入串w:w:文法文法G:G:IPIP分析过程：1 1）ww输入串；输入串；IP IP c c S S扩充；扩充；c a dc a d2 2）=c A d=c A d；与与 IP IP c c匹配；匹配；3

3、 3）IP IP a aA A扩展，第一式扩展，第一式ab,ab,IP IP a a与与abab匹配；匹配；IP IP d d,但但d d与与b b不匹配不匹配;4 4）报告失败，撤销）报告失败，撤销A A的子树，的子树，回到回到A;A;指针回退到指针回退到IP IP a a;A A还有替换式未试过，而又可能还有替换式未试过，而又可能匹配；匹配；语法树的形成语法树的形成第4页，本讲稿共60页l上述分析方法的实现：上述分析方法的实现：每一非终结符对应一个递归子程序，在只生成每一非终结符对应一个递归子程序，在只生成两个串的文法，过程无须递归，而对生成无数个串的文两个串的文法，过程无须递归，而对生成

4、无数个串的文法，递归是不可避免的；法，递归是不可避免的；递归子程序：是一个布尔过程，一旦发现它的递归子程序：是一个布尔过程，一旦发现它的某个候选式与输入串匹配，它就按此式扩充语法树，某个候选式与输入串匹配，它就按此式扩充语法树，并返回并返回truetrue，指针移过已匹配子串。否则，指针移过已匹配子串。否则，返回返回falsefalse，保持原来的语法树和指针不变。，保持原来的语法树和指针不变。第5页，本讲稿共60页l程序实现：程序实现：l使用记号：使用记号：input_symbolinput_symbol：当前符号内容：当前符号内容input_pointerinput_pointer：输入字

5、符指针：输入字符指针l使用过程：使用过程：ADVANCE()ADVANCE()：把：把input_pointerinput_pointer移到下一输入符号位置，移到下一输入符号位置，置置input_symbolinput_symbol是当前符号内容；是当前符号内容；使用两个过程：使用两个过程：S()S()和和A()A()，它们送回，它们送回true or falsetrue or false，决定于它们是否在输入串中找到相应的非终结符所构成的串。决定于它们是否在输入串中找到相应的非终结符所构成的串。第6页，本讲稿共60页procedure S();procedure S();beginbegi

6、n if input_symbol=cthen if input_symbol=cthen begin beginADVANCE();ADVANCE();if A()thenif A()then if inputSymbol=d if inputSymbol=d then thenbeginbegin ADVANCE();ADVANCE();return true return trueendend end;end;return false;return false;end;end;procedure A();procedure A();beginbegin isave:=input_poin

7、ter;isave:=input_pointer;if input_symbol=a then if input_symbol=a then begin beginADVANCE();ADVANCE();if inputSymbol=b thenif inputSymbol=b then begin begin ADVANCE();return true;ADVANCE();return true;end end end end/*failure to find ab*/*failure to find ab*/input_pointer:=isave;input_pointer:=isave

8、;if inputSymbol=a then if inputSymbol=a thenbeginbegin ADVANCE();return true;ADVANCE();return true;endend else return false;else return false;end;end;第7页，本讲稿共60页2 2、困难和问题、困难和问题l文法的左递归文法的左递归l回溯回溯l用替换符的顺序会影响所接受的语言用替换符的顺序会影响所接受的语言 如：如：A ab|a A ab|a 改为改为 A a|ab A a|ab l难以报告出错的确切位置难以报告出错的确切位置l穷举试探法穷举试探法低

9、效的分析方法低效的分析方法第8页，本讲稿共60页三、自上而下分析的问题解决三、自上而下分析的问题解决消除文法的左递归克服回溯问题第9页，本讲稿共60页1 1、区分三种类型的左递归、区分三种类型的左递归-直接左递归直接左递归 即形如：即形如：NNNN-间接左递归间接左递归 即形如：即形如：NANA AB AB BN BN-潜在左递归潜在左递归即形如：即形如：NNNN 而而 第10页，本讲稿共60页2 2、直接左递归的消除、直接左递归的消除候选式：候选式：AAAA|A A A AA A A|消除方法：消除方法：若：若：A AA A|，其中，其中不以不以A A开头开头则修改规则为：则修改规则为：A

10、A AA A A A|A|第11页，本讲稿共60页消去直接左递归后：消去直接左递归后：E TEE TE E+TE|E+TE|T FTT FT T*FT|T*FT|F F （E E）|i|i例例4.2 4.2 文法：文法：E E+T|TE E+T|TT T*F|FT T*F|FF F （E E）|i|i消除方法：消除方法：若：若：A AA A|，(不以不以P P开头开头)则修改规则为：则修改规则为：A A AA A A A|A|第12页，本讲稿共60页3 3、间接和潜在左递归的消除、间接和潜在左递归的消除代入法代入法 将一个产生式规则右部的将一个产生式规则右部的中的非终结符中的非终结符NN替替换

11、为换为NN的候选式。如果的候选式。如果NN有有 n n个候选式，右边的个候选式，右边的重复重复n n次，而且每一次重复都有次，而且每一次重复都有NN的不同候选式来的不同候选式来代替代替NN。例例4.34.3 Na|Bc|Na|Bc|在在SpNqSpNq中的代入结果为中的代入结果为Spaq|pBcq|pqSpaq|pBcq|pq间接和潜在左递归通常通过代入能转换为直接左递归第13页，本讲稿共60页4 4、消除一个文法的一切左递归算法、消除一个文法的一切左递归算法l对文法G的所有非终结符进行排序l按上述顺序对每一个非终结符Pi依次执行:for(j=1；j i-1；j+)将Pj代入Pi的产生式（若可

12、代入的话）；消除关于Pi的直接左递归；l化简上述所得文法。第14页，本讲稿共60页5 5、消除回溯、提左因子、消除回溯、提左因子l回溯原因回溯原因若若当前符号当前符号=a=a，对，对 A A 展开，而展开，而 A A 1 1|2 2|m m，那么，要知道哪一个那么，要知道哪一个i i是获得以是获得以a a开头的串的唯一替换式。开头的串的唯一替换式。即：选择哪一个即：选择哪一个i i，亦即通过查看第一个（当前）符号来发，亦即通过查看第一个（当前）符号来发现合适的替换式现合适的替换式i i。怎样选择怎样选择i i？以以a a为头的为头的i i如有多个如有多个i i以以a a为头的，这是文法的问题为

13、头的，这是文法的问题第15页，本讲稿共60页例如，有产生式：例如，有产生式：语句语句if if 条件条件 then then 语句语句 else else 语句语句|whilewhile 条件条件 do do 语句语句|beginbegin 语句表语句表 end end 若要寻找一个语句，那么关键字 if，while，begin就提示我们哪一个替换式是仅有可能成功的替换式。抽象地看问题：抽象地看问题：若要求不得回溯，文法若要求不得回溯，文法G G（当然（当然G G不含左递归）不含左递归）的必要条件是什么，也即对文法有什么要求？的必要条件是什么，也即对文法有什么要求？第16页，本讲稿共60页若由

14、若由i i a a，选该，选该必中，但若必中，但若j j a a，就会导致无法百发百中，解决办法是对文法本身提就会导致无法百发百中，解决办法是对文法本身提出要求：出要求：“不会出现以上情况不会出现以上情况”，把这些阐明清楚，把这些阐明清楚是用一个是用一个FIRST(FIRST()。l定义定义FIRST(FIRST()：FIRST(FIRST()=a|)=a|a a,aV,aVT T 若若 ，规定，规定FFIRST(IRST()第17页，本讲稿共60页l定理定理若一个若一个 A AV VNN，就有许多，就有许多FIRST(FIRST(i i)，如果，如果A A的的任何两个候选式任何两个候选式i

15、i和和j j，均有，均有FIRST(FIRST(i i)FIRST()FIRST(j j)=)=意味着，意味着，A A的每一候选式的每一候选式推导后所得的字符串推导后所得的字符串第一个第一个V VT T均不同。均不同。于是，对输入符号于是，对输入符号a a，如果，如果a aFIRST(FIRST(i i)，则，则a nota notFIRSTFIRST(j j)，(ji)(ji)，因此，对，因此，对A A的展开无疑应选候选式的展开无疑应选候选式i i，才有可能命中。才有可能命中。第18页，本讲稿共60页l消除回溯目的：消除回溯目的：非终结符非终结符A A的所有侯选式的首符集两两不相交的所有侯选

16、式的首符集两两不相交l方法：提取公共左因子方法：提取公共左因子若若：A A 1 1|2 2|n n|1 1|2 2|mm (其中其中,每个每个不以不以开头开头)那么那么,可以把这些规则改写成可以把这些规则改写成 A A A A|1 1|2 2|mm A A1 1|2 2|n n第19页，本讲稿共60页四、递归下降分析程序构造四、递归下降分析程序构造在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。第20页，本讲稿共60页 E TEE TE

17、E +TE|E +TE|T FT T FT T *FT|T *FT|F F （E E）|i|i每个非终结符所对应的递归子程序如下所示：每个非终结符所对应的递归子程序如下所示：1 1 例例4.44.4 文法文法 G G：第21页，本讲稿共60页PROCEDURE PROCEDURE E;E;BEGINBEGIN T;E T;EEND;END;PROCEDURE PROCEDURE T;T;BEGINBEGIN F;T F;TEND;END;PROCEDURE PROCEDURE E E;IF IF SYM=+THEN SYM=+THEN BEGINBEGIN ADVANCE;ADVANCE;T;

18、E T;EEND;END;E TEE TEE +TE|E +TE|T FTT FT第22页，本讲稿共60页PROCEDURE TPROCEDURE T;IF SYM=*THENIF SYM=*THENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEND;END;PROCEDURE F;PROCEDURE F;IF SYM=iTHEN ADVANCEIF SYM=iTHEN ADVANCEELSEELSE IF SYM=(THEN IF SYM=(THEN BEGIN BEGIN ADVANCE;ADVANCE;E;E;IF SYM=)THEN ADVANCE IF SYM

19、=)THEN ADVANCE ELSE ERROR ELSE ERROR END END ELSE ERROR;ELSE ERROR;面临输入：面临输入：i i1 1+i+i2 2*i*i3 3时的分析步骤如下：时的分析步骤如下：T*FT|T*FT|F F （E E）|i|i第23页，本讲稿共60页i i1 1+i+i2 2*i*i3 3 分析过程：分析过程：ETEFTi i1 1PROCEDURE PROCEDURE E;E;BEGINBEGIN T;E T;EEND;END;PROCEDURE PROCEDURE T;T;BEGINBEGIN F;T F;TEND;END;PROCEDUR

20、E F;PROCEDURE F;IF SYM=iTHEN ADVANCEIF SYM=iTHEN ADVANCEELSEELSE IF SYM=(THEN IF SYM=(THEN BEGIN BEGIN ADVANCE;ADVANCE;E;E;IF SYM=)THEN ADVANCE IF SYM=)THEN ADVANCE ELSE ERROR ELSE ERROR END END ELSE ERROR;ELSE ERROR;PROCEDURE TPROCEDURE T;IF SYM=*THENIF SYM=*THENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEN

21、D;END;第24页，本讲稿共60页i1+i2*i3 分析过程：ETEFT+ETFT*FTi1i i2 2i i3 3PROCEDURE PROCEDURE E E;IF IF SYM=+THEN SYM=+THEN BEGINBEGIN ADVANCE;ADVANCE;T;E T;EEND;END;PROCEDURE TPROCEDURE T;IF SYM=*THENIF SYM=*THENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEND;END;第25页，本讲稿共60页2 2、注意：、注意：有有，自动匹配，不会失败，自动匹配，不会失败无成功无成功/失败消息返回失败

22、消息返回出错位置不确切出错位置不确切第26页，本讲稿共60页五、预测分析程序五、预测分析程序问题：用递归子程序描写递归下降分析器，要求实现该编译系统的语言允许递归。改进：使用一张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程序叫预测分析程序。第27页，本讲稿共60页 a a 总控程序预测分析表Mx x#输 出栈输入串1 1、预测分析程序的工作过程、预测分析程序的工作过程第28页，本讲稿共60页l预测分析程序有预测分析程序有四四部分部分求值X:=ABD条件控制WHILE ABD DO SIF ABD THEN S1 ELSE S21）一个）一个输入输入：含有要分析的串，右端有：

23、含有要分析的串，右端有#2）一个）一个栈栈：栈底是：栈底是#，栈内是一系列文法符号。，栈内是一系列文法符号。开始时，开始时，#和和S先进栈先进栈3）分析表分析表：二维数组：二维数组MA，a，其中，其中a VT；A VN4）输出输出：根据分析表内元素做规定的语义动作：根据分析表内元素做规定的语义动作第29页，本讲稿共60页l分析程序的动作分析程序的动作 程序测定栈顶有程序测定栈顶有X X和当前输入符和当前输入符a a，由（，由（X X，a a）决定程序动作，三种可能决定程序动作，三种可能:1 1）若）若X=a=#X=a=#，分析停止，宣告成功地完成，分析停止，宣告成功地完成分析；分析；2 2）若

24、）若X=a#X=a#，则，则X X弹出栈，下移输入指针；弹出栈，下移输入指针；3 3）若）若XVXVNN，则去查分析表，则去查分析表MM的元素的元素MXMX，aa，该元素或为该元素或为X X的产生式，或为一个出错元素。的产生式，或为一个出错元素。第30页，本讲稿共60页如：如：MXMX，a=Xa=XUVWUVW,就用就用WVUWVU（U U在顶）替在顶）替换栈顶的换栈顶的X X作为输出；作为输出；如：如：MXMX，a=errora=error，则调用，则调用errorerror程序。程序。对第对第3 3）条，）条，XVXVNN，查分析表，查分析表MM的元素的元素MXMX，aa第31页，本讲稿共

25、60页l分析表格式分析表格式id+*()#EE TEE TEEE+TEE E TT FTT FTTT T*FTT T FF idF (E)E TE E+TE|T FT T*FT|F （E）|i第32页，本讲稿共60页l例4.5 按预测分析程序，对于输入 id+id*id 所作动作如下所示：栈输 入输 出1#E id+id*id#1#E id+id*id#2#E2#ET id+id*id#ETET id+id*id#ETE3#ETF id+id*id#T3#ETF id+id*id#TFTFT4#ETid id+id*id#F4#ETid id+id*id#Fidid5#ET +id*id#5#

26、ET +id*id#6#E +id*id#T6#E +id*id#T7#ET+id*id#E7#ET+id*id#E+TE+TE8 8#ET id*id#ET id*id#9 9#ETF id*id#T FT#ETF id*id#T FTM E,id=E TEM T,id=T FT 左部出栈，右部反序压栈!MF,id=F id匹配，匹配，id出栈出栈输入串指针后移输入串指针后移XaE EididT TididF Fidididididid第33页，本讲稿共60页栈输 入输 出10#ETid id*id#Fid10#ETid id*id#Fid11#ET *id#11#ET *id#12#ETF

27、*id#T12#ETF*id#T*FT*FT13#ETF id#13#ETF id#14#ETid id#F14#ETid id#F id id15#ET#15#ET#16#E#T16#E#T1717#E#E 有有:X=a=#:X=a=#，分析成功。，分析成功。ididididXaT T idid*F FididididididT T#E E#第34页，本讲稿共60页结论：结论：输出的产生式就是最左推导的产生式。栈中放右输出的产生式就是最左推导的产生式。栈中放右部，等待与部，等待与匹配；匹配；表指出（栈顶，表指出（栈顶，a a）时，如何扩充树，出错马上发）时，如何扩充树，出错马上发现。现。实质

28、：实质：栈：残缺规范句型栈：残缺规范句型表：指出表：指出V VNN按哪一条扩充，依赖于按哪一条扩充，依赖于V VT T上述分析过程生成的语法树：第35页，本讲稿共60页F (E)F idFT T T*FTT TT FTT FTTE E E+TEEE TEE TEE#)(*+idid+id*id#id+id*id#：+ETFT*FTididididETEFTidid第36页，本讲稿共60页2、分析表的构造u分析表格式：分析表格式：id+*()#EE TEE TEEE+TEE E TT FTT FTTT T*FTT T FF idF (E)u思路：思路：1 1）把产生式填到何处？）把产生式填到何处

29、？2 2）按）按?将产生式分为两种：将产生式分为两种：一种是：一种是：a a另种是：另种是：第37页，本讲稿共60页u先要构造两个与先要构造两个与G G有关的集合：有关的集合：FIRST(FIRST()和和FOLLOW(A)FOLLOW(A)；1 1）定义：若）定义：若G G，V V*，S S，AVAVNN FIRST(FIRST()=a|)=a|a a,aV,aVT T 若若 ，规定，规定FFIRST(IRST()FOLLOW(A)=a|S FOLLOW(A)=a|S AaAa，aVaVT T，,VV *第38页，本讲稿共60页2 2）构造）构造FIRST(FIRST()l先构造先构造FIR

30、ST(X),XVFIRST(X),XV。连续使用以下规则，直至再无终结符，连续使用以下规则，直至再无终结符，或或加入任一加入任一FIRSTFIRST集为止集为止第39页，本讲稿共60页 若若XVXVT T，则，则 FIRST(X)FIRST(X)是是XX 若若XVXVNN,且且XaXa，则，则 a FIRST(X)a FIRST(X)XX，则则 FIRST(X)FIRST(X)若若XVXVNN,XY,XY,YVYVNN,则则 FIRST(Y)FIRST(Y)FIRST(X)FIRST(X)进而：进而：XYXY1 1Y Y2 2YYi-1i-1Y Yi iYYk k,Y,Yj jVVN N ,1

31、ji-1,1ji-1 FIRST(Y FIRST(Yj j)，即，即Y Y1 1Y Y2 2YYi-1i-1 ，则，则 当当 则则 FIRST(X)FIRST(X)第40页，本讲稿共60页l再进而构造再进而构造FIRST(XFIRST(X1 1X X2 2X Xn n)FIRST(XFIRST(X1 1)的的非非终结符终结符加入加入FIRST(FIRST()若若FIRST(XFIRST(X1 1)，则则FIRST(XFIRST(X2 2)的所有非的所有非终结符加入终结符加入FIRST(FIRST()若若FIRST(XFIRST(X1 1),),FIRST(XFIRST(X2 2)，则则FIRS

32、T(XFIRST(X3 3)的所有非的所有非终结符加入终结符加入FIRST(FIRST()最后，若最后，若 FIRST(X FIRST(Xi i),),i=1.n i=1.n，则，则 加入加入FIRST(FIRST()第41页，本讲稿共60页3 3）构造）构造FOLLOW(A)FOLLOW(A)应用下列规则，直到再没有什么加进任一应用下列规则，直到再没有什么加进任一FOLLOWFOLLOW为止为止#属于属于FOLLOW(S)FOLLOW(S)若存在若存在AAB B，则则FIRST(FIRST()FOLLOW(B)FOLLOW(B)，除除外外若有若有AAB B，或，或 A AB B 且且FIRS

33、T(FIRST()，则则 FOLLOW(B)FOLLOW(A)FOLLOW(B)FOLLOW(A)第42页，本讲稿共60页4 4）例）例4.64.6 已知文法已知文法G G：E TE E TE T*FT|T*FT|E+TE|E+TE|F F （E E）|i|iT FTT FT求它的求它的FIRST(FIRST(),FOLLOW(A),FOLLOW(A)FIRST集的构造：集的构造：FIRST(E)=FIRST(T)=FIRST(F)=(,i FIRST(E)=+,FIRST(T)=*,第43页，本讲稿共60页#属于属于FOLLOW(S)FOLLOW(S)若存在若存在AAB B，则，则FIRST

34、(FIRST()FOLLOW(B),)FOLLOW(B),除除外外由由得：得：FOLLOW(E)=#由由得：得：E TEE TE则则 FIRST(E)FIRST(E)FOLLOW(T)，即即 FOLLOW(T)=+T FTT FT则则 FIRST(T)FIRST(T)FOLLOW(F),即即 FOLLOW(F)=*F F （E E）则则 FIRST(FIRST()FOLLOW(E),即即 FOLLOW(E)=#,)FOLLOW集的构造：集的构造：FIRST(T FIRST(T)=*,)=*,FIRST(E FIRST(E)=+,)=+,第44页，本讲稿共60页即即 FOLLOW(F)=*,若有

35、若有AAB B，或，或 A AB B 且且FIRST(FIRST(),),则则FOLLOW(B)FOLLOW(A)FOLLOW(B)FOLLOW(A)FOLLOW(E)=),#FOLLOW(T)=+FOLLOW(F)=*由由得得：E TEE TE得得 FOLLOW(E)FOLLOW(E)，即即 FOLLOW(E )=,)#E TEE TE且且 E E 得得 FOLLOW(E)FOLLOW(E)FOLLOW(T)，即即 FOLLOW(T)=+,)#T FTT FT得得 FOLLOW(T)FOLLOW(T)FOLLOW(T),即即 FOLLOW(T )=,T FTT FT且且 T T 得得 FOL

36、LOW(T)FOLLOW(F),)#+)#+第45页，本讲稿共60页FIRST(E)=FIRST(T)=FIRST(F)=(,i FIRST(E)=+,FIRST(T)=*,FOLLOW(E)=FOLLOW(E)=),#FOLLOW(T)=FOLLOW(T)=+，)，#FOLLOW(F)=*,+,),#最终构造结果：最终构造结果：注意：注意：注意：注意：FIRSTFIRSTFIRSTFIRST集针对终结符，非终结符，候选式而构造；集针对终结符，非终结符，候选式而构造；集针对终结符，非终结符，候选式而构造；集针对终结符，非终结符，候选式而构造；FOLLOWFOLLOWFOLLOWFOLLOW集只

37、对非终结符构造。集只对非终结符构造。集只对非终结符构造。集只对非终结符构造。第46页，本讲稿共60页5 5）构造分析表）构造分析表算法：输入算法：输入G1G1文法，输出文法，输出分析表分析表MM对文法的每一个对文法的每一个AA,做做和和；对于任对于任aFIRST(aFIRST(),),把把AA 加进加进MAMA，a a若若F FIRST(IRST()，则把，则把AA 加进加进 MA,b,b MA,b,b FOLLOW(A)FOLLOW(A)；若若F FIRST(IRST()，$FOLLOW(A),$FOLLOW(A),则把则把AA加进加进 MA,$MA,$第47页，本讲稿共60页6)6)例例4

38、.74.7 算法应用于文法算法应用于文法G G E TE E TE 填法：填法：FIRST(TE)=FIRST(T)=(,id M E,(=E TE M E,id=E TE E +TE E +TE 填法：填法：M E,+=E +TE 第48页，本讲稿共60页E E 填法：填法：FOLLOW(E)=),#M E,)=E M E,#=E 第49页，本讲稿共60页六、六、LLLL（1 1）分析法）分析法lLL：第一个L表示从左到右扫描输入串，第二个L表示最左推导l（1）：表示分析时每一步只需向前查看一个符号第50页，本讲稿共60页2 2、LLLL（1 1）文法的条件）文法的条件1 1、LLLL（1

39、1）文法）文法一个文法一个文法G，若它的分析表，若它的分析表M不含多重定义入口，则称它是不含多重定义入口，则称它是一个一个LL（1）文法）文法。（1 1）FIRST(FIRST(）FIRST(FIRST()=)=（2 2）若）若 ，则，则 FIRST FIRST（）FOLLOW FOLLOW（A A）=文法文法G G是是LL(1)LL(1)的，则对于的，则对于G G的每一个非终结符的每一个非终结符A A的任何两个不同产生式的任何两个不同产生式 A A|,有：有：第51页，本讲稿共60页 使用LL(1)文法，一定可以实现不带回溯的自上而下分析；对对 A A|，若条件（若条件（1 1）不成立，）不

40、成立，则则FIRST(FIRST(）FIRST(FIRST()，假设，假设，FIRST(FIRST(）FIRST(FIRST()=a)=a 第52页，本讲稿共60页那么那么，当，当A A面临输入符号面临输入符号a a，而，而a a同时属于同时属于FIRST(FIRST(）和）和 FIRST(FIRST()，则分析无法继续进行下，则分析无法继续进行下去，因为不能确定用哪一个候选式可以保证一定去，因为不能确定用哪一个候选式可以保证一定能够得到匹配而不进行回溯。能够得到匹配而不进行回溯。实质实质就是分析表的就是分析表的MA,aMA,a中包含两条候选式中包含两条候选式A A A A 反之，反之，分析表

41、的分析表的MA,aMA,a中只包含一条候选式中只包含一条候选式则意味着可以进行确定性的无回溯的分析。则意味着可以进行确定性的无回溯的分析。第53页，本讲稿共60页对对 A A|，若若 ，且条件（，且条件（2 2）不成立，）不成立，则则 FIRSTFIRST（）FOLLOW FOLLOW（A A）假设，假设，FIRST(FIRST(）FOLLOW(A)FOLLOW(A)=a =a 那么，当那么，当A A面临输入符号面临输入符号a a时时，若选候选式若选候选式A A ，则由于，则由于a FIRST(a FIRST(）可以）可以使使a a一定得到匹配；一定得到匹配；同时，若选候选式同时，若选候选式A

42、 A 也可以满足要求，也可以满足要求，这是由这是由 ，而，而a FOLLOW(A)a FOLLOW(A)。第54页，本讲稿共60页实质实质同样是由于分析表的同样是由于分析表的MA,aMA,a中包含两条候选式：中包含两条候选式：A A A A 而这与而这与LL(1)LL(1)文法的定义互相矛盾。文法的定义互相矛盾。综上所述，综上所述，若某文法为若某文法为LL(1)LL(1)文法，则该文文法，则该文法一定满足这两个条件，它意味着进行自上而下分法一定满足这两个条件，它意味着进行自上而下分析时可以对候选式进行不带回溯的确定性的选择。析时可以对候选式进行不带回溯的确定性的选择。因此，不能确定用哪一个候选

43、式可以保因此，不能确定用哪一个候选式可以保证一定能够得到证一定能够得到a a的后续匹配而不进行回溯。的后续匹配而不进行回溯。第55页，本讲稿共60页但是，条件语句文法不能改造成但是，条件语句文法不能改造成LL(1)LL(1)文法文法语句语句 if if 条件条件 then then 语句语句 else else 语句语句|if|if 条件条件 then then 语句语句例例4.8 S iCtS|iCtSeS|a C b提公因子后，文法成为：提公因子后，文法成为：S iCtSS|a SeS|C b 计算该文法的计算该文法的FIRSTFIRST集和集和FOLLOWFOLLOW集为：集为：第56页

44、，本讲稿共60页abeit#SS aSiCtSS S S eS CC bFIRST(S)=iFIRST(S)=i，a a FIRST(SFIRST(S)=e)=e，FIRST(C)=b FIRST(C)=b FOLLOW(S)=#FOLLOW(S)=#，e e FOLLOW(SFOLLOW(S)=#)=#，e e FOLLOW(C)=t FOLLOW(C)=t 按构造分析表算法，该文法的分析表按构造分析表算法，该文法的分析表MM为：为：文法：文法：S iCtSS|a SeS|C b第57页，本讲稿共60页abeit#SS aSiCtSS SS S eSS CC b FIRST(SFIRST(S

45、)=e)=e，而：而：FOLLOW(SFOLLOW(S)=#,e)=#,e SS填入填入 M S M S,#,#和和 M S M S,e,e，即，即候选式候选式 S S填法（填法（SeS|SeS|）：第58页，本讲稿共60页由上表可见，改造后的文法仍然是非由上表可见，改造后的文法仍然是非LL(1)LL(1)文文法。法。（这是因为，（这是因为，M S M S,e ,e 含有多个候选式含有多个候选式;或说：或说：FIRST(eS)FOLLOW(SFIRST(eS)FOLLOW(S)=e )=e ）因此，因此，强制令强制令 M SM S,e =S,e =SeS eS（即：坚持把（即：坚持把e e和最

46、近的和最近的t t相结合。）相结合。）从程序语言来看，相当于规定从程序语言来看，相当于规定ELSEELSE坚持与坚持与最近的最近的THENTHEN相结合。相结合。第59页，本讲稿共60页参考资料参考资料l陈火旺，程序设计语言编译原理（第三版）陈火旺，程序设计语言编译原理（第三版）,国防国防工业出版社，工业出版社，66836683l冯博琴译，现代编译程序设计，邮电出版社冯博琴译，现代编译程序设计，邮电出版社2.2.32.2.3，2.2.42.2.4lKenneth C.Louden,Kenneth C.Louden,冯博琴冯博琴 等译，编译原理与实等译，编译原理与实践，机械工业出版社践，机械工业出版社第60页，本讲稿共60页