编译原理 第8章 常用中间语言

语法制导翻译

属性文法 语法制导翻译概论

计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译
属性文法

属性文法的形式化定义 属性文法是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法。 V:有穷的属性集,每个属性与文法的一个终结 符或非终结符相连。 F:关于属性的断言或谓词集。每个断言与一个 产生式相联。
综合属性

将属性附着在分析树对应文法符号上，形成注释分 析树。（属性作为分析树的注释） 8+5*2的分析树 L E
E
T F
+
T
T F digit F
digit
digit
综合属性

将属性附着在分析树对应文法符号上，形成注释分 析树。（属性作为分析树的注释） 8+5*2的注释分析树 L E.val E.val + T.val F.val T.val F.val digit.lexval
属性文法

属性的抽象表示 例如：E.val（值） E.type（类型） E.code（代码序列） E.place（存储空间）
属性文法

E
T
文法G：

+
T
ET1+T2|T1 or T2 Tnum|true|false
3
4
ET1+T2 {T1.t=int AND T2.t=int} ET1orT2{ T1.t=bool AND T2.t=bool} E{T1.t=T2.t} Tnum {T.t=int} T{T1.t=int} + Ttrue {T.t=bool} T{T2.t=int} Tfalse {T.t=bool}

8.2.1 基本块与流图 一、 基本块 是指程序中一顺序执行的语句序列， 其中只有一个入口和一个出口， 入口就 是其中的第一个语句，出口就是其中 最后一个语句。 对一个基本块来说，执行时，只能 从入口进入，从出口退出
计算机学院 辛明影
R=10; Pi=3.14
一个给定的程序，可以把 它划分为一系列的基本块
计算机学院
辛明影
删除无用赋值后
i=m-1 j=n t1=4*n v=a[t1]
B1
i=i+1 B2 t2=4*i t3=a[t2] if t3<v goto B2 j=j-1 B3 t4=4*j t5=a[t4] if t5<v goto B3 if i>=j goto B6 B4 B5 B6
a[t2]=t5 a[t4]=t3 goto B2
计算机学院 辛明影
中 间 代 码
① read x ② read y ③ r=x mod y ④ if r=0 goto ⑧ ⑤ x=y ⑥ y=r ⑦ goto ③ ⑧ write y ⑨ end
计算机学院
辛明影
入口语句： 入口语句： ① 、③、⑤、⑧ 基本块： 基本块： ①、②; ③、④；⑤、⑥、⑦； 、⑨； ⑧ 基本块内除可用： 基本块内除可用：删除公共子表达式 复写传播 删除无用赋值 还可用下面的变换： 还可用下面的变换：
2。临时变量改名 1。合并已知量 3。交换语句的位置 4。代数变换 代数变换
计算机学院 辛明影
二、程序流图 程序流图为一以基本块为结点的有向图； 含有程序中第一条语句的结点叫作首结点 含有程序中第一条语句的结点叫作首结点 程序流图构造方法： 程序流图构造方法： 条件或无条件语句从B1转到B2 B1转到 1。条件或无条件语句从B1转到B2 B2紧跟在B1后面 紧跟在B1后面（ B1最后语句 2。B2紧跟在B1后面（且B1最后语句 不是无条件转移语句） 不是无条件转移语句） 此时称B2为 的后继 的后继， 为 的前驱 此时称 为B1的后继，B1为B2的前驱

运行时存储组织
活动记录（activation record）
过程活动记录
• 函数/过程调用或返回时，在运行栈上创建或从运行栈 上消去的栈帧（frame） 包含局部变量，函数实参，临时值（用于表达式计算的 中间单元）等数据信息以及必要的控制信息 某个数据对象的地址= 活动记录起始地址 + 偏移地址（offset）
D[2]
D[1]
Q 的活动记录
P 的活动记录 S 的活动记录
D[0]
main 的活动记录
运行时存储组织
活动记录
嵌套过程语言的栈式分配
• Display 表的维护（过程被调用和返回时的保存和恢复） 方法一 极端的方法是把整个 Display 表存入活动记录 若过程为第 n 层，则需要保存 D[0] ~D[n] ） 一个过程（处于第 n 层）被调用时，从调用 过程的 Display 表中自下向上抄录 n 个 SP 值，再加上本层的 SP 值 方法二 只在活动记录保存一个的 Display 表项，在静 态存储区或专用寄存器中维护全局 Display 表
数据信息
活动记录起始地址 （通常存于某专用寄存器中）
控制信息
运行时存储组织
活动记录
过程活动记录的栈式分配举例
void p( ) { … q( ); } void q( ) { … q( ); } int main { p( ); }
函数 q 被第二次激活时运 行栈上活动记录分配情况
q 的活动记录
运行时存储组织
栈式存储分配
用于有效实现可动态嵌套的程序结构
• 如实现过程/函数，块层次结构
可以实现递归过程/函数
• 比较：静态分配不宜实现递归过程/函数

t1= b*c t2 = a− t1 x = t2
2020/8/6
13
2．三地址语句的种类
作为中间语言的三地址语句非常类似于汇编代 码，它可以有符号标号和各种控制流语句。
常用的三地址语句有以下几种： (1) x=y op z形式的赋值语句，其中op为二目的
算术运算符或逻辑运算符。 (2) x=op y形式的赋值语句，其中op为一目运
使用中间代码的优点
–与机器无关，便于移植。 –便于进行独立于机器的代码优化。
介绍几种常用的中间表示
–图形表示: 语法树 – 逆波兰表示法: 后缀表示 –三地址代码
用语法制导定义和翻译方案的方法将源程序翻译成中 间形式
2020/8/63 Nhomakorabea4.3.1 抽象语法树
抽象语法树(Abstract syntax tree)：每一 个叶结点都表示诸如常量或变量这样的 运算对象(操作数)，而其它内部结点则表 示运算符(操作符) 。
(X62)、过…程，调X用n)可语用句下pa列r X三和地c址all代P码,n。表源示程：序中的P(X1、 par X1
par X2
par Xn call P,n
其中，整数n为实参个数。
过程返回语句为return y，其中y为过程返回值。
2020/8/6
15
(7) 变址赋值语句x=y[i]，其中x、y、i均代 表数据对象，表示把从地址y开始的第i个 地址单元中的值赋给x。x[i]=y则表示把y的 值赋给从地址x开始的第i个地址单元。
编译原理 Principle of Compiling
郭一晶
厦门大学嘉庚学院 2008 年 9 月
2020/8/6
1
4.3 几种常见的中间语言