自顶向下的语法分析

1第五章自顶向下语法分析方法2语法分析语法分析（Ch3:句子分析）是编译程序的核心部分。其作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）。语法分析方法自顶向下分析自底向上分析3自顶向下分析——面向目标的分析方法确定的自顶向下分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，是最常用的方法之一。不确定的自顶向下分析方法是带回溯的分析方法，实际是一种穷举的试探方法，效率低，代价高，使用较少。自顶向下的语法分析4自顶向下的语法分析5.1确定的自顶向下分析思想5.2不确定的自顶向下分析5.3非LL(1)文法的等价变换5.4LL(1)文法的判别5.5确定的自顶向下分析方法5确定的自定向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）惟一的确定选用哪个产生式替换相应非终结符向下推导，或如何构造一棵相应的语法树。什么样的文法能够进行确定的自顶向下语法分析？5.1确定的自顶向下分析思想6文法G1[S]：S→pA|qBA→cAd|aB→dB|c识别输入串w=pccadd#是否是G1[S]的句子例1自顶向下的推导过程为：S

pApcAdpccAddpccadd##7文法特点：每个产生式右部都由终结符号开始如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始文法在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，分析过程唯一确定。S→pA|qBA→cAd|aB→dB|c8文法G2[S]：S→Ap|Bq

A→cA|aB→dB|b识别输入串w=ccap#是否是G2[S]的句子

例2推导过程：S#Ap#

cAp#

ccAp#

ccap#9S→Ap|Bq

A→cA|a

B→dB|b文法特点：产生式的右部不全是由终结符开始如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始文法中无空产生式对于产生式中相同左部含有非终结符开始的产生式时，可通过考察产生式向下推导时能够推导出的第一个终结符唯一确定该用哪个产生式进行替换。具有相同左部的产生式向下推导时能够推导出不同的终结符10FIRST集的定义设G=(VT，VN，P，S)是上下文无关文FIRST()={a|=>a，a∈VT，，∈V*}若=>ε则规定ε∈FRIST()

称FRIST()为的开始符号集或首符号集。在文法G2中：S->ApA->cA|aFRIST(Ap)={a，c}S->BqB->dB|bFRIST(Bq)={b，d}

使得面向非终结符S为某一输入符号x寻求匹配时,可由x与两集合的归属关系确定选用哪个产生式进行推导。（文法1同）**交集为空无空产生式11例3（含空产生式的文法）文法G[S]：S→aA|dA→bAS|ε识别输入串w=abd#

是否是G[S]的句子当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。A->bAS|b|εA->bAS|d|ε推导过程：SaA

abASabS

abd12FOLLOW集的定义设G=(VT，VN，P，S)是上下文无关文法，A∈VN，S是开始符号FOLLOW(A)={aS=>A,a∈VT，a∈FRIST()，∈V*，∈V+}若S=>

A，且=>ε，则#∈FOLLOW(A)也可定义为：FOLLOW(A)={aS=>…Aa…，且a∈VT}若有S=>

…A，则规定#∈FOLLOW(A)

（用“#”作为输入串的结束符，或称输入串括号）*****13结论当文法中含有形如

A→A→（A∈VN，，∈V*）的产生式时，若和不能同时推导出空，假定=>ε,=>ε则当FIRST()∩(FIRST()∪FOLLOW(A))=Ø时，若当前非终结符为A,面临某一输入符号x，可由x的归属决定选择A的哪个候选式对非终结符A进行替换。**14Select集（Predict集）给定上下文无关文法的产生式A→，A∈VN，∈V*，若=>ε，则SELECT(A→)=FIRST()如果

=>ε，则

SELECT(A→)=(FIRST()-{ε})∪FOLLOW(A)**一个上下文无关文法能进行确定的自顶向下语法分析的充分必要条件是：对每个非终结符A的两个不同产生式，A→，A→，满足

SELECT(A→)∩SELECT(A→)=Ø

其中、不同时能=>ε,这样的文法称为LL(1)文法。LL(1)文法*16LL(1)文法能够使用自顶向下分析技术的文法是LL(1)文法。LL(1)的含义第1个L:自顶向下分析时从左向右扫描输入串第2个L:分析过程中将用最左推导1:只需向右看一个符号便可决定如何推导即选择哪个产生式（进行）推导类似也可以有LL(k)文法，也就是需向前查看k个符号才可确定选用哪个产生式。17例文法G[S]：S→aA|d

