第4章自顶向下语法分析方法 0 4.1确定的自顶向下语法分析思想 ▣4.2LL(1)文法的判别 口4.4不确定的自顶向下分析思想 0 4.3某些非LL(1)文法到LL(1)文法的等价变换 口回溯—提取公共左因子 口无限循环一消除左递归 0 4.5确定的自顶向下分析方法 口4.5.1递归子程序法 口4.5.2表驱动LL(1)分析程序或预测分析方法 0 本章练习 0 作业 课程目录
1 第4章 自顶向下语法分析方法 4.1 确定的自顶向下语法分析思想 4.2 LL(1)文法的判别 4.4 不确定的自顶向下分析思想 4.3 某些非LL(1)文法到LL(1)文法的等价变换 回溯——提取公共左因子 无限循环——消除左递归 4.5 确定的自顶向下分析方法 4.5.1 递归子程序法 4.5.2 表驱动LL(1)分析程序或预测分析方法 本章练习 作业 课程目录
内容回顾 ■句型、句子和语言的定义： ■句型 ◆有文法G[S],若S=*>a,且a∈V*,】 则称 是a是文法G的一个句型。 ■句子 ◆有文法G[S],若S=*>a,且a∈V*,则称 是a是文法G的一个句子。 ■语言 ◆由文法G产生的所有句子的集合 L(G)={aS==+>a,且a∈Vm} 2 可D
2 内容回顾 ◼句型、句子和语言的定义： ◼句型 ◆有文法G[S]，若S ==*>α，且α∈Ｖ* , 则称 是α是文法G的一个句型。 ◼句子 ◆有文法G[S]，若S ==*>α，且α∈ＶT * ,则称 是α是文法G的一个句子。 ◼语言 ◆由文法 G 产生的所有句子的集合 L(G)={α|S==+>α,且α∈VT *}
■最左（最右）推导 内容回顾（续 G ◆在推导的任何一步都对当前句型中的最左（最若）非 终结符进行替换。 ■句型分析（句子分析） ◆识别一个符号串是否为某文法的句型（句子）的过程。 ◆也就是某文法的某个推导的构造过程。 口设文法G为： E E→E+T|T T→T*FF F→(E)|i 自项向下 自底向上 01 请问符号串i+i*i是 否为该文法的句子？ KC
3 内容回顾(续) ◼最左(最右)推导 ◆在推导的任何一步都对当前句型中的最左(最右)非 终结符进行替换。 ◼句型分析(句子分析) ◆识别一个符号串是否为某文法的句型(句子)的过程。 ◆也就是某文法的某个推导的构造过程。 设文法G为: E →E+T|T T →T*F|F F →(E)|i 请问符号串i+i*i是 否为该文法的句子? E E + T T * F F F T i i i 自 顶 向 下 自 底 向 上
常用语法分析方法 ■语法分析算法可分为两大类： ■自顶向下分析法 ◆从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 自底向上分析法 ◆从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 ■i 两种方法反映了两种不同的语法树的构造过程 ◆自顶向下—一从树根推导到树叶。 ◆自底向上—一从树叶归约到树根。 可)
4 常用语法分析方法 ◼语法分析算法可分为两大类: ◼自顶向下分析法 ◆从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 ◼自底向上分析法 ◆从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 ◼两种方法反映了两种不同的语法树的构造过程 ◆自顶向下——从树根推导到树叶。 ◆自底向上——从树叶归约到树根
5.1确定的自顶向下分析思想 p686 ■基本方法 ◆对任何输入串，试图从开始符号出发，自上而 下地为输入串建立一棵语法树，或者说为输入 串寻找一个最左推导。 ■过程本质 ◆某文法符号对应当前输入符号时，有唯一的产 生式进行替换并向下推导
5 5.1 确定的自顶向下分析思想 p68 ◼基本方法 ◆对任何输入串,试图从开始符号出发， 自上而 下地为输入串建立一棵语法树，或者说为输入 串寻找一个最左推导。 ◼过程本质 ◆某文法符号对应当前输入符号时，有唯一的产 生式进行替换并向下推导
例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) >#一输入串的结束符也可看作是句子的括号#$# ◆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)出错