编 译 原 理 指导教师:杨建国 二零一零年三月

第五章 自顶向下语法分析方法 第一节 确定的自顶向下分析思想 第二节 LL（1）文法的判别 第五章　自顶向下语法分析方法 第一节 确定的自顶向下分析思想 第二节 LL（1）文法的判别 第三节 某些非LL（1）文法到LL（1）文法的等价变换 第四节 不确定的自顶向下分析思想 第五节 确定的自顶向下分析方法 第六节　典型例题及解答

知识结构

第五章 自顶向下语法分析方法 5.1 确定的自顶向下分析思想 语法分析是编译程序的核心部分 语法分析作用：识别由词法分析给出的单词符号序列 第五章　自顶向下语法分析方法 5.1　确定的自顶向下分析思想 语法分析是编译程序的核心部分 语法分析作用：识别由词法分析给出的单词符号序列 　是否是给定文法的正确句子（程序） 语法分析的方法： 自顶向下分析：确定分析、不确定分析(ch05) 自底向上分析：算符优先分析(ch06)、LR分析(ch07)

确定的自顶向下分析文法：它是从文法的开始符号出 　发，考虑如何根据当前的输入符号（单词符号）唯一 　地确定选用哪个产生式替换相应非终结符以往下推导 　，或如何构造一棵相应的语法树

例5.1 若有文法G1[S]: S → pA |qB A →cAd|a B →d B |c 识别输入串w= pccadd是否是G1[S]的句子 试探推导过程： S pA pcAd pccAdd pccadd 试探成功

相应语法树为图5.1 ： 图 5.1 确定的自顶向下语 法分析树(一)

这个文法的特点： 每个产生式的右部都由终结符号开始 如果两个产生式有相同的左部，那么它们的右部由不同的 　终结符开始

例5.2 若有文法G2[S]: S → Ap |Bq A →a|cA B →b|dB 识别输入串w=ccap是否是G2[S]的句子，那么试探推出 输入串的推导过程为 ： S Ap cAp ccAp ccap 试探推导成功

相应语法树为图5.2 ： 图 5.2 确定的自顶向下语 法分析树(二)

这个文法的特点： 产生式的右部不全是由终结符开始 如果两个产生式有相同的左部，它们的右部是由不同的终 　结符或非终结符开始 文法中无空产生式

定义5.1： 　设G=(VT，VN，S，P)是上下文无关文法 　FIRST(α)={a | α a β， a ∈ VT， α ，β ∈ V*} 　若α 　　ε，则规定ε ∈ FIRST(α)，称FIRST(α)为α的 开始符号集(首符号集) 思考：FIRST(ε)= ? * *

例 若有文法G[A]: A →Bf|cA B →e|dB e, c, d FIRST（A）＝? FIRST（B）＝? e, d

例5.3 若有文法G3[S]: (含有空产生式) S → aA|d A →bAS|ε 识别输入串w=abd是否是G3[S]的句子 试探推导出abd的推导过程为： S aA abAS abS abd 试探推导成功

相应语法树为图5.3 ： 图 5.3 确定的自顶向下语 法分析树(三)

