当前位置：文档之家 › 编译原理 第八章

编译原理 第八章

  • 格式：ppt
  • 大小：135.50 KB
  • 文档页数：11

下载文档原格式

  / 11

合集下载

编译原理：第八章 符号表

编译原理：第八章 符号表
规定主程序的层次为1主程序中定义的层次为2依次类推名字的类型类型有整型ints字符型chars布尔型bool数组arrays对于无类型的名字填入notype一个布尔量用于标明名字是否为变量形参名当名字是否为变量形参名时填入false其他情况填入true或不填当名字为数组类型或数组变量名时ref指向该数组在数组信息表中的位置
合肥工业大学 计算机与信息学院软件所
表 0.1 符号名表 SNT NAME INFORMATION M 形式参数，整 型，值参数 N 形式参数，整 型，值参数 K 整型，变量
表 0.2 常数表 CT 值 (VALUE) (1) 1 (2) 4
表 0.3 入口名表 ENT NAME INFORMATION (1) INCWAP 二目子程序, 入口四元式:1

ax→
数组下限 数组上限 数组元素的体积 数组本身的体积 当元素为数组时，它指向 数组元素类型 数组的下标类型 该元素数组信息在atab表 中的位置，其他情况为0
合肥工业大学 计算机与信息学院软件所
type a=array[1..10, 1..10] of integer;
name kind typ ref
合肥工业大学 计算机与信息学院软件所
PL 语言编译程序的符号表
1. 表格的定义 名字表(nametab) 程序体表(btab) 层次显示表(display) 数组信息表(atab) 中间代码表(code)
合肥工业大学 计算机与信息学院软件所
1) 名字表(nametab) 名字表nametab：登记程序中出现的各种名 字及其属性
lastpar last psize vsize 0 1

bx→
指向本程序体中最后一个形式参在 本程序体所有局部数据所 指向本程序体中最后一个名字在 本程序体所有形参所需体积、包 nametab 中的位置 需空间大小 nametab 中的位置 括连接数据所占空间

编译原理第8章

编译原理第8章

8.3 动态存储分配
TOP 临时变量 内情向量 局部变量
1. 返回地址 保存该被调过程 返回后的地址。
2. 动态链 指向调用该过程 前的最新活动记录 地址(即前一个活动 记录的地址)。
形式单元 静态链
SP 动态链 返回地址
8.3 动态存储分配
TOP 临时变量 内情向量 局部变量 3. 静态链 指向静态直接外层 最新活动记录地址的 指针，用来访问非局 部数据。
形式单元 静态链
SP 动态链 返回地址
8.3 动态存储分配
TOP 临时变量 内情向量 局部变量
4. 形式单元 存放相应的实在 参数的地址或值。
5. 局部变量 一个子程序(过程) 的局部变量。
形式单元 静态链
SP 动态链 返回地址
8.3 动态存储分配
TOP 临时变量 内情向量 局部变量 6. 临时变量 比如计算表达式过 程中需存放中间结果 用的临时值单元。 连接数据
8.2 静态存储分配
CNSUME 的代码 PRDUCE 的代码 CHARACTER * 50 BUF INTEGER NEXT CHARACTER C CHARACTER * 80 BUFFER INTEGER NEXT
代码
静态数据
该图描 述了程 序中局 部变量 的静态 存储位 置。
8.2 静态存储分配
8.1 概述
程序设计语言关于名字的作用域和 生成期的定义规则决定了分配目标程序 数据空间的基本策略。
在大部分现有编译中目标程序数据 空间的分配策略有：
8.1 概述
静态存储分配策略 分配策略
栈式动态存储分配
动态存储分配策略
堆式动态存储分配
8.1 概述
静态存储分配策略

编译原理,清华大学,第2版_第8章 语法制导翻译和中间代码生成

编译原理,清华大学,第2版_第8章 语法制导翻译和中间代码生成

