第5章自顶向下语法分析方法完教材课程

第5章自顶向下语法分析方法2025/1/11第5章自顶向下语法分析方法Page2第五章

自顶向下语法分析方法学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL(1)文法了解：不确定的自顶向下分析2025/1/11Page3第5章自顶向下语法分析方法语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子.分类:语法分析自顶向下分析（第五章）自底向上分析确定的不确定的算符优先分析（第六章）LR分析（第七章）自顶向下的基本思想:

从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子。2025/1/11第5章自顶向下语法分析方法Page45.1 确定的自顶向下分析思想5.2 LL(1)文法的判别5.3 某些非LL(1)文法到LL(1)文法的等价变换5.4 不确定的自顶向下分析思想5.5 确定的自顶向下分析方法第五章自顶向下语法分析方法2025/1/11Page6第5章自顶向下语法分析方法1确定分析的条件

从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。2025/1/11Page7第5章自顶向下语法分析方法例1设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b

若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特点：

(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。2025/1/11Page8第5章自顶向下语法分析方法例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集）——First集，分析过程可能是确定的。若输入串W=ccap,自顶向下的推导过程为：2025/1/11Page9第5章自顶向下语法分析方法例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=>abd

S=>abAS=>abS文法的特点是：包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集）——Follow集，分析过程可能是确定的。=>aA2025/1/11Page10第5章自顶向下语法分析方法1确定分析的条件要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义开始符号集FIRST集后跟符号集FOLLOW集选择集合SELECT集2025/1/11Page11第5章自顶向下语法分析方法2

开始符号集FIRST(α)的定义定义:

设G=(VN,VT,P,S)是上下文无关文法，

(VN

VT)*

FIRST(

)={a

VT|

*a}

若

*ε

则规定ε∈FIRST(

)

直观上说，文法符号串

的开始符号集是由

推导出的开头的终结符（包括ε）组成。2025/1/11Page12第5章自顶向下语法分析方法例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)=FIRST(Bq)=FIRST(a)=FIRST(cA)=FIRST(b)=FIRST(dB)=由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析{a,c}{b,d}{a}{c}{b}{d}First:开始符号集2025/1/11Page13第5章自顶向下语法分析方法例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>ApS→ApFIRST(Ap)={a,c}S→BqFIRST(Bq)={b,d}A→aFIRST(a)={a}A→cAFIRST(cA)={c}B→bFIRST(b)={b}B→dBFIRST(dB)={d}若输入串W=ccap,自顶向下的推导过程为：2025/1/11Page14第5章自顶向下语法分析方法3

后跟符号集FOLLOW(A)的定义定义： 设G=(VT,VN,P,S)是上下文无关文法，A∈VN

，

FOLLOW(A)={a|S=>*…Aa…，a∈VT}， 若有S=>*…A，则规定#∈FOLLOW(A)

（注：#输入串#，‘#’做为输入串的结束符） 直观上说，非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。2025/1/11Page15第5章自顶向下语法分析方法例文法G3[S]: S→aA|dA→bAS|ε由S=>*S

得#∈FOLLOW(S)

由S=>aA=>abAS=>abbASS=>abbASaA

…=>abbASd

