第八章语法制导翻译和中间代码生成 8.1概述 8.2属性文法和语法制导翻译 8.3语义分析 8.4中间代码 8.5一些语句的翻译
第八章语法制导翻译和中间代码生成 8.1概述 8.2属性文法和语法制导翻译 8.3语义分析 8.4中间代码 8.5一些语句的翻译
概述 语义处理 语法分析后的源程序→ 语义处理 。程序设计语言的语义 ·静态语义是对程序约束的描述，这些约束无法通过抽 象语法规则来妥善地描述，实质上就是语法规则的良 形式条件，它可以分为类型规则和作用域/可见性规则 两大类类型相容性变量先声明后引用名称相关要 求 动态语义程序单位描述的计算 ·编译程序的语义处理工作静态语义审查解释执行动 态语义（计算)生成代码
概述 语义处理 • 程序设计 语言的语义 • 静态语义是对程序约束的描述，这些约束无法通过抽 象语法规则来妥善地描述，实质上就是语法规则的良 形式条件，它可以分为类型规则和作用域/可见性规则 两大类 类型相容性 变量先声明后引用 名称相关要 求 动态语义 程序单位描述的计算 • 编译程序的语义处理工作 静态语义审查 解释执行动 态语义（计算）生成代码... 语 法 分 析 后 的 源 程 序 语义处理
概述 语义形式化语义建模 ·文法模型。属性文法 ·命令式或操作式模型--操作语义学 。应用式模型指称语义学 ·公理式模型--公理语义学
概述 语义形式化 语义建模 • 文法模型---- 属性文法 • 命令式或操作式模型 ----- 操作语义学 • 应用式模型-----指称语义学 • 公理式模型-----公理语义学
属性文法 表达式文法E一>T+TT or T T>nb E→T1+T2 Tl.type int T2.type=TI.type E.type :=int E→T10rT2 TI.type bool T2.type=TI.type E.type =bool) T→n T.type :int} T→b T.type bool}
属性文法 表达式文法 E—>T+T| T or T T—>n | b E→T 1 + T2 { T1.type = int T 2.type= T1.type E.type :=int} E →T 1 or T2 { T1.type = bool T 2.type= T1.type E.type :=bool} T → n { T.type := int} T → b { T.type := bool}
操作语义 描述一段程序的含义是通过执行该段程序所改变的计 算机（虚拟计算机）状态来反映。这个计算机的状态与 程序执行时的状态相对应：包括变量的所有值，可执行 程序本身，各种系统定义的内部数据结构。计算机里所 有的寄存器的值和存储单元的值作为计算机的状态，用 一组形式定义的操作来说明执行一条指令相应的状态怎 样变化。 For (expr1;expr2;expr3){ exprl; Loop:if expr2=0 goto out … expr3; goto loop 0ut:…
操作语义 描述一段程序的含义是通过执行该段程序所改变的计 算机（虚拟计算机）状态来反映。这个计算机的状态与 程序执行时的状态相对应：包括变量的所有值，可执行 程序本身，各种系统定义的内部数据结构。计算机里所 有的寄存器的值和存储单元的值作为计算机的状态，用 一组形式定义的操作来说明执行一条指令相应的状态怎 样变化。 For (expr1;expr2;expr3){ expr1; ... Loop:if expr2=0 goto out } … expr3; goto loop out:
公理语义 一个语言的每个语法成分的含义定义为公理和演绎规则， 用于推导出该成分执行的效果。 公理语义概念是随着程序正确性的证明而发展的。当正 确性证明能构造时表明程序执行它的规格说明所描述 的计算。在一个证明中，每一个语句之前之后都有一 个逻辑表达式对程序的变量进行约束，以此说明这个语 句的含义。 般的记号{P}S{Q} 如果在语句$执行前P为真，则在语句S执行并终止后Q为 真
公理语义 一个语言的每个语法成分的含义定义为公理和演绎规则， 用于推导出该成分执行的效果。 公理语义概念是随着程序正确性的证明而发展的。当正 确性证明能构造时表明程序执行它的规格说明所描述 的计算。在一个证明中，每一个语句之前之后都有一 个逻辑表达式对程序的变量进行约束,以此说明这个语 句的含义。 一般的记号 {P} S {Q} 如果在语句S执行前P为真，则在语句S执行并终止后Q为 真
演绎规测的例子 规则 前驱 后继 赋值：x:=expr P(expr)x:=exprP(x) While:{P∧B}S{P} P}while B do S end PA (not B)) if--then--else {B∧P}S1{Q},{(otB)∧P}S2{Q} (P)if B then S else S2{Q}
演绎规则的例子 规则 前驱 后继 赋值：x:=expr {P(expr)}x:=expr{P(x)} While: {P ∧ B} S {P} {P} while B do S end {P ∧ (not B)} if--then--else {B ∧ P} S1 {Q}, {(not B) ∧ P} S2 {Q} {P} if B then S1 else S2{Q}
指称语义 ·指称语义的基本概念是给每一段程序实体定义一个数 学意义上的对象，和一个从实体实例向数学意义对象 的映射的函数 ·特点：不但对全部程序赋予全文而且对程序设计语法 每一个语法成分短语（表达式，命令，声明.） 都给予含义。 每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。 即语义结构平行于语法结构。 ·语义函数： 程序设计语言的语义利用映射函数来证 明。 语义函数将短语映射到它的指称
指称语义 • 指称语义的基本概念是给每一段程序实体定义一个数 学意义上的对象，和一个从实体实例向数学意义对象 的映射的函数 • 特点： 不但对全部程序赋予全文而且对程序设计语法 每一个语法成分短语（表达式，命令，声明…） 都给予含义。 每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。 即 语义结构 平行于语法结构。 • 语义函数： 程序设计语言的语义利用映射函数来证 明。 语义函数将短语映射到它的指称
·例： 二进制数语言 110或10101 语法实体 指称（自然数） 6或21 语义实体 二进制数文法 Numeral::=0 :=1 ::Numeral 0 :=Numeral 1 自然数 Natrual=-{0,l,2,3,.…} 语义函数 Valuation:Numeral->Natural
• 例： 二进制数语言 110或10101 语法实体 指称（自然数） 6 或 21 语义实体 二进制数文法 Numeral::=0 ::=1 ::= Numeral 0 ::=Numeral 1 自然数 Natrual={0,1,2,3,…} 语义函数 Valuation:Numeral→Natural
Valuation[101]表示把Valuation)施用于l01 Valuation[N]------ 把它施用于N 定义：Valuation(用四个方程)因为有四个形式numeral Valuation[0]=0 Valuation[1]=1 Valuation[NO]=2x Valuation [N] Valuation[N1]=2x Valuation [N]+1 所以： Valuation[110]=2 x Valuation[11] =2×(2×Valuation[1]+l) =2×(2×1+1) =6
• Valuation[101] 表示把Valuation施用于101 Valuation[N] ------ 把它施用于N 定义: Valuation（用四个方程)因为有四个形式numeral Valuation[0] 0 Valuation[1] 1 Valuation[N0] 2Valuation [N] Valuation[N1] 2Valuation [N]+1 所以： Valuation[110]=2 Valuation[11] = 2 (2 Valuation[1]+1) =2 (2 1+1) =6