定义5.2： 　设G=(VT，VN，S，P)是上下文无关文法，A ∈ VN ，S是开 始符号，＃是输入串的结束符（输入串括号） 　FOLLOW(A)={a | S μAβ且a ∈ VT， a ∈FIRST（ β ），μ ∈ VT*， β ∈ V+} 　若S 　　 μAβ且β 　　ε ，则＃ ∈ FOLLOW(A) 　也可以定义为： 　 FOLLOW (A)={a | S …Aa …, a ∈ VT｝ 　若有S 　　 …A，则规定＃ ∈ FOLLOW(A) 　思考：FOLLOW(ε)= ? * * * * *

例 若有文法G[A]: A →Bf|cB B →e # FOLLOW（A）＝? FOLLOW（B）＝? f, #

定义5.3： 　给定上下文无关文法的产生式A　　 α，A ∈ VN， α ∈ V*， α　　 ε，则SELECT（ A　　 α）＝FIRST（ α ） α　　 ε ，则SELECT（ A　　 α）＝（FIRST（ α ） －｛ ε ｝）∪FOLLOW（A） * *

例 若有文法G[A]: A →Bf |cB B →e | ε e, f c SELECT（ A →Bf ）＝? SELECT（ A →cB ）＝? e SELECT（ B →e ）＝? SELECT（ B → ε ）＝? f, #

定义5.4： 　 一个上下文无关文法是LL（1）文法的充分必要条件是， 对每个非终结符A的两个不同产生式， A　　α， A　　 β ， 满足SELECT（ A　　 α）∩SELECT（ A　　 β）＝Ø 其中α、 β不能同时　　 ε *

根据前面的讨论容易看出：能够使用自顶向下分析技术的 　文法正是LL（1）文法： 第一个L表明自顶向下分析是从左向右扫描输入串 第二个L表明分析过程中将用最左推导 1表明只需向右看一个符号便可决定如何推导即选择哪个 　产生式（规则）进行推导 LL（k）文法，也就是需向前查看k个符号才可确定选用 　哪个产生式

例5.3文法G3[S]： S → aA|d A →bAS|ε SELECT(S　　 a A)={a} SELECT(S　　 d)={d} SELECT(A　　 bAS)={b} SELECT(A　　 ε)={a, d, #} 　所以 SELECT(S　 αA) ∩ SELECT(S 　 d) ={α} ∩ {d} ）＝Ø SELECT(A　　 bAS)∩ SELECT(A　　 ε) 　= {b} ∩ {α,d,#}＝Ø 例5.3是LL（1）文法，所以可以用确定的自顶向下分析

例5.4　设文法G［S］为： S　　 aAS　　　　S　　 b　　A　　 bA　　A　　 ε则 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 ｝ ≠Ø 例5.4不是LL（1）文法，所以不能用确定的自顶向下分析

5.2 LL(1)文法的判别 注意：假定所给文法是经过压缩的（不包含多余规则） 例5.5 若文法G[S]为： S AB S bC A ε B　　 aD C　　 AD C　　 b D　　 aS D　　 c

判断LL（1）文法的步骤： 　1）求出能推出ε的非终结符： 　首先建立一个以文法的非终结符个数为上界的一维数组， 其数组元素为非终结符，对应每一非终结符有一标志位，用 以记录能否推出，其值有三种：未定、是、否

例5.5所对应数组X[ ]的内容如表5.1： 表5.1 非终结符能否推出空的表 非终结符 S A B C D 初值 第1次扫描 第2次扫描 未定 未定 未定 未定 未定 是 是 否 是 否

　　计算能推出ε的非终结符步骤如下： ① 将数组X[ ]中对应每一非终结符的标记置初值为“未定” ② 扫描文法中的产生式： (a) 删除所有右部含有终结符的产生式，若这使得以某一非终 　结符为左部的所有产生式都被删除，则将数组中对应该非 　终结符的标记值改为“否”，说明该非终结符不能推出ε (b) 若某一非终结符的某一产生式右部为ε，则将数组中对应 　该非终结符的标志置为“是”，并从文法中删除该非终结符 　的所有产生式。例中对应非终结符A、B的标志改为“是”

③ 扫描产生式右部的每一符号: (a) 若所扫描到的非终结符号在数组中对应的标志是“是”，则 　删去该非终结符，若这使产生式右部为空，则对产生式左 　部的非终结符在数组中对应的标志改“是”，并删除该非终 　结符为左部的所有产生式 (b) 若所扫描到的非终结符号在数组中对应的标志是“否”，则 　删去该产生式，若这使产生式左部非终结符的有关产生式 　都被删去，则把在数组中该非终结符对应的标志改成“否” ④ 重复③，直到扫描完一遍文法的产生式，数组中非终结符 　对应的特征再没有改变为止

2)计算FIRST集: ① 根据定义计算： 　对每一文法符号X∈V 计算FIRST(X) (a) 若X∈VT，则FIRST(X)＝{X} (b) 若X∈VN，且有产生式X→a…，a∈VT， 则 a∈FIRST(X) (c) 若X∈VN，X→ε,则ε∈FIRST(X) (d) 若X， Y1，Y2，…，Yn都∈VN，且有产生式X→Y1 Y2 … 　Yn；当Y1 Y2 … Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1)- {ε}、FIRST(Y2) -{ε} 、…、FIRST(Yi-1)- {ε}，FIRST(Yi) 　都包含在FIRST(X)中

