第四章 语法分析一.ppt

1、1,2,编译原理,LL(1)分析,语法分析算法之,3,语法分析器,编译程序 后续部分,符号表,扫描器,原程序,语法分析树,单词符号,取单词,语法分析及语法分析程序 (语法分析程序又称分析器),语法分析器的地位和结构,4,序(语法分析程序的功能),语法分析程序又简称为分析器，它以单词串形式的源程序作为输入或分析的对象，其基本任务是：根据程序设计语言的语法规则(即定义该语言的前后文无关文法)，分析源程序的语法结构，即分析如何由这些单词组成该源程序的各种语法成分(如下标变量、函数、各种表达式、各程序语句等等)，并在分析过程中进行语法正确性检查，产生内部形式的中间代码，供编译程序后续阶段处理。,5,序

2、(语法分析程序的功能),目前，已存在许多语法分析方面的方法，但就产生语法树的方向而言，可大致把它们分为自顶向下分析和自底向上分析两大类。 自顶向下分析:介绍递归下降分析法和预测分析法；自底向上分析:介绍算符优先分析法和LR分析法。这几种分析方法各有优缺点。但都是当今编译程序构造的实用方法。,6,4.1 自顶向下的语法分析,定义 自顶向下分析法也称面向目标的分析方法，所谓自顶向下的语法分析，是指对于给定输入串w，试图为其构造一个从文法开始符号到w的最左推导 ，或为w自上而下地构造一棵以S为根结点的语法树。如果这一尝试得到成功，则证明w是相应文法的一个句子；反之，则不是。,7,4.1 自顶向下的语

3、法分析,自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。 不确定的方法即带回溯的分析方法，这种方法实际上是一种举穷的试探方法，因此效率低，代价高，因而极少使用。,8,4.1 自顶向下的语法分析,在进行自顶向下的语法分析时，通常有下列两个障碍须加以解决： (1)由于采取了最左推导，故当相应文法G中含有左递归的非终结符号时，便会使语法分析过程陷入循环不已的状况。 (2)采用最左推导以实现对符号串w的匹配，实际上是一个用文法产生式的诸候选式反复进行试探的过程，这势必会出现大量的回溯

4、，从而导致语法分析效率的大幅度下降。因此，欲实现自顶向下的语法分析，其首要任务是改造程序设计语言的文法，以消除其中的左递归和避免回溯的出现。,9,主要内容,自 顶 向 下 的 语 法 分 析,1.消除文法的左递归,2.回溯的消除及LL(1)文法,3.First和Follow集的定义和计 算,4.递归下降分析法,5.预测分析法,6.非LL(1)文法的改造,10,自 顶 向 下 分 析 的 一 般 过 程 和 问 题,11,1.文法的定义,定义2.1(前后文无关文法): 文法G定义为四元组（VN，VT，P，S） VN ：非终结符集 VT ：终结符集 P： 产生式（规则）集合 U= S： 开始符号

5、SVN VNVT= V=VNVT，称为文法G的文法符号集合,12,2.句型、句子、语言的定义,句型 有文法G S，若S x，则称x是文法G的句型。 句子 有文法G S ，若S x ，且xVT*，则称x是文法G的句子。 例：G S ： S0S1， S01 S 0S1 00S11 000S111 00001111,13,3.上下文无关文法的句型推导,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。由规范推导所得的句型称为规范句型 自顶向下分析:最左推导,14,4.句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构

6、造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,15,4.句型的分析,分析算法分类： 自顶向下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。 自底向上分析法：从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号。,16,5.算术表达式的文法及语法分析,文法GE: E E+T|T T T*F|F F (E)| I,17,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式:

7、 a+b*C,最左推导：E,E,语法树,18,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+T,E,+,T,E,语法树,19,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+T,E,+,T,T,E,语法树,20,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+T,E,+,T,T,F,E,语法树,21,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+Ta+T,E,+,T,T,F,a,E,语法

8、树,22,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+TA+Ta+T*F,E,+,T,T,T,*,F,F,a,E,语法树,23,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+TA+Ta+T*F a+F*F,E,+,T,T,T,*,F,F,F,a,E,语法树,24,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+TA+Ta+T*F a+F*Fa+b*F,E,+,T,T,T,*,F,F,F,a,b,E,语法树,25,5.算术表

