第4章语法分析-自顶向下的语法分析

1、编译系统原编译系统原 理理电气与信息学院 王 艳4.1 4.1 自顶向下分析方法自顶向下分析方法4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.3 4.3 递归下降分析递归下降分析4.4 LL(1)4.4 LL(1)分析方法分析方法第四章第四章 语法分析语法分析- -自顶向下分析自顶向下分析4.1 4.1 自顶向下分析方法自顶向下分析方法语法分析器语法树4.1 4.1 自顶向下分析方法自顶向下分析方法语法分析的任务：语法分析的任务： 检查源程序语法上是否正确，并生成相应检查源程序语法上是否正确，并生成相应的内部表示（如分析树）供下一阶段使用。的内部表示（如分

2、析树）供下一阶段使用。结果输出：结果输出：分析树：分析树：产生式序列产生式序列出错处理要求出错处理要求l尽快发现错误，准确定位，尽快发现错误，准确定位，l可能时进行恢复处理，继续语法分析可能时进行恢复处理，继续语法分析4.1 4.1 自顶向下分析方法自顶向下分析方法常用的语法分析方法：常用的语法分析方法： 分析法分析法分析法分析法分析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析)1()1()1()0()(LALRLRSLRLRLRKLL无论那种分析方法，语法分析都是自左至右的读入字符无论那种分析方法，语法分析都是自左至右的读入字符4.1 4

3、.1 自顶向下分析方法自顶向下分析方法n自顶向下的分析方法自顶向下的分析方法就是从文法的开始符号出发，就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输按最左推导方式向下推导，试图推导出要分析的输入串。即：入串。即： 开始符号开始符号 输入符号串输入符号串+n自底向上的分析方法自底向上的分析方法从输入符号串开始，按最左从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：归约方式向上归约到文法的开始符号。即： 开始符号开始符号 输入符号串输入符号串 归约归约4.1 4.1 自顶向下分析方法自顶向下分析方法上下文无关文法（上下文无关文法（2 2型文法）型文法）编程语言

4、的语法大都可用型文法来描述编程语言的语法大都可用型文法来描述 例例4.1： ETE E+TE E TFT T*FT T F(E)|i没有一种方法能够有效地分析所没有一种方法能够有效地分析所有上下文无关文法有上下文无关文法l存在无法处理的型文法存在无法处理的型文法每种方法能够处理一部分上下文每种方法能够处理一部分上下文无关文法无关文法l每种方法都有适用范围每种方法都有适用范围4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.1 FIRST4.2.1 FIRST集合集合FIRST集合定义：集合定义：假定假定是文法是文法G的任一符号串，的任一符号串，则：则： F

5、IRST()=a | a，aVt若若 , 则规定则规定FIRST()。 * 实际上，实际上，FIRST()就是从就是从可能推导出的所有可能推导出的所有开头终结符号或开头终结符号或。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合文法符号的FIRST集合构造方法： 对于文法中的对于文法中的符号符号X XVV，其，其FIRST(X)FIRST(X)集合可反复应用下列规则集合可反复应用下列规则计算，直到其计算，直到其FIRST(X)FIRST(X)集合不再增大为止：集合不再增大为止： 1)1)若若XVXVt t，则，则FIRST(X)=XFIRST(X)=X。2)2)

6、若若XVXVn n，且具有形如，且具有形如XXa a的产生式的产生式( (a aVVt t) )，或具有形如，或具有形如XX的产生式，则把的产生式，则把a a或或加进加进FIRST(X)FIRST(X)。3)3)设设G G中有形如中有形如XYXY1 1Y Y2 2YYk k的产生式，若的产生式，若Y Y1 1VVn n，则把，则把FIRST(YFIRST(Y1 1) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X)；对于一切；对于一切2ik2ik，若，若Y Y1 1，Y Y2 2，Y Yi-1i-1均为非终结符号，且均为非终结符号，且FIRST(YFIRST(Yj j)

7、)，1ji-11ji-1，则，则将将FIRST(YFIRST(Yi i) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X)；但若对一切；但若对一切1ik1ik，均有，均有FIRST(YFIRST(Yi i) )，则将，则将符号加进符号加进FIRST(X)FIRST(X)。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合对于文法对于文法G G的任一的任一符号串符号串=X=X1 1X X2 2XXn n可按下列步骤构造其可按下列步骤构造其FIRST()FIRST()集合：集合：1)1)置置FIRST()=;FIRST()=;2)2)将将FIR