将if-then-else看作一个完整的操作符，则e、x和 y 分别是三个操作数，这显然是一个三元运算。根据后缀式 的特点，它的后缀式可以写为：
exy if-then-else(记为: exy￥) 但是，这样的表示有个弱点。按照算法的计算次序，e、 x和y均需计算，而实际上，根据条件e的取值，计算x则不 计算y，计算y则不计算x。
一、逆波兰表示 典型特征是操作数在前，操作符紧跟其后。 特点:由于操作符紧跟操作数之后，因此只要知道操作 符有几个操作数，每一步的运算就可以确定。
1、 表达式的表示：
例：a+b 例：-a+b*c 例： (a+b)*c ab+ a@bc*+ ab+c* <左部><表达式的逆波兰式> ::=
2、 赋值语句的逆波兰表示：
E → E1 + E2
E → E1 * E2 E → (E1) E → num
E.val := E1.val + E2.val;
val[top] := val[top]+val[top+2];
E.val := E1.val * E2.val; E.val := E1.val; E.val := num.lexval;
第八章 语法制导翻译和中间代码生成
• 教学要求：本章介绍编译程序的第三个阶段语 义分析及中间代码生成的设计原理和实现方法，
要求理解语法制导翻译、语义动作的基本概念；
掌握语义规则和中间代码的表示形式。 • 教学重点：语义规则，中间代码的表示形式， 自下而上分析制导翻译概述。
语义处理功能： • 1、静态语义审查：验证语法结构合理 的程序是否真正有意义。 • 2、解释执行动态语义、生成代码：执 行真正的翻译（生成中间代码或目标代 码）。

编译原理蒋宗礼课件第8章

编译原理蒋宗礼课件第8章

22
8.4.2 程序块结构符号表的其他实现
对图8.10 中的程序
...
a0 ... b0 ...
NULL NULL
(a) 处理到语句(5)时的符号表
... a0 ... b1 ... b0 NULL NULL
(b) 处理到语句(7)时的符号表
23
8.4.2 程序块结构符号表的其他实现
对图8.10中的程序
名字 符号种类 符号表表项1 符号表表项2 符号表表项3 abc i myarray ... 变量 变量 数组 int int int ... 基本属性 类型 地址 扩展属性指针 0 4 8 NULL NULL 维数 2 各维维长 3 4 扩展属性
图8.3 多种符号共用符号表的一种实现结构
11
8.1.2 符号表中的属性
19
8.4.2 程序块结构符号表的其他实现
• 将所有块的符号表放在一个大数组中，然后再引入 一个程序块表来描述各程序块的符号表在大数组中 的位置及其相互关系
名字 外层块 符号个数 起始指针 0 1 2 3 -1 0 1 1 2 1 1 1 程序块表 1 2 3 4 5 a b b b a 符号表 属性
– 如栈式存储分配时，i的地址是以栈指针sp为基址 加上i相对于活动记录起始地址的偏移量offseti
• 符号表中各符号的地址属性就是该符号相对于 第一个符号的偏移地址
13
8.3 符号表的组织结构 8.3.1 符号表的线性表实现
• 用线性表实现符号表较为直观
– 数组实现：插入n个符号、执行e次查找操作的时 间复杂度为T(n, e) = O(n(n+e)) – 有序数组实现：插入n个符号、执行e次查找操作 的时间复杂度为T(n, e) = elog n+ (log i) + i ≤ (n+e)log n+O(n2)

编译原理第8章

编译原理第8章