9、达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+TA+Ta+T*F a+F*Fa+b*Fa+b*c,E,+,T,T,T,*,F,F,F,a,b,c,E,语法树,26,5.算术表达式的文法及语法分析(自顶向下的语法分析),表达式: a+b*C,最左推导：EE+TT+TF+Ta+Ta+T*F a+F*Fa+b*Fa+b*c,E,+,T,T,T,*,F,F,F,a,b,c,E,语法树,27,6.自上而下语法分析的一般过程,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SSS (1)cAdcAd (2) a b 推导过程：

10、S cAd cabd (3),28,从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。,文法G：S cAd A ab |a 识别输入串w=cad 试探推导过程：S cAd cabd,SSS cAdcAd a b 回朔:试探推导过程：S cAd cad S c A d,a,29,7.左递归文法导致分析过程循环不已,GS: SSa Sb L=ban | n1 W=baa S 试探推导 试探推导,b,S,S,a,S,a,a,循环不已,30,8.自顶向下语法分析存在的问题,1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：V 1 |2 | N

11、，那么如何确定用哪个右部i去替代V？ 2）如果文法是左递归的，则必然导致分析过程循环不已(死循环) 。,31,8.自顶向下语法分析存在的问题,自顶向下分析的主要问题及解决途经：1、文法的左递归： 消除左递归。2、文法的多个候选产生式： 提取左因子、前看若干个单词、回溯。3、文法的二义性： 消除文法的二义性。,32,4.1.1 消除文法的左递归,关于左递归 非终结符A的规则 直接左递归 若 A A | 、 V* 且不以A开头 一般 左递归 SAa ASb Ab,33,1)消除直接左递归 设文法是已化简的 形如：A A | 非， 不以A打头 改写为： A A A A| ,4.1.1 消除文法的左递

12、归,34,证明文法A A | 与 文法 A A A A| 等价 证明: A A A A A A A A A A A A A ,4.1.1 消除文法的左递归,35,例: GE: E E+T|T T T*F|F F (E) | I 改写后GE: E TE E +TE| T FT T *FT| F (E) | I,4.1.1 消除文法的左递归,36,文法 GE ET EAT TF TMF F(E) i (4.1) A+ - M* / 改写为 ETE E ATE | TFT T MFT | F(E)|i A+|- M *|/,4.1.1 消除文法的左递归,(4.1) ,37,4.1.1 消除文法的左递

13、归,一般地,如果一个文法GS（VN，VT，P，S）中的A产生式具有如下的形式： 其中每个i均不以A打头，则A是一个直接左递归的非终结符号。为消除此种左递归，可引人一个新的非终结符号A，并将上述A产生式改写为 即可。,38,2) 消除文法左递归的矩阵方法(一次性消除文法的所有左递归) 设文法的非终结符为 X1, X2, , Xn, 其中,Xi的产生式可分为以VN符和VT符打头的两类.类似正规式方法,将|改写为+,有 Xi=X11i+X22i+Xnni+i 其中, i 是以VT符打头的产生式之和, Ki 可以为,4.1.1 消除文法的左递归,39,4.1.1 消除文法的左递归,这样,文法G可表示为

14、：,或: X=XA+B,X,A,B,X,40,4.1.1 消除文法的左递归,该方程有解: X=BA* ,为得到A*,由,Z,41,则有: X=BZZ=I+AZ 其中X的产生式以VT符打头,而Z的产生式以ijV* 打头,因此将不含左递归。 注意,由此所得的文法含有无用符号和无用产生式,需化简。,4.1.1 消除文法的左递归,42,4.1.1 消除文法的左递归,例4.1 SSa | Ab | a ASc 相应的矩阵为:,43,4.1.1 消除文法的左递归,展开矩阵,得 S aZ11 A aZ12 Z11aZ11 |cZ21| Z12 aZ12 |cZ21 Z21 bZ11 Z22 bZ12 | 文

