国防科技大学：《编译原理》课程电子教案（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=<i,+,*,（,)},{E},E,P>,其 中，P由下列产生式组成： E→i E→E+E E→E*E E→(E) 国防科技大学计算机系602教研室

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