2
在程序的执行过程中，程序中数据的存取是通过对 应的存贮单元进行的。
在早期的计算机上，这个存贮管理工作是由程 序员自己来完成的。在程序执行以前，首先要将用机 器语言或汇编语言编写的程序输送到内存的某个指定 区域中，并预先给变量和数据分配相应的内存地址。
在有了高级语言之后，程序员不必直接和内存 地址打交道，程序中使用的存贮单元都由逻辑变量(标 识符)来表示，他们对应的内存地址都是由编译程序在 编译时或由其生成的目标程序运行时进行分配。程序 执行时，源程序中同样的名字可以指示目标机器中不 同的数据对象，本章即考察名字与数据对象的对应关 系。所以，对编译程序来说，存贮的组织及管理是一 个复杂而又十分重要的问题。 编译程序根据如何组织运行环境而生成目标代码。
• 简单变量： （以字节为单位）
– char:1，可以分配在任何地址。 – integer，short:2，对齐到2（即从能被2或4整除的
地址开始分配） – long : 4，对齐到4 – float: 4至16，对齐到相应字节数 – double(双精度型):8,对齐到8 – booleans: 1位，但常设为1个字节 • 指针：unsigned integers • 一维数组：一块连续的存储区 • 多维数组：一块连续的存储区，按行存放 • 结构(记录)：把所有域（field)存放在一块存储区 • 对象：类的实例变量象结构的域一样存放在一块连续 的存储区，但方法（成员函数）不存在该对象里
即使在一个程序中每一个名字只被说明一次，同一个名 字在运行时刻仍可能代表不同的数据目标。 一个名字的说明是静态的概念，名字的联编是名字的说 明的动态副本。
7
•引进两个函数,environment(环境) state (状态) – environment把名字映射到一个存储单元上（Lvalue左-值)。 – state把存储单元映射到那里所存放的值上，即把 一个L-value(左-值)映射为一个 R-value(右-值)。如 下图所示。

编译原理编译第八章

编译原理编译第八章

一. 状态转换图的定义
有限的有向图 有向边上标记字符
x
2
唯一初态
1
若干终态（至少一个）
y
3
精选ppt
二. 状态转换图识别的串
从初态出发到某一终态路径上字符的连 接。下图是识别标识符的状态转换图：
字母或数字
字母
0
1 其它字符
* 2
精选ppt
第四节 词法分析器的设计
一. 单词符号
第四章设计的语言允许下述单词： 标识符、数字串、begin、end、integer、if、 then、else、function、read、write、
精选ppt
(9)buildlist:将token中的标识符存入符号表，并 将其在符号表中的位置填入val (10)dtb:将token中的数字串转换成二进制，并 存入常数表，位置填入val (11)val:存放标识符在符号表中的位置，或常数 在常数表中的位置 (12)return(c,val)：返回二元式 (13)error：出错处理
<=
<>
类别编码
9 10 11 12 13 14
15
16
精选ppt
助记符
$FUNCTION $READ $WRITE $SUB $MUL $LT
$LE
$NE
单词符号
= > >= := ； （
）
类别编码
17 18 19 20 21 22 23
精选ppt
助记符
$EQ $GT $GE $ASSIGN $SEM $LPAR $RPAR
‘ : ‘: begin getchar; if character = ‘ = ‘ then return($ASSIGN,—) else error

编译原理第八章


2013年8月21日2时45分
(3) 在符号表的信息栏中引入一个指针域（previous）用以 链接它在同一过程内的前一域名字在表中的下标（相对位 置）。每一层的最后一个域名字，其previous之值为0。这 样，每当需要查找一个新名字时，就能通过DISPLAY找出 当前正在处理的最内层的过程及所有外层的子符号表在栈 符号表中的位置。然后，通过previous可以找到同一过程 内的所有被说明的名字。
2013年8月21日2时45分
8.4 符号表的内容
符号表的信息栏中登记了每个名字的有关的性质，如类型、 种属、大小以及相对数。 对于变量名、数组名和过程名，信息栏中一般有下列信息： (1)变量 类型(整数、实、双实、布尔、字符、复、标号 或指针)； 种属(简单变量、数组或记录结构)； 长度(所需的存储单元数)； 相对数(存储单元数)； 若为数组，则记录其内情况向量。
2013年8月21日2时45分
杂凑技术
对于表格处理来说，根本问题在于如何保证查表与填表两 方面的工作都能高效地进行。对于线性表来说，填表快， 查表慢。而对于对折法而言，则填表慢，查表快。杂凑法 正是一种争取查表、填表两方面都能高速进行的统一技术。 这种办法是：假定有一个足够大的区域，这个区域以填写 一张含N项的符号表。构造一个地址函数H。对于地址函 数H有两点要求：第一，函数的计算要简单、高效；第二， 函数值能比较均匀地分布。对于杂凑技术还应设法解决 “地址冲突”的问题。
2013年8月21日2时45分
8.2 整理与查找
符号表作为一个多元组，表中元组的排列组织是构造符号 表的重要成分。在编译程序的整个工作过程中，符号表被 频繁地用来建立表项，找查表项，填充和引用表项的属性 。因此表项的排列组织对该系统运行的效率起着十分重要 的作用。在编译程序中，符号表项的组织传统上采用三种 构造方法。即线性法，二分法及散列法。