* (e) 当(d)中所有Yi　　　ε,(i=1,2,…n)，则 　FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε} (f)反复使用上述(b)～(e)步直到每个符号的FIRST集合不再增 　大为止

由此算法可计算例5.5文法各非终结符的FIRST集： FIRST(S)={FIRST(A)-{ε}}∪{FIRST(B)-{ε}}∪{ε}∪{b} ={b,a,ε} FIRST(A)={b}∪{ε}={ b,ε} FIRST(B)＝{ε}∪{a}＝{a,ε} FIRST(C)={FIRST(A)-{ε}}∪FIRST(D)∪FIRST(b)={b,a,c} FIRST(D)={a}∪{c}={a,c}

所以最终求得： FIRST(S)={a,b,ε} FIRST(A)={b,ε} FIRST(B)={a,ε} FIRST(C)={a,b,c} FIRST(D)={a,c}

求出每个文法符号的FIRST集合后也就不难求出一个符号串 * 若符号串α∈V*，α=X1 X2 … Xn,当X1不能 ε,则置 　FIRST(α)= FIRST(X1) 若对任何j(1≤j≤i-1，2≤i≤n), ε∈FIRST(Xj), ε FIRST(Xi)则 　FIRST(α)= 　(FIRST(Xj)-{ε})∪FIRST(Xi) 当所有FIRST(Xj)(1≤j≤n)都含有{ε}时，则 　FIRST(α)= 　(FIRST(Xj)) ∪{ε} ∈

每个产生式的右部符号串的开始符号集合为： FIRST(AB)={a,b,ε} FIRST(bC)={b} FIRST(ε)＝{ε} FIRST(b)＝{b} FIRST(aD)={a} FIRST(AD)={a,b,c} FIRST(b)={b} FIRST(aS)={a} FIRST(c)={c}