8、ST(XFIRST(X1 1) )中的一切非中的一切非符号加进符号加进FIRST()FIRST()；3)3)若若FIRST(XFIRST(X1 1) )，将，将FIRST(XFIRST(X2 2) )中的一切非中的一切非符号加进符号加进FIRST()FIRST()；若；若FIRST(XFIRST(X1 1) )和和FIRST(XFIRST(X2 2) )，将，将FIRST(XFIRST(X3 3) )中中的一切非的一切非符号加进符号加进FIRST()FIRST()；其余类推。；其余类推。4)4)若对于一切若对于一切1in1in，FIRST(XFIRST(Xi i) )，则将，则将符号加进符号加

9、进FIRST()FIRST()。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例4-1 4-1 有文法：有文法： ETE E+TE E TFTETE E+TE E TFT T T* *FT T F(E)|iFT T F(E)|i求文法中非终结符号以及各产生式右部符号串的求文法中非终结符号以及各产生式右部符号串的FIRSTFIRST集。集。解：该文法的非终结符号有解：该文法的非终结符号有E、E、T、T和和F。FIRST(E)=FIRST(T) =FIRST(F) = ( ，i FIRST(E)= + ，FIRST(T)= * ，右部符号串的右部符号串的FIR

10、ST集：集：FIRST(TE) =FIRST(T)=FIRST(F) = ( ，i FIRST(+TE)= + FIRST()=FIRST(FT)=FIRST(F) = ( ，i FIRST(*FT)= * FIRST(E)= ( FIRST(i)= i 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例 S:=aABbcd| A:=ASd| B:=SAh|eC| C:=Sf|Cg| 求此文法的每一个非终结符号的求此文法的每一个非终结符号的FIRST集。集。解：解：FIRST(S)=FIRST(aABbcd)FIRST() =a=a,FIRST(A)=FIRS

11、T(ASd)FIRST() =a,d=a,d, FIRST(B)=FIRST(SAh)FIRST(eC) FIRST() =a,d,he=a,d,h,e,FIRST(C)=FIRST(Sf)FIRST(Cg) FIRST() =a,fa,f,g=a,f,g,4.2.1 FIRST4.2.1 FIRST集合集合4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合练习练习 ：S:=aAcB|Bd A:=AaB|c B:=bBcA|b| 求此文法的每一个非终结符号的求此文法的每一个非终结符号的FIRST集集解：解：FIRST(S)=FIRST(aAcB)FIRST(Bd)

12、 =ab,d =a,b,dFIRST(A)=FIRST(AaB)FIRST =cc =cFIRST(B)=FIRST(bBcA)FIRST(b) FIRST() =bb =b, 4.2.1 FIRST4.2.1 FIRST集合集合4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.2 FOLLOW4.2.2 FOLLOW集合集合FOLLOW集合定义：集合定义： 假定假定S是文法的开始符号，对于是文法的开始符号，对于G的任何非的任何非终结符号终结符号A，则：，则： FOLLOW(A)= a | S Aa， aVt 若若S A，则规定，则规定#FOLLOW(A)

13、。 * FOLLOW(A)FOLLOW(A)就是在所有句型中出现在紧接就是在所有句型中出现在紧接A A之后的之后的终结终结符号或符号或# #。注意：在。注意：在FOLLOWFOLLOW集合中无集合中无。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合 对于文法中的符号对于文法中的符号AVAVn n，其，其FOLLOW(A)FOLLOW(A)集合可反集合可反复应用下列规则计算，直到其复应用下列规则计算，直到其FOLLOW(A)FOLLOW(A)集合不再增集合不再增大为止：大为止：1)1)对于文法的对于文法的开始符号开始符号S S，令，令#FOLLOW(S)#FOL

14、LOW(S)2)2)若若G G中有形如中有形如BA BA 的产生式，且的产生式，且 ，则，则将将FIRST()FIRST()中的一切非中的一切非符号加进符号加进FOLLOW(A)FOLLOW(A)。3)3)若若G G中有形如中有形如BABA或或BA BA 的产生式，且的产生式，且FIRST()FIRST()，则，则FOLLOW(B)FOLLOW(B)中的全部元素均属于中的全部元素均属于FOLLOW(A)FOLLOW(A)，即即FOLLOW(B) FOLLOW(A)FOLLOW(B) FOLLOW(A) 。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例4-2

