4.1确定的自顶向下分析思想 p686> ■基本方法 ◆对任何输入串，试图从开始符号出发，自上而下地为输入串建立 棵语法树，或者说为输入串寻找一个最左推导。 若有文法G1[S]: ■ 若有文法G2[S]: ■若有文法G3S]: ◆S→pAqB ◆S→Ap|Bq ◆S→aAd ◆A→cAda ◆A→cAa ◆A→bASIE ◆B→dBb ◆B→dBb ■判断输入串W=abd? ■判断输入串W=pccadd? ■判断输入串W=ccap? ■ 过程本质 ◆某文法符号对应当前输入符号时，有唯一的产生式进行替换并向下推导。 ■ LL(1)文法 ◆(A,a)A是语法树上准备进行推导的符号，a是面临的输入符号。 ◆如果我们知道所有候选式的SELECT(A→a)、所有候选式FIRST(a)、所 有非终结符号FOLLOW(A)。 ◆当有产生式：A→aa2.|an SELECT(A→ai)∩SELECT(A→a)=φ 6
6 4.1 确定的自顶向下分析思想 p68 ◼ 过程本质 ◆某文法符号对应当前输入符号时，有唯一的产生式进行替换并向下推导。 ◼ 若有文法G1[S]： ◆S → pA|qB ◆A → cAd|a ◆B → dB|b ◼ 判断输入串W=pccadd？ ◼ 若有文法G2[S]： ◆S → Ap|Bq ◆A → cA|a ◆B → dB|b ◼ 判断输入串W=ccap？ ◼ 基本方法 ◆对任何输入串,试图从开始符号出发， 自上而下地为输入串建立 一棵语法树，或者说为输入串寻找一个最左推导。 ◼ 若有文法G3[S]： ◆S → aA|d ◆A → bAS|ε ◼ 判断输入串W=abd？ ◼ LL(1)文法 ◆ (A, a) A是语法树上准备进行推导的符号，a是面临的输入符号。 ◆ 如果我们知道所有候选式的SELECT(A→ α)、所有候选式FIRST(α)、所 有非终结符号FOLLOW(A)。 ◆ 当有产生式：A→α1| α2 |.| αn SELECT(A→αi)∩SELECT(A→αj)= φ
LL(1)分析p71 ■含义 ◆第一个L表示从左向右扫描输入符号串； ◆第二个L表示生成最左推导； ◆1表示读入一个符号可确定下一步推导。 ■LL()文法能够对输入串进行有效的。 ■ 无回溯的自上而下分析
7 LL(1)分析 p71 ◼含义 ◆第一个 L 表示从左向右扫描输入符号串； ◆第二个 L 表示生成最左推导； ◆1 表示读入一个符号可确定下一步推导。 ◼LL(1)文法能够对输入串进行有效的。 ◼ 无回溯的自上而下分析
FIRST(a)集合的定义p69 ■设G=(VT,VN,S,P)a∈V* ■FIRST(a)={aa=*>aB,a∈Vr} ◆若a==*>e,则e∈FIRST(a) ◆FIRST(a)是a的所有可能推导的首遇终结 符号或e,是选择产生式的依据。 S→ApBq FIRST(Ap)={a,c A→cAa Ap==>apAp==>cAp FIRST (Bq)={b,d} B→dBlb Ba ==>ba Bq==>dBq ■ 因为S的两个候选式FIRST(Ap)∩FIRST(Bq)=Φ，所以 当S与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(Ap),选择S→Ap匹配 (2)i∈FIRST(Bq),选择S→Bq匹配(3)出错
8 FIRST(α)集合的定义 p69 ◼ 设G=(ＶT，ＶN，S，P） α∈Ｖ* ◼ FIRST(α)={a|α==*> aβ，a∈ＶT} ◆若α==*>ε，则ε∈FIRST(α) ◆FIRST(α)是α的所有可能推导的首遇终结 符号或ε，是选择产生式的依据。 α a . S → Ap|Bq A → cA|a B →dB|b FIRST(Ap) ={ a，c } Ap==>ap Ap==>cAp FIRST（Bq） ={ b，d} Bq ==>bq Bq==>dBq ◼ 因为S的两个候选式FIRST(Ap)∩ FIRST(Bq)=φ,所以 当S与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(Ap)，选择S → Ap匹配 (2)i∈FIRST(Bq)，选择S → Bq匹配 (3)出错
FOLLOW(A)集合的定义p70 A∈VN ■F0LL0W(A)={a|S==*>.Aa.,a∈Vr} ● ◆若S==>.A,则#∈FOLL0W（A) >#一输入串的结束符也可看作是句子的括号#S# ◆FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号 s→aAd #∈F0LL0W(A)S==>aA A→bASE a EFOLLOW (A)S==>aA==>abAS==>abAaA dEFOLLOW (A)S==>aA==>abAS==>abAd 因为A的两个候选式FIRST(bAS)∩FOLLOW(A)=Φ，所以 当A与面临的输入符号1匹配时，可能出现几种选择？ (1)i∈FIRST(bAS),选择A→bAS匹配 (2)i∈FOLL0W(A),选择A→e自动匹配(3)出错 ☒D
9 FOLLOW(A)集合的定义 p70 A∈ＶN ◼ FOLLOW(A)={ a｜S==*>.Aa. ，a∈ＶT } ◆若S==*>.A，则#∈FOLLOW（A） ➢#—输入串的结束符 也可看作是句子的括号 #S# ◆FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号 S .Aa. S → aA|d A → bAS|ε a∈FOLLOW(A)S==>aA==>abAS==>abAaA d∈FOLLOW(A)S==>aA==>abAS==>abAd #∈FOLLOW(A) S ==> aA ◼ 因为A的两个候选式FIRST(bAS)∩FOLLOW(A)=φ,所以 当A与面临的输入符号i匹配时，可能出现几种选择？ (1)i∈FIRST(bAS)，选择A → bAS匹配 (2)i∈FOLLOW(A)，选择A → ε自动匹配 (3)出错
SELECT(A→a)集合的定义P7 ■设G=(Vr,VN,S,P)a∈V* ■FIRST(a)={aa=*>aB,a∈Vr} ◆若a*>e,则SELECT(A→a)=FIRST(a) ◆若a==*>e,则SELECT(A→a) =(FIRST(a)-{e})UFOLLOW(A) S→aAd FOLLOW (A)={a,d,#} A→bASE SELECT (A-bAS)=FIRST(bAS)={b} SELECT(A→E) =(FIRST(E)-E)UFOLLOW(A)={a,d,# SaAld FOLLOW(A)=(a,d,#FIRST(K)={c,E} A→bASK SELECT (A-bAS)=FIRST (bAS)=(b} K→clE SELECT(A一→K) =(FIRST(K)-8)UFOLLOW (A)={c,a,d,# 可D
10 SELECT(A → α)集合的定义 p71 ◼ 设G=(ＶT，ＶN，S，P） α∈Ｖ* ◼ FIRST(α)={a|α==*> aβ，a∈ＶT} ◆若α==*>ε，则SELECT(A→α)= FIRST(α) S → aA|d A → bAS|K K → c|ε FOLLOW(A)={a,d,#} SELECT(A →bAS)=FIRST(bAS)={b} SELECT(A →ε) =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} S → aA|d A → bAS|ε FOLLOW(A)={a,d,#} FIRST(K)={c, ε} SELECT(A →bAS)=FIRST(bAS)={b} SELECT(A →K) =(FIRST(K)-ε) ∪FOLLOW(A)={c,a,d,#} ◆若α==*>ε，则SELECT(A→α) = (FIRST(α)-{ε})∪FOLLOW(A)