15、法中含有无用产生式,消除之.最后,有 S aZ11Z11aZ11 |cZ21| Z21 bZ11,44,消除一般左递归要求文法:1.无回路(A A ) 2.无空产生式,（1） 以某种顺序将文法非终结符排列A1 ,A2, ,An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai-1r| 2r| k r替代 形如Ai- Ajr的规则,其中 Aj- 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由2得到的文法。,另一种方法,45,4.1.2 回溯的消除及LL(1)文法,一、为解决回溯问题,我们从句子的最左推导

16、开始讨论: 设G=(VN,VT,P,S) 为一CFG, w=a1a2an是VT上的符号串,现需判明w是否是L(G)中的句子。为此,从S开始进行最左推导。设经若干步推导后我们得到:,46,4.1.2 回溯的消除及LL(1)文法,讨论(续) 注意,i=1时,w1 =,A=S。,47,4.1.2 回溯的消除及LL(1)文法,讨论(续) 由假设可知,到目前为止,w的前缀w1已匹配,现在需对A进行推导. 为得到w的剩余部分aiai+1an.由最左推导的定义,考虑A的所有产生式:,48,讨论(续) 对于当前输入符号ai,若只有一个 j (称为候选式)使得从j出发可以推导出一个以ai打头的符号串: j ai

17、 而其它的k(kj), k都推导不出以ai打头的符号串,则选定产生式Aj就是唯一可行的推导, 即 wL(G) ：选Aj正确; wL(G) ：选任何产生式均不能匹配； 显然,若P中产生式能满足上述要求,则回溯可消除。,4.1.2 回溯的消除及LL(1)文法,49,讨论总结 由前面的讨论可知，要实现无回溯的自顶向下分析，文法必须满足一定的条件。为导出这些条件， 我们定义候选式的终结首符集(FIRST()集) FIRST()集的定义: 设G=(VN ,VT ,S ,P)是上下文无关文法 First（）=a| a,aVT, , V* 若 则规定FIRST（）。,4.1.2 回溯的消除及LL(1)文法,

18、50,4.1.2 回溯的消除及LL(1)文法,讨论总结 消除回溯的条件 若对于A-产生式的每个候选式i(i=1,2,m)都推不出 , 且FIRST(j)与 FIRST(i )(ij)互不相交,则当正扫描的当前输入符号为aiFIRST(j)时,唯一可用于推导的产生式只能是: A j,51,4.1.2 回溯的消除及LL(1)文法,讨论总结 消除回溯的条件 例如,文法G1S: SAA AaAb | *, A-产生式有两个候选式, 且 FIRST(aAb)=a FIRST(*)=* 两集不相交,设输入串为aa*bb*,其最左推导为 SAA(a)aAbA(a)aaAbbA(*)aa*bbA(*) aa*

