《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析——自上而下分析

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

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

源程序 词法分析器 出 单词符号 表格管理 语法分析器 语法单位错 语义分析与中间代码 生成器 四元式处 优化段 四元式 理 目标代码生成器← 目标代码 编译原理

编译原理 四元式 单词符号 语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 优化段 源程序 表 格 管 理 出 错 处 理 目标代码生成器

第四章语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析,必须对语言的语法结构 进行描述 口采用正规式和有限自动机可以描述和识别语言 的单词符号; 口用上下文无关文法来描述语法规则。 编译原理

编译原理 第四章 语法分析—自上而下分析 ◼ 本章主要介绍语法分析的处理 ◼ 要进行语法分析，必须对语言的语法结构 进行描述。 采用正规式和有限自动机可以描述和识别语言 的单词符号； 用上下文无关文法来描述语法规则

上下文无关文法的定义: 一个上下文无关文法G是一个四元式 G=(V,V,S,P),其中 OVr:终结符集合(非空) V:非终结符集合(非空),且VrVn S:文法的开始符号,SeVN P:产生式集合(有限),每个产生式形式为 P→a,PEVn,a∈(VrV)* 口开始符S至少必须在某个产生式的左部出现一次 编译原理

编译原理 ◼上下文无关文法的定义： 一个上下文无关文法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) 编译原理

编译原理 ◼ 例，定义只含+， *的算术表达式的文法 G=， 其 中，P由下列产生式组成： E → i E → E+E E → E*E E → (E)

定义:称aAB直接推出ayB,即 aA→ay 仅当A→y是一个产生式, 且a,B∈(VV 如果a1→a2→…an,则我们称这个序 列是从a到an的一个推导。若存在一个从 a到an的推导,则称a1可以推导出an 例:对文法(1) e→(e)→(e+e)→i+e)→i+i) 编译原理

编译原理 ◼ 定义：称A直接推出，即 A 仅当A → 是一个产生式， 且，  (VT  VN) * 。 ◼ 如果1  2   n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 ◼ 例：对文法(1) E  (E)  (E+E) (i+E) (i+i)

通常,用a1→an表示:从a1出发,经过 一步或若干步,可以推出an 用a1→an表示:从a1出发,经过0步或 若步,可以推出an 所以:a→β即a=或a→β 口定义:假定G是一个文法,S是它的开始符号。 如果 S 则a称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言,将它记为L(G)。 (G)={a|s→a,a∈r}

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

4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 语法分析器的功能:按照文法的产生式 (语言的语法规则),识别输入符号串是 否为一个句子(合式程序)。 编译原理

编译原理 4.1 语法分析器的功能 ◼ 语法分析的任务是分析一个文法的句子 结构。 ◼ 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)

单词符号 语法分 源程序词法分 语法分析树编译程序 析器 析器 后续部分 取下一单词 个 符号表 编译原理

编译原理 源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分

语法分析的方法: 口自下而上分析法(Bottom--up) 基本思想:从输入串开始,逐步进行“归 约”,直到文法的开始符号。即从树末端开 始,构造语法树。所谓归约,是指根据文法的 产生式规则,把产生式的右部替换成左部符号。 算符优先分析法:按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 LR分析法:规范归约 编译原理

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