A→bAS|εSELECT(S→aA)={a}SELECT(S→d)={d}SELECT(A→bAS)={b}SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=ØSELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,#}=Ø文法为LL(1)文法，可对输入串进行确定的自顶向下分析。18例文法G[S]：S→aAS|b

A→bA|εSELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)={a，b}SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=ØSELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b}≠Ø该文法不是LL(1)文法.不能对输入串（如w=ab）进行确定的自顶向下的语法分析。

S=>aAS=>abAS=>abS=>?=>aS=>ab195.2不确定的自顶向下分析当文法不满足LL(1)文法的条件时，不能进行确定的自顶向下分析，分析过程中会出现回溯现象，即只能进行不确定的自顶向下分析。三种情况下会引起分析过程中的回溯：20第一种情况关于同一非终结符的不同产生式右部FIRST集交集不为空而引起回溯：如：文法S->xAyA->ab|a输入串w=xay，分析过程可能为：关于同一非终结符的不同产生式右部以相同的符号串开始（A->|），称为具有左公因子。左公因子的存在必定会使FIRST集交集不为空。SxAyabSxAya21第二种情况关于同一非终结符的不同产生式右部存在能=>ε的产生式，且该非终结符的FOLLOW集与其它产生式右部FIRST集的交集不为空。如文法G[S]：S→aAS|b

A→bA|εFirst(bA)与Follow(A)的交集不为空。对输入串W=ab的分析存在回溯（前面已经证明）。*22第三种情况文法中含有左递归。文法G，存在U∈Vn，如果有U->U…,则G为左递归文法（直接左递归）类似的：U->V…V->U…（间接左递归）如：S->SaS->b

输入串W=baa的分析：S=>b=>Sa=>ba=>Saa=>baa（回溯）不难证实，若文法中含有间接左递归，也会引起回溯。23不确定的自顶向下分析分析过程是一种试探过程，分析过程需进行回溯，也称这种方法是带回溯的自顶向下分析方法。语法分析的同时往往进行语义分析，回溯代价高，在实际的编译程序设计中很少使用。245.3非LL(1)文法的改造若文法中含有左公因子或左递归，则文法肯定不是LL(1)文法，不能进行确定的自顶向下语法分析。通过提取左公共因子、消除左递归对文法进行等价变换，在某些特殊情况下可使非LL(1)文法变为LL(1)文法。提取左公因子，消除左递归之后文法只是满足LL(1)文法的必要条件，而不是充分条件，所以不一定是LL(1)文法。25提取左公因子若文法中含有形如Ａβ|的产生式，则称文法中含有左公因子。这将导致关于同一非终结符的不同产生式右部的FIRST集交集不为空，不满足LL(1)文法的充要条件。如if语句的文法S→ifEthenS|ifEthenSelseS|other

存在左公因子ifEthenS

影响:遇到if时难以判断用哪一个产生式进行匹配（推导）26提取左公因子可将文法中的Aβ|变换为：ＡB

Bβ|（B为新引入的非终结符）若β和中仍含有左公共因子，可再次提取，直至引入新非终结符的有关产生式再无左公共因子为止。如if语句文法S→ifEthenS|ifEthenSelseS|other改写为：

S→ifEthenSS’|otherS'→ε|elseS27提取左公因子更一般的，可将形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm

的规则改写为

A→αA’|γ1|γ2|…|γmA'→β1|β2|…|βn28例1：文法G1的产生式为(1)S→aSb(2)S→aS(3)S→(1)(2)提取左公共因子后得S→aS(b|)S→

进一步变为G1’：S→aSAS→A→bA→

（非LL(1)文法）

29例2：文法G2的产生式为(1)A→ad

(2)A→Bc(3)B→aA(4)B→bB将(3)(4)代入(2)得到：

(1)A→ad(2)A→aAc(3)A→bBc(4)B→aA(5)B→bB左公共因子可能是隐式的30提取(1)(2)的左公共因子

A→a(d|Ac)A→bBcB→aAB→bB引入新终结符A’(1)A→aA’(2)A→bBc(3)A’→d(4)A’→Ac(5)B→aA(6)B→bB（LL(1)文法）注意：有些文法不能在有限步骤内提取左公因子。(P86例5.9)提取左公因子后若不含空产生式和左递归则文法是LL(1)文法，否则需进一步判定。(1)A→ad(2)A→aAc(3)A→bBc(4)B→aA(5)B→bB31消除直接左递归直接左递归若文法中含有形如A→Aα|β的产生式，则称文法中含有直接左递归（生成的串的形式为ba...）直接左递归的消除：将A→Aα|β替换为A→βA’

