例4.1p68 若有文法G1[S]: ◆S→pAqB ◆A→cAda ◆B→dBb ■ 若输入串W=pccadd,请问每一步推导产 生式选择是不是唯一的？ ■给出语法树唯一的 ■文法的特点： ◆每个产生式的右部都由终结符开始； ◆若两个产生式左部相同，则右部由不同的终结 符开始。 6 ☑☒
6 例4.1 p68 ◼若有文法G1[S]： ◆S → pA|qB ◆A → cAd|a ◆B →dB|b ◼若输入串W=pccadd，请问每一步推导 产 生式选择是不是唯一的？ ◼给出语法树 唯一的 ◼文法的特点： ◆每个产生式的右部都由终结符开始； ◆若两个产生式左部相同，则右部由不同的终结 符开始
例4.2p68 ■若有文法G2[S]: ◆S→AplBg A→cAaB→dBIb ■若输入串W=ccap,请问每一步推导产生 式选择是不是唯一的？ ■给出语法树唯一的 ■文法的特点： ◆产生式右部不全是由终结符开始； ◆若两个产生式左部相同，则右部由不同的终结 符或不同的非终结符开始。 ◆无空产生式。 ■如何选择唯一的产生式进行推导？Fist集合 可D
7 例4.2 p68 ◼若有文法G2[S]： ◆S → Ap|Bq A → cA|a B →dB|b ◼若输入串W=ccap，请问每一步推导 产生 式选择是不是唯一的？ ◼给出语法树 唯一的 ◼文法的特点： ◆产生式右部不全是由终结符开始； ◆若两个产生式左部相同，则右部由不同的终结 符或不同的非终结符开始。 ◆无空产生式。 ◼如何选择唯一的产生式进行推导？First集合
FIRST(a)集合的定义p69 ■设G=(VT,VN,S,P)a∈V* ■FIRST(a)={aa=*>aB,a∈Vr} a ◆若a=>e,则e∈FIRST(a) ◆FIRST(a)是a的所有可能推导的首遇终结 符号或e,是选择产生式的依据。 S→Ap|Bq FIRST(Ap)={a,c A→cAa Ap==>apAp==>cAp FIRST (Bg)=b,d} B->dBlb Bq ==>bq Bq==>dBq ■ 因为S的两个候选式FIRST(Ap)∩FIRST(Bq)=Φ，所以 当$与面临的输入符号匹配时，可能出现几种选择？ (I)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)出错
例4.3p70 ■ 若有文法G2[S]: ◆S→aAdA→bASIE ■若输入串W=abd,请问每一步推导产生 式选择是不是唯一的？ ■给出语法树唯一的 ■特点： ◆含空产生式。 ◆当A面临d时，d不属于FIRST(bAS),用A→E 自动匹配，前提非终结符A的后继符号中含有d。 ■如何选择唯一的产生式进行推导？ FOLLOW集合
9 例4.3 p70 ◼若有文法G2[S]： ◆S → aA|d A → bAS|ε ◼若输入串W=abd，请问每一步推导 产生 式选择是不是唯一的？ ◼给出语法树 唯一的 ◼特点： ◆含空产生式。 ◆当A面临d时，d不属于FIRST(bAS)，用A→ε 自动匹配，前提非终结符A的后继符号中含有d。 ◼如何选择唯一的产生式进行推导？ FOLLOW集合
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)出错 KD
10 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)出错