国防科技大学：《编译原理》课程电子教案（PPT教学课件）第4章 语法分析——自上而下分析

编译原理 第四章 语法分析一自上而下分析

编译原理 第四章 语法分析—自上而下分析

源程序 表 词法分析器 出 单词符号 语法分析器 格 语法单位 错 ← 语义分析与中间代码 生成器 管 四元式 处 优化段 理 四元式 理 目标代码生成器 目标代码 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 四元式 单词符号 语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 优化段 源程序 表 格 管 理 出 错 处 理 目标代码生成器

第四章语法分析一自上而下分析 ■本章主要介绍语法分析的处理 ■ 要进行语法分析，必须对语言的语法结构 进行描述。 口采用正规式和有限自动机可以描述和识别语言 的单词符号； ▣用上下文无关文法来描述语法规则。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 第四章 语法分析—自上而下分析 ◼ 本章主要介绍语法分析的处理 ◼ 要进行语法分析，必须对语言的语法结构 进行描述。 采用正规式和有限自动机可以描述和识别语言 的单词符号； 用上下文无关文法来描述语法规则

■上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(W,VN,S,P),其中 口V:终结符集合（非空） 口VN:非终结符集合（非空），且VTOVN=☑ 口S:文法的开始符号，S∈VN 口P:产生式集合（有限），每个产生式形式为 P→o,P∈VN,o∈(VTUVNZ)* 口开始符$至少必须在某个产生式的左部出现一次。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT  VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P→， PVN，   (VT  VN) * 开始符S至少必须在某个产生式的左部出现一次

■例，定义只含+，*的算术表达式的文法 G=,其 中，P由下列产生式组成： E→i E→E+E E→E*E E→(E) 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 例，定义只含+， *的算术表达式的文法 G=， 其 中，P由下列产生式组成： E → i E → E+E E → E*E E → (E)

定义：称oAB直接推出oy,即 AB→0yB 仅当A→Y是一个产生式， 且o,B∈(VUVN)。 ■如果01→02→..→0n’ 则我们称这个序 列是从到a的一个推导。若存在一个从 o1到on的推导，则称可以推导出on。 ■例：对文法(1) E→(E)→(E+E)=→(+E)=→(+i) 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 定义：称A直接推出，即 A 仅当A → 是一个产生式， 且，  (VT  VN) * 。 ◼ 如果1  2   n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 ◼ 例：对文法(1) E  (E)  (E+E) (i+E) (i+i)

通常，用a,→n 表示：从出发，经过 一步或若干步，可以推出o 用必1→Cn表示：从o1出发，经过0步或 若干步，可以推出on。 所以：C→B即=B或→B 口定义：假定G是一个文法，S是它的开始符号。 如果 则称是一个句型。仅含终结符 坐是句子。文法所产生的句子的全 体是一个语言，将它记为L(G)。 L(G)={Ox|S→,Ox∈V}

国防科技大学计算机系602教研室 ◼ 通常，用 表示：从1出发，经过 一步或若干步，可以推出n。  n + 1   n * 用 1  表示：从1出发，经过0步或 若干步，可以推出n。  =    +    * 所以 ：  即 或 ( ) { | , } * VT L G = S  +    ❑定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。  * S 

4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 g】 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子（合式程序）。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 4.1 语法分析器的功能 ◼ 语法分析的任务是分析一个文法的句子 结构。 ◼ 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)

单词符号 语法分 源程序词法分 语法分 析树 编译程序 析器 取下一单词 析器 后续部分 符号表 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分

语法分析的方法： 口自下而上分析法(Bottom-up) ■基本思想：从输入串开始，逐步进行“担 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ■算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ■LR分析法：规范归约 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼语法分析的方法： 自下而上分析法(Bottom-up) ◼基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ◼算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ◼ LR分析法：规范归约