编译原理 第18讲(第八章)


布尔表达式的翻译举例
例：a or b and not c 翻译成四元 b and t1 (3) t3:= a or t2
例：a < b 翻译成四元式序列， 可看成等价的条件语句 if a < b then 1 else 0 (1) if a<b goto (4) (2) t:=0 (3) goto(5) (4) t:=1 (5) ……
布尔表达式gotoetruegotoefalsegotoetruegotoefalse翻译不是最优2四元式不需要我们把该表达式放在条件语句中考虑可翻译成如下的四元式序列gotop1p1是整个布尔表达式的假出口gotop1s1elses2拉链与回填技术转移地址并不能在产生这些四元式的同时得知
第八章 语义分析
例：布尔表达式 a<b or c<d and e>f
可翻译成如下四元式： 可翻译成如下四元式： （1） if a<b goto E.true ） （2） goto （3） ） ） （3） if c<d goto （5） ） ） （4） goto E.false ） （5） if e>f goto E.true ） （6） goto E.false ） （翻译不是最优，（ ）四元式不需要） 翻译不是最优，（2）四元式不需要） ，（
//在符号表中查找指定名字的标识符，如果存在则返 在符号表中查找指定名字的标识符， 在符号表中查找指定名字的标识符 回该项指针，否则返回nil 回该项指针，否则返回
过程： 过程： emit(t := arg1 op arg2);
//生成一个四元式（文本） 生成一个四元式（文本） 生成一个四元式
newtemp;
8.1 语义处理概述 8.2 属性文法和语法制导翻译 8.3 中间代码的形式 8.4 中间代码的生成 典型语句的翻译 中间代码的生成(典型语句的翻译 典型语句的翻译) 8.5 符号表

编译原理第17讲(第八章)


01
02
数据结构优化
选择合适的数据结构来存储和操作数 据，以减少内存占用和提高数据访问 速度。
03
循环优化
通过对循环进行展开、合并、重排等 操作，减少循环次数和提高循环效率 。
05
04
函数优化
通过对函数进行内联、外联、合并等 操作，减少函数调用开销和提高函数 执行效率。
程序性能提升的策略
优化内存管理
全局优化
针对整个程序的优化，包括函数 内联、循环展开、公共子表达式 消除等。
机器相关优化
针对特定机器指令集和硬件特性 进行的优化，如指令调度、寄存 器分配等。
常用的优化技术
无用代码删除
删除程序中不会被执行到的代 码，以及不会对程序结果产生 影响的代码。
循环展开
将循环体中的代码复制多次， 从而减少循环次数和循环控制 的开销，提高程序执行效率。
语法分析
编译器首先对源程序进行语法分析，生成 语法树（Syntax Tree）。
目标代码生成
编译器将优化后的中间代码转换成目标代 码，生成与特定计算机体系结构相关的机 器指令序列。
语义分析
编译器对语法树进行语义分析，检查源程 序的语义正确性，并进行类型检查、符号 表管理等。
优化
编译器对中间代码进行优化，提高目标代 码的执行效率。
01
目标代码（Object Code）是指编译器将源程序翻译成机器语 言后生成的代码，它是计算机能够直接执行的指令序列。
02
目标代码通常与特定的计算机体系结构相关，不同的计算机体
系结构需要不同的目标代码。
目标代码通常以二进制格式存储，可以被链接器（Linker）链
03
接成可执行文件。

