第4章 自顶向下语法分析方法 n4.1确定的自顶向下语法分析思想 n 4.2LL(①)文法的判别 n4.4不确定的自顶向下分析思想 n4.3某些非LL(1)文法到LL(1)文法的等价变换 u回溯一提取公共左因子 u无限循环一消除左递归 n4.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 作业 课程目录
内容回顾 n句型、句子和语言的定义： n句型 u有文法G[S],若S=>a,且a∈V*,则称 是a是文法G的一个句型。 n句子 u有文法G[S],若S=>a,且a∈V*,则称 是a是文法G的一个句子。 n语言 u由文法G产生的所有句子的集合 L(G)={aS==+>a,且a∈Vr*
2 内容回顾 n 句型、句子和语言的定义： n 句型 u有文法G[S]，若S ==*>α，且α∈Ｖ* , 则称 是α是文法G的一个句型。 n 句子 u有文法G[S]，若S ==*>α，且α∈ＶT * ,则称 是α是文法G的一个句子。 n 语言 u由文法 G 产生的所有句子的集合 L(G)={α|S==+>α,且α∈VT *}
n最左（最右）推导 内容回顾（续） u在推导的任何一步都对当前句型中的最左（最右）非 终结符进行替换。 n句型分析（句子分析） u识别一个符号串是否为某文法的句型（句子）的过程。 U也就是某文法的某个推导的构造过程。 n设文法G为： E E→E+T|T T→T*F|F F→(E)|i 自项向下 自底向上 n请问符号串+ii是 否为该文法的句子？ ☒
3 内容回顾(续) n 最左(最右)推导 u在推导的任何一步都对当前句型中的最左(最右)非 终结符进行替换。 n 句型分析(句子分析) u识别一个符号串是否为某文法的句型(句子)的过程。 u也就是某文法的某个推导的构造过程。 n 设文法G为: E →E+T|T T →T*F|F F →(E)|i n 请问符号串i+i*i是 否为该文法的句子? E E + T T * F F F T i i i 自 顶 向 下 自 底 向 上
常用语法分析方法 n语法分析算法可分为两大类： n自顶向下分析法 u从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 n自底向上分析法 u从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 门两种方法反映了两种不同的语法树的构造过程 u自顶向下一一从树根推导到树叶。 u自底向上一一从树叶归约到树根
4 常用语法分析方法 n 语法分析算法可分为两大类: n 自顶向下分析法 u从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 n 自底向上分析法 u从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 n 两种方法反映了两种不同的语法树的构造过程 u自顶向下——从树根推导到树叶。 u自底向上——从树叶归约到树根
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→dBb uB→dBlb n 判断输入串W=abd? n判断输入串W=pccadd? n判断输入串W=ccap? u请分析，引入FIRST(a)FOLL0W(A)SELECT(A→a)3个终结符集合 同
5 4.1 确定的自顶向下分析思想p68 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？ u 请分析, 引入 FIRST(α) FOLLOW(A) SELECT(A→α) 3个终结符集合
4.1确定的自顶向下分析思想p68 n基本方法 U对任何输入串，试图从开始符号出发，自上而下地为输入串建立 一棵语法树，或者说为输入串寻找一个最左推导。 n若有文法G1[S]: n若有文法G2[S]: n若有文法G3[S]: u SpA gB uS→Ap Bq u SaA d uA→cAda uA→cAa uA→bAS uB→dBb uB→dB|b n 判断输入串W=abd? n判断输入串W=pccadd? n 判断输入串W=ccap? n过程本质 U某文法符号对应当前输入符号时，有唯一的产生式进行替换并向下推导。 nLL(1)文法 u(A,a)A是语法树上准备进行推导的符号，a是面临的输入符号。 u如果我们知道所有候选式的SELECT(A→a)、所有候选式FIRST(a)、所有 非终结符号FOLL0W(A)。 u当有产生式：A→a1a2.|an SELECT(A→a)∩SELECT(A→a)=Φ
6 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无回溯的自上而下分析。 可)
7 LL(1)分析 p71 n 含义 u第一个 L 表示从左向右扫描输入符号串； u第二个 L 表示生成最左推导； u1 表示读入一个符号可确定下一步推导。 n LL(1)文法能够对输入串进行有效的。 n 无回溯的自上而下分析
FIRST(a)集合的定义p69 n设G(VT,VN,S,P)a∈V* n FIRST(a)={aa==*>aB,aE VT} a u若a=*>e,则e∈FIRST(a) uFIRST(a)是a的所有可能推导的首遇终结 符号或e，是选择产生式的依据。 S→ApBq nFIRST (Ap)={a,c} A→cAa Ap-=>apAp==>cAp B→dBb nFIRST (Bq)={b,d} Bg ==>bqBq==>dBq n因为S的两个候选式FIRST(Ap)∩FIRST(Bq)=Φ，所以 当$与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(Ap),选择S→Ap匹配 (2)i∈FIRST(Bq),选择S→Bq匹配(3)出错
8 FIRST(α)集合的定义p69 n 设G=(ＶT，ＶN，S，P） α∈Ｖ* n FIRST(α)={a|α==*> aβ，a∈ＶT} u若α==*>ε，则ε∈FIRST(α) uFIRST(α)是α的所有可能推导的首遇终结 符号或ε，是选择产生式的依据。 α a . S→Ap|Bq A→cA|a B→dB|b nFIRST(Ap) ={ a，c } Ap==>ap Ap==>cAp nFIRST（Bq） ={ b，d} Bq ==>bq Bq==>dBq n 因为S的两个候选式FIRST(Ap)∩ FIRST(Bq)=φ,所以 当S与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(Ap)，选择S→Ap匹配 (2)i∈FIRST(Bq)，选择S→Bq匹配 (3)出错
F0LL0W(A)集合的定义D70 A∈VN nF0LL0W(A)={a|S=*>.Aa.,a∈Vr} U若S=>.A,则#∈FOLLOW（A) ☑#一输入串的结束符也可看作是句子的括号S# U FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号 S→aAd n#∈FOLLOW(A)S=>aA A→bASe n aEFOLLOW (A)S==>aA==>abAS==>abAaA n dEFOLLOW(A)S==>aA==>abAS==>abAd n 因为A的两个候选式FIRST(bAS)∩FOLL0W(A)=Φ，所以 当A与面临的输入符号1匹配时，可能出现几种选择？ (1)i∈FIRST(bAS),选择A→bAS匹配 (2)i∈F0LL0W(A),选择A→e自动匹配(3)出错 K
9 FOLLOW(A)集合的定义 p70 A∈ＶN n FOLLOW(A)={ a｜S==*>.Aa. ，a∈ＶT } u若S==*>.A，则#∈FOLLOW（A） Ø#—输入串的结束符 也可看作是句子的括号 #S# uFOLLOW(A)表示了句型中可能紧跟在A后面的终结符号 S .Aa. S→aA|d A→bAS|ε n a∈FOLLOW(A) S==>aA==>abAS==>abAaA n d∈FOLLOW(A) S==>aA==>abAS==>abAd n #∈FOLLOW(A) S ==> aA 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 FIRST(a)={aa==*>aB,ae VT} u若a立*>e,则SELECT(A→a)=FIRST(a) u若a=*>e,则SELECT(A→a) =(FIRST(a)-{e})UFOLLOW(A) S→aAd nFOLLOW (A)={a,d,#) AbAS nSELECT (A bAS)=FIRST (bAS)={b} nSELECT(A→e) S→aAd nFOLLOW (A)={a,d,#FIRST(K)={c,e} A→bASK nSELECT (A -bAS)=FIRST(bAS)={b} K→ce nSELECT(A→K) =(FIRST(K)-e)UFOLLOW (A)={c,a,d,#} KD
10 SELECT(A→α)集合的定义 p71 n 设G=(ＶT，ＶN，S，P） α∈Ｖ* n FIRST(α)={a|α==*> aβ，a∈ＶT} u若α==*>ε，则SELECT(A→α)= FIRST(α) S→aA|d A→bAS|K K→c|ε nFOLLOW(A)={a,d,#} nSELECT(A →bAS)=FIRST(bAS)={b} nSELECT(A→ε) =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} S→aA|d A→bAS|ε nFOLLOW(A)={a,d,#} FIRST(K)={c, ε} nSELECT(A→bAS)=FIRST(bAS)={b} nSELECT(A→K) =(FIRST(K)-ε) ∪FOLLOW(A)={c,a,d,#} u若α==*>ε，则SELECT(A→α) = (FIRST(α)-{ε})∪FOLLOW(A)