FOLLOW(S)={#,a,d}由S=>*aA得#∈FOLLOW(A)

由S=>*abAS=>*abAaA得a∈FOLLOW(A)

…=>*abAd

得d∈FOLLOW(A)

FOLLOW(A)={#,a,d}2025/1/11Page16第5章自顶向下语法分析方法3

后跟符号集FOLLOW(A)的定义说明：对于非终结符A的两个产生式A→bAS和A→ε：当输入符号∈FIRST(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d}时，选A→ε推导。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。2025/1/11Page17第5章自顶向下语法分析方法例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=>abd

S=>abAS=>abS文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。=>aAFIRST(bAS)={b}FOLLOW(A)={#,a,d}2025/1/11Page18第5章自顶向下语法分析方法4

选择集合SELECT(A→α)的定义定义 对给定的上下文无关文法的产生式A→α，A∈VN，α∈V*，若α≠>*ε,则

SELECT(A→α)=FIRST(α)若α=>*ε,则

SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page19第5章自顶向下语法分析方法4

选择集合SELECT(A→α)的定义解释 当A面对应输入符a，若First(α)中包含a，在自顶向下的分析中应选择产生式A→α进行推导； 此外若α可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a属于Follow(A)时，选择产生式A→α也是可以的。

直观上说某产生式A→α的SELECT集是指遇到哪些输入符号（包括#）时选用该产生式向下推导。SELECT(A→α)={a,b,c}2025/1/11Page20第5章自顶向下语法分析方法4

选择集合SELECT(A→α)的定义即：若α≠>*ε,则是否选择A→α这条产生式进行推导，主要是看当时输入字符是否属于FIRST(α)，若是，则选它。若α=>*ε,则是否选择A→α这条产生式进行推导，除了看当时输入字符是否属于FIRST(α)，还可以看当时输入字符是否属于FOLLOW(A)，若属于其中一个集合，则选它。若α≠>*ε,则SELECT(A→α)=FIRST(α)若α=>*ε,则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page21第5章自顶向下语法分析方法例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=SELECT(S→d)=SELECT(A→bAS)=SELECT(A→ε)=若α≠>*ε,则SELECT(A→α)=FIRST(α)若α=>*ε,则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)FIRST(aA)=FIRST(d)=FIRST(bAS)=FOLLOW(A)={#,a,b}{b}{d}{a}2025/1/11Page22第5章自顶向下语法分析方法4选择集合SELECT(A→α)的定义说明： 同一非终结符的不同产生式A→α与A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，则一定可以进行确定的自顶向下分析。SELECT(A→α)={a,b}SELECT(A→β)={c,d}SELECT(A→α)={a,b}SELECT(A→β)={a,d}可确定不可确定2025/1/11Page23第5章自顶向下语法分析方法5LL(1)文法的定义定义:

一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A→α与A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ（无交集）。LL(1)文法的含义是：第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。2025/1/11Page24第5章自顶向下语法分析方法例有文法G[S]为：

S→aAS S→b A→bA A→εSELECT(S→aAS)={a}由于SELECT(A→bA)∩SELECT(A→ε)={b}≠Φ，所以文法G[S]不是LL(1)文法，当A遇输入符b时，不能确定选A→bA还是A→ε去推导。SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)=Follow(A)={a,b}2025/1/11第5章自顶向下语法分析方法Page25§5.2LL(1)文法的判别要判别一个上下文无关文法是否是LL(1)文法分为五步：

1.

求出能推出ε的非终结符集

2.

计算每个产生式右部α的FIRST(α)集

3.

计算每个非终结符A的FOLLOW(A)集

4.

计算每个产生式A→α的SELECT(A→α)集

5.

按LL(1)文法的定义判别2025/1/11Page26第5章自顶向下语法分析方法1.

求出能推出ε的非终结符集步骤：(1)第1次扫描——扫描文法中的产生式对能直接推出ε的产生式左部的终结符标“是”。删除所有右部含有终结符的产生式。若以某一非终结符为左部的所有产生式都被删除，则该非终结符不能推出ε，将其标为“否”。2025/1/11Page27第5章自顶向下语法分析方法1.

求出能推出ε的非终结符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非终结符SABCD第1次扫描第2次扫描是是否2025/1/11Page28第5章自顶向下语法分析方法1.

求出能推出ε的非终结符集(2)第2次扫描——扫描产生式右部的符号对每个产生式p:A→X1Xn，如果X1,…,Xn都被标为“是”(即X1,…,Xn都能推出ε)，则A也能推出ε，将其标为“是”。如果A→Y1Yn中，Y1Yn中任一个已被标为“否”，则删掉该产生式，若这么做使得A的所有产生式都被删去，则A不能推出ε，将其标为“否”。2025/1/11Page29第5章自顶向下语法分析方法1.

求出能推出ε的非终结符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非终结符SABCD第1次扫描第2次扫描是是否是否能推出ε的非终结符集为{A,B,S}2025/1/11Page30第5章自顶向下语法分析方法2.

计算每个产生式右部α的FIRST(α)集首先对每一文法符号X

(X

VT

VN)，求FIRST(X)的算法:对每个a

VT

：FIRST(a)={a}对每个A

VN

：若

A

*ε

，则ε

FIRST(A)对每个A

VN

：若A→a···,a

VT

，则a

FIRST(A)2025/1/11Page31第5章自顶向下语法分析方法2.

计算每个产生式右部α的FIRST(α)集若X,Y1,Y2,…,Yn都

VN,有产生式X→Y1Y2…Yn.当Y1,Y2,…,Yn-1都

*ε时，FIRST(Y1)-{ε},FIRST(Y2)-{ε},…,FIRST(Yn-1)-{ε},FIRST(Yn)都包含在FIRST(X)中。当4中所有Yi

*ε，则FIRST(X)=FIRST(Y1)

FIRST(Y2)…FIRST(Yn){ε}2025/1/11Page32第5章自顶向下语法分析方法例G[S]： S→AB S→

bC A→b A→

ε B→aD B→

ε C→AD C→

b D→aS D→

cbaacbacεaεbεbaFirst集(3)baacbεaεb

εbFirst集(2)ba

εεεFirst集(1)ABCDabSabFirst集(0)已求出能推出ε的非终结符集为{A,B,S}babacaacεεεb2025/1/11Page33第5章自顶向下语法分析方法利用求出每个文法符号的FIRST集求符号串的FIRST集设α=X1X2…Xn当X1不能=>*ε，则FIRST(α)=FIRST(X1)若对任何j(1≤j＜n）都有ε∈FIRST(Xj),

则FIRST(α) =(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε}) ∪FIRST(Xj+1)若对所有i(1≤i≤n)，都有ε∈FIRST(Xi)，

则

FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)∪{ε}2025/1/11Page34第5章自顶向下语法分析方法例G[S] S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c已求出非终结符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}产生式右部符号串的开始符集合为:S→ABFIRST(AB)=

