编译原理讲义 (第六章语义分析和 目标代码生成) 南京大学计算机系 赵建华
编译原理讲义 (第六章:语义分析和 目标代码生成) 南京大学计算机系 赵建华
概念 编译程序的作用是:将源程序转换为具有相同效果的 可运行程序。 所谓相同效果就是程序的语义。 并不是所有满足语法规则的程序都是有意义的(we form)的 所谓语义分析,就是确定程序是有意义的,分析程序 的含义,并做出相应的处理 程序的含义包括: 数据结构的含义:和标识符相关联的数据对象。 控制结构的含义:由语言定义。规定了每个语句的 执行效果
概念 • 编译程序的作用是：将源程序转换为具有相同效果的 可运行程序。 • 所谓相同效果就是程序的语义。 • 并不是所有满足语法规则的程序都是有意义的(wellform)的。 • 所谓语义分析，就是确定程序是有意义的，分析程序 的含义，并做出相应的处理。 • 程序的含义包括： – 数据结构的含义：和标识符相关联的数据对象。 – 控制结构的含义：由语言定义。规定了每个语句的 执行效果
基本功 ·确定类型:确定标识符所关联的数据对象的数 据类型。 类型检査:按照语言的类型规则,对运算及分 量进行类型检查,必要时做出相应类型转换。 识别含义:根据程序设计语言的语义定义,确 定各个构造部分组合后的含义,做出相应处理 (生成中间代码或者目标代码)。 其它静态语义检查:比如控制流检査,嵌套层 数检查
基本功能 • 确定类型：确定标识符所关联的数据对象的数 据类型。 • 类型检查：按照语言的类型规则，对运算及分 量进行类型检查，必要时做出相应类型转换。 • 识别含义：根据程序设计语言的语义定义，确 定各个构造部分组合后的含义，做出相应处理 （生成中间代码或者目标代码）。 • 其它静态语义检查：比如控制流检查，嵌套层 数检查
语义分析的输入输出 ·输入为前面语法分析的结果。 输出为中间表示代码(抽象语法树,三元式.)。 把生成中间代码和代码生成分开,可以使难 点分解。 对中间代码的分析比较容易,便于进行优化。 可以把编译程序分成机器独立部分和机器相 关部分 便于任务的分解,和开发人员的分组开发
语义分析的输入输出 • 输入为前面语法分析的结果。 • 输出为中间表示代码(抽象语法树，三元式…)。 – 把生成中间代码和代码生成分开，可以使难 点分解。 – 对中间代码的分析比较容易，便于进行优化。 – 可以把编译程序分成机器独立部分和机器相 关部分。 – 便于任务的分解，和开发人员的分组开发
属性文法 对于某个压缩了的文法,当把每个文法符号和 组属性相关联,并把重写规则附加以语义规 则的时候,就得到属性文法 语法制导的翻译过程:由于属性文法的规则和 重写规则是一一对应的关系。所以,由属性文 法的确定的语义分析可以在语法分析的过程中 进行。这个过程成为语法指导的翻译。 语法指导的定义/翻译方案:语法指导的定义比 较抽象,隐藏了实现细节,无需指明语义规则 的计算次序。翻译方案则指明的计算次序
属性文法 • 对于某个压缩了的文法，当把每个文法符号和 一组属性相关联，并把重写规则附加以语义规 则的时候，就得到属性文法。 • 语法制导的翻译过程：由于属性文法的规则和 重写规则是一一对应的关系。所以，由属性文 法的确定的语义分析可以在语法分析的过程中 进行。这个过程成为语法指导的翻译。 • 语法指导的定义/翻译方案：语法指导的定义比 较抽象，隐藏了实现细节，无需指明语义规则 的计算次序。翻译方案则指明的计算次序
语法制导定义的例子 L∴=En Print(E. val) E∴=E1+T E. val= e, val+T val E∷=T E.yal=Tⅴal T: : =T*F Tval=t, val*f. val 工:三F Tval= f val F::=(E) Eval=e val F∷= digit F. val digit. lexval 对于语法符号E,TF,都确定了属性val,表示它们的值。 如果一个重写规则中有两个相同的符号,需加足标区 别 在归约过程中,每个归约得到的符号都对应于输入符 号串中的某一段
语法制导定义的例子 • 对于语法符号E,T,F，都确定了属性val，表示它们的值。 • 如果一个重写规则中有两个相同的符号，需加足标区 别。 • 在归约过程中，每个归约得到的符号都对应于输入符 号串中的某一段。 L::=En Print(E.val) E::=E1+T E.val = E1 .val+T.val E::=T E.val = T.val T::=T1*F T.val = T1 .val*F.val T::=F T.val = F.val F::=(E) F.val = E.val F::=digit F.val = digit.lexval
语法制导定义的例子(2) D:=TL L in=T type T =int T type: =integer T. - real T type integer L∴=L1.id LI. in: =L in; addtype(id entry .n) L:=空 L的属性包括in;T的属性值为type addtype表示将d对应的类型信息加入到标识符 表中
语法制导定义的例子（2） • L的属性包括:in；T的属性值为type • addtype表示将id对应的类型信息加入到标识符 表中。 D::=TL L.in = T.type T::=int T.type := integer T::=real T.type := integer L::=L1, id L1.in := L.in; addtype(id.entry, L.in) L::= 空
属性的计算和注释分析树 在语法制导分析过程中,我们不仅生成了一棵语法树, 还可以得到各个结点的属性值。把这些值加入到语法树 上面之后,就得到了注释分析树。 ·结点的属性值的计算过程有两种类型: 结点的属性由其子结点确定,称为综合属性。 结点的属性由兄弟结点和父结点的属性确定,称为继 承属性 在概念上,翻译过程如下 1:分析输入符号,建立语法树 2:从语法分析树得到描述结点属性之间的依赖关系,得到计算 次序 3:按照语义规则计算属性值
属性的计算和注释分析树 • 在语法制导分析过程中，我们不仅生成了一棵语法树， 还可以得到各个结点的属性值。把这些值加入到语法树 上面之后，就得到了注释分析树。 • 结点的属性值的计算过程有两种类型： – 结点的属性由其子结点确定，称为综合属性。 – 结点的属性由兄弟结点和父结点的属性确定，称为继 承属性。 • 在概念上，翻译过程如下： – 1：分析输入符号，建立语法树 – 2：从语法分析树得到描述结点属性之间的依赖关系，得到计算 次序。 – 3：按照语义规则计算属性值
分析过程和注释分析树例子(1) val=15 E+ T val=15 f val=4 val=5 va 5 4 lexval=4 Lexval=3
分析过程和注释分析树例子(1) L E n E T T F F 3 T * + Lexval=3 val=3 5 val=5 val=3 val=15 val=15 F 4 lexval=4 val=4 Val=4 Val=19
分析过程和注释分析树例子(2) ype- real in=real in=reak rea in=real l
分析过程和注释分析树例子(2) D T L real L , i3 L , i2 i1 type=real in=real in=real in=real