Download presentation
Presentation is loading. Please wait.
1
编 译 原 理 指导教师:杨建国 二零一零年三月
2
第五章 自顶向下语法分析方法 第一节 确定的自顶向下分析思想 第二节 LL（1）文法的判别
第五章 自顶向下语法分析方法 第一节 确定的自顶向下分析思想 第二节 LL（1）文法的判别 第三节 某些非LL（1）文法到LL（1）文法的等价变换 第四节 不确定的自顶向下分析思想 第五节 确定的自顶向下分析方法 第六节 典型例题及解答
3
知识结构
4
第五章 自顶向下语法分析方法 5.1 确定的自顶向下分析思想 语法分析是编译程序的核心部分 语法分析作用：识别由词法分析给出的单词符号序列
第五章 自顶向下语法分析方法 5.1 确定的自顶向下分析思想 语法分析是编译程序的核心部分 语法分析作用：识别由词法分析给出的单词符号序列 是否是给定文法的正确句子（程序） 语法分析的方法： 自顶向下分析：确定分析、不确定分析(ch05) 自底向上分析：算符优先分析(ch06)、LR分析(ch07)
5
确定的自顶向下分析文法：它是从文法的开始符号出
发，考虑如何根据当前的输入符号（单词符号）唯一 地确定选用哪个产生式替换相应非终结符以往下推导 ，或如何构造一棵相应的语法树
6
例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 若有文法G1[S]: S → pA |qB. A →cAd|a. B →d B |c. 识别输入串w= pccadd是否是G1[S]的句子. 试探推导过程： S pA pcAd pccAdd pccadd.](http://slidesplayer.com/slide/11558942/62/images/6/%E4%BE%8B5.1+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G1%5BS%5D%3A+S+%E2%86%92+pA+%7CqB.+A+%E2%86%92cAd%7Ca.+B+%E2%86%92d+B+%7Cc.+%E8%AF%86%E5%88%AB%E8%BE%93%E5%85%A5%E4%B8%B2w%3D+pccadd%E6%98%AF%E5%90%A6%E6%98%AFG1%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90.+%E8%AF%95%E6%8E%A2%E6%8E%A8%E5%AF%BC%E8%BF%87%E7%A8%8B%EF%BC%9A+S+pA+pcAd+pccAdd+pccadd..jpg "试探成功.")
7
相应语法树为图5.1 ： 图 5.1 确定的自顶向下语 法分析树(一)
8
这个文法的特点： 每个产生式的右部都由终结符号开始 如果两个产生式有相同的左部，那么它们的右部由不同的 终结符开始
9
例5.2 若有文法G2[S]: S → Ap |Bq A →a|cA B →b|dB 识别输入串w=ccap是否是G2[S]的句子，那么试探推出 输入串的推导过程为 ： S Ap cAp ccAp ccap 试探推导成功
![例5.2 若有文法G2[S]: S → Ap |Bq. A →a|cA. B →b|dB. 识别输入串w=ccap是否是G2[S]的句子，那么试探推出. 输入串的推导过程为 ： S Ap cAp ccAp ccap.](http://slidesplayer.com/slide/11558942/62/images/9/%E4%BE%8B5.2+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G2%5BS%5D%3A+S+%E2%86%92+Ap+%7CBq.+A+%E2%86%92a%7CcA.+B+%E2%86%92b%7CdB.+%E8%AF%86%E5%88%AB%E8%BE%93%E5%85%A5%E4%B8%B2w%3Dccap%E6%98%AF%E5%90%A6%E6%98%AFG2%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90%EF%BC%8C%E9%82%A3%E4%B9%88%E8%AF%95%E6%8E%A2%E6%8E%A8%E5%87%BA.+%E8%BE%93%E5%85%A5%E4%B8%B2%E7%9A%84%E6%8E%A8%E5%AF%BC%E8%BF%87%E7%A8%8B%E4%B8%BA+%EF%BC%9A+S+Ap+cAp+ccAp+ccap..jpg "试探推导成功.")
10
相应语法树为图5.2 ： 图 5.2 确定的自顶向下语 法分析树(二)
11
这个文法的特点： 产生式的右部不全是由终结符开始 如果两个产生式有相同的左部，它们的右部是由不同的终 结符或非终结符开始 文法中无空产生式
12
定义5.1： 设G=(VT，VN，S，P)是上下文无关文法 FIRST(α)={a | α a β， a ∈ VT， α ，β ∈ V*} 若α ε，则规定ε ∈ FIRST(α)，称FIRST(α)为α的 开始符号集(首符号集) 思考：FIRST(ε)= ? * *
13
例 若有文法G[A]: A →Bf|cA B →e|dB e, c, d FIRST（A）＝? FIRST（B）＝? e, d
![例 若有文法G[A]: A →Bf|cA B →e|dB e, c, d FIRST（A）＝ FIRST（B）＝ e, d](http://slidesplayer.com/slide/11558942/62/images/13/%E4%BE%8B+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G%5BA%5D%3A+A+%E2%86%92Bf%7CcA+B+%E2%86%92e%7CdB+e%2C+c%2C+d+FIRST%EF%BC%88A%EF%BC%89%EF%BC%9D+FIRST%EF%BC%88B%EF%BC%89%EF%BC%9D+e%2C+d.jpg "例 若有文法G[A]: A →Bf|cA B →e|dB e, c, d FIRST（A）＝ FIRST（B）＝ e, d")
14
例5.3 若有文法G3[S]: (含有空产生式) S → aA|d A →bAS|ε 识别输入串w=abd是否是G3[S]的句子 试探推导出abd的推导过程为： S aA abAS abS abd 试探推导成功
![例5.3 若有文法G3[S]: (含有空产生式) S → aA|d. A →bAS|ε. 识别输入串w=abd是否是G3[S]的句子. 试探推导出abd的推导过程为： S aA abAS abS abd.](http://slidesplayer.com/slide/11558942/62/images/14/%E4%BE%8B5.3+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G3%5BS%5D%3A+%28%E5%90%AB%E6%9C%89%E7%A9%BA%E4%BA%A7%E7%94%9F%E5%BC%8F%29+S+%E2%86%92+aA%7Cd.+A+%E2%86%92bAS%7C%CE%B5.+%E8%AF%86%E5%88%AB%E8%BE%93%E5%85%A5%E4%B8%B2w%3Dabd%E6%98%AF%E5%90%A6%E6%98%AFG3%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90.+%E8%AF%95%E6%8E%A2%E6%8E%A8%E5%AF%BC%E5%87%BAabd%E7%9A%84%E6%8E%A8%E5%AF%BC%E8%BF%87%E7%A8%8B%E4%B8%BA%EF%BC%9A+S+aA+abAS+abS+abd..jpg "试探推导成功.")
15
相应语法树为图5.3 ： 图 5.3 确定的自顶向下语 法分析树(三)
16
定义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(ε)= ? * * * * *
17
例 若有文法G[A]: A →Bf|cB B →e # FOLLOW（A）＝? FOLLOW（B）＝? f, #
![例 若有文法G[A]: A →Bf|cB B →e # FOLLOW（A）＝ FOLLOW（B）＝ f, #](http://slidesplayer.com/slide/11558942/62/images/17/%E4%BE%8B+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G%5BA%5D%3A+A+%E2%86%92Bf%7CcB+B+%E2%86%92e+%23+FOLLOW%EF%BC%88A%EF%BC%89%EF%BC%9D+FOLLOW%EF%BC%88B%EF%BC%89%EF%BC%9D+f%2C+%23.jpg "例 若有文法G[A]: A →Bf|cB B →e # FOLLOW（A）＝ FOLLOW（B）＝ f, #")
18
定义5.3： 给定上下文无关文法的产生式A α，A ∈ VN， α ∈ V*， α ε，则SELECT（ A α）＝FIRST（ α ） α ε ，则SELECT（ A α）＝（FIRST（ α ） －｛ ε ｝）∪FOLLOW（A） * *
19
例 若有文法G[A]: A →Bf |cB B →e | ε e, f c SELECT（ A →Bf ）＝? SELECT（ A →cB ）＝? e SELECT（ B →e ）＝? SELECT（ B → ε ）＝? f, #
![例 若有文法G[A]: A →Bf |cB. B →e | ε. e, f. c. SELECT（ A →Bf ）＝ SELECT（ A →cB ）＝ e. SELECT（ B →e ）＝](http://slidesplayer.com/slide/11558942/62/images/19/%E4%BE%8B+%E8%8B%A5%E6%9C%89%E6%96%87%E6%B3%95G%5BA%5D%3A+A+%E2%86%92Bf+%7CcB.+B+%E2%86%92e+%7C+%CE%B5.+e%2C+f.+c.+SELECT%EF%BC%88+A+%E2%86%92Bf+%EF%BC%89%EF%BC%9D+SELECT%EF%BC%88+A+%E2%86%92cB+%EF%BC%89%EF%BC%9D+e.+SELECT%EF%BC%88+B+%E2%86%92e+%EF%BC%89%EF%BC%9D.jpg "SELECT（ B → ε ）＝ f, #")
20
定义5.4： 一个上下文无关文法是LL（1）文法的充分必要条件是， 对每个非终结符A的两个不同产生式， A α， A β ， 满足SELECT（ A α）∩SELECT（ A β）＝Ø 其中α、 β不能同时 ε *
21
根据前面的讨论容易看出：能够使用自顶向下分析技术的
文法正是LL（1）文法： 第一个L表明自顶向下分析是从左向右扫描输入串 第二个L表明分析过程中将用最左推导 1表明只需向右看一个符号便可决定如何推导即选择哪个 产生式（规则）进行推导 LL（k）文法，也就是需向前查看k个符号才可确定选用 哪个产生式
22
例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.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, #} 所以.](http://slidesplayer.com/slide/11558942/62/images/22/%E4%BE%8B5.3%E6%96%87%E6%B3%95G3%5BS%5D%EF%BC%9A+S+%E2%86%92+aA%7Cd.+A+%E2%86%92bAS%7C%CE%B5.+SELECT%28S+a+A%29%3D%7Ba%7D+SELECT%28S+d%29%3D%7Bd%7D+SELECT%28A+bAS%29%3D%7Bb%7D+SELECT%28A+%CE%B5%29%3D%7Ba%2C+d%2C+%23%7D+%E6%89%80%E4%BB%A5..jpg "SELECT(S αA) ∩ SELECT(S d) ={α} ∩ {d} ）＝Ø. SELECT(A bAS)∩ SELECT(A ε) = {b} ∩ {α,d,#}＝Ø. 例5.3是LL（1）文法，所以可以用确定的自顶向下分析.")
23
例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）文法，所以不能用确定的自顶向下分析
24
5.2 LL(1)文法的判别 注意：假定所给文法是经过压缩的（不包含多余规则） 例5.5 若文法G[S]为： S AB S bC A ε
B aD C AD C b D aS D c
![5.2 LL(1)文法的判别 注意：假定所给文法是经过压缩的（不包含多余规则） 例5.5 若文法G[S]为： S AB S bC A ε](http://slidesplayer.com/slide/11558942/62/images/24/5.2+LL%281%29%E6%96%87%E6%B3%95%E7%9A%84%E5%88%A4%E5%88%AB+%E6%B3%A8%E6%84%8F%EF%BC%9A%E5%81%87%E5%AE%9A%E6%89%80%E7%BB%99%E6%96%87%E6%B3%95%E6%98%AF%E7%BB%8F%E8%BF%87%E5%8E%8B%E7%BC%A9%E7%9A%84%EF%BC%88%E4%B8%8D%E5%8C%85%E5%90%AB%E5%A4%9A%E4%BD%99%E8%A7%84%E5%88%99%EF%BC%89+%E4%BE%8B5.5+%E8%8B%A5%E6%96%87%E6%B3%95G%5BS%5D%E4%B8%BA%EF%BC%9A+S+AB+S+bC+A+%CE%B5.jpg "B aD. C AD. C b. D aS. D c.")
25
判断LL（1）文法的步骤： 1）求出能推出ε的非终结符： 首先建立一个以文法的非终结符个数为上界的一维数组， 其数组元素为非终结符，对应每一非终结符有一标志位，用 以记录能否推出，其值有三种：未定、是、否
26
例5.5所对应数组X[ ]的内容如表5.1： 表5.1 非终结符能否推出空的表 非终结符 S A B C D 初值 第1次扫描 第2次扫描
未定 未定 未定 未定 未定 是 是 否 是 否
![例5.5所对应数组X[ ]的内容如表5.1： 表5.1 非终结符能否推出空的表 非终结符 S A B C D 初值 第1次扫描 第2次扫描](http://slidesplayer.com/slide/11558942/62/images/26/%E4%BE%8B5.5%E6%89%80%E5%AF%B9%E5%BA%94%E6%95%B0%E7%BB%84X%5B+%5D%E7%9A%84%E5%86%85%E5%AE%B9%E5%A6%82%E8%A1%A85.1%EF%BC%9A+%E8%A1%A85.1+%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6%E8%83%BD%E5%90%A6%E6%8E%A8%E5%87%BA%E7%A9%BA%E7%9A%84%E8%A1%A8+%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6+S+A+B+C+D+%E5%88%9D%E5%80%BC+%E7%AC%AC1%E6%AC%A1%E6%89%AB%E6%8F%8F+%E7%AC%AC2%E6%AC%A1%E6%89%AB%E6%8F%8F.jpg "未定. 未定. 未定. 未定. 未定. 是. 是. 否. 是. 否.")
27
计算能推出ε的非终结符步骤如下： ① 将数组X[ ]中对应每一非终结符的标记置初值为“未定” ② 扫描文法中的产生式： (a) 删除所有右部含有终结符的产生式，若这使得以某一非终 结符为左部的所有产生式都被删除，则将数组中对应该非 终结符的标记值改为“否”，说明该非终结符不能推出ε (b) 若某一非终结符的某一产生式右部为ε，则将数组中对应 该非终结符的标志置为“是”，并从文法中删除该非终结符 的所有产生式。例中对应非终结符A、B的标志改为“是”
![计算能推出ε的非终结符步骤如下： ① 将数组X[ ]中对应每一非终结符的标记置初值为 未定 ② 扫描文法中的产生式： (a) 删除所有右部含有终结符的产生式，若这使得以某一非终. 结符为左部的所有产生式都被删除，则将数组中对应该非.](http://slidesplayer.com/slide/11558942/62/images/27/%E8%AE%A1%E7%AE%97%E8%83%BD%E6%8E%A8%E5%87%BA%CE%B5%E7%9A%84%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6%E6%AD%A5%E9%AA%A4%E5%A6%82%E4%B8%8B%EF%BC%9A+%E2%91%A0+%E5%B0%86%E6%95%B0%E7%BB%84X%5B+%5D%E4%B8%AD%E5%AF%B9%E5%BA%94%E6%AF%8F%E4%B8%80%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6%E7%9A%84%E6%A0%87%E8%AE%B0%E7%BD%AE%E5%88%9D%E5%80%BC%E4%B8%BA+%E6%9C%AA%E5%AE%9A+%E2%91%A1+%E6%89%AB%E6%8F%8F%E6%96%87%E6%B3%95%E4%B8%AD%E7%9A%84%E4%BA%A7%E7%94%9F%E5%BC%8F%EF%BC%9A+%28a%29+%E5%88%A0%E9%99%A4%E6%89%80%E6%9C%89%E5%8F%B3%E9%83%A8%E5%90%AB%E6%9C%89%E7%BB%88%E7%BB%93%E7%AC%A6%E7%9A%84%E4%BA%A7%E7%94%9F%E5%BC%8F%EF%BC%8C%E8%8B%A5%E8%BF%99%E4%BD%BF%E5%BE%97%E4%BB%A5%E6%9F%90%E4%B8%80%E9%9D%9E%E7%BB%88.+%E7%BB%93%E7%AC%A6%E4%B8%BA%E5%B7%A6%E9%83%A8%E7%9A%84%E6%89%80%E6%9C%89%E4%BA%A7%E7%94%9F%E5%BC%8F%E9%83%BD%E8%A2%AB%E5%88%A0%E9%99%A4%EF%BC%8C%E5%88%99%E5%B0%86%E6%95%B0%E7%BB%84%E4%B8%AD%E5%AF%B9%E5%BA%94%E8%AF%A5%E9%9D%9E..jpg "终结符的标记值改为 否 ，说明该非终结符不能推出ε. (b) 若某一非终结符的某一产生式右部为ε，则将数组中对应. 该非终结符的标志置为 是 ，并从文法中删除该非终结符. 的所有产生式。例中对应非终结符A、B的标志改为 是")
28
③ 扫描产生式右部的每一符号: (a) 若所扫描到的非终结符号在数组中对应的标志是“是”，则 删去该非终结符，若这使产生式右部为空，则对产生式左 部的非终结符在数组中对应的标志改“是”，并删除该非终 结符为左部的所有产生式 (b) 若所扫描到的非终结符号在数组中对应的标志是“否”，则 删去该产生式，若这使产生式左部非终结符的有关产生式 都被删去，则把在数组中该非终结符对应的标志改成“否” ④ 重复③，直到扫描完一遍文法的产生式，数组中非终结符 对应的特征再没有改变为止
29
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)中
30
* (e) 当(d)中所有Yi ε,(i=1,2,…n)，则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε} (f)反复使用上述(b)～(e)步直到每个符号的FIRST集合不再增 大为止
31
由此算法可计算例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}
32
所以最终求得： FIRST(S)={a,b,ε} FIRST(A)={b,ε} FIRST(B)={a,ε} FIRST(C)={a,b,c} FIRST(D)={a,c}
33
求出每个文法符号的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)) ∪{ε} ∈
34
每个产生式的右部符号串的开始符号集合为：
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}
35
② 由关系图法求文法符号的FIRST集： (a)每个文法符号对应图中一个结点，对应终结符的结点时用 符号本身标记，对应非终结符的结点用FIRST(A)标记。这 里A表示非终结符 (b)如果文法中有产生式A→αXβ，且α ε,则从对应A的 结点到对应X的结点连一条箭弧 (c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的 终结符都为FIRST(A)的成员 (d)由判别步骤1）确定ε是否为某非终结符FIRST集的成员， 若是则将ε加入该非终结符的FIRST集中 *
36
图 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 ε
37
3)计算FOLLOW集: ① 根据定义计算： 对文法中每一 A∈VN 计算 FOLLOW(A) (a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为 句子括号) (b)若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入 FOLLOW(B)中。 如果β ε则把FOLLOW(A)也加入FOLLOW(B)中 (c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止 *
38
现计算例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)
39
由以上最终计算结果得： FOLLOW(S)={#} FOLLOW(A)={a,#,c} FOLLOW(B)={#} FOLLOW(C)＝{#} FOLLOW(D)={#}
40
② 由关系图法求非终结符的FOLLOW集：
(a)文法G中的每个符号和“#”对应图中的一个结点，对应终结 符和“#”的结点用符号本身标记。对应非终结符的结点(如 A∈VN)则用FOLLOW(A)或FIRST(A)标记 (b)从开始符号S的FOLLOW(S)结点到“#”号的结点连一条箭弧 (c)如果文法中有产生式A→αBβX,且β ε,则从 FOLLOW(B)结点到FIRST(X)结点连一条弧，当X∈VT时，则 与X相连 *
41
* (d) 如果文法中有产生式A→αBβ,且β ε，则从 FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧 (e) 对每一FIRST(A)结点如果有产生式A→αXβ,且 α ε, 则从FIRST(A)到FIRST(X)连一条箭弧 (f)凡是从FOLLOW(A)结点有路径可以到达的终结符或“#”号的 结点，其所标记的终结符或"#"号即为FOLLOW(A)的成员 *
42
现在对例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集
43
对例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}
44
每个产生式的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}
45
由以上计算结果可得相同左部产生式的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集的交集不为空
46
5.3 某些非LL(1)文法到LL（1）文法的等价变换
1.提取左公共因子： A αβ1| αβ2|…| αβn，提取左公共因子后变为： A α（β1| β2|…| βn），再引进非终结符A`，变为： A αA` A` β1| β2|…| βn
47
例5.6 若文法G1的产生式为： （1）S aSb （2）S aS （3）S ε
48
对产生式（1）、（2）提取左公共因子后得： S aS（b｜ ε） S ε 进一步变换为文法G`1： S aSA A b A ε
49
例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
50
提取产生式（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
51
经验证提取公共因子后，文法G`1仍不是LL（1）文法，而
注意：对文法进行提取左公共因子变换后，有时会使某些产 生式变成无用产生式，在这种情况下必须对文法重新压缩 （化简）
52
例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
53
对（1）、（2）提取左公共因子后得： S aS（d｜c） 引入新非终结符A`后变为： （1）S aSA` （2）S bc （3）A` d|c （4）A aS （5）A b A不可到达
54
有些文法不能在有限步骤内提取完公共因子 例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`结果得等价文法为：
55
（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
56
2.消除左递归： ①A A β A∈VN， β ∈ V* 直接左递归 ② A Bβ B Aa A,B∈VN， a,β ∈ V* 间接左递归
57
例5.10 若文法G5的产生式为： （1）S S a （2）S b 所能产生的语言L={ban|n ≥0}, 输入串baaaa#是语言的句子 思考：什么时候用产生式（2）
58
例5.11 若文法G6的产生式为： （1）A aB （2）A Bb （3）B Ac （4）B d 若有输入串为adbcbcbc#，则分析过程的语法树为下图： 思考：什么时候用产生式（4）
59
由上述例子可以知道：含有左递归的文法绝对不是
LL（1）文法，为了使某些含有左递归的文法经等价变换 消除左递归后可能变为LL（1）文法，可采取下列变换公 式：
60
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`| ε
61
文法G5： （1）S S α （2）S b 可改写为： （1）S bS` （2）S` α S`| ε
62
2）消除间接左递归： 先通过产生式非终结符置换，将间接左递归变为直接左递 归，然后再按上面的方法消除直接左递归： 文法G6： （1）A aB （2）A Bb （3）B Ac （4）B d
63
用产生式（1）、（2）的右部置换产生式（3）中的A得
到左部为B的产生式： （1）B aBc （2）B Bbc （3）B d
64
消除左递归后得： （1）B (αBc|d)B` （2）B` bcB`| ε 再把原来其余的产生式（1）、（2）加入，最终文法为： （1）A αB （2）A Bb （3）B (αBc|d)B` （4）B` bcB`| ε
65
对文法中一切递归的消除要求文法中不含回路即无A A 的推导 满足这个要求的充分条件是，文法中不包含形如A A 的有害规则和A ε的空产生式
3）消除文法中一切左递归的算法： 对文法中一切递归的消除要求文法中不含回路即无A A 的推导 满足这个要求的充分条件是，文法中不包含形如A A 的有害规则和A ε的空产生式 算法步骤： （1）把文法的所有非终结符按某一顺序排序,如: A1| A2|… |An +
66
（2）从A1开始消除左部为A1的产生式的直接左递归，然
A1开始的产生式中的A1，并消除左部为A2的产生式中的直 接左递归。继而以同样方式把A1、A2的右部代入左部为A3 右部以A1或A2开始的产生式中，消除左部为A3的产生式之 直接左递归，直到把左部为A1，A2，…，An-1的右部代入 左部为An的产生式中，从An中消除直接左递归
67
把上述算法归结为：若非终结符的排序为： 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
68
（3）去掉无用产生式 例如 若文法的产生式为： （1）S Qc|c （2）Q Rb|b （3）R Sa|a
69
该文法的每个非终结符为间接左递归，消除方法：
非终结符排序为：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`|ε
70
最终文法变为： S Qc|c Q Rb|b R (bca|ca|a)R` R` bcaR`|ε
71
非终结符排序为：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
72
由于Q、R为不可到达的非终结符,所以删除得最终文法：
S (abc|bc|c|)S` S` abcS`| ε 结论：当非终结符排序不同时，最后结果的产生式形式不 同，但它们是等价的
73
5.4 不确定的自顶向下分析思想 不确定的自顶向下分析（带回溯的自顶向下分析）：在文 法中当关于某个非终结符的产生式有多个候选时，而面临
5.4 不确定的自顶向下分析思想 不确定的自顶向下分析（带回溯的自顶向下分析）：在文 法中当关于某个非终结符的产生式有多个候选时，而面临 当前的输入符无法确定选用唯一的产生式，从而引起回溯
74
1.由于相同左部产生式的右部FIRST集交集不为空而引起回溯
例如，文法： S xAy A ab|a 若当前输入串为xay
75
* 2.由于相同左部非终结符的右部存在能 ε的产生式，且 该非终结符的FOLLOW集中含有其他产生式右部FIRST 集的元素 例如，文法G［S］为： S aAS S b A bAS A ε 对输入串ab#的试探推导， 如右图所示：
76
3.由于文法含有左递归而引起回溯 例如，文法G［S］为： S Sa S b 对输入串baa#的试探推导，如下图所示：
77
由以上例子可知： 带回溯的自顶向下分析是是一个试探过程，当分析不成 功时则推翻分析退回到适当位置再重新试探其余候选可能的 推导，这样需要记录已选过的产生式，直到把所有可能的推 导序列都试完仍不成功才能确认输入串不是该文法的句子而 报错 由于在编译程序真正实现时往往是边分析边插入语义动作， 因而带回溯分析代价很高，效率很低，在实用编译程序中 几乎不用，因此对它实现的详细算法不做介绍
78
5.5 确定的自顶向下分析方法 1.递归子程序法： 实现思想：是对应文法中每个非终结符编写一个递归过
5.5 确定的自顶向下分析方法 1.递归子程序法： 实现思想：是对应文法中每个非终结符编写一个递归过 程，每个过程的功能是识别由该非终结符推出的串，当某非 终结符的产生式有多个候选时能够按LL（1）形式可唯一地确 定选择某个候选进行推导 缺点： 对文法要求高，必须满足LL（1）文法，个别LL（2）例外 速度慢占用空间多
79
2.预测分析方法： 预测分析器的组成： 预测分析程序 先进后出栈 预测分析表：用矩阵M[A,a]表示，A表示非终结符，a为终 结符或句子括号#，矩阵M[A,a]中的内容是一条关于A的产 生式，表明当用非终结符A向下推导时，面临输入符a时， 所应采取的候选产生式，当元素内容无产生时，则表明用A 为左部向下推导时遇到了不该出现的符号，因此元素内容 为转向出错处理的信息
![2.预测分析方法： 预测分析器的组成： 预测分析程序. 先进后出栈. 预测分析表：用矩阵M[A,a]表示，A表示非终结符，a为终. 结符或句子括号#，矩阵M[A,a]中的内容是一条关于A的产.](http://slidesplayer.com/slide/11558942/62/images/79/2.%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E6%96%B9%E6%B3%95%EF%BC%9A+%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E5%99%A8%E7%9A%84%E7%BB%84%E6%88%90%EF%BC%9A+%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E7%A8%8B%E5%BA%8F.+%E5%85%88%E8%BF%9B%E5%90%8E%E5%87%BA%E6%A0%88.+%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E8%A1%A8%EF%BC%9A%E7%94%A8%E7%9F%A9%E9%98%B5M%5BA%2Ca%5D%E8%A1%A8%E7%A4%BA%EF%BC%8CA%E8%A1%A8%E7%A4%BA%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6%EF%BC%8Ca%E4%B8%BA%E7%BB%88.+%E7%BB%93%E7%AC%A6%E6%88%96%E5%8F%A5%E5%AD%90%E6%8B%AC%E5%8F%B7%23%EF%BC%8C%E7%9F%A9%E9%98%B5M%5BA%2Ca%5D%E4%B8%AD%E7%9A%84%E5%86%85%E5%AE%B9%E6%98%AF%E4%B8%80%E6%9D%A1%E5%85%B3%E4%BA%8EA%E7%9A%84%E4%BA%A7..jpg "生式，表明当用非终结符A向下推导时，面临输入符a时， 所应采取的候选产生式，当元素内容无产生时，则表明用A. 为左部向下推导时遇到了不该出现的符号，因此元素内容. 为转向出错处理的信息.")
80
预测分析程序工作过程示意图： ＃句子括号即输入串的括号，S文法的开始符号 X存放当前栈顶符号的工作单元，a存放当前输入符号a的工作单元
81
例，表达式文法为： E E+T|T T T*F|F F i|(E)
82
构造步骤： (1) 判断文法是否为LL(1)文法 由于文法中含有左递归，所以必须先消除左递归，使 文法变为： E→TE′ E′→+TE′|ε T→FT′ T′→*FT′|ε F→i|(E)
83
可推出ε的非终结符表为: E E` T T` F 否 是
84
各非终结符的FIRST集合如下： FIRST(E)={(,i} FIRST(E′)={+,ε} FIRST(T)={(,i} FIRST(T′)={*,ε} FIRST(F)={(,i}
85
各非终结符的FOLLOW集合为： FOLLOW(E)={),#} FOLLOW(E′)={)，#} FOLLOW(T)={+，)，#} FOLLOW(T′)={+，)，#} FOLLOW(F)={*，+，)，#}
86
各产生式的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)文法
87
(2)构造预测分析表： 对每个终结符或“#”号用a表示 若a∈SELECT(A→α)，则把A→α放入M[A,a]中 把所有无定义的M[A,a]标上出错标记 为了使表简化，其产生式的左部可以不写入表中，表中 空白处为出错
![(2)构造预测分析表： 对每个终结符或 # 号用a表示. 若a∈SELECT(A→α)，则把A→α放入M[A,a]中. 把所有无定义的M[A,a]标上出错标记. 为了使表简化，其产生式的左部可以不写入表中，表中.](http://slidesplayer.com/slide/11558942/62/images/87/%282%29%E6%9E%84%E9%80%A0%E9%A2%84%E6%B5%8B%E5%88%86%E6%9E%90%E8%A1%A8%EF%BC%9A+%E5%AF%B9%E6%AF%8F%E4%B8%AA%E7%BB%88%E7%BB%93%E7%AC%A6%E6%88%96+%23+%E5%8F%B7%E7%94%A8a%E8%A1%A8%E7%A4%BA.+%E8%8B%A5a%E2%88%88SELECT%28A%E2%86%92%CE%B1%29%EF%BC%8C%E5%88%99%E6%8A%8AA%E2%86%92%CE%B1%E6%94%BE%E5%85%A5M%5BA%2Ca%5D%E4%B8%AD.+%E6%8A%8A%E6%89%80%E6%9C%89%E6%97%A0%E5%AE%9A%E4%B9%89%E7%9A%84M%5BA%2Ca%5D%E6%A0%87%E4%B8%8A%E5%87%BA%E9%94%99%E6%A0%87%E8%AE%B0.+%E4%B8%BA%E4%BA%86%E4%BD%BF%E8%A1%A8%E7%AE%80%E5%8C%96%EF%BC%8C%E5%85%B6%E4%BA%A7%E7%94%9F%E5%BC%8F%E7%9A%84%E5%B7%A6%E9%83%A8%E5%8F%AF%E4%BB%A5%E4%B8%8D%E5%86%99%E5%85%A5%E8%A1%A8%E4%B8%AD%EF%BC%8C%E8%A1%A8%E4%B8%AD..jpg "空白处为出错.")
88
表达式文法的预测分析表如表5.3 : VT i + * VN ( ) # E →TE′ →TE′ E` →+TE′ →+ ε →+ ε T →FT` →FT` T` → ε → *FT` → ε → ε → i → (E) F
89
下面用预测分析程序，栈和预测分析表对输入串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
90
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 # # 接受
91
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]的句子
![5.6 典型例题及解答 例题1 已知文法G[S]: S aH H aMd|d M Ab|ε A aM|e](http://slidesplayer.com/slide/11558942/62/images/91/5.6+%E5%85%B8%E5%9E%8B%E4%BE%8B%E9%A2%98%E5%8F%8A%E8%A7%A3%E7%AD%94+%E4%BE%8B%E9%A2%981+%E5%B7%B2%E7%9F%A5%E6%96%87%E6%B3%95G%5BS%5D%3A+S+aH+H+aMd%7Cd+M+Ab%7C%CE%B5+A+aM%7Ce.jpg "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]的句子.")
92
例题2 已知文法G[S]: S Aa|b A SB B ab 1.试对G[S]进行改写，并判断改写后的文法是否为LL（1）文 法 2.对于一个文法若消除左递归，提取了左公共因子后是否一定 为LL（1）文法
![例题2 已知文法G[S]: S Aa|b A SB. B ab. 1.试对G[S]进行改写，并判断改写后的文法是否为LL（1）文. 法. 2.对于一个文法若消除左递归，提取了左公共因子后是否一定.](http://slidesplayer.com/slide/11558942/62/images/92/%E4%BE%8B%E9%A2%982+%E5%B7%B2%E7%9F%A5%E6%96%87%E6%B3%95G%5BS%5D%3A+S+Aa%7Cb+A+SB.+B+ab.+1.%E8%AF%95%E5%AF%B9G%5BS%5D%E8%BF%9B%E8%A1%8C%E6%94%B9%E5%86%99%EF%BC%8C%E5%B9%B6%E5%88%A4%E6%96%AD%E6%94%B9%E5%86%99%E5%90%8E%E7%9A%84%E6%96%87%E6%B3%95%E6%98%AF%E5%90%A6%E4%B8%BALL%EF%BC%881%EF%BC%89%E6%96%87.+%E6%B3%95.+2.%E5%AF%B9%E4%BA%8E%E4%B8%80%E4%B8%AA%E6%96%87%E6%B3%95%E8%8B%A5%E6%B6%88%E9%99%A4%E5%B7%A6%E9%80%92%E5%BD%92%EF%BC%8C%E6%8F%90%E5%8F%96%E4%BA%86%E5%B7%A6%E5%85%AC%E5%85%B1%E5%9B%A0%E5%AD%90%E5%90%8E%E6%98%AF%E5%90%A6%E4%B8%80%E5%AE%9A..jpg "为LL（1）文法.")
93
例题3 已知文法G[S]: S Ab|Ba A aA|a B a 是LL（1）文法吗？若不是，请改写为等价的G`[S]，证 明改写后的文法是否为LL(1)文法
![例题3 已知文法G[S]: S Ab|Ba A aA|a B a 是LL（1）文法吗？若不是，请改写为等价的G`[S]，证 明改写后的文法是否为LL(1)文法](http://slidesplayer.com/slide/11558942/62/images/93/%E4%BE%8B%E9%A2%983+%E5%B7%B2%E7%9F%A5%E6%96%87%E6%B3%95G%5BS%5D%3A+S+Ab%7CBa+A+aA%7Ca+B+a+%E6%98%AFLL%EF%BC%881%EF%BC%89%E6%96%87%E6%B3%95%E5%90%97%EF%BC%9F%E8%8B%A5%E4%B8%8D%E6%98%AF%EF%BC%8C%E8%AF%B7%E6%94%B9%E5%86%99%E4%B8%BA%E7%AD%89%E4%BB%B7%E7%9A%84G%60%5BS%5D%EF%BC%8C%E8%AF%81+%E6%98%8E%E6%94%B9%E5%86%99%E5%90%8E%E7%9A%84%E6%96%87%E6%B3%95%E6%98%AF%E5%90%A6%E4%B8%BALL%281%29%E6%96%87%E6%B3%95.jpg "例题3 已知文法G[S]: S Ab|Ba A aA|a B a 是LL（1）文法吗？若不是，请改写为等价的G`[S]，证 明改写后的文法是否为LL(1)文法")
94
【本章小结】 确定的自顶向下分析方法虽对文法有一定的限制，但由 于实现方法简单、直观，便于手工构造或自动生成语法分析
确定的自顶向下分析方法虽对文法有一定的限制，但由 于实现方法简单、直观，便于手工构造或自动生成语法分析 器，因而仍是目前常用的方法之一。要求学员通过本章的学 习后，能够对一个给定的文法判断是否是LL(1)文法；能构造 预测分析表；能用预测分析方法判断给定的输入符号串是否 是该文法的句子；对某些非LL(1)文法做等价变换后可能变成 LL(1)文法。
95
第5章 作业题 P99： 1. 3. 7.(2)(3)
Similar presentations
