第7章 中间代码生成

F.node:= E.node
⑻ F → id
F.node := mkleaf(id, id.entry)
⑼ F → num
F.node := mkleaf(num, num.val)
*
生成dag的语法制导定义
*
7.2 声明语句的翻译
声明语句的作用 为程序中用到的变量或常量名指定类型 类型的作用 类型检查：类型检查的任务是验证程序运行时的行为是否遵守语言的类型的规定，也就是是否符合该语言关于类型的相关规则。 辅助翻译：编译器从名字的类型可以确定该名字在运行时所需要的存储空间。在计算数组引用的地址、加入显式的类型转换、选择正确版本的算术运算符以及其它一些翻译工作时同样需要用到类型信息。 编译的任务 在符号表中记录被说明对象的属性(种别、类型、相对地址、作用域……等) ，为执行做准备
P→MD M→ {offset := 0 }
*
7.2.4 过程内声明语句的翻译
*
enter(x,real,0)
offset=0
offset=8
T.type=real T.width=8
offset=12
T.type=integer T.width=4
enter(i,integer,8)
D→id : T {enter( , T.type, offset ); offset := offset + T.width}
7.2.1 类型表达式
*
*
5．类型构造符record作用于由域名和域类型所形成的表达式也是类型表达式。记录record是一种带有命名域的数据结构，可以用来构成类型表达式。例如，下面是一段Pascal程序段： type row = record address: integer; lexeme: array[1..15] of char end; var table : array [1..10] of row; 该程序段声明了表示下列类型表达式的类型名row： record ((address×integer)×(lexeme×array (1..15, char)))

编译原理和技术
中国科学技术大学 计算机科学与技术学院 陈意云
第七章 中间代码生成
记号 分析 流 器 本章内容
–介绍几种常用的中间表示：后缀表示、图形表示 和三地址代码 –用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间形式
静态 检查 器
中间 代码 中间 代码 生成 代码 生成 器 器
7.1 中 间 语 言
7.1.2 图形表示 • 语法树是一种图形化的中间表示 • 有向无环图也是一种中间表示
assign a + + a assign +
+ c uminus d uminus c c d d b b (b) DAG (a) 语法树 a = (b + cd) + cd的图形表示
7.1 中 间 语 言
7.1.4 静态单赋值形式 • 一种便于某些代码优化的中间表示 • 和三地址代码的主要区别
– 所有赋值指令都是对不同名字的变量的赋值 – 一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x a; 改成 if (flag) x1 = 1; else x2 = 1; x3 = (x1, x2); //由flag的值决定用x1还是x2
E E1 E2 E.nptr = mkNode( ‘’, E1.nptr, E2.nptr) E.nptr = mkUNode( ‘uminus’, E1.nptr) E E1 E (E1) F id E.nptr = E1.nptr E.nptr = mkLeaf (id, id.entry)
符号表实例
7.2 声 明 语 句
• 符号表的特点
–各过程有各自的符号表 –符号表之间有双向链 –构造符号表时需要符号表栈 –构造符号表需要活动记录栈 sort var a:…; x:…; readarray var i:…; exchange quicksort var k, v:…; partition var i, j:…;

• 赋值
• (ASSIG, id1, n, id2) --- 把id1的值赋值给id2(长度为n)
• I/O 操作
• (READI, _ , _ , id)
--- 输入整数到id
• (READF, _ , _ , id)
--- 输入实数到id
• (WRITE, _ , _ , id)
--- 把id的值输出
中间代码生成在编译器中的作用
词法分析 语法分析 语义分析
分析
目标代码生成 中间代码优化
中间代码生成
合成
中间代码生成
• 中间代码生成是将源程序翻译成等价中间表示的过程 • 中间代码生成 不是编译程序的必经阶段
• 生成中间代码的目的有二：
• 增强语言的可移植性 • 进行中间代码级别的优化
• 中间代码生成方法：
－带括号表达式的后缀式生成
• 注意: 任何运算符的优先级都大于 ‘(’;
• (1)初始化: S1和S2为空; (2) 读token: tk=ReadOne();
• (3) Switch tk of
•
(i) #: if (S1为空) exit;
•
else while (S1不为空)
/*产生剩余运算符的后缀表示*/
• 临时变量的层数为－1，偏移为编号，mode ＝ dir或indir
为便于阅读, 课件和书中用对应的变量名, 函 数名或者标号, 值等代替相应的FORM结构
作业
• 请写出下列表达式的后缀式表示.
• (a * (b-d) + d) * a + (c-e)/d • (a+b) *(c+d) – (a+b+c)
• 源程序级别优化取决于用户对算法的取舍 • 编译程序可进行中间代码和目标代码上的优化

(1)s=s0
(2)s=s1 (3)s=ε
课程名称
第七章 语法制导翻译和中间代码生成（22）
输入输出对可由(,)表示，其中是输入句子形式而是输出句子形 式。
(S,S)开始用产生式s0s来扩展得到(0S,S0).
再用一次规则(1)，得到(00S,S00)。 再用规则(2)，就得到(001S,S100). 然后应用规则(3)并得到(001,100)。
L id
T.type=integer T.type:=real
L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)
课程名称
第七章 语法制导翻译和中间代码生成（17）
Real id1,id2,id3
D T.type=real real L.in= real L.in= real ， id3
E T T F F
T T1 * F F (E) digit
设表达式为3＊5+4，则语义动作打印数值19
. L
E.val=19 E.val=15
+
T.val=3 F.val=3 digit.lexval=3 F.val=5
*
F.val=4
digit.lexval=4 digit.lexval=5
课程名称
第七章 语法制导翻译和中间代码生成（23）
课程名称
第七章 语法制导翻译和中间代码生成（3）
属性文法 表达式文法 E—>T+T| T or T T—>n | b ET1 + T2 { T1.type = int T2.type= T1.type E.type :=int} E T1 or T2 { T1.type = bool T2.type= T1.type E.type :=bool} T n { T.type := int} T b { T.type := bool}