A’→αA’｜ε文法S->Sa|b改写后对输入串baaa#是否可进行确定分析？32表达式文法消除左递归G[E]:E→E+T｜TT→T*F｜FF→i｜(E)消除左递归后为：E→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i将A→Aα|β替换为A→βA’A’→αA’｜ε33一般而言，假定关于P的全部产生式是P→P1|P2|…|Pm

|1|2|…|n

则消除P的直接左递归之后为：

P→1P|2P|…|nPP→1P|2P|…|mP|左递归变右递归消除直接左递归34消除间接左递归间接左递归SAa|b(1)(2)ASd|(3)(4)先变换成直接左递归((1)(2)代入(3))SAa|bAAad|bd|

再消除左递归SAa|bAbdA|A

A

adA|35消除一切左递归1.把文法G的所有非终结符按任一种顺序排列成A1，A2，…，An；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DOBEGIN

把形如Ai→Aj的规则改写成

Ai→1|2|…|k;(其中Aj→1|2|…|k是关于Aj的所有规则)END

消除关于Ai规则的直接左递归性

END3.化简由2所得的文法。去除无用产生式。注意该算法要求文法中不含形如A->A的产生式和空产生式。36消除一切左递归例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a 虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc37文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S对于R，不存在直接左递归，把R代入到Q的有关候选后，把Q的规则变为

Q→Sab|ab|b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc|abc|bc|c消除一切左递归38S变成：S→Sabc|abc|bc|c消除S的直接左递归后：

S→abcS|bcS|cS S→abcS| Q→Sab|ab|b R→Sa|a关于Q和R的规则已是多余的，化简为：

S→abcS|bcS|cS S→abcS|消除一切左递归39注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例如，若对前面文法的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：

S→Qc|c Q→Rb|b R→bcaR|caR|aR R→bcaR|

消除一切左递归40非LL(1)文法的改造提取左公因子，消除左递归之后文法只是满足LL(1)文法的必要条件，而不是充分条件，所以不一定是LL(1)文法。根据定义进行判别415.4LL(1)文法的判别根据定义进行判别对每个非终结符A的两个不同产生式，A→，A→，满足SELECT(A→)∩SELECT(A→)=Ø

，其中、不同时能=>ε，这样的文法称为LL(1)文法。为求SELECT(A→)，需求出FIRST(),若

=>ε，则还需求出FOLLOW(A),因此判别步骤为：1)求出能推出的非终结符2)计算非终结符的FIRST集3)计算非终结符的FOLLOW集（若所有非终结符均不能推出空，此步可省）4)计算SELECT集合，根据定义判定。*42以改造后的表达式文法为例G’[E]E→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i431)求出能推出的非终结符P79-80(略)：逐次扫描的过程一般情况：若有形如A->的空产生式，则A能推出空若每个产生式右部都含有终结符，则肯定不能推出空当关于某一非终结符的一个产生式右部全是非终结符且每一个都能推出空时，该非终结符能推出空如：文法G’[E]E→TE’

E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i能推出空能推出空不能推出空不能推出空不能推出空442)计算FIRST集求一个文法符号的FIRST集(1)若XV，则FIRST(X)={X}(2)若XVN，且有产生式Xa…，aV，则aFIRST(X)(3)若XVN，X，则FIRST(X)(4)若X，Y1，Y2，…，Yn都VN，而有X→Y1Y2…Yn，当Y1，Y2，…，Yi-1都=>时(1≤i≤n)，则First(Y1)–{}，First(Y2)–{}，…，First(Yi-1)–{}，First(Yi)都包含在First(X)中(5)当(4)所有Yi=>时(i=1，2，…，n)，则First(X)包含

First(Y1)∪First(Y2)∪…∪First(Yn)∪{}反复使用(2)～(5)直到每个符号的FIRST集不再扩大为止**45表达式文法FIRST(E)=FIRST(T)={}FIRST(E’)=FIRST(T)=FIRST(F)={}FIRST(T’)=FIRST(F)=E→TE’

否E’→+TE’|ε是T→FT’