19、bb* (#) 注:上面每步推导右侧括号内为当前扫描的输入符号,#为结束符。,52,4.1.2 回溯的消除及LL(1)文法,消除回溯的条件 我们得到了一个无回溯的条件: FIRST(i) FIRST(j)=。 ij,53,4.1.2 回溯的消除及LL(1)文法,継续讨论:消除回溯的另一条件 然而还存在另外一种情况,可能存在某个候选式i, i ,即FIRST(i)(这样的候选式是唯一的(?!),此时,为匹配当前扫描的符号a就可能有两种选择,一是存在某j,使j推导出以a打头的符号串,另一种选择是让A推导出i,并让跟随在A后的符号串推导出以a打头的符号串。,54,4.1.2 回溯的消除及LL(1)文

20、法,継续讨论:消除回溯的另一条件 若这两种选择都可行,则回溯不可避免. 因此,就必须要求当i 时,跟在A后的符号串不能推导出其它j 所能推导出的首终结符符号串. 为此,我们定义可紧跟在A后的所有终结符之集 : FOLLOL集的定义: FOLLOL（A）=aS A 且a FIRST（）， V*， V+ 若S A ,且 ，则#FOLLOL(A),55,4.1.2 回溯的消除及LL(1)文法,FOLLOL集也可定义为： FOLLOW(A) 紧跟在A后的所有终结符之集 FOLLOW（A）=aS Aa,a VT 若S A,则规定#FOLLOW(A),56,4.1.2 回溯的消除及LL(1)文法,消除回溯

21、的另一条件 现在,我们可把无回溯的另一条件描述为: 若i , 则FOLLOW(A)与其它的FIRST(j) 互不相交: FOLLOW(A) FIRST(j )=.,57,4.1.2 回溯的消除及LL(1)文法,例 SaA | b AcAS | FIRST(cAS)= c FOLLOW(A) =FIRST(S)#=a,b,# FIRST(cAS) FOLLOW(A)= 两个集合不相交, 故可进行无回溯的自顶向下分析. 设输入串w=aca#,其推导过程如下:,58,4.1.2 回溯的消除及LL(1)文法,S#aA# 当前输入符a属于FIRST(aA),用 SaA推导 acAS# 当前输入符c属于F

22、IRST(cAS),用AcAS推导 acS# 当前输入符a属于FOLLOW(A),用A推导. acaA# 当前输入符a属于FIRST(aA),用SaA推导 aca# 当前输入符#属FOLLOW(A),用A推导,成功。,对w=aca#之推导,59,4.1.2回溯的消除及LL(1)文法,消除回溯的条件 例如,文法G1S: SAA AaAb | *, A-产生式有两个候选式, 且 FIRST(aAb)=a FIRST(*)=* 两集不相交,设输入串为aa*bb*,其最左推导为 SAA(a)aAbA(a)aaAbbA(*)aa*bbA(*)aa*bb* (#) 注:上面每步推导右侧括号内为当前扫描的输

23、入符号,#为结束符。,60,最后,我们将消除回溯的条件归纳为: 对G中每个AVN,A-产生式中任何两个候选式i,j,均满足: (1)FIRST(i) FIRST(j)= (ij 1i,jm)； (2) i,j中,至多有一个能推导出; (3)若j ,则FIRST(i)FOLLOW(A)= (i=1,2,m ij)； 注: 条件(2)可省略. 即(1) (2)； 我们把满足上述条件的文法称为LL(1)文法。,LL(1)文法定义,61,LL(1)文法定义,一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立： FIRST（）FIRST()=,也就是和推导不出以

24、 同一个终结符a为首的符号串；它们不应该都能推出空字 .假若 ，那么， FIRST（) FOLLOW（A）.也就是，若 . 则所能推出的串的首符号不应在FOLLOW(A）中 结论：LL(1)文法是无二义的,62,4.1.3 递归下降分析法,概念: 将一个非终结符A的文法规则看作识别A的过程定义. 文法中的每个非终结符号对应一个递归过程。 根据输入句子的当前单词，确定所用的产生式。当存在多个候选产生式时，采用试探法，试错了则回溯。 对于产生式右部的终结符号，则将其与输入单词匹配；对于产生式右部的非终结符号，则调用相应的递归过程。 重复以上过程，构造关于输入句子的最左推导。,63,4.1.3 递归

25、下降分析法,递归下降分析法(recursive descent method)的原理是,对于文法的每个非终结符,根据其各候选式的结构,为其建立一个递归的子程序(函数),用于识别该非终结符所表示的语法范畴。 例如,产生式E+TE,相应的子程序(函数)为 expr_prime( ) if(match(PLUS) advance( ); term( ); expr_prime( ); ,64,4.1.3递归下降分析法(续),程序中,函数match( )的功能是,以其实参与当前正扫描的符号进行匹配,若成功则返回1,否则返回0; advance( )是读下一单词的函数,将所读单词赋给变量lookahea

26、d; term( )函数是与非终结符T相对应的子程序. 对于文法的每个非终结符,都建立了子程序后,这组子程序组成了所需的自顶向下语法分析程序。 注意,由于文法的递归性,子程序一定有递归.因此,只能使用允许递归的程序设计语言编写.,65,例4.2文法Gstatements: statements expression;statements | expression term expression expression +term expression | term factor term term *factor term | factor num_or_id | (expression) 可以

27、验证，Gstatements满足LL(1)文法条件。故可用递归下降法分析。分析程序如下:,4.1.3递归下降分析法(续),66,/*Basic parser,show the structure but theres no code generation */ #include #include “lex.h” statements( ) /*statements-expression SEMI * |expression SEMI statements */ exprssion( ) ; if (match(SEMI),程序4-1 文法Gstatements的递归下降语法分析程序,67,4.

28、1.3递归下降语法分析程序(续),advance( ); else fprintf(stderr, “%d: Inerting missing semicolon n”,yylineno); if(! match (EOI) statements( ); /* Do another statements. */ expression( ) /* expression - term expression */ trem( ); expr_prime( );,68,4.1.3递归下降语法分析程序(续), expr_prime( ) /* expession- PLUS term expressio

29、n * |epsilon */ if(match (PLUS) advance( ); term( ); expr_prime( ); ,69,递归下降语法分析程序(续), term( ) /* term- factor term */ factor( ); term_prime( ); term_prime( ) /* term_TIMES factor term * | epsilon */,70,递归下降语法分析程序(续),if(match (TIMES) advance( ); factor( ); term_prime( ); faction( ) /*factor -NUM_OR_

30、ID * |LP expression RP */ if (match (NUM_OR_ID),71,advance( ); else if(match (LP) advance( ); expression( ); if(match(LP) advance( ); else fprintf (stderr, “%d: Mismatched parenthesis n”,yylineno); else fprintf(stderr,”%d: Number or identifier expected n”,yylineno); ,递归下降语法分析程序(续),72,其中,在文件lex.h里,将分

31、号、加号、乘号、左右括号、输入结束符及运算对象分别命名为SEMI、PLUS、TIMES、LP、RP、EOI及NUM_OR_ID,并指定了其内部码;另外,还对外部变量yytext, yyleng, yylineno进行了说明. 程序4-2对4-1进行了改进,它利用扩充BNF范式对文法进行改写,使相应程序效率高，且有较完善的语法检查。,递归下降语法分析程序(续),73,程序4-2改进的递归下降语法分析程序,利用程序4-1进行语法分析时，约定，当前的输入符号不是应出现的符号(例如 ，对于第37行，当前的输入符号不是加号) ，则用相应的产生式进行推导。另外，上述程序有两个明显的缺点：一是频繁的递归调用

32、将使工作效率大为降低；二是缺乏较完善的语法检查和出错处理。可通过适当改写文法和扩充程序功能来改善。,74,程序4-2改进的递归下降语法分析程序,文法Gstatements改写为: G statements statements expression expression term +term term factor *factor factor num_or_id | (expression) 此时，对一些子程序的递归调用就可用一段代码的重复执行来代替。如程序4-2,75,/* Revised parser */ #include #include “lex.h” void factor (v

33、oid); void term (void); void expression (void); statements( ) /* statements -expression SEMI | expression */ while (! match (EOI) ,程序4-2 改进的递归下降语法分析程序,76,expression ( ); if (match (SEMI) advance( ); else fprintf (stderr,”%d: Inserting missing semicolonn”,yylineon); void expression( ) /* expression -

34、 term expression * expression -PLUS term expression | epsilon */,改进的递归下降语法分析程序(续),77,if(! Legal_lookahead (NUM_OR_ID, LP,0) return: term( ); while (match (PLUS ) advance( ); term( ); void term( ) if(! legal_lookahead(NUM_OR_ID, LP,) return;,改进的递归下降语法分析程序(续),78,factor( ); while (match (TIMES) advance

35、( ); factor( ); void factor() if(! legal_lookahead (NUM_OR_ID, LP, 0) return; if( match (NUM_OR_ID) advance( );,改进的递归下降语法分析程序(续),79,改进的递归下降语法分析程序(续),else if (match (LP) advance ( ); expression(); if(match (RP) advance( ); else fprintf (stderr,”%d: Mismatched parenthesisn”,yylineno); else fprintf (st

36、derr,”%d: Number of identifier expected n”,yylineno); ,80,在程序4-2的expression( ) ， term( ) ， factor() 三个函数中，都调用了一个名为legal_lookahead的函数。此函数的实参是相应非终结符FIRST集的各个元素，并且用一个0作为最后一个实参，其功能是：检查当前的输入符号是否属于相应非终结符的FIRST集，若是其中的元素，则继续进行分析；否则除报错外，还逐个删除输入串中的符号，直到出现属于该FIRST集的某个符号为止。,程序4-3函数legal_lookahead,81,程序4-3 函数leg

37、al_lookahead,#include #define MAXFIRST 16 #define SYNICH SEMI int legal_lookahead (first_agr) int first_arg; /* Simple error detection and recovery. Arguments are a *0-terminated list of those tokens that can legitimately come in the *input. If the list is empty, the end of file must come next.Print

38、 an *error message if necessary. Recovery is performed by discarding *all input symbols until one thats in the input list is found * * Return true if theres no error or if we recovered from the error, *false if we can,82,函数legal_lookahead (续),*/ va_list agrs;/* The agrs variable is a pointer to the

39、agrument list */ int look; int lookaheadsMACFIRST, *p=lookaheads, *current; int error_printe=0; int rval=0; va_start (agrs,first_agr); /*The agrs is initialized */ if(! First_agr) if(match (CEI) rval =1; ,83,函数legal_lookahead (续),else *p+=first_arg; while(tok=va_arg(args,int) if(! Error_printed),84,

40、函数legal_lookahead (续), fprintf(stderr,”Line %d: Syntax errorn”, yylineno); error_printed =1; advance( ); exit; va_end(args); /*The va_end() macro tells that there are no more agruments to get */ return rval; ,85,4.1.4 预测分析法,预测分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一个分析栈组成。 输入是待分析的符号串（单词流），以#结尾。 分析表

41、是一个二维数组M: VN(VT#) ，行标与VN关连，列标与( VT#)关连 ， MA,a的值按下述规则确定:,86,4.1.4 预测分析法,对于每个产生式A1| 2 |m (1)若aFIRST(i), 置MA,a=“Ai”； (2)FIRST(i), aFOLLOW(A), 置 MA.a=“Ai”； (3)除上述两种情况外,其它元素均填 “ERR”。 分析表元素的含义:指明当前应用何产生式进行推导,或指明输入串出现错误。,87,预测分析器结构,输入, #,控制程序,X Y Z #,分 析 栈,分析表,图4-1 预测分析器的逻辑结构,a2,ai,an,a1,88,输入,a + b $,预测分析

42、 控制程序,分析表M,输出 (选用的产生式),栈,X Y Z $,预测分析器结构,89,预测分析控制程序,置ip指向w$的第一个符号 repeat 令X是栈顶符号, a是ip所指向的符号; if X 是一个终结符号或$ then if X=a then 把X从栈中弹出,并且更新ip else error() else /*X是非终结符号*/ if MX,a=X Y1 Y2. . Yk then begin 把X从栈中弹出; 把 Yk, Yk-1,. ., Y1压入栈中, 即Y1在顶上; 输出产生式 X Y1 Y2. .Yk end else error() until X=$ /*栈为空*/,

43、90,一、分析器的工作原理,1.初始化.首先将#及开始符S压入栈,各指针 置初值.此时,格局为,# S,a1 a2 an #,2.设在分析的某时刻的分析格局为,# X1 X2 Xm-1 Xm,ai ai+1 an #,分析器对每个输入串的分析在控制程序的控制下进行，步骤如下：,91,一、分析器的工作原理,此时,根据当前栈顶符号Xm的不同情况,分别作如下处理: (1) XmVT,且Xm=ai,则匹配,将Xm 出栈,输入指针+;否则(Xmai),出错; (2) XmVN 查表MXm,ai,若MXm,ai=“ERR”,则出错;若MXm,ai= “Xm Y1Y2Yk” ,则将Xm 出栈, Y1Y2Yk

44、 按逆序压入栈,得到格局,# X1X2Xm-1YkYk-1Y1,aiai+1an#,92,(3)若Xm=ai=#,则表明输入串已完全得到匹配,分析成功,结束。,一、分析器的工作原理,93,预测分析法实例,考虑文法(4.1).各个 FIRST集与FOLLOW集如表41；文法(4.1)相应的LL(1)分析表见表42。 注:在实际的表存储时,还可用产生式编号表示。,94,预测分析法实例,表 4-1,95,预测分析法实例,表 4-2,96,对i+i*i进行预测分析的过程,表 4-3,97,(1)计算FIRST集 1.若XV,则FIRST(X)=X 2.若XVN,且有产生式Xa，则把a加入到FIRST(

45、X)中;若X也是一条产生式,则把也加到FIRST(X)中.,二、构造FIRST集FOLLOW集的算法,98,(1)计算FIRST集 3.若XY是一个产生式且Y VN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中; 若X Y1 Y2 YK 是一个产生式, Y1,Y2 , Y(i-1)都是非终结符,而且,对于任何j, 1j i-1,FIRST(Yj)都含有 (即Y1,Y2 , Y(i-1) 都能推导出) ，则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是，若所有的FIRST(Yj) ，(j=1,2,K)均含有 ，则把加到FRIST(X)中。,二、构造FIRST集F

46、OLLOW集的算法,99,(1)计算FIRST集 求FIRST(X),反复应用如下规则,直到集合不再增大: (1)if (X VT) FIRST(X)=X;； (2)if(XVN)if(XaPaVT) a入FIRST(X); if (XP) 入FIRST(X); ； (3) if (XY1Y2YkP) if(Y1VN) FIRST(Y1)-入FIRST(X); for(1 j k-1)if(YjVNFIRST(Yj) FIRST(Yj)-入FIRST(X); if (for(1 j k): FIRST(Yj) 入FIRST(X);V*,=X1X2Xn, 类似于求XY1Y2Yk,略。,二、构造F

47、IRST集FOLLOW集的算法,100,(2)计算FOLLOW集 1.对于文法的开始符号S,置#于FOLLOW(S)中; 2.若B是一个产生式,则把 FIRST()加至FOLLOW(B)中; 3.若B是一个产生式,或B是 一个产生式而 (即FIRST()）， 则把FOLLOW（A）加至FOLLOW（B）中,二、构造FIRST集FOLLOW集的算法,101,(2)计算FOLLOW集 反复使用如下规则,直到每个Follow集不再增大: 1. # 入FOLLOW(S); 2. if (ABP) FIRST()- 入FOLLOW(B);； 3. if ( (ABP) ( AB FIRST() ) )

48、入FOLLOW(A)入FOLLOW(B);；,二、构造FIRST集FOLLOW集的算法,102,算法的证明: 对于1.,由定义直接得到; 对于2.,由于A是有用符号,则必存在含A的句型: S A B Ba (a FIRST()； 对于3., 类似地, S A B,显然,FIRST()FOLLOW(A),并且, FIRST()FOLLOW(B)。证毕/,二、构造FIRST集FOLLOW集的算法,103,构造FIRST集和FOLLOW集的例子,以文法(4.1)为例,计算FIRST集和FOLLOW集. 1.求所有VN符的FIRST集.利用规则(2),有 FIRST(M)=*,/, FIRST(A)=

49、+,-FIRST(F)=(,i; 再利用规则(3),有FIRST(T)=FIRST(M)=*,/, ,FIRST(T)=FIRST(F)=(,i,FIRST(E)=FIRST(A) =+,-, FIRST(E)=FIRST(T)=(,i；,104,构造FIRST集和FOLLOW集的例子,2.求FOLLOW集 (1)由规则(1),#FOLLOW(E),再由产生式F(E), )FOLLOW(E), 从而,FOLLOW(E)=),#； (2)由规则(3)及产生式ETE可知FOLLOW(E)FOLLOW(E),即有 FOLLOW(E)=),#；,105,构造FIRST集和FOLLOW集的例子,2.求F

50、OLLOW集 (1)由规则(1),#FOLLOW(E),再由产生式F(E), )FOLLOW(E), 从而,FOLLOW(E)=),#； (2)由规则(3)及产生式ETE可知FOLLOW(E)FOLLOW(E),即有 FOLLOW(E)=),#；,106,构造FIRST集和FOLLOW集的例子,(3)由规则(2)及产生式EATE有 FIRST(E)-FOLLOW(T) ;再由规则(3)及ETE和E 有 FOLLOW(E)FOLLOW(T) 即FOLLOW(T)=+,-),#=+,-,),#； (4)由规则(3)有TFT有FOLLOW(T)FOLLOW(T),即FOLLOW(T)=+,-,),#

51、；,107,构造FIRST集和FOLLOW集的例子,(5)由规则(2)及TMFT,有 FIRST(T)- FOLLOW(F),再由规则(3)及TMFT和T ,有FOLLOW(T) FOLLOW(F),从而, FOLLOW(F)=*, /+,-,),#=+,-,*,/,),#；,108,构造FIRST集和FOLLOW集的例子,(6)由规则(2)及EATE,T MFT ,有 FIRST(T)FOLLOW(A), FIRST(F) FOLLOW(M),故有 FOLLOW(A)=(,i, FOLLOW(M)=(,i。 最终所得的FIRST集和FOLLOW集结果,见P119(表4-1)。,109,文法

52、GE ETE EATE| TFT TMFT| F(E)|i A+|- M *|/,表 4-1,110,LL（1）文法,一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立： FIRST（）FIRST()=,也就是和推导不出以 同一个终结符a为首的符号串；它们不应该都能推出空字 .假若 ，那么， FIRST（) FOLLOW（A）.也就是，若 . 则所能推出的串的首符号不应在FOLLOW(A）中 结论：LL(1)文法是无二义的,111,三、预测分析表的构造,算法 预测分析表的构造 输入:文法G. 输出: 分析表M. 方法: 1. 对文法G的每个产生式A执行

53、第2步和第3步; 2. 对每个终结符号aFirst(), 把A加到MA,a中; 3. 若 First(), 则对任何b Follow(A),把A加到MA,b中; 4. 把所有无定义的MA,a标上错误标志。,112,预测分析表的构造实例,表 4-2,文法 GE ETE EATE| TFT TMFT| F(E)|i A+|- M *|/,113,4.1.5 非LL(1)文法的改造,消除左递归 提左公因子 将产生式| 变换为： B B |,114,非LL(1)文法的改造,例.对于文法GS SS+aFaF+aF F *aF*a 1.消除文法的左递归和回溯。 2.构造相应的FIRST集和FOLLOW集。

54、 3.构造LL（1）分析表。,115,非LL(1)文法的改造,1、消除文法的左递归 SS+aFaF+aF S aFS+aFS S+aFS 提左公因子消除回溯 F *aF*a F *aF FF,116,非LL(1)文法的改造,2. FIRST集和FOLLOW集 FIRST FOLLOWS S aFS a # +aFS + S +aFS + # F *aF * +,# F F * +,# ,117,非LL(1)文法的改造,3. LL（1）分析表 + a * # S S +aFS S aFS S S+aFS S F F *aF F F FF F,118,例,例：考虑文法 S (L) | a L L,

55、S | S 消除左递归后的文法为 S (L) | a L SL L ,SL | ,119,每个非终结符能推导出的第一个字符的集合 First(A)= a | A a, a VT 若A ，则需要考虑跟随在A后面的终结符号,称为非终结符号的跟随符号集合。 Follow(A) = a | S .Aa., a VT $ ,Follow(L) = ) ,First(S) = (, a First(L)= (, a First(L) = , , ,例,120,( ) , a # S S(L) S a L LSL LSL L L L ,SL,分析表M,S (L) | aL SLL ,SL | ,FOLLOW

56、(L) = ) ,First(S) = (, a First(L)= (, a First(L) = , , ,121,推导产生的句型 输入串 S (a),a)$ (L) (a),a)$ ( L) (a),a)$ ( SL) (a),a)$ ( (L)L) (a),a)$ ( ( L)L) a),a)$ ( ( SL)L) a),a)$ ( ( aL)L) a),a)$ ( ( a L)L) ),a)$ ( ( a )L) ),a)$ ( ( a ) L) ,a)$ ( ( a ) ,SL) ,a)$ ( ( a ), SL) a)$ ( ( a ), aL) a)$ ( ( a ),a L) )$ ( ( a ),a ) )$ ( ( a ),a) $,S (L) | aL SLL ,SL | ,122,算法4