编译原理 第八章

义子程序。
例 算术表达式求值的语义描述
（0）L→E
print（E.val)
（1）E→ E1 + T E.val:=E1.val+T.val
（2）E→ T
E.val:=T.val
（3）T→ T1 * F T.val:=T1.val*F.val
（4）T→ F
T.val:=F.val
（5）F→（E） F.val:=E.val
2
r
r44rr44
S4
8 23
r
r
6
6
r
r
6
6
S4
93
S
10
4
S
S
6
11
r1
S7
r1
r1
r
r
3
3
r
r
3
3
r
r
5
5
r
r
5
5
LR分析输入串2+3*5
步骤 状态栈 语义栈（值栈） 符号栈
1
0
-
#
剩余输入串 归约动作
2+3*5#
2
05
--
#2
+3*5#
3
03
-2
#F
+3*5#
r6
4
02
-2
#T
+3*5#
r4
E { T1．t =T2．t}
{ T1．= int} T + T { T2．= int}
3
4
A为属性文法
如果对G中的某一输入串而言，A中的所有断言 对该输入串的语法树的结点的属性全为真，则该串 也是A语言中的句子。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

② for(i=6,j=0; j<i; ++j) fun(i); 在六次循环中，i的值保持为6，则可优化为： for(i=6,j=0;j<6; ++j) fun(6);
3. 综合使用常数传播和常数合并进行优化处理 为了对保持定值的所有变量之值进行跟踪，建立一个局部符号表，使 每一个活动的变量在该表中有一个登记项，每当对这些变量进行再定 值时，就相应的修改其登记项中的内容。 例： t1=1; t1+=5; 优化为： t1=6; t2=t1; t2=6;
一. 强度削弱
用一种（或一串）执行时间较短的操作去等价的代替一个操作。 1. x*2n 替换为 x<<n （乘法用左移运算替换） x/2n 替换为 x>>n x%2n 替换为 x&(2n-1) 2. 乘以一个较小的整数可以用多个加法代替 x*=3 替换为 x1=x; x+= x1; x+= x1; 3. 较大整数的乘法可以联合使用位移和加法进行强度削弱优化 x*=9 替换为 x1=x; x*=27 替换为 x1=x; x1<<=3; x1<<=1; x+= x1; x+= x1; x1<<=2; x+= x1; x1<<=1; 4. 对于非算术运算进行强度削弱的情形 x+= x1; 例如：许多机器有多种形式的转移指令， 优化程序可以从其中选择效率更高的指令。
三. 无用变量与无用代码的删除
1. 无用变量：变量的最后一次引用到对该变量再置初值期间，可视为无用 变量。在变量的无用期间，对该变量的所有定值(如赋值)指令均可删去。 例： t=a; t+=5; x=t; …… /*此后的一个时间间隔内，t成为无用变量*/ t=c; /*在t的无用期内，对t的定值可以删除*/ …… t=b; /*t被再次置初值，无用期结束*/ y=t+a;
i=5; ++i; return i+1;
编译器产生 的中间代码
删除无 用变量
i=5； i=6; ret_reg=7; ret;
删除无 用赋值
i=6; ret_reg=7; ret;
§8.3 基于结构信息的优化
8.3.1 基本块及其优化


