第4章自顶向下语法分析方法 n4.1确定的自顶向下语法分析思想 n 4.2LL(1)文法的判别 n 4.4不确定的自顶向下分析思想 n4.3某些非LL(1)文法到LL(1)文法的等价变换 u回溯一提取公共左因子 u无限循环一消除左递归 n 4.5确定的自顶向下分析方法 u4.5.1递归子程序法 u4.5.2表驱动LL(1)分析程序或预测分析方法 n 本章练习 n 作业 课程目录
1 第4章 自顶向下语法分析方法 n 4.1 确定的自顶向下语法分析思想 n 4.2 LL(1)文法的判别 n 4.4 不确定的自顶向下分析思想 n 4.3 某些非LL(1)文法到LL(1)文法的等价变换 u 回溯——提取公共左因子 u 无限循环——消除左递归 n 4.5 确定的自顶向下分析方法 u 4.5.1 递归子程序法 u 4.5.2 表驱动LL(1)分析程序或预测分析方法 n 本章练习 n 作业 课程目录
4.1确定的自顶向下分析思想p68 n基本方法 u对任何输入串，试图从开始符号出发，自上而下地为输入串建立 一棵语法树，或者说为输入串寻找一个最左推导。 n若有文法G1[S]: n若有文法G2[S]: n 若有文法G3[S]: uS→pAqB uS→ApBq uS→aAd uA→cAda uA→cAa uA→bAS|e uB→dBlb uB→dBb n 判断输入串W=abd? n判断输入串W=pccadd? 判断输入串W=ccap? n过程本质 u某文法符号对应当前输入符号时，有唯一的产生式进行替换并向下推导。 nLL(1)文法 u(A,a)A是语法树上准备进行推导的符号，a是面临的输入符号。 u 如果我们知道所有候选式的SELECT(A→a)、所有候选式FIRST(a)、所有 非终结符号FOLLOW(A)。 u当有产生式：A→a1a2.|an SELECT(A→ai)nSELECT(A→a)=Φ 冈
2 4.1 确定的自顶向下分析思想 p68 n 过程本质 u 某文法符号对应当前输入符号时，有唯一的产生式进行替换并向下推导。 n 若有文法G1[S]： u S → pA|qB u A → cAd|a u B → dB|b n 判断输入串W=pccadd？ n 若有文法G2[S]： u S → Ap|Bq u A → cA|a u B → dB|b n 判断输入串W=ccap？ n 基本方法 u 对任何输入串,试图从开始符号出发， 自上而下地为输入串建立 一棵语法树，或者说为输入串寻找一个最左推导。 n 若有文法G3[S]： u S → aA|d u A → bAS|ε n 判断输入串W=abd？ n LL(1)文法 u (A, a) A是语法树上准备进行推导的符号，a是面临的输入符号。 u 如果我们知道所有候选式的SELECT(A → α)、所有候选式FIRST(α)、所有 非终结符号FOLLOW(A)。 u 当有产生式：A→α1| α2 |.| αn SELECT(A→αi)∩SELECT(A→αj)= φ
LL(1)分析p71 n含义 u第一个L表示从左向右扫描输入符号串； u第二个L表示生成最左推导； u1表示读入一个符号可确定下一步推导。 nLL(1)文法能够对输入串进行有效的。 n无回溯的自上而下分析。 4 同区
3 LL(1)分析 p71 n 含义 u 第一个 L 表示从左向右扫描输入符号串； u 第二个 L 表示生成最左推导； u 1 表示读入一个符号可确定下一步推导。 n LL(1)文法能够对输入串进行有效的。 n 无回溯的自上而下分析
FIRST(a)集合的定义p69 n设G=(Vr,VN,S,P)a∈V* n FIRST(a)={aa==*>aB,aE VT} a u若a=*>e,则e∈FIRST(a) S→ApBq nFIRST (Ap)={a,c} A→cAa nFIRST (Bg)={b,d} B→dBb n因为S的两个候选式FIRST(Ap)∩FIRST(Bq)=Φ，所以 当$与面临的输入符号匹配时，可能出现几种选择？ (1)i∈FIRST(Ap),选择S→Ap匹配 (2)i∈FIRST(Bq),选择S→Bq匹配 (3)否则，出错 ☑D)
4 FIRST(α)集合的定义 p69 n 设G=(ＶT，ＶN，S，P） α∈Ｖ* n FIRST(α)={a|α==*> aβ，a∈ＶT} u 若α==*>ε，则ε∈FIRST(α) α a . S → Ap|Bq A → cA|a B →dB|b nFIRST(Ap) ={ a，c } nFIRST（Bq） ={ b，d} n 因为S的两个候选式FIRST(Ap)∩ FIRST(Bq)=φ,所以 当S与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(Ap)，选择S → Ap匹配 (2)i∈FIRST(Bq)，选择S → Bq匹配 (3)否则，出错
F0LL0W(A)集合的定义p70 A∈VN n FOLL0W(A)={a|S==*>.Aa.,a∈Vr} u若S=>.A,则#∈FOLLOW（A) 0☑#一输入串的结束符也可看作是句子的括号S# S→aAd nFOLLOW (A)={#,a,d} A→bASe n 因为A的两个候选式FIRST(bAS)∩FOLLOW(A)=Φ，所以 当A与面临的输入符号匹配时，可能出现几种选择？ (1)i∈FIRST(bAS),选择A→bAS匹配 (2)i∈FO0LL0W(A),选择A→e自动匹配 (3)否则，出错 D
5 FOLLOW(A)集合的定义 p70 A∈ＶN n FOLLOW(A)={ a｜S==*>.Aa. ，a∈ＶT } u 若S==*>.A，则#∈FOLLOW（A） Ø#—输入串的结束符 也可看作是句子的括号 #S# S .Aa. S → aA|d A → bAS|ε nFOLLOW(A)={#, a, d} n 因为A的两个候选式FIRST(bAS)∩FOLLOW(A)=φ,所以 当A与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(bAS)，选择A → bAS匹配 (2)i∈FOLLOW(A)，选择A → ε自动匹配 (3)否则，出错
SELECT(A→a)集合的定义p71 n设G=(Vr,VN,S,P)a∈V* n对每一个产生式：A→a u若a三)e则SELECT(A→a)=FIRST(a) u若a=>e则SELECT(A→a)=(FIRST(a)-e})UFOLL0W(A) S→aAd nFOLLOW (A)={a,d,# nSELECT (A -bAS)=FIRST(bAS)=(b} A→bASe nSELECT(A-e)=(FIRST (e)- 是LL(1)文法 e }UFOLLOW(A)={a,d,# n因为：SELECT(A→bAS)SELECT(A→e)=Φ S→aAd nFIRST (K)={c,e} A→bASK nFOLLOW (A)={a,d,#FOLLOW (K)={a,d,# nSELECT(K-c)=FIRST (c)={c} K→ce nSELECT (Ke)=(FIRST (K)-{e})UFOLLOW(A)={c,a,d,#} n因为：SELECT(K→c)∩SELECT(K→e)、Φ 不是LL(1)文 法 6 ☑D☑
6 SELECT(A → α)集合的定义 p71 n 设G=(ＶT，ＶN，S，P） α∈Ｖ* n 对每一个产生式：A→α u 若α==*>ε则SELECT(A→α)= FIRST(α) S → aA|d A → bAS|K K → c|ε 不是LL(1)文 法 nFOLLOW(A)={a,d,#} nSELECT(A →bAS)=FIRST(bAS)={b} nSELECT(A →ε)=(FIRST(ε)- {ε})∪FOLLOW(A)={a,d,#} n因为：SELECT(A →bAS)∩SELECT(A →ε)=φ S → aA|d A → bAS|ε 是LL(1)文法 nFIRST(K)={c, ε} nFOLLOW(A)={a,d,#} FOLLOW(K)={a,d,#} nSELECT(K →c)=FIRST(c)={c} nSELECT(K →ε)=(FIRST(K)-{ε}) ∪FOLLOW(A)={c,a,d,#} n因为：SELECT(K →c)∩SELECT(K →ε) == φ u 若α==*>ε则SELECT(A→α)=(FIRST(α)-ε})∪FOLLOW(A)
LL(1)文法的定义p71 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→a,A→B ,满足：SELECT(A→a)∩SELECT(A→B)=Φ S→aAd 求所有SELECT:集合： A→bASe nSELECT(S-aA)=FIRST(aA)={a} nSELECT(S-d)=FIRST(d)={d} nSELECT (A -bAS)=FIRST (bAS)={b} nSELECT(A→e) =(FIRST(e)-e)UFOLLOW(A)={a,d,# 求每个非终结符不同产生式SELECTI的交集： nSELECT(S→aA)∩SELECT(S→d)=Φ nSELECT(A→bAS)∩SELECT(A→e)=Φ 所以，该文法是LL(1)文法。 可回
7 LL(1)文法的定义 p71 n 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→α，A→β ，满足：SELECT(A→α)∩SELECT(A→β)= φ 求所有SELECT集合： nSELECT(S→aA)=FIRST(aA)={a} nSELECT(S →d)=FIRST(d)={d} nSELECT(A →bAS)=FIRST(bAS)={b} nSELECT(A →ε) n =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} S → aA|d A → bAS|ε 求每个非终结符不同产生式SELECT的交集： nSELECT(S→aA)∩SELECT(S →d)=φ nSELECT(A →bAS)∩SELECT(A →ε)=φ 所以，该文法是LL(1)文法
LL(1)文法的定义p71 n一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→a,A→B ,满足：SELECT(A→a)∩SELECT(A→B)=Φ S→aASb nFOLLOW (A)={a,b} A→bAe 求所有SELECT集合： nSELECT(S-aAS)=FIRST(aAS)={a} 存在问题： nSELECT(S -b)=FIRST (b)={b} n当A面临输入符 nSELECT (A-bA)=FIRST (bA)=(b} 号b时，无法用唯 nSELECT(Ae) 一的产生式去匹 n =(FIRST(e)-e)UFOLLOW(A)={a,b} 配。 求每个非终结符不同产生式SELECT的交集： nSELECT(S→aAS)∩SELECT(S→b)=Φ nSELECT(A→bA)∩SELECT(A→e)={b}≠Φ 所以，该文法不是LL(1)文法。 ☒D
8 LL(1)文法的定义 p71 n 一个上下文无关文法是LL(1)文法的充分必要条件是， 对每个非终结符的两个不同的产生式，A→α，A→β ，满足：SELECT(A→α)∩SELECT(A→β)= φ nFOLLOW(A)={a,b} 求所有SELECT集合： nSELECT(S→aAS)=FIRST(aAS)={a} nSELECT(S →b)=FIRST(b)={b} nSELECT(A →bA)=FIRST(bA)={b} nSELECT(A →ε) n =(FIRST(ε)-ε) ∪FOLLOW(A)={a,b} S → aAS|b A → bA|ε 求每个非终结符不同产生式SELECT的交集： nSELECT(S→aAS)∩SELECT(S →b)=φ nSELECT(A →bA)∩SELECT(A →ε)={b}≠φ 所以，该文法不是LL(1)文法。 存在问题： n当A面临输入符 号b时，无法用唯 一的产生式去匹 配
LL(1)分析 n对于文法G,当面临的输入符号为a,要用非 终结符A进行匹配时，假设A的所有产生式为 A→a1a2.an 1)若a∈SELECT(A→a:),则指派a去匹配 2)否则，a的出现是一种语法错误 章节目录
9 LL(1)分析 n 对于文法G，当面临的输入符号为a，要用 非 终结符A进行匹配时，假设A的所有产生 式为 A→α1| α2 |.| αn 1)若a∈SELECT(A →αi )，则指派αi去匹配 2)否则，a的出现是一种语法错误 章节目录
4.2LL(1)文法的判别p72 n FIRST:集合的计算 n FOLLOW:集合的计算 n SELECT集合的计算 nLL(1)文法的判别举例 nLL(1)文法判别课堂练习 章节目录 10 ☑
10 4.2 LL(1)文法的判别 p72 n FIRST集合的计算 n FOLLOW集合的计算 n SELECT集合的计算 n LL(1)文法的判别举例 n LL(1)文法判别课堂练习 章节目录