15、 有文法有文法 ETE，E+TE，E，TFT，T*FT，T，F(E)|i，求各非终结符号的，求各非终结符号的FOLLOW集集。解：先求出某些符号的解：先求出某些符号的FIRST集合：集合：FIRST(E)=FIRST(T) =FIRST(F) = ( ,i FIRST(E)= + ,FIRST(T)= * ,再求再求FOLLOW集合：集合：FOLLOW(E)=) ， #FOLLOW(E)= FOLLOW(E)=) ,# FOLLOW(T)= FIRST(E) FOLLOW(E) FOLLOW(E)= + , ) , # FOLLOW(T)= FOLLOW(T)= +,) , # FOLLOW(

16、F)=FIRST(T) FOLLOW(T) FOLLOW(T) = *,+,) ,# 例例 设文法设文法GS:S:=SbA|aA A:=Bc B:=Sb求此文法的每一个非终结符号的求此文法的每一个非终结符号的FOLLOW集。集。解：解：1. 因为因为S为文法的开始符号，所以为文法的开始符号，所以#FOLLOW(S);由由S:=SbA，有，有FIRST(bA)=bFOLLOW(S); 由由B:=Sb，有，有FIRST(b)=bFOLLOW(S);因此，因此，FOLLOW(S)=b,#。2. 由由S:=SbA或或S:=aA，有，有FOLLOW(S) FOLLOW(A)。因此，。因此，FOLLOW(

17、A)=b,#。3. 由由A:=Bc，有，有FIRST(c)=cFOLLOW(B)。因此，。因此，FOLLOW(B)=c。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合练习练习 已知文法已知文法GS:S:=A A:=BA A:=iBA| B:=CB B:=+CB| C:=)A*|( 求求FOLLOW(C)。解：解：FOLLOW(C)=FIRST(B) FOLLOW(B)FOLLOW(B) =+,i,*,#4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.2 FOLLOW4.2.2 FOLLOW集合集合4.3 4.3 递归下

18、降分析法递归下降分析法递归下降分析的基本方法递归下降分析的基本方法思路：思路：为每个非终结符号构造一个子程序，以完为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识成该非终结符号所对应的语法成分的分析和识别。别。1. 若若U的右部的右部只有一个候选式只有一个候选式，则按从左向右的顺序构造，则按从左向右的顺序构造U的识别过的识别过程代码。程代码。 （1 1）若有终结符号，则判断与输入符号是否匹配，如果相同，继）若有终结符号，则判断与输入符号是否匹配，如果相同，继 续读入下一符号，否则就意味着有语法错误；续读入下一符号，否则就意味着有语法错误； （2 2）若有非终结符号，

19、则调用该符号的子程序。）若有非终结符号，则调用该符号的子程序。2. 若若U的右部的右部有多个候选式有多个候选式，则根据每个候选式的第一个符号确定，则根据每个候选式的第一个符号确定该候选式分支。该候选式分支。3. 只有输入串的每一个符号全部匹配成功，且正确返回时，该语法只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。成分才算真正获得识别。4.3 4.3 递归下降分析法递归下降分析法例例4-3 考虑文法考虑文法Z:=(U)|aUb ，U:=dZ|e为其构造递归下降分析子为其构造递归下降分析子程序。并对输入串程序。并对输入串aeb进进行语法分析行语法分析 。解：文法中有

