第4章自顶向下语法分析方法 0 4.1确定的自顶向下语法分析思想 口4.2LL(1)文法的判别 口4.4不确定的自顶向下分析思想 口4.3某些非LL(1)文法到LL(1)文法的等价变换 ▣回溯一提取公共左因子 无限循环一消除左递归 4.5确定的自顶向下分析方法 4.5.1递归子程序法 0 口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)={a|S=+>a,且a∈V*}
2 内容回顾 ◼句型、句子和语言的定义： ◼句型 ◆有文法G[S]，若S ==*>α，且α∈Ｖ* , 则称 是α是文法G的一个句型。 ◼句子 ◆有文法G[S]，若S ==*>α，且α∈ＶT * ,则称 是α是文法G的一个句子。 ◼语言 ◆由文法 G 产生的所有句子的集合 L(G)={α|S==+>α,且α∈VT *}
■最左（最右）推导 内容回顾（续 ◆在推导的任何一步都对当前句型中的最左（最右）非 终结符进行替换。 ■句型分析（句子分析） ◆识别一个符号串是否为某文法的句型（句子）的过程。 ◆也就是某文法的某个推导的构造过程。 0 设文法G为： E E→E+T|T T→T*FF F→(E)|i 自顶向下 自底向上 0请问符号串i+i*i是 否为该文法的句子？ ☑
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 常用语法分析方法 ◼语法分析算法可分为两大类: ◼自顶向下分析法 ◆从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 ◼自底向上分析法 ◆从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 ◼两种方法反映了两种不同的语法树的构造过程 ◆自顶向下——从树根推导到树叶。 ◆自底向上——从树叶归约到树根
4.1确定的自顶向下分析思想 p686 ■ 基本方法 ◆对任何输入串，试图从开始符号出发，自上而下地为输入串建立 棵语法树，或者说为输入串寻找一个最左推导。 ■若有文法G1[S]: ■若有文法G2[S]: 若有文法G3[S]: ◆S→pAlqB ◆S→Ap/Bq ◆S→aAd ◆A→cAda ◆AcAa ◆A→bASIE ◆B→dBb ◆B→dBb ■判断输入串W=abd? ■ 判断输入串W=pccadd? ■判断输入串W=ccap? ◆请分析，引入FIRST(a)FOLL0W(A)SELECT(A→a)3个终结符集合 5
5 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？ ◆请分析, 引入 FIRST(α) FOLLOW(A) SELECT(A → α) 3个终结符集合