自顶向下语法分析详解

自顶向下语法分析详解演示文稿当前1页，总共47页。（优选）自顶向下语法分析当前2页，总共47页。任务：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。两大类分析方法：自顶向下分析自底向上分析语法分析的任务当前3页，总共47页。+若xS则xL(G[S])否则xL(G[S])G[S]存在主要问题:回溯问题,左递归问题主要方法：递归子程序法、LL分析法自顶向下分析算法的基本思想为：自底向上分析算法的基本思想为：+若xS则xL(G[S])否则xL(G[S])G[S]存在主要问题:“可归约串”的识别问题主要方法：算符优先分析法、LR分析法当前4页，总共47页。5.1自顶向下分析法自顶向下分析的一般过程从S出发采用最左推导，试图逐步推出输入串α,αL(G[S])?S作为语法树的根，试图自上而下地为α构造一棵语法树若叶结点从左向右排列恰好α，则表示α是文法的句子，而这棵语法树就是句子α的语法结构若构造不出语法树，则α不是文法的句子当前5页，总共47页。自顶向下分析方法分类确定的不确定的回溯当前6页，总共47页。【例】

G1[S]:S→pA|qBA→cAd|aB→dB|c识别输入串w=pccadd是否是G1[S]的句子试探推导过程：SpApcAdpccAddpccadd试探成功

这个文法的特点：1、每个产生式的右部都由终结符号开始2、如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始当前7页，总共47页。【例】

G2[S]:S→Ap|BqA→a|cAB→b|dB识别输入串w=ccap是否是G2[S]的句子试探推导过程：SApcApccApccap试探成功

这个文法的特点：1、产生式的右部不全是由终结符开始2、如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始3、文法中无空产生式当前8页，总共47页。1.FIRST集FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：，则规定∈FIRST()若【例】

S→aAbA→cd|ca…，a∈VTFIRST()={a|FIRST(aAb)={a}FIRST(cd)={c}FIRST(c)={c}【例】

S→AaA→a|

FIRST(a)={a}FIRST()={}FIRST(Aa)={a}FIRST(S)={a}FIRST(A)={c}FIRST(S)={a}FIRST(A)={a,}当前9页，总共47页。（1）若α=aβ，且a∈VT，则a∈FIRST(α)；

例：FIRST(i)={i}FIRST(+TE')={+}E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i构造FIRST集的算法（2）若α=Xβ，X∈VN，且有产生式X→b…，则把b加入到FIRST(α)中；

例：FIRST(FT')={(,i}??当前10页，总共47页。（3）若α=X1X2…Xn，其中Xi∈VN,1≤i≤n；①将FIRST(X1)中的一切非ε的终结符加进FIRST(α)；②若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)；③若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)；④依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i例：FIRST(FT')=

注意：要顺序往下做，一旦不满足条件，过程就要中断进行FIRST(F)-{ε}={(,i}当前11页，总共47页。【例】

G2[S]:S→Ap|BqA→a|cAB→b|dB识别输入串w=ccap是否是G2[S]的句子试探推导过程：SApcApccApccap试探成功

FIRST（Ap）＝｛a，c｝FIRST（Bq）＝｛b，d｝当前12页，总共47页。FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(,i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(,i}【例】G[E]E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i计算文法中非终结符的First集合当前13页，总共47页。【例】

G3[S]:S→aA|dA→bAS|ε识别输入串w=abd是否是G3[S]的句子试探推导过程：SaAabASabSabd试探成功

这个文法的特点：1、含有空产生式2、非空产生式右部首符号集合两两不相交3、紧跟该非终结符右边可能出现的终结符集合也不相交当前14页，总共47页。2.FOLLOW集FOLLOW(A)：是所有句型中紧接A之后的终结符号或#对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下：…A，则规定#∈FOLLOW(A)若S…Aa…，a∈VT}FOLLOW(A)={a|SE→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|iT+TE'

，则+∈FOLLOW(T)E当前15页，总共47页。构造集合FOLLOW的算法（1）若A为开始符号，则把“#”加入FOLLOW(A)中；（2）若B→A(≠)，则把FIRST()-{}加入FOLLOW(A)中；

注：FOLLOW集合中不含有ε（3）若B→A或B→A，且则把FOLLOW(B)加入FOLLOW(A)中。，E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i#∈FOLLOW(E)由F→(E)可知，

)∈FOLLOW(E)由E→TE'，应把FOLLOW(E)加入∈FOLLOW(E')由E'→+TE'且E'ε，应把FOLLOW(E')加入FOLLOW(T)当前16页，总共47页。【例】G[E]E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|iFOLLOW(E)={#,)}∵E是开始符号∴#∈FOLLOW(E)又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}

∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)

又E’ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}

∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}

∵T→FT’∴FOLLOW(F)=FIRST（T’）-{ε}

又T’ε∴FOLLOW(T)加入FOLLOW(F)FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}求FOLLOW集合当前17页，总共47页。LL的含义－自左向右扫描分析输入符号串－从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则5.2LL(1)文法的判别要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法。

当前18页，总共47页。

一个文法G是LL(1)的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式Ａ

αβ，下面的条件成立：１．FIRST(α)∩FIRST(β)=,也就是α和β推导不出以同一个终结符a为首的符号串；它们不应该都能推出．２.假若β=>

，那么，FIRST（α)∩FOLLOW（A）＝.也就是，若β=>

,则α所能推出的串的首符号不应在FOLLOW(A）中．**当前19页，总共47页。若α=>ε，则SELECT(Aα)=First(α)若α=>ε，则SELECT(Aα)=(First(α)-{ε})∪Follow(A)**一个文法是LL(1)的充要条件：对于每个形如Ａ

αβ的产生式，满足Select(Ａα)∩Select(Ａβ)=其中：α、β不能同时推出εLL(1)文法的判别条件当前20页，总共47页。求出能推出ε的非终结符计算First集合计算Follow集合计算Select集合不满足Select(Ａα)∩Select(Ａβ)=的不是LL(1)文法，否则是LL(1)文法。LL(1)文法的判别步骤当前21页，总共47页。【例】G[E]：E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i判别该文法是否为LL(1)文法？FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}当前22页，总共47页。E’–>+TE’|FIRST(+TE')=｛+｝

FOLLOW(E')=｛)，＃｝T’–>*FT’|FIRST(*FT')=｛*｝

FOLLOW(T')=｛+,)，＃｝F–>(E)|iFIRST((E))=｛(｝

FIRST(i)=｛i｝所以G[E]是LL（1）的【例】G[E]：E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i当前23页，总共47页。例1：设有文法

(1)S->xAy (2)A->**|*

现有输入串：x*y

其分析过程如下：SxAy**失败，需要退回，重新选取A的侯选式这时使得分析器的动作不稳定产生的原因？x*y输入符号串：*自顶向下分析面临的问题

问题1：回溯当前24页，总共47页。1.回溯问题什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件：文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的低效率：语法分析要重做、语义处理工作要推倒重来自顶向下分析存在的主要问题当前25页，总共47页。迷宫求解当前26页，总共47页。消除回溯的途径：改写文法对具有多个右部的规则反复提取左因子【例】对下述两个产生式，提取公共左因子改造文法。<if语句>→ifEthenS1elseS2

<if语句>→ifEthenS1

<if语句>→ifEthenS1UU→elseS2|ε当前27页，总共47页。A→αβ1|αβ2|…|αβn如果β1~βn中还有几个首符号相同，可反复提取引入了许多非终结符和ε产生式A→αA′A′→β1|β2|…|βn当前28页，总共47页。1.递归规则：规则右部有与左部相同的符号 左递归规则：A→A…

右递归规则：A→…A

自嵌入递归规则：A→…A…递归文法2.递归文法：含有递归规则的文法，为直接递归文法A→BaB→AbG[S]：S→L|SL|SDL→a|b|…|zD→0|1|…|9间接递归文法当前29页，总共47页。递归文法的优点：可用有穷条规则，定义无穷语言例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!G[S]：S→SD|DD→0|1|2|3|4|5|6|7|8|9当前30页，总共47页。左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环G[E]：E→i+i|i*i|(i+i)*i该文法所描述的语言为L(G)={i+i,i*i,(i+i)*i}，无法表示无穷的表达式语言当前31页，总共47页。2.左递归问题【例】文法G[E]：E→E+T|TT→T*F|FF→(E)|i给出i*i+i自顶向下的分析过程。要实行自顶向下分析，必须要消除文法的左递归从左向右扫描源程序，同时实施最左推导EE+TE+TE+T…失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。当前32页，总共47页。将左递归规则改为右递归规则A→A|

【例】文法G[E]：E→E+T|TT→T*F|F

F→(E)|iE→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i消除左递归A→A'A'→A'|（1）消除直接左递归当前33页，总共47页。消除直接左递归——课内练习文法G:PPaPb|BaP转化为：PBaPP`P`aPbP`|注：只有最左边的P参加变换。当前34页，总共47页。(2)消除间接左递归（了解自学）先通过产生式进行非终结符置换将间接左递归变为直接左递归消除直接左递归把置换的产生式加入详例见书文法G6，P89当前35页，总共47页。5.3某些非LL(1)文法到LL(1)文法的等价转换消除左递归和提取公共左因子

【例】G[S]:S→aSb|AA→bAc|bBcB→Ba|aS→aSb|AA→bAc|bBcB→aB'B'→aB'|消除左递归提取公因子S→aSb|AA→bA'A'→Ac|BcB→aB'B'→aB'|LL(1)文法的判别条件LL(1)文法【例】G[S]:S→aSb|AA→bAc|bBcB→Ba|a当前36页，总共47页。不确定的自顶向下分析思想当文法不满足LL(1)时，不能用确定的自顶向下分析，但可用不确定的自顶向下分析，也就是带回溯的自顶向下分析法（试探）。由于相同左部的产生式的右部First集交集不为空引起由于相同左部非终结符的右部存在能推导出的产生式，且该非终结符的Follow集中含有其他产生式右部First集的元素文法含左递归当前37页，总共47页。确定的自顶向下分析方法递归子程序法对文法中的每个非终结符（语法成分）编写一个子程序，而子程序的代码结构由相应非终结符的产生式右部所决定：产生式右部的终结符与输入符号相匹配非终结符与相应的子程序调用对应构造方法非常简单程序结构清晰递归调用较多，占用内存多、速度慢如果所采用的高级语言不允许递归，则不能使用此方法

特点当前38页，总共47页。自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导

LL(1):向前看一个输入符号，便能唯一确定产生式

LL(k):向前看k个输入符号，才能唯一确定产生式基本思想：LL(1)分析法使用下推自动机的方式实现。使用一个二维分析表和栈联合进行控制来实现分析。确定的自顶向下分析方法预测分析法当前39页，总共47页。

a1a2a3…ai…an#

分析表M总控程序X1…Xn-1Xn#LL(1)分析器的逻辑结构：分析栈、分析表、总控程序文法符号根据栈顶符号X和当前输入符号a来决定分析器的动作当前40页，总共47页。在实际语言中，每一种语法成分都有确定的左右界符，为研究问题方便，统一以‘＃’表示输入串结束分析表：二维矩阵MA→αi

A∈Vn、αi∈V*、a∈VTor#

errorM[A,a]=E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i

i

+

*

(

)

#

E

E→TE'

E→TE'

E'

E'→

+TE'

E→ε

E→ε

T

T→FT'

T→FT'

T'

T'→ε

T'→*FT'

T'→ε

T'→ε

F

F→

i

F→(E)

第1列为非终结符第1行为终结符+’#’每个元素为产生式或空分析表中的元素表示：在分析时需要将A展开，如果当前符号为a时，应该选择元素M[A,a]中存放的产生式。如果M[A,a]为空，表示出现语法错误。当前41页，总共47页。预测分析表构造算法1.对每个终结符aSelect(Ａ)，把Ａ加至[A,a]中；2.把所有无定义的[A,a]标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。当前42页，总共47页。E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i

i

+

*

(

)

#

E

E→TE'

E→TE'

E'

E'→

+TE'

E→ε

E→ε

T

T→FT'

T→FT'

T'

T'→ε

T'→*FT'

T'→ε

T'→ε

F

F→

i

F→(E)

请按照上述算法构造分析表当前43页，总共47页。总控程序算法描述将’#’压入堆栈中，将开始符号S压入堆栈中读取下一个符号到a；每次执行下述动作：栈顶符号弹出放入X中；如果X为终结符号：如果X==a==‘#’，分析结束，接受句子。如果X==a!=‘#’，表明成功匹配;X出栈,a取下一个符号如果X!=a，出错处理。如果X为非终结符号,则查分析表M:如果M[X,a]为空，出错处理。如果M[X,a]=‘X1X2…Xn’,则:{ X出栈;