20、两个非终结符号解：文法中有两个非终结符号Z Z和和U U，那么我们需要分别编两个过程来完那么我们需要分别编两个过程来完成成Z Z和和U U规则的识别。规则的识别。 对于规则对于规则Z:=(U)|aUbZ:=(U)|aUb，右部有，右部有两个候选式，因此，两个候选式，因此，U U的识别过程的识别过程有两个分支，分别根据符号有两个分支，分别根据符号( (和和a a来来判别。判别。 同理对规则同理对规则U:=dZ|eU:=dZ|e设计的过设计的过程也分为两个分支。程也分为两个分支。4.3 4.3 递归下降分析法递归下降分析法Z:=(U)|aUb非终结符号非终结符号Z的分析程序的分析程序 4.3 4.

21、3 递归下降分析法递归下降分析法非终结符号非终结符号U的分析程序的分析程序U:=dZ|e4.4 LL(1)4.4 LL(1)分析法分析法LL(1)分析法的含义：分析法的含义：第一个第一个L表示自左向右顺序扫描输入符号串表示自左向右顺序扫描输入符号串第二个第二个L表示分析过程产生一个句子的最左推导表示分析过程产生一个句子的最左推导括号中的括号中的1表示每进行一步推导，只需要向前查看表示每进行一步推导，只需要向前查看1个输入符号，便能确定当前所应选用的规则个输入符号，便能确定当前所应选用的规则 LL(1)分析程序的结构：分析程序的结构： LL(1)分析器由一个总控程序、一张分析表和一分析器由一个总

22、控程序、一张分析表和一个分析栈组成。个分析栈组成。 4.4 LL(1)4.4 LL(1)分析法分析法是一个二维表，它概括了是一个二维表，它概括了文法的全部信息，指出了文法的全部信息，指出了分析器应采取的动作。分析器应采取的动作。存放一系列存放一系列文法符号。文法符号。分析开始时，分析开始时，先将先将# #入栈，入栈，然后再将文然后再将文法的开始符法的开始符号入栈。号入栈。分析过程中使用的产生式序列。分析过程中使用的产生式序列。要分析的输入符号串。串的末尾放置一个特殊符号要分析的输入符号串。串的末尾放置一个特殊符号# #，表示结束，表示结束根据栈顶符根据栈顶符号和当前的号和当前的输入符号，输入符

23、号，按照分析表按照分析表的指示来完的指示来完成分析过程。成分析过程。4.4 LL(1)4.4 LL(1)分析法分析法分析表分析表M：是一个二维表，可用一个二维数组是一个二维表，可用一个二维数组MA，a来表示，它指出了分析器来表示，它指出了分析器应采取的动作。应采取的动作。分析表中的分析表中的每一行是文每一行是文法中的一个法中的一个非终结符号、非终结符号、终结符号或终结符号或# #；分析表每一分析表每一列是文法的列是文法的一个终结符一个终结符号或号或# #。分析表的列数是分析表的列数是终结符号的个数加终结符号的个数加1；行数是；行数是非终结符号和终结符号的数目加非终结符号和终结符号的数目加1。1

24、) 分析开始时，首先将符号分析开始时，首先将符号#及文法的开始符号及文法的开始符号S依次置于依次置于分析栈的底部，并把各指示器调整至起始位置。然后，反复分析栈的底部，并把各指示器调整至起始位置。然后，反复执行第二步的操作。执行第二步的操作。 输入符号串：输入符号串： #ana2a1分析栈：分析栈：#S 分析开始时状况分析开始时状况 2) 假设分析的某一步，分析栈及余留的符号串，则根据假设分析的某一步，分析栈及余留的符号串，则根据栈顶的符号栈顶的符号Xm，采取下列动作：，采取下列动作： aiai+1 an#X1X2Xm-1Xm 分析进行中的状况分析进行中的状况 (1)若若XmVn，则查分析表的，

25、则查分析表的Xm所在行和所在行和ai所在列，假设所在列，假设MXm,ai为为POP,PUSH（WVU），则将，则将Xm出栈，并将出栈，并将WVU入栈，这意味入栈，这意味着使用了规则着使用了规则XmUVW；MXm,ai为为POP，则将，则将Xm出栈，这意出栈，这意味着使用了规则味着使用了规则Xm ；若；若MXm，ai为空或为空或ERROR，则出错。，则出错。 aiai+1 an#XmUVW(2)若若Xm=ai#，表示栈顶与扫描的符号匹配，则查分析表为，表示栈顶与扫描的符号匹配，则查分析表为POP，NEXTSYM，则栈顶符号，则栈顶符号Xm出栈，输入指针指向下一个符号。出栈，输入指针指向下一个符号

26、。( 3 ) 若若Xm=ai= #，表示输入串完全匹配，分析成功。，表示输入串完全匹配，分析成功。 #X1X2Xm-1WVU #X1X2Xm-1Xm #X1X2Xm-1 Xm例：算术表达式文法例：算术表达式文法ETE，E+TE，E，TFT,T*FT,T,F(E)|i，该文法的该文法的LL(1)分析表为分析表为:POP：将栈顶元将栈顶元素从栈内弹出。素从栈内弹出。PUSH：将括将括号内的符号串号内的符号串压入栈。压入栈。NEXTSYM：将将读符号指针指向读符号指针指向下一个符号。下一个符号。ACCEPT：分析成功分析成功分析表的动作含义：分析表的动作含义：例例根据表根据表4-1，对，对符号串符号

27、串i+i*i进行进行分析。分析。符号串符号串i+i*i的分析过程的分析过程i+ii+i* *i i的最左推导：的最左推导：E ET TEEF FTTE E i iTTEEi iEEi i+ +T TEEi+i+F FTTEEi+i+i iTTEEi+ii+i* *F FTTEEi+ii+i* *i iTTE E i+ii+i* *i iEE i+ii+i* *i i 对文法对文法G中的每个产生式中的每个产生式A，按下列规则确定，按下列规则确定LL(1)分析分析表中的元素表中的元素M：1)对对FIRST()中的每个终结符中的每个终结符a，置，置MA,a=“POP，PUSH()” ，其中其中为为的