② 由关系图法求文法符号的FIRST集： (a)每个文法符号对应图中一个结点，对应终结符的结点时用 　符号本身标记，对应非终结符的结点用FIRST(A)标记。这 　里A表示非终结符 (b)如果文法中有产生式A→αXβ，且α　　ε,则从对应A的 结点到对应X的结点连一条箭弧 (c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的 　终结符都为FIRST(A)的成员 (d)由判别步骤1）确定ε是否为某非终结符FIRST集的成员， 　若是则将ε加入该非终结符的FIRST集中 *

图 5.4 计算FIRST集的关系图： b FIRST(C) FIRST(S)={b,a,ε} FIRST(A)={b,ε} FIRST(B)={a,ε} FIRST(C)={a,b,c} FIRST(D)={a,c} 思考：ε结点可以画在关系图中吗？ FIRST(S) FIRST(A) FIRST(B) FIRST(D) a c ε

3)计算FOLLOW集: ① 根据定义计算： 　　对文法中每一 A∈VN 计算 FOLLOW(A) (a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为 　句子括号) (b)若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入 　FOLLOW(B)中。 　如果β　　ε则把FOLLOW(A)也加入FOLLOW(B)中 (c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止 *

现计算例5.5文法各非终结符的FOLLOW集： FOLLOW(S)={#}∪ FOLLOW(D) FOLLOW(A)=(FIRST(B)－{ε})∪ FOLLOW(S) ∪ FIRST(D) FOLLOW(B)=FOLLOW(S) FOLLOW(C)=FOLLOW(S) FOLLOW(D)=FOLLOW(B)∪FOLLOW(C)

由以上最终计算结果得： FOLLOW(S)={#} FOLLOW(A)={a,#,c} FOLLOW(B)={#} FOLLOW(C)＝{#} FOLLOW(D)={#}

② 由关系图法求非终结符的FOLLOW集： (a)文法G中的每个符号和“#”对应图中的一个结点，对应终结 　符和“#”的结点用符号本身标记。对应非终结符的结点(如 　A∈VN)则用FOLLOW(A)或FIRST(A)标记 (b)从开始符号S的FOLLOW(S)结点到“#”号的结点连一条箭弧 (c)如果文法中有产生式A→αBβX,且β　　ε,则从 FOLLOW(B)结点到FIRST(X)结点连一条弧，当X∈VT时，则 与X相连 *

* (d) 如果文法中有产生式A→αBβ,且β　　ε，则从 FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧 (e) 对每一FIRST(A)结点如果有产生式A→αXβ,且 α　　ε, 则从FIRST(A)到FIRST(X)连一条箭弧 (f)凡是从FOLLOW(A)结点有路径可以到达的终结符或“#”号的 　结点，其所标记的终结符或"#"号即为FOLLOW(A)的成员 *

现在对例5.5文法用关系图法计算FOLLOW集： # FOLLOW(B) FOLLOW(S) FOLLOW(D) FOLLOW(A) FIRST(B) FOLLOW(C) FIRST(D) c a FOLLOW(S)={#} FOLLOW(A)={a,c,#} FOLLOW(B)={#} FOLLOW(C)={#} FOLLOW(D)={#} 自学：用关系矩阵法计算FIRST集和FOLLOW集

对例5.7文法的FIRST集和FOLLOW集计算结果如表5.2 4)计算SELECT集: 　对例5.7文法的FIRST集和FOLLOW集计算结果如表5.2 非终结符名 是否T*ε FIRST集 FOLLOW集 S 是 {b,a,ε} {#} A {b,ε} {a,c,#} B {a,ε} C 否 {a,b,c} D {a,c}

每个产生式的SELECT集合计算为： SELECT(S→AB)=FIRST(AB)∪ FOLLOW(S)={b,a,#} SELECT(S→bC)=FIRST(bC)={b} SELECT(A→ε)=FIRST(ε)∪FOLLOW(A)={a,c,#} SELECT(A→b)=FIRST(b)={b} SELECT(B→ε)=FIRST(ε)∪FOLLOW(B)={#} SELECT(B→aD)=FIRST(aD)={a} SELECT(C→AD)=FIRST(AD)={a,b,c} SELECT(C→b)=FIRST(b)={b} SELECT(D→aS)=FIRST(aS)={a} SELECT(D→c)=FIRST(c)={c}

由以上计算结果可得相同左部产生式的SELECT交集为： SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠ Ø SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩{b}= Ø SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}= Ø SELECT(C→AD)∩SELECT(C→b)＝{b,a,c}∩{b}＝{b}≠ Ø SELECT(D→aS)∩SELECT(D→c)={a}∩{c}＝ Ø 由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的 　相同左部其产生式的SELECT集的交集不为空

5.3 某些非LL(1)文法到LL（1）文法的等价变换 1.提取左公共因子： A　　 αβ1| αβ2|…| αβn，提取左公共因子后变为： A　　 α（β1| β2|…| βn），再引进非终结符A`，变为： A　　 αA` A`　　 β1| β2|…| βn

例5.6　若文法G1的产生式为： （1）S　　 aSb （2）S　　 aS （3）S　　 ε

对产生式（1）、（2）提取左公共因子后得： S　　 aS（b｜ ε） S　　 ε 进一步变换为文法G`1： S　　 aSA A　　 b A　　 ε

例5.7　若文法G2的产生式为： （1）A　　 ad （2）A　　 Bc （3）B　　 a A （4）B　　 bB 　对文法G2分别用(3)、(4)的右部替换（2）中的B，可得： （2）A　　 aAc （3）A　　 bBc （4）B　　 aA （5） B　　 bB

　提取产生式（1）、（2）的左公共因子得： A　　 a（d｜ Ac） A　　 bBc B　　 aA B　　 bB 　引进新非终结符A`，去掉“(”，“）”后得G`2为： （1）A　　 aA` （2）A　　 bBc （3）A`　　 d （4）A`　　 Ac （5） B　　 aA （6）B　　bB

经验证提取公共因子后，文法G`1仍不是LL（1）文法，而 注意：对文法进行提取左公共因子变换后，有时会使某些产 　生式变成无用产生式，在这种情况下必须对文法重新压缩 　（化简）

例5.8　若文法G3的产生式为： （1）S　　 aSd （2）S　　 Ac （3）A　　 aS （4）A　　 b 　用产生式(3)、(4)中右部替换产生式（2）中的A，可得： （2）S　　 aSc （3）S　　 bc （4）A　　 aS （5）A　　 b

　对（1）、（2）提取左公共因子后得： 　S　　 aS（d｜c） 　引入新非终结符A`后变为： （1）S　　 aSA` （2）S　　 bc （3）A`　　 d|c （4）A　　 aS （5）A　　 b A不可到达

有些文法不能在有限步骤内提取完公共因子 例5.9　若文法G4的产生式为： （1）S　　 Ap|Bq （2）A　　 aAp|d （3）B　　 aBq|e 　用产生式(2)、(3)中右部替换（1）中的A、B，可得： （1）S　　 aApp|aBqq （2）S　　 dp|eq （3）A　　 aAp|d （4）B　　 aBq|e 　对（1）提取左公共因子则得： 　S　　a(App|Bqq) 　再引入新非终结符S`结果得等价文法为：

（1）S　　 aS` （2）S　　 dp|eq （3）S`　　 App|Bqq （4）A　　aAp|d （5）B　　aBq|e 　同样分别用(4)、(5)中右部替换（3）中的A、B，可得： （3）S`　　 aS`` （4）S`　　 dpp|eqq （5）S``　　 Appp|Bqqq （6）A　　 aAp|d （7）B　　 aBq|e

2.消除左递归： ①A　　 A β 　A∈VN， β ∈ V* 　　直接左递归 ② A　　 Bβ 　 B　　Aa A,B∈VN， a,β ∈ V*　间接左递归　

例5.10　若文法G5的产生式为： （1）S　　 S a （2）S　　 b 所能产生的语言L={ban|n ≥0}, 输入串baaaa#是语言的句子 思考：什么时候用产生式（2）

例5.11　若文法G6的产生式为： （1）A　　aB （2）A　　 Bb （3）B　　 Ac （4）B　　 d 　若有输入串为adbcbcbc#，则分析过程的语法树为下图： 思考：什么时候用产生式（4）

由上述例子可以知道：含有左递归的文法绝对不是 　LL（1）文法，为了使某些含有左递归的文法经等价变换 　消除左递归后可能变为LL（1）文法，可采取下列变换公 　式：

1）消除直接左递归，把直接递归改写为右递归： 　一般情况下，假定关于A的全部产生式是： 　A　　Aa1| Aa2|… |Aam| β1| β2|…| βn 　　其中，ai(1≤i ≤m)不等于ε,β j(1≤j ≤n)不以A开头， 消除直接左递归后改写为： A　　 β 1A`| β 2A`|… | β nA` A`　 a 1A`| a2A`|… | a mA`| ε

文法G5： （1）S　　 S α （2）S　　 b 　可改写为： （1）S　　 bS` （2）S`　　 α S`| ε

2）消除间接左递归： 　先通过产生式非终结符置换，将间接左递归变为直接左递 归，然后再按上面的方法消除直接左递归： 文法G6： （1）A　　aB （2）A　　 Bb （3）B　　 Ac （4）B　　 d

　用产生式（1）、（2）的右部置换产生式（3）中的A得 到左部为B的产生式： （1）B　　aBc （2）B　　 Bbc （3）B　　 d

　消除左递归后得： （1）B　　(αBc|d)B` （2）B`　　 bcB`| ε 　再把原来其余的产生式（1）、（2）加入，最终文法为： （1）A　　αB （2）A　　 Bb （3）B　　(αBc|d)B` （4）B`　　 bcB`| ε

对文法中一切递归的消除要求文法中不含回路即无A A 的推导 满足这个要求的充分条件是，文法中不包含形如A A 的有害规则和A ε的空产生式 3）消除文法中一切左递归的算法： 对文法中一切递归的消除要求文法中不含回路即无A　　A 　的推导 满足这个要求的充分条件是，文法中不包含形如A　　A 　的有害规则和A　　 ε的空产生式 算法步骤： （1）把文法的所有非终结符按某一顺序排序,如: A1| A2|… |An +

（2）从A1开始消除左部为A1的产生式的直接左递归，然 　A1开始的产生式中的A1，并消除左部为A2的产生式中的直 　接左递归。继而以同样方式把A1、A2的右部代入左部为A3 　右部以A1或A2开始的产生式中，消除左部为A3的产生式之 　直接左递归，直到把左部为A1，A2，…，An-1的右部代入 　左部为An的产生式中，从An中消除直接左递归

把上述算法归结为：若非终结符的排序为： A1| A2|… |An FOR i:=1 TO N DO BEGIN FOR j:=1 TO i-1DO 　若Aj的所有产生式为： 　Aj　　δ 1| δ 2|… | δ k 　 　替换形如Ai Ajr的产生式变为： 　 Ai　　 δ1r| δ2r|… | δkr 　END 消除Ai中的一切直接左递归 END　

（3）去掉无用产生式 例如　若文法的产生式为： （1）S　　Qc|c （2）Q　 Rb|b （3）R　 Sa|a

　该文法的每个非终结符为间接左递归，消除方法： 非终结符排序为：S、Q、R 把（1）右部代入（3）得： （4）R　　Qca|ca|a　再将（2）的右部代入（4）得： （5）R`　 Rbca|bca|ca|a　对（5）消除直接左递归得： 　R　　(bca|ca|a)R` 　R`　 bcaR`|ε

　最终文法变为： 　S　　Qc|c 　Q　 Rb|b 　R　　(bca|ca|a)R` 　R`　 bcaR`|ε

非终结符排序为：R、Q、S 把（3）右部代入（2）得： Q　　Sab|ab|b　再将此式代入（1）得： S　 Sabc|abc|bc|c　消除该产生式的左递归得： S　　 (abc|bc|c|)S` S`　 abcS`| ε Q　　Rb|b R　 Sa|a

　由于Q、R为不可到达的非终结符,所以删除得最终文法： S　　 (abc|bc|c|)S` S`　 abcS`| ε 结论：当非终结符排序不同时，最后结果的产生式形式不 　同，但它们是等价的

5.4 不确定的自顶向下分析思想 不确定的自顶向下分析（带回溯的自顶向下分析）：在文 法中当关于某个非终结符的产生式有多个候选时，而面临 5.4　不确定的自顶向下分析思想 不确定的自顶向下分析（带回溯的自顶向下分析）：在文 　法中当关于某个非终结符的产生式有多个候选时，而面临 　当前的输入符无法确定选用唯一的产生式，从而引起回溯

1.由于相同左部产生式的右部FIRST集交集不为空而引起回溯 例如，文法： S　　 xAy A　　 ab|a 若当前输入串为xay

* 2.由于相同左部非终结符的右部存在能　　　ε的产生式，且 　该非终结符的FOLLOW集中含有其他产生式右部FIRST 　集的元素 　例如，文法G［S］为： S　　 aAS　　　　 S　　 b　　 A　　 bAS　　 A　　 ε 　 对输入串ab#的试探推导， 如右图所示：

3.由于文法含有左递归而引起回溯 　例如，文法G［S］为： S　　 Sa　　　　 S　　 b　　 　对输入串baa#的试探推导，如下图所示：

由以上例子可知： 　　带回溯的自顶向下分析是是一个试探过程，当分析不成 功时则推翻分析退回到适当位置再重新试探其余候选可能的 推导，这样需要记录已选过的产生式，直到把所有可能的推 导序列都试完仍不成功才能确认输入串不是该文法的句子而 报错 由于在编译程序真正实现时往往是边分析边插入语义动作， 　因而带回溯分析代价很高，效率很低，在实用编译程序中 　几乎不用，因此对它实现的详细算法不做介绍

5.5 确定的自顶向下分析方法 1.递归子程序法： 实现思想：是对应文法中每个非终结符编写一个递归过 5.5　确定的自顶向下分析方法 1.递归子程序法： 　　实现思想：是对应文法中每个非终结符编写一个递归过 程，每个过程的功能是识别由该非终结符推出的串，当某非 终结符的产生式有多个候选时能够按LL（1）形式可唯一地确 定选择某个候选进行推导 　缺点： 对文法要求高，必须满足LL（1）文法，个别LL（2）例外 速度慢占用空间多

2.预测分析方法： 　预测分析器的组成： 预测分析程序 先进后出栈 预测分析表：用矩阵M[A,a]表示，A表示非终结符，a为终 　结符或句子括号#，矩阵M[A,a]中的内容是一条关于A的产 　生式，表明当用非终结符A向下推导时，面临输入符a时， 　所应采取的候选产生式，当元素内容无产生时，则表明用A 　为左部向下推导时遇到了不该出现的符号，因此元素内容 　为转向出错处理的信息

预测分析程序工作过程示意图： ＃句子括号即输入串的括号，S文法的开始符号 X存放当前栈顶符号的工作单元，a存放当前输入符号a的工作单元

例，表达式文法为： E　　 E+T|T　　　　 T　　 T*F|F F　　 i|(E)

构造步骤： (1) 判断文法是否为LL(1)文法 　由于文法中含有左递归，所以必须先消除左递归，使 文法变为： 　E→TE′ 　E′→+TE′|ε 　T→FT′ 　T′→*FT′|ε 　F→i|(E)

可推出ε的非终结符表为: E E` T T` F 否 是

各非终结符的FIRST集合如下： FIRST(E)={(,i} FIRST(E′)={+,ε} FIRST(T)={(,i} FIRST(T′)={*,ε} FIRST(F)={(,i}

各非终结符的FOLLOW集合为： FOLLOW(E)={),#} FOLLOW(E′)={)，#} FOLLOW(T)={+，)，#} FOLLOW(T′)={+，)，#} FOLLOW(F)={*，+，)，#}

各产生式的SELECT集合为： 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} 由上可知有相同左部产生式的SELECT集合的交集为空， 　所以文法是LL(1)文法

(2)构造预测分析表： 对每个终结符或“#”号用a表示 若a∈SELECT(A→α)，则把A→α放入M[A,a]中 把所有无定义的M[A,a]标上出错标记 　　为了使表简化，其产生式的左部可以不写入表中，表中 空白处为出错

表达式文法的预测分析表如表5.3 : VT i + * VN ( ) # E →TE′ →TE′ E` →+TE′ →+ ε →+ ε T →FT` →FT` T` → ε → *FT` → ε → ε → i → (E) F

下面用预测分析程序，栈和预测分析表对输入串i+i*i# 进行分析，给出栈的变化过程如表5.4 : 步骤 分析栈 剩余输入串 推导所用产生式或匹配 1 ＃E i+i*i# E→TE′ 2 #E`T i+i*i# T→FT′ 3 #E`T`F i+i*i# F→i 4 #E`T`i i+i*i# “i”匹配 5 #E`T` +i*i# T`→ ε 6 #E` +i*i# E`→ +TE` 7 #E`T+ +i*i# “+”匹配 8 #E`T i*i# T→FT` 9 #E`T`F i*i# F→i

10 ＃E`T`i i*i# “i”匹配 11 #E`T` *i# T`→*FT′ 12 #E`T`F* *i# “*”匹配 13 步骤 分析栈 剩余输入串 推导所用产生式或匹配 10 ＃E`T`i i*i# “i”匹配 11 #E`T` *i# T`→*FT′ 12 #E`T`F* *i# “*”匹配 13 #E`T`F i# F→i 14 #E`T`i i# “i”匹配 15 #E`T` # T`→ ε 16 #E` # E`→ ε 17 # # 接受

5.6 典型例题及解答 例题1 已知文法G[S]: S aH H aMd|d M Ab|ε A aM|e 5.6　典型例题及解答 例题1　已知文法G[S]: S　　 aH　　　　 H　　 aMd|d M　　 Ab|ε A　　 aM|e 1.判断G[S]是否为LL（1）文法，若是，请构造相应的LL（1 　）预测分析表 2.若G[S]是LL（1）文法，请给出对输入串aaabd#的预测分析 　过程，并说明该输入串是否是G[S]的句子

例题2　已知文法G[S]: S　　 Aa|b　　　　 A　　 SB B　　 ab 1.试对G[S]进行改写，并判断改写后的文法是否为LL（1）文 　法 2.对于一个文法若消除左递归，提取了左公共因子后是否一定 　为LL（1）文法

例题3　已知文法G[S]: S　　 Ab|Ba　　　　 A　　 aA|a B　　 a　 　　是LL（1）文法吗？若不是，请改写为等价的G`[S]，证 明改写后的文法是否为LL(1)文法

【本章小结】 确定的自顶向下分析方法虽对文法有一定的限制，但由 于实现方法简单、直观，便于手工构造或自动生成语法分析 　　确定的自顶向下分析方法虽对文法有一定的限制，但由 于实现方法简单、直观，便于手工构造或自动生成语法分析 器，因而仍是目前常用的方法之一。要求学员通过本章的学 习后，能够对一个给定的文法判断是否是LL(1)文法；能构造 预测分析表；能用预测分析方法判断给定的输入符号串是否 是该文法的句子；对某些非LL(1)文法做等价变换后可能变成 LL(1)文法。

第5章　作业题 P99： 1. 3. 7.(2)(3)