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

编译系统原理电气与信息学院王艳§4.1自顶向下分析方法§4.2FIRST集合和FOLLOW集合§4.3递归下降分析§4.4LL(1)分析方法第四章语法分析-自顶向下分析§4.1自顶向下分析方法语法分析器语法树§4.1自顶向下分析方法语法分析的任务：检查源程序语法上是否正确，并生成相应的内部表示（如分析树）供下一阶段使用。结果输出：分析树：产生式序列出错处理要求尽快发现错误，准确定位，可能时进行恢复处理，继续语法分析§4.1自顶向下分析方法常用的语法分析方法：分析法分析法分析法分析法分析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析)1()1()1()0()(LALRLRSLRLRLRKLL无论那种分析方法，语法分析都是自左至右的读入字符§4.1自顶向下分析方法自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即：开始符号输入符号串+自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：开始符号输入符号串归约←§4.1自顶向下分析方法上下文无关文法（2型文法）编程语言的语法大都可用２型文法来描述例4.1：E→TE′E′→+TE′E′→εT→FT′T′→*FT′T′→εF→(E)|i没有一种方法能够有效地分析所有上下文无关文法存在无法处理的２型文法每种方法能够处理一部分上下文无关文法每种方法都有适用范围§4.2FIRST集合和FOLLOW集合4.2.1FIRST集合FIRST集合定义：假定α是文法G的任一符号串，则：FIRST(α)={a|αa…，a∈Vt}若αε,则规定ε∈FIRST(α)。**实际上，FIRST(α)就是从α可能推导出的所有开头终结符号或ε。§4.2FIRST集合和FOLLOW集合文法符号的FIRST集合构造方法：对于文法中的符号X∈V，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：1)若X∈Vt，则FIRST(X)={X}。2)若X∈Vn，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。3)设G中有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。§4.2FIRST集合和FOLLOW集合对于文法G的任一符号串α=X1X2…Xn可按下列步骤构造其FIRST(α)集合：1)置FIRST(α)=φ;2)将FIRST(X1)中的一切非ε符号加进FIRST(α)；3)若ε∈FIRST(X1)，将FIRST(X2)中的一切非ε符号加进FIRST(α)；若ε∈FIRST(X1)和FIRST(X2)，将FIRST(X3)中的一切非ε符号加进FIRST(α)；其余类推。4)若对于一切1≤i≤n，ε∈FIRST(Xi)，则将ε符号加进FIRST(α)。§4.2FIRST集合和FOLLOW集合例4-1有文法：E→TE′E′→+TE′E′→εT→FT′T′→*FT′T′→εF→(E)|i求文法中非终结符号以及各产生式右部符号串的FIRST集。解：该文法的非终结符号有E、E′、T、T′和F。FIRST(E)=FIRST(T)=FIRST(F)={(，i}FIRST(E′)={+，ε}FIRST(T′)={*，ε}右部符号串的FIRST集：FIRST(TE′)=FIRST(T)=FIRST(F)={(，i}FIRST(+TE′)={+}FIRST(ε)={ε}FIRST(FT′)=FIRST(F)={(，i}FIRST(*FT′)={*}FIRST((E))={(}FIRST(i)={i}§4.2FIRST集合和FOLLOW集合例S::=aABbcd|εA::=ASd|εB::=SAh|eC|εC::=Sf|Cg|ε求此文法的每一个非终结符号的FIRST集。解：FIRST(S)=FIRST(aABbcd)∪FIRST(ε)={a}∪{ε}={a,ε}FIRST(A)=FIRST(ASd)∪FIRST(ε)={a,d}∪{ε}={a,d,ε}FIRST(B)=FIRST(SAh)∪FIRST(eC)∪FIRST(ε)={a,d,h}∪{e}∪{ε}={a,d,h,e,ε}FIRST(C)=FIRST(Sf)∪FIRST(Cg)∪FIRST(ε)={a,f}∪{a,f,g}∪{ε}={a,f,g,ε}4.2.1FIRST集合§4.2FIRST集合和FOLLOW集合练习：S::=aAcB|BdA::=AaB|cB::=bBcA|b|ε求此文法的每一个非终结符号的FIRST集解：FIRST(S)=FIRST(aAcB)∪FIRST(Bd)={a}∪{b,d}={a,b,d}FIRST(A)=FIRST(AaB)∪FIRST©={c}∪{c}={c}FIRST(B)=FIRST(bBcA)∪FIRST(b)∪FIRST(ε)={b}∪{b}∪{ε}={b,ε}4.2.1FIRST集合§4.2FIRST集合和FOLLOW集合4.2.2FOLLOW集合FOLLOW集合定义：假定S是文法的开始符号，对于G的任何非终结符号A，则：FOLLOW(A)={a|S…Aa…，a∈Vt}若S…A，则规定#∈FOLLOW(A)。**FOLLOW(A)就是在所有句型中出现在紧接A之后的终结符号或#。注意：在FOLLOW集合中无ε。§4.2FIRST集合和FOLLOW集合对于文法中的符号A∈Vn，其FOLLOW(A)集合可反复应用下列规则计算，直到其FOLLOW(A)集合不再增大为止：1)对于文法的开始符号S，令#∈FOLLOW(S)2)若G中有形如B→αAβ的产生式，且β≠ε，则将FIRST(β)中的一切非ε符号加进FOLLOW(A)。3)若G中有形如B→αA或B→αAβ的产生式，且ε∈FIRST(β)，则FOLLOW(B)中的全部元素均属于FOLLOW(A)，即FOLLOW(B)FOLLOW(A)。§4.2FIRST集合和FOLLOW集合例4-2有文法E→TE′，E′→+TE′，E′→ε，T→FT′，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(F)=FIRST(T′)∪FOLLOW(T)∪FOLLOW(T′)={*,+,),#}例设文法G[S]:S::=SbA|aAA::=BcB::=Sb求此文法的每一个非终结符号的FOLLOW集。解：1.因为S为文法的开始符号，所以#∈FOLLOW(S);由S::=SbA，有FIRST(bA)={b}∈FOLLOW(S);由B::=Sb，有FIRST(b)={b}∈FOLLOW(S);因此，FOLLOW(S)={b,#}。2.由S::=SbA或S::=aA，有FOLLOW(S)∈FOLLOW(A)。因此，FOLLOW(A)={b,#}。3.由A::=Bc，有FIRST(c)={c}∈FOLLOW(B)。因此，FOLLOW(B)={c}。§4.2FIRST集合和FOLLOW集合练习已知文法G[S]:S::=AA::=BA′A′::=iBA′|εB::=CB′B′::=+CB′|εC::=)A*|(求FOLLOW(C)。解：FOLLOW(C)=FIRST(B′)∪FOLLOW(B)∪FOLLOW(B′)={+,i,*,#}§4.2FIRST集合和FOLLOW集合4.2.2FOLLOW集合§4.3递归下降分析法递归下降分析的基本方法思路：为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别。1.若U的右部只有一个候选式，则按从左向右的顺序构造U的识别过程代码。（1）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误；（2）若有非终结符号，则调用该符号的子程序。2.若U的右部有多个候选式，则根据每个候选式的第一个符号确定该候选式分支。3.只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。§4.3递归下降分析法例4-3考虑文法Z::=(U)|aUb，U::=dZ|e为其构造递归下降分析子程序。并对输入串aeb进行语法分析。解：文法中有两个非终结符号Z和U，那么我们需要分别编两个过程来完成Z和U规则的识别。对于规则Z::=(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号(和a来判别。同理对规则U::=dZ|e设计的过程也分为两个分支。§4.3递归下降分析法Z::=(U)|aUb非终结符号Z的分析程序§4.3递归下降分析法非终结符号U的分析程序U::=dZ|e§4.4LL(1)分析法LL(1)分析法的含义：第一个L表示自左向右顺序扫描输入符号串第二个L表示分析过程产生一个句子的最左推导括号中的1表示每进行一步推导，只需要向前查看1个输入符号，便能确定当前所应选用的规则LL(1)分析程序的结构：LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成。§4.4LL(1)分析法是一个二维表，它概括了文法的全部信息，指出了分析器应采取的动作。存放一系列文法符号。分析开始时，先将#入栈，然后再将文法的开始符号入栈。分析过程中使用的产生式序列。要分析的输入符号串。串的末尾放置一个特殊符号#，表示结束根据栈顶符号和当前的输入符号，按照分析表的指示来完成分析过程。§4.4LL(1)分析法分析表M：是一个二维表，可用一个二维数组M[A，a]来表示，它指出了分析器应采取的动作。分析表中的每一行是文法中的一个非终结符号、终结符号或#；分析表每一列是文法的一个终结符号或#。分析表的列数是终结符号的个数加1；行数是非终结符号和终结符号的数目加1。1)分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置。然后，反复执行第二步的操作。输入符号串：#an…………a2a1分析栈：#S分析开始时状况2)假设分析的某一步，分析栈及余留的符号串，则根据栈顶的符号Xm，采取下列动作：aiai+1…………an##X1X2…Xm-1Xm分析进行中的状况(1)若Xm∈Vn，则查分析表的Xm所在行和ai所在列，假设M[Xm,ai]为POP,PUSH（WVU），则将Xm出栈，并将WVU入栈，这意味着使用了规则Xm→UVW；M[Xm,ai]为POP，则将Xm出栈，这意味着使用了规则Xm→ε；若M[Xm，ai]为空或ERROR，则出错。aiai+1…………an#Xm→UVW(2)若Xm=ai≠#，表示栈顶与扫描的符号匹配，则查分析表为POP，NEXTSYM，则栈顶符号Xm出栈，输入指针指向下一个符号。(3)若Xm=ai=#，表示输入串完全匹配，分析成功。#X1X2…Xm-1WVU#X1X2…Xm-1Xm#X1X2…Xm-1Xm→ε例：算术表达式文法E→TE′，E′→+TE′，E′→ε，T→FT′,T′→*FT′,T′→ε,F→(E)|i，该文法的LL(1)分析表为:POP：将栈顶元素从栈内弹出。PUSH：将括号内的符号串压入栈。NEXT