基本块：具有唯一入口和唯一出口的中间代码序列，入口和出口分别是 块中第一个和最后一个操作，块中各操作顺序执行，不出现任何分叉。 划分基本块的算法：（算法8.1将一个四元式序列划分为基本块） 基本块的DAG表示 利用DAG进行基本块上的优化处理
§8.1 语法制导翻译阶段的优化
遇有函数调用语句，特别是一些常用的代码较短的函数（如内部数学函 数），可以采用直接插入函数代码的方式，从而避免在代码调用过程中 所需的现场保护等附加动作，以提高效率。 语法制导翻译阶段的优化只能局限于单个产生式，难以结合前后文环境一段相邻的中间代码（或目标代码）指令，将其中 的某些组合替换为效率更高的指令组。 线性窥孔优化的特点： ① 对优化对象进行线性扫描 ② 每次处理得是一组相邻指令（暴露在一个观察窗口内的指令） ③ 优化对象即可以是中间代码，也可以是最终的目标代码
四. 消除公共子表达式
T1=A*B; T2=B/C; T3=T1-T2; T4=A*B; T5=T4+D; …… 优化为 T1=A*B; T2=B/C; T3=T1-T2; T5=T1+D; ……
五. 窥孔优化实例
窥孔优化的特点是每个改进都可能引发新的改进机会，为了得到最好的 改进结果，一般可能需要对待优化的代码重复扫描进行窥孔优化。 i=5； i+=1; 计算表达式之值 T1=i; 及常数传播优化 T1=i; T1+=1; ret_reg=T1; ret; i=5； i=6; T1=6; T1=6; T1=7; ret_reg=7; ret;
8.3.2 数据流分析方法 8.3.3 循环优化
二. 常数合并和常数传播
1. 常数合并：在编译阶段就将源程序中常数表达式之值算出，而不必生成 用于计算该常数表达式的代码。 例如：① a+2*3翻译成a+6（在语法制导翻译时可以完成） ② a+2+3由于产生式归约顺序方面的原因，在语法分析时不可 能进行常数合并，而产生如下代码： T1=a; T1+=2; 替换为 T1=a; T1+=3; T1+=5; ③ 删除形如a+=0; a*=1;等操作。
第八章 代码优化
代码优化是编译程序为了产生高质量的目标代码而对源程序的中间代码进 行等价变换，或制定某种策略以使所产生的目标代码能合理地利用目标计 算机的资源的工作。 （减少目标程序占用的空间，并尽可能的提高运行速度，从而提高效率。） 按范围可分为： ①局部优化：指优化工作在程序的一个局部范围内进行。 （例如：线性窥孔优化；基本块的优化） ②全局优化：全局范围内控制流程和数据流程的分析 按阶段可分为： ①语法制导翻译阶段的优化 ②中间代码优化：中间代码序列一些代码的挪动或删除 ③目标代码优化：寄存器的分配，机器指令的使用和选择 另外，优化又可分时间优化和空间优化等 合算原则：以较低的代价取得较好的优化效果， 为值得优化的程序进行优化。
2. 无用代码：是控制无法达到或不进行任何有用操作的代码。 例： 对于 if(0) fun(); 编译器将其翻译成如下的中间代码指令序列： (jz, 0, 0, label) 测试条件总是真 (call_sub,0,0,_fun) 无用代码(删除) (:=,ret_reg,0,T1 ) 无用赋值(删除) (将fun的返回值存储到临时单元T1中) label: ……
无用代码的删除可能会受到常数传播的影响 常数传播到达数组元素，修改为j=a[6]; 这样 i 就变 fun( ) { int i, j, a[10]; 为无用变量，删除无用变量和无用赋值后，程序变为： fun() i=5; { int j,a[10]; ++i; j=a[6]; j=a[i]; …… …… } } 注：一般由用户定义的变量不予删除 3. 在涉及到硬件接口时，上述几种优化方法可能会产生不可预料的错误。 ANSI C中用关键字volatile来屏蔽编译程序对此类变量进行上述优化处理。 char *port; /* volatile char *port; */ port=(char *) 0x10; /* 将物理地址0x10处的8位内存单元映射为某个I/O端口 */ *port=0; /* 用*port访问该端口 */ *port=1; /* 在输出端口产生高电平 */ delay( ); *port=0;
2. 常数传播：若在程序运行时，一些变量的值在某一段程序范围内保持不 变，则对该变量的引用可以替换为对其值的直接引用。 这种常数传播可以一直延续到该变量被重新定值为止。 例： ① a=3; a=3; …… /*未对a重新定值*/ 替换为 …… b=a; b=3;
因为在多数机器上，用常数对变量赋值比内存单元间的复制有更高的效率。