S→bCFIRST(bC)=

A→εFIRST(ε)=

A→b FIRST(b)=

C→ADFIRST(AD)=

D→aSFIRST(aS)=

FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}{b}{b}(FIRST(A)-{ε})∪FIRST(D)={b,a,c}{a}{ε}2025/1/11Page35第5章自顶向下语法分析方法3．计算每个非终结符A的FOLLOW(A)集1.对所有A

VN令Follow(A)={};对开始符S，令Follow(S)={#}因为S=>*S，显然#∈FOLLOW(S)2.

对每条产生式A→xBy，考察产生式右部的每一非终结符B，x,y∈V*，如果y不能推出ε

Follow(B)=Follow(B)

First(y),否则,若y

*ε，

Follow(B)=Follow(B)

(First(y)-{ε})

Follow(A)3.

重复2，直至对所有A

VN，Follow(A)收敛为止。若a∈FOLLOW(A),则表明S=>*…Aa…，由于A→xBy，且y=>*ε,则有

S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)2025/1/11Page36第5章自顶向下语法分析方法例G[S]：[1]S→AB[2]S→bC[3]A→b[4]A→ε[5]B→aD[6]B→ε[7]C→AD[8]C→b[9]D→aS[10]D→c已求出非终结符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε} First(C)={a,b,c}First(D)={a,c}#D#C#Ba#A###a#c＃＃＃SFollow集(2)Follow集(1)Follow集(0)c2025/1/11Page37第5章自顶向下语法分析方法4．计算每个产生式A→α的SELECT(A→α)集按定义计算SELECT(A→α)：若α≠>*ε，则

SELECT(A→α)=FIRST(α)若α=>*ε，则

SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page38第5章自顶向下语法分析方法例G[S]：

S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c是否=>*εFirst集Follow集S是{a,b,ε}{#}A是{b,ε}{a,c,#}B是{a,ε}{#}C否{a,b,c}{#}D否{a,c}{#}部分产生式的select集合SELECT(S→AB)=SELECT(S→bC)=SELECT(A→ε)=SELECT(A→b)=SELECT(B→aD)=SELECT(C→AD)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}FIRST(bC)={b}FIRST(b)={b}FIRST(aD)={a}FIRST(AD)={b,a,c}(FIRST(ε)-{ε})∪FOLLOW(A)={a,c,#}2025/1/11Page39第5章自顶向下语法分析方法5.

按LL(1)文法的定义判别产生式的select集如下:SELECT(S→AB)={b,a,#} SELECT(S→bC)=={b}SELECT(A→ε)={a,c,#} SELECT(A→b)={b}SELECT(B→ε)={#} SELECT(B→aD)={a}SELECT(C→AD)={b,a,c} SELECT(C→b)={b}SELECT(D→aS)={a} SELECT(D→c)={c}由于

SELECT(S→AB)∩SELECT(S→bC)={b}≠ф SELECT(C→AD)∩SELECT(C→b)={b}≠ф所以文法G[S]不是LL(1)文法一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A→α与A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ2025/1/11第5章自顶向下语法分析方法Page40非LL(1)文法含有左公共因子的文法

若文法中含有形如：A→αβ|αr的产生式，称文法含有左公共因子。 显然, SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等价变换2025/1/11第5章自顶向下语法分析方法Page41含有左递归的文法

文法中只要含有下列形式的产生式（含有①或含有②或二者皆有），则称文法含有左递归:A→AβA→Bβ B→Aα

在①中含有左递归的产生式，称为直接左递归；

在②中虽然没有含左递归的产生式，

但A=>Bβ=>Aαβ即A=>+

A…,称为间接左递归.5.3某些非LL(1)文法到

LL(1)文法的等价变换2025/1/11第5章自顶向下语法分析方法Page42以直接左递归为例，若有如下产生式

A→A

|

A→其中和

为任意语法符号串。不难证明有下面关系式：

Select(A→A

))

First(A

)

First(

) Select(A→

))