28、倒置；的倒置；2)若若FIRST()， 则对属于则对属于FOLLOW(A)的每个符号的每个符号b(b为终结为终结符或符或#)，置，置MA,b=“POP” ；3)把把M中的所有中的所有Ma,a置为置为“POP，NEXTSYM”， aVt ；4)置置M#,#=“ ACCEPT”;5)把把M中所有不按上述规则定义的元素均置为空或中所有不按上述规则定义的元素均置为空或“ERROR”。 4.4 LL(1)4.4 LL(1)分析法分析法例例:ETE，E+TE，E，TFT，T*FT，T，F(E)|i，构造该文法的分析表。，构造该文法的分析表。对规则对规则ETE ：FIRST(TE)= (，i)，那么在分析表

29、的符号，那么在分析表的符号E所在所在的行、符号的行、符号(和和i所在的列对应的位置分别填入所在的列对应的位置分别填入“POP,PUSH(ET)”，见表见表4-1的的E行。行。对规则对规则E+TE：FIRST(+TE)=+，在符号，在符号E行符号行符号+列对应的位列对应的位置填入置填入“POP,PUSH(ET+)” ，见表，见表4-1的的E行。行。对规则对规则E：因为：因为FIRST()，FOLLOW(E)=)，#，所以在符，所以在符号号E行符号行符号)和和#列对应的位置填入列对应的位置填入“POP”，见表，见表4-1的的E行。行。 其它规则处理方法相同（略）。其它规则处理方法相同（略）。对于一个文法，若按上述方法构造的分析表对于一个文法，若按上述方法构造的分析表M不含多重定义，则称不含多重定义，则称它是一个它是一个LL(1)文法文法。 4.4 LL(1)4.4 LL(1)分析法分析法分析表的简化分析表的简化