否T’→*FT’｜ε是F→(E)｜i否(,i(,i(1)若XV，则FIRST(X)={X}(2)若XVN，且有产生式Xa…，aV，则aFIRST(X)(3)若XVN，X，则FIRST(X)(4)若X，Y1，Y2，…，Yn都VN，而有X→Y1Y2…Yn，当Y1，Y2，…，Yi-1都=>时(1≤i≤n)，则First(Y1)–{}，First(Y2)–{}，…，First(Yi-1)–{}，First(Yi)都包含在First(X)中(5)当(4)所有Yi=>时(i=1，2，…，n)，则First(X)=First(Y1)∪First(Y2)∪…∪First(Yn)∪{}｛(,i｝｛*,ε｝｛+,ε｝46求出每个文法符号的FIRST集后可以求出一个符号串的FIRST集若符号串V*，=X1X2…Xn，当X1不能=>，则置First()=First(X1)若对任何j(1≤j≤i-1，2≤i≤n)，FIRST(Xj)，FIRST(Xi)，则当所有FIRST(Xj)(1≤j≤n)，都含有时，则如FIRST(TE’)=FIRST(T)={(,i}FIRST(*FT’)={*}文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM根据定义求解First(S)=First(M)∪First(H)∪{ε}∪{a}={a,b,d,e,ε}First(H)=First(L)∪{ε}={e,ε}First(K)={d}∪{ε}={d,ε}First(L)={e}First(M)=First(K)∪{b}={b,d,ε}例：求文法G[s]每个非终结符的First集47是是是否是483)计算FOLLOW集(1)对于文法的开始符号S，置#于FOLLOW(S)中(2)若ＡαBβ是一个产生式，则把FIRST(β)的非空元素加至FOLLOW(B)中;

如果β=>(即FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。(3)反复使用(2)直至每个非终结符的FOLLOW集不再增大为止。*49FOLLOW(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’)=

{+，*，)，#}表达式文法FIRST(E)={(,i}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i}E→TE’

否E’→+TE’|ε是T→FT’

否T’→*FT’｜ε是F→(E)｜i否(1)对于文法的开始符号S，置#于FOLLOW(S)中(2)若ＡαBβ是一个产生式，则把FIRST(β)的非空元素加至FOLLOW(B)中，如果β=>(即FIRST(β)），则把FOLLOW（A）加至FOLLOW（B）中。文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM根据定义求解Follow(S)={o,#}Follow(H)=Follow(S)∪{f}={f,o,#}Follow(K)=Follow(M)={e,o,#}Follwo(L)=(First(So)-{ε})∪Follow(K)∪(First(M)-{ε})∪Follow(M)=

{a,b,d,e,o,#}Follow(M)=(First(H)-{ε})∪Follow(S)∪(First(L)-{ε})=

{e,o,#}例：求文法G[s]每个非终结符的Follow集是是是否是First(S)={a,b,d,e,ε}First(H)={e,ε}First(K)={d,ε}First(L)={e}First(M)={b,d,ε}51E’–>+TE’|SELECT(E’–>+TE’)=FIRST(+TE’)=｛+｝SELECT(E’–>)=FOLLOW(E′)=｛)

,＃｝T’–>*FT’|SELECT(T’–>*FT’)=FIRST(*FT’)=｛*｝SELECT(T’–>)=FOLLOW(T′)=｛+，)，＃｝F–>(E)|iSELECT(F–>(E))=FIRST((E))=｛(｝SELECT(F–>i)=FIRST(i)=｛i｝关于同一非终结符的不同产生式的SELECT集合交集为空结论：G’[E]是LL（1）文法4)计算SELECT集FIRST(E)={(,i}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={+,*,),#}给定上下文无关文法的产生式A→，A∈VN，∈V*，若=>*

ε，则SELECT(A→)=FIRST()。如果

=>*

ε，则

SELECT(A→)=(FIRST()-{ε})∪FOLLOW(A)求文法G[s]的Select集并判定是否为LL(1)文法文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM52First(S)={a,b,d,e,ε}First(H)={e,ε}First(K)={d,ε}First(L)={e}First(M)={b,d,ε}Follow(S)={o,#}Follow(H)={f,o,#}Follow(K)={e,o,#}First(L)={a,b,d,e,o,#}Follow(M)={e,o,#}是是是否是?YES！53关系图法求FIRST集、FOLLOW集（略）54例文法:

S→AB|bCA→b|B→aD|

C→AD|b

D→aS|c判断其是否为LL(1)文法求FIRST集FIRST(S)=(FIRST(A)-{ε})∪FIRST(B)-{ε})∪{ε}∪{b}={a,b,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}此时是否能够得到结论？55文法S→AB|bCA→b|B→aD|

C→AD|b

D→aS|c求FOLLOW集FOLLOW(S)={#}∪FOLLOW(D)={}(First(B)-{})∪(First(D)-{})∪FOLLOW(S)

={a,c}

∪FOLLOW(S)={}FOLLOW(B)=FOLLOW(S)={}FOLLOW(C)=FOLLOW(S)={}FOLLOW(D)=FOLLOW(B)∪FOLLOW(C)={}FIRST(B)={a,ε}FIRST(D)={a,c}####a,c,#FOLLOW(A)=56求SELECT集合S→AB|bCSELECT(S→AB)=(FIRST(AB)-{})∪FOLLOW(S)={a,b,#}SELECT(S→bC)=FIRST(bC)={b}交集不为空A→b|SELECT(A→b)=FIRST(b)={b}SELECT(A→)=)=(FIRST()-{})∪FOLLOW(A)={a,c,#}文法S→AB|bCA→b|B→aD|

C→AD|bD→aS|c57B→aD|

SELECT(B→aD)=FIRST(aD)={a}SELECT(B→)=)=(FIRST()-{})∪FOLLOW(B)={#}C→AD|bSELECT(C→AD)=FIRST(AD)={a,b,c}SELECT(C→b)=FIRST(b)={b}交集不为空D→aS|cSELECT(D→aS)=FIRST(aS)={a}SELECT(D→c)=FIRST(c)={c}判定：结论：G[S]不是LL(1)文法文法S→AB|bCA→b|B→aD|

C→AD|bD→aS|c58典型例题及解答给定一文法，进行改写后判定是否为LL(1)P97例2P98例3通常将非终结符的FIRST集FOLLOW集表示在一张表中（例如P96表5.5）作业：P101.7，选做其一595.5确定的自顶向下分析方法递归子程序法（预测分析）分析高效（线性时间）、容易实现（方便手工编码）、错误定位和诊断信息准确、被很多开源和商业的编译器所采用GCC4.0，LLVM，……表驱动的预测分析方法分析高效（线性时间）、错误定位和诊断信息准确、有很多开源或商业的生成工具ANTLR，……前提：文法为LL(1)文法60递归子程序法实现思想对每个非终符按其产生式结构产生相应语法分析子程序；终结符产生匹配命令，而非终结符则产生调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序法（递归下降分析方法）。61当产生式形如:A->β1|β2|…|βn

则按下面的方法编写子程序A：（Pascal风格）procedureA()

beginiftoken∈Select(A->β1)thenθ(β1)else

iftoken∈Select(A->β2)thenθ(β2)else

……

iftoken∈Select(A->βn)

thenθ(βn)else

err()

end其中对βi=X1X2…Xn，θ(βi)=θ’(X1);θ’(X2);…;θ’(Xn);如果X∈VN，θ’(X)=X();如果X∈VT，θ’(X)=Match(X)

（若匹配，则Match中应包含向前读一输入符号的动作，也有的书中写为：advance()或nextsym()）如果X=ε,θ(ε)=skip(空语句)递归子程序法62递归子程序法例：1）假设有文法Z→aBaB→bB|cSelect(Z→aBa)={a},Select(B→bB)={b},Select{B→c}={c}

则相应的递归子程序可如下：63procedureZ()//Z→aBabegin

iftoken==athenMatch(a)；//ReadToken

B（）；

Match(a)；

elseerr()；

end;procedureB()//B→bB|c

begin

iftoken==bthenMatch(b);//ReadToken

B（）;

elseiftoken==cthenMatch(c);

elseerr()

end;语法分析主程序：BeginReadToken;Z()；

IFtoken

<

>’#’THENerr()EndZ→aBaB→bB|c对输入串abbbbbbbbbbbbca#的递归下降分析match(a);B();match(a);abbbbbbbbbbbbca64例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

PROCEDUREE()BEGIN T()；E()END

PROCEDUREE()BEGINIFtoken==‘+’THEN BEGIN ADVANCE()；

T()；E()

END//否则认为与匹配END65PROCEDURET()BEGIN F()；T()END例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

PROCEDURET()BEGINIFtoken==‘*’THENBEGINADVANCE()；

F()；T()END//否则认为与匹配END66例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

PROCEDUREF()BEGINIFtoken==‘i’THENADVANCE()ELSE IFtoken==‘(’THEN BEGIN ADVANCE(); E()；

IFtoken==‘)’THENADVANCE() ELSEERR() END ELSEERR()END67例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

主程序:PROGRAMPARSER()BEGINADVANCE();E();IFtoken

<

>’#’THENERR()END.68递归子程序法优点：1）直观、简单、可读性好2）便于扩充缺点：1)递归算法的实现效率低2)处理能力相对有限（只能处理LL(1)文法）3)通用性差，难以自动生成69表驱动的预测分析（LL(1)分析方法）自顶向下分析的另一种方法。一个预测分析器（或LL(1)分析器）由三部分组成：总控程序：对所有的文法和输入串都是一样的。分析表

M[A,a]是一个矩阵，AVN

，aVT或‘＃’，M[A,a]有两种情况：产生式A->X1X2…Xn空（出错标志）分析表对不同的文法是不同的分析栈

STACK用于存放分析过程中的文法符号改造后表达式文法的LL(1)分析表70总控程序分析表X#输入串分析栈STACKa1a2...ai…#预测分析器预测分析器71总控程序是如何工作的？回忆一个自顶向下的分析过程（手工）：文法G1[S]：S→pA|qBA→cAd|aB→dB|c识别输入串w=pccadd#是否是G1[S]的句子自顶向下的推导过程为：S#pA#pcAd#pccAdd#pccadd#自动化72初始情况下：分析栈中为“#S”（S为文法开始符号），分析串以#结束。总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1.若X＝a＝‘＃’，则宣布分析成功，停止分析。2.若X＝a‘＃’，则X出栈，a指向下一个输入符号。匹配成功总控程序分析成功733.若X是一个非终结符，则查看分析表M。若M[X，a]中存放着关于X的一个产生式，则X出栈，将产生式右部符号串逆序入栈(若产生式右部为，则只将X出栈即可)若M[X，a]为空或为“出错标志”，则调用错误处理程序进行相应的错误处理。推导总控程序74例：对于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 输入串为i1*i2+i3，利用分析表进行预测分析：75步骤

符号栈

输入串

所用产生式0 #E i1*i2+i3#E→TE1 #ET i1*i2+i3#T→FT2 #ETF i1*i2+i3#F→i3 #ETi i1*i2+i3# i匹配为何要逆序入栈76步骤

符号栈

输入串

所用产生式3 #ETi i1*i2+i3# i匹配4 #ET *i2+i3#T→*FT5 #ETF* *i2+i3# *匹配6 #ETFi2+i3#F→i7 #ETi i2+i3#i匹配77步骤

符号栈

输入串

所用产生7 #ETi i2+i3#i匹配8 #ET +i3#T→9 #E +i3# E→+TE10 #ET+ +i3# +匹配11 #ET i3#T→FT78步骤

符号栈

输入串

所用产生11 #ET i3#T→FT12 #ETF i3# F→i13 #ETi i3# i匹配14 #ET #T→15 #E # E→16 # # acc(接受)79课堂练习：已知文法G[S]及其LL(1)分析表，请给出对输入串aaabd#的预测分析过程。80分析表M[A,a]的构造基本思想:当文法中某一非终结符出现在栈顶时,根据当前的输入符号,分析表应指示要选择该非终结符的哪一条规则进行下一步的匹配（推导）。构造方法：对每个终结符或’#’用a表示若aSelect(A->α)，则把A->α放入M[A,a]所有无定义的M[A,a]标上出错标记或置空。81也可表述为（略）：在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。1.对文法G的每个产生式A→执行第2步和第3步；2.对每个终结符aFIRST()，把A→加至M[A，a]中；3.若FIRST()，则对任何bFOLLOW(A)把A→加至M[A，b]中。4.把所有无定义的M[A，a]标上“出错标志”。82例如：对于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 1.首先计算每个非终结符的FIRST集和FOLLOW集

FIRST(E)={(,i}FIRST(E)={+,}FIRST(T)={(,i}FIRST(T)={*,}FIRST(F)={(,i} FOLLOW(E)={),#}FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}832.计算产生式的Select集合SELECT(E–>TE’)=FIRST(TE’)=｛(，i｝SELECT(T–>FT’)=FIRST(FT’)=｛(，i｝E’–>+TE’|SELECT(E’–>+TE’)=FIRST(+TE’)=｛+｝SELECT(E’–>)=FOLLOW(E′)=｛)，＃｝T’–>*FT’|SELECT(T’–>*FT’)=FIRST(*FT’)=｛*｝SELECT(T’–>)=FOLLOW(T′)=｛+，)，＃｝F–>(E)|iSELECT(F–>(E))=FIRST((E))=｛(｝SELECT(F–>i)=FIRST(i)=｛i｝3.构造表达式文法的分析表也可只写产生式右部SELECT集的另一种表示84①LL(1)的含义（P78）②预测分析法是