First(

)故A→A

和A→的Select集相交，不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等价变换A

A

A

A

…不知何时结束不确定若α≠>*ε,则SELECT(A→α)=FIRST(α)若α=>*ε,则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11第5章自顶向下语法分析方法Page43对非LL(1)文法进行等价变换提取左公共因子消除左递归 注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。5.3某些非LL(1)文法到

LL(1)文法的等价变换2025/1/11Page44第5章自顶向下语法分析方法将产生式A→αβ|αr等价变换为: A→α(β|r)， 将括号内用一新引入的非终结符A’表示,得 A→αA’，A’→β|r一般形式：若A→αβ1|αβ2|…|αβn,

提取左公共因子后变为 A→α(β1|β2|…|βn)，引进新的非终结符A’，得：

A→αA’，A’→β1|β2|…|βn

若在βi中仍含有左公共因子,可再次提取.1、提取左公因子2025/1/11Page45第5章自顶向下语法分析方法例文法G1：

S→aSb|aS|ε

提左因子得:S→aS(b|ε)|ε

引进新的非终结符S’得: S→aSS’|ε S’→b|ε1、提取左公因子2025/1/11Page46第5章自顶向下语法分析方法1)消除直接左递归文法G:S→Sa|b

可改写成 S→bS’

S’→aS’|ε一般情形:

含直接左递归的文法G：

A→Aα1|Aα2|…|Aαm|β1|β2|…|βn

消除左递归后改写成：

A→β1A’|β2A’|…|βnA’ A’→α1A’|α2A’|…|αmA’|ε

2、消除左递归不难验证，改写前和改写后的文法都产生语言{ban|n≥0}

2025/1/11Page47第5章自顶向下语法分析方法2)消除间接左递归将间接左递归变成直接左递归，再加以消除。算法步骤：把文法的所有非终结符按任一顺序排列，

如：A1，A2，…，An从A1开始，按以下顺序处理Ai。首先，消除左部为Ai的产生式的直接左递归；然后，若左部为Ai的产生式的右部为非终结符Aj(j<i)开头，即Ai→Aj…，则用左部为Aj的所有产生式的右部分别代替Ai→Aj…

中的Aj；最后，得到的左部为Ai的产生式若有直接左递归，则消除之。去掉无用产生式。2025/1/11Page48第5章自顶向下语法分析方法例文法G：(1)S→Qc|c (2)Q→Rb|b(3)R→Sa|a将非终结符排序：R，Q，S对R：产生式(3)不含直接左递归，所以保持不变

对Q：把(3)代入(2)得(2’)Q→Sab|ab|b，无直接左递归

对S：把(2’)代入(1)得(1’)S→Sabc|abc|bc|c，有直接左递归，消除直接左递归得

S→abcS’|bcS’|cS’ S’→abcS’|ε

处理结果为：R→Sa|a Q→Sab|ab|b S→abcS’|bcS’|cS’

S’→abcS’|ε由于Q，R是不可到达的非终结符，其产生式应删除。最终得文法G’：S→abcS’|bcS’|cS’

S’→abcS’|ε2025/1/11Page49第5章自顶向下语法分析方法示例说明：当非终结符顺序为R，Q，S，消除左递归的最终结果为：

S→abcS’|bcS’|cS’ S’→abcS’|ε若非终结符顺序为S，Q，R，则消除左递归的最终结果为：

S→Qc|c Q→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。2025/1/11第5章自顶向下语法分析方法Page50不确定的自顶向下分析也称带回溯的自顶向下分析定义：

