∴该文法不是LL(1)文法。
SAB | bC Ab |ε BaD |ε CAD | b DaS | c
黄淮学院 信息工程学院
§5.3 某些非LL(1)文法到LL（1）文法的等价变换
1. 相同左部的产生式中，右部由相同的非终结符开始是否
可以进行确定的自顶向下分析？ 提取左公共因子： A 1 | 2 A A‟ A‟ 1 | 2 A 1 | ... | n | 1 | ... | m
(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 若文法G[S]为： SAB | bC Ab |ε BaD |ε CAD | b DaS | c 该文法是LL(1)文法吗？
黄淮学院 信息工程学院
1) 求出能推出ε的非终结符：S、A、B
2)计算First集:
根据定义计算：对每一文法符号X∈V， 计算First(X)
∩Select(Aβ)＝Ф ，其中α、 β不能同时
ε
黄淮学院 信息工程学院
例5.3 文法：
Select(SaA)={a} Select(Sd)={d} S → aA S→d A → bAS A→ε
Select(AbAS)={b}
Select(Aε)={a,d,#} 所以
Select(SaA)∩Select(Sd) ={a}∩{d} ＝Ф Select(AbAS)∩Select(Aε) = {b}∩{a,d,#}＝Ф
T
若α
* ε ，则规定ε ∈ First(α)，称First(α)为α的
开始符号集（首符号集）
黄淮学院 信息工程学院
例5.3 若有文法G3[S]: S → aA|d A →bAS|ε 识别输入串w=abd是否是G3[S]的句子
黄淮学院 信息工程学院
定义5.2：
设G=(VN ，VT ，P ，S)是上下文无关文法，A ∈ VN ，
SAB | bC Ab |ε BaD |ε CAD | b DaS | c
黄淮学院 信息工程学院
由以上最终计算结果得： Follow(S)={#} Follow(A)={a,#,c} Follow(B)={#}
SAB | bC Ab |ε BaD |ε CAD | b DaS | c
S → pA|qB A →cAd|a
B →dB|c
识别输入串w= pccadd是否是G1[S]的句子
黄淮学院 信息工程学院
例5.2 若有文法G2[S]: S → Ap |Bq A →a|cA B →b|dB 识别输入串w=ccap是否是G2[S]的句子
黄淮学院 信息工程学院
定义5.1： 设G=(VN ,VT , P , S)是上下文无关文法， * a β， a ∈ V ， α,β ∈ V*} First(α)={a | α
文法中不含左公共因子只是LL（1）文法的必要条件， 而不是充分条件； 对文法进行提取左公共因子变换后，有时会使某些产 生式变成无用产生式；
有些文法不能在有限步骤内提取完公共因子。
黄淮学院 信息工程学院
2. 产生式中含左递归，能否进行确定的自顶向下分析？ ① A Aβ ② A Bβ B Aa A,B∈VN， a,β ∈ V* 例5.10 SSa Sb 输入串：baaa# 含左递归不能进行确定的自上而下分析 间接左递归 A∈VN， β ∈ V* 直接左递归
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(C)={#}
Follow(D)={#}
黄淮学院 信息工程学院
4)计算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}
黄淮学院 信息工程学院
问题：以下程序语句的语法 是否正确？ int i = 0; int count = 0; while(i<=10) count++; 类似于： 输入串abba是否是给定 语言的句子？
S a b b B B B a
• 递归子程序法 • 预测分析法

• 算符优先分析法 • LR分析法
黄淮学院 信息工程学院
由此算法可计算例5.5文法各非终结符的First集： First(S)={First(A)-{ε }}∪{First(B)-{ε }}∪{ε }∪{b} ={b,a,ε } First(A)={b}∪{ε }={ b,ε } First(B)={ε }∪{a}={a,ε }
SAB | bC Ab |ε BaD |ε CAD | b DaS | c
∴该文法是LL(1)文法。
黄淮学院 信息工程学院
例5.4 文法：
Select(SaAS)＝{a} Select(Sb)＝{b} SaAS
S b
AbA Aε
Select(AbA)＝{b}
Select(Aε)＝{a,b} 所以
Select(SaAS)∩Select(S b) ={a}∩{b} ＝Ф Select(A bA)∩Select(Aε)= {b}∩{a,b}≠Ф
∴该文法不是LL(1)文法。
黄淮学院 信息工程学院
5.2 LL(1)文法的判别
注意：假定所给文法是经过压缩的（不包含多余规则） 判断LL(1)文法的步骤：
1）求出能推出ε的非终结符
2）求出文法中所有非终结符的First集 3）求出文法中所有非终结符的Follow集 4）求出每个产生式的Select集 5）求相同左部产生式的Select集的交集，并给出结论。
黄淮学院 信息工程学院
定义5.3：
给定产生式Aα，A ∈ VN， α ∈ V*，
(α *ε) First ( ) Select( A ) * ( ( First ( ) { }) Follow A) (α ε)
定义5.4：
一个CFG是LL(1)文法的充要条件是，对每个非终结符A 的两个不同产生式， Aα， Aβ ，满足Select(Aα)
黄淮学院 信息工程学院
由此算法可计算例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)
A A‟ | 1 | ... | m A‟ 1 | ... | n
黄淮学院 信息工程学院
练习：提取左公因子 例5.6 SaSb SaS Sε 例5.7 Aad ABc BaA BbB 例5.8 SaSd SAc AaS Ab 例5.9 SAp|Bq AaAp|d BaBq|e
黄淮学院 信息工程学院
1）消除直接左递归，把直接递归改写为右递归：
AA| （ 不以 A开头） 消除直接左递归 A A’ A’ A’ | （改写为右递归） 一般情况： A A 1 | ... | A m | 1 | ... | n 消除直接左递归 A 1 A’ | ... | n A’ A’ 1 A’ | ... | m A’ | （1 ... n 不以 A开头）
第五章 自顶向下语法分析方法
田丽芳
1
语法分析概览
• 语法分析对单词流进行处理；其最小项目是一个单词。
正规式 单词
错误处理
中间代码
源语言 程序
ห้องสมุดไป่ตู้
词法分析器
获取下一 个单词
语法分析器
语法树
前端剩余 部分处理
符号表
•用文法检验单词流的结构 是否正确、识别正确的语 法、生成语法树 •语法错误处理及恢复
•语法分析的部分技术 问题； •获取更多的单词属性 信息、类型检查、语义 分析等
First(C)={First(A)-{ε }}∪First(D)∪First(b)={b,a,c}
First(D)={a}∪{c}={a,c}
黄淮学院 信息工程学院
每个产生式的右部符号串的开始符号集合为： First(AB)={a,b,ε } First(bC)={b} First(ε )＝{ε }