不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。5.4不确定的自顶向下分析思想2025/1/11Page51第5章自顶向下语法分析方法例1

设有文法

S→xAyA→ab|a，对输入串w=xay，推导树为SxAySxAybaSxAy回溯aSxAy由于A的两条产生式：A→ab和A→a右部First集交集不为空，从而引起回溯2025/1/11Page52第5章自顶向下语法分析方法例2

文法G：S→aAS

S→b A→bAS A→ε

输入串w=ab，推导树为:SaAS回溯SaASSaASSbASaASεb由于A的产生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)={b}≠ф

，从而引起回溯2025/1/11Page53第5章自顶向下语法分析方法例3

文法G：S→Sa S→b

输入串w=baa，推导树为:SSabSbSSa回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯2025/1/11第5章自顶向下语法分析方法Page545.5确定的自顶向下分析方法确定的自顶向下分析方法有：递归子程序法(recursive-descentparser)预测分析法(predictiveparser)两种方法都要求文法是LL(1)文法。2025/1/11第5章自顶向下语法分析方法Page55实现思想： 对应文法中每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。5.5.1递归子程序法2025/1/11第5章自顶向下语法分析方法Page565.5.1递归子程序法由于递归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复——先进后出栈。优点：简单直观、易于构造缺点：对文法要求高，必须是LL(1)文法递归调用多，速度慢，占用空间多2025/1/11第5章自顶向下语法分析方法Page575.5.2预测分析方法一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入‘#’和文法开始符，结束时栈应是空的。预测分析表：是一张二维表，元素M[A,a]的内容是当非终结符A面临输入符号a(终结符或句子括号＃)时应选取的产生式，当无产生式时，元素内容为转向出错处理。2025/1/11Page58第5章自顶向下语法分析方法构造预测分析表步骤：

(1)把文法转变为LL(1)文法

(2)求出每条产生式的SELECT集

(3)依照SELECT集把产生式填入分析表对每个终结符或‘＃’用a表示若a

SELECT(A→

)，则把A→

放入M[A,a]中，把所有无定义的M[A,a]标上出错标记。2025/1/11Page59第5章自顶向下语法分析方法例算术表达式文法G

E→E+T│T T→T*F│F F→(E)│i（1）消除G的左递归得到文法

G‘ E→TE' E'→+TE'│ε T→FT' T'→*FT'│ε F→(E)│i 2025/1/11Page60第5章自顶向下语法分析方法（2）求出每个产生式的select集,G’是LL(1)文法

SELECT(E→TE')={(,i} SELECT(E'→+TE')={+}SELECT(E'→ε)={),#} SELECT(T→FT')={(,i}SELECT(T'→*FT')={*} SELECT(T'→ε)={+,),#}SELECT(F→(E))={(} SELECT(F→i)={i}F→(E)F→iFT'→εT'→εT'→*FT'T'→εT'T→FT’T→FT’TE'→εE'→εE'→+TE’E'E#）（*+iE→TE’E→TE’（3）依照选择集合把产生式填入分析表注：表中空白处为出错2025/1/11Page61第5章自顶向下语法分析方法上托栈顶符放入XNYYNNNNYYY把’#’和文法开始符压入分析栈；当前输入符送a把产生式右部反序进栈X∈VT?X=’#’?X=a?X=a?读下一输入符到aM[X,a]有产生式？出错结束出错预测分析程序工作过程预测分析程序2025/1/11Page62第5章自顶向下语法分析方法输入串i+i*i#的分析过程i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)+匹配+i*i##E’T+7E’→+TE’+i*i##E’6T’→ε+i*i##E’T’5i匹配i+i*i##E’T’i4F→ii+i*i##E’T’F3T→FT’i+i*i##E’T2E→TE’i+i*i##E1所用产生式剩余输入串分析栈步骤反序压栈!2025/1/11Page63第5章自顶向下语法分析方法T→FT’ i*i##E’T8F→i i##E’T’F13i匹配 i##E’T’i14T’→ε ##E’T’15E’→ε ##E’16接受 ##17*匹配 *i##E’T’F*12T’→*FT’ *i##E’T’11i匹配 i*i##E’T’i10F→i i*i##E’T’F9i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)2025/1/11Page64第5章自顶向下语法分析方法P96例1已知文法G[S]: SaH HaMd|d MAb|ε AaM|e1.判断G[S]是否为LL(1