当前位置：文档之家 › 编译原理课件-第二章第九章

编译原理课件-第二章第九章

  • 格式：ppt
  • 大小：215.00 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

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

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

2019/3/26
10
9.1.3 过程及其活动
• 出现在过程定义中的某些标识符具有特殊的 意义，称为该过程的形式参数，简称为形参。 调用过程时，表达式作为实在参数(或实参)传 递给被调用的过程，以替换出现在过程体中 的对应形式参数。9.1.4节将讨论实参和形参 的结合方法。 • 过程体的每次执行叫做该过程的一个活动。 过程p的一个活动的生存期是从过程体执行的 第一步到最后一步，包括执行被p调用的过程 的时间，以及再由这样的过程调用其它过程 所花的时间，等等。
• 计算实参并将其右值传递给被调用过程 • 传值方式可以如下实现：
– 被调用过程为每个形参开辟一个称为形式单元的 存储单元，用于存放相应实参的值。 – 调用过程计算实参，并把右值放入相应的形式单 元中。
实际参数A
A 单向传值
形式参数X
A的值 被调用者 直接使用
14
调用者
2019/3/26
2. 传地址
24
每个过程的活动记录内容
TOP 临时变量 数组内情向量 局部变量 形式单元

2 1
SP 0
静态链 动态链 返回地址
形式单元：存放相 应的实在参数的地 址或值。 局部数据区：局部 变量、内情向量、 临时工作单元 ( 如存 放对表达式求值的 结果)。
25
2019/3/26
9.2.3 局部数据的组织
2019/3/26
9
9.1.3 过程及其活动
• 将“过程、函数和方法”统称为“过程” • 过程定义是一个声明，它的最简单形式是把 一个标识符和一个语句联系起来。该标识符 是过程名，而这个语句是过程体。 • 当过程名出现在可执行语句中时，称相应的 过程在该点被调用。过程调用就是执行被调 用过程的过程体。注意，过程调用也可以出 现在表达式中。

编译原理 课件第九章

编译原理 课件第九章

上下文语义的合法性检查的依据
在语义分析中，符号表所登记的内容将用于语义检查（如检查 一个名字的使用和原先的说明是否一致）和产生中间代码。通 过符号表中属性记录可进行相应上下文的语义检查。 例如，在一个C语言程序中出现 … int i [3][5]; //定义整型数组i … float i[4][2]; //定义实型数组i,重定义冲突 … int i [3][5]; //定义整型数组i,重定义冲突 … 编译过程首先在符号表中记录了标识符i的属性是3×5个整型元 素的数组，而后在分析第二、第三这两个定义说明时编译系统 可通过符号表检查出标识符i的二次重定义冲突错误。本例还可 以看到不论在后二句中i的其它属性与前一句是否完全相同，只 要标识符名重定义，就将产生重定义冲突的语义错误。
9.1符号表的作用和地位 符号表的作用和地位 9.2符号的主要属性及作用 符号的主要属性及作用 9.3符号表的组织 符号表的组织
9.1 符号表的作用和地位
收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据
收集符号属性
编译程序扫描说明部分，收集有关标识符的属性，并在符号表 中建立符号的相应属性信息。 例如，编译程序分析到下述两个说明语句 int A; float B[5]; 则在符号表中收集到关于符号A的属性是一个整型变量，关于 符号B的属性是具有5个浮点型元素的一维数组。
9.2 符号的主要属性及作用
符号属性
1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符型的成员信息 （３） 函数及过程的形参
① 符号名 符号表中设置一个符号名域，存放该标识符，该域通 常就是符号表的关键字域。
作为目标代码生成阶段地址分配的依据

编译原理第九章 运行时存储空间组织

编译原理第九章 运行时存储空间组织
• 简单栈区（可以带递归，但不可以嵌套定义） • 复杂栈区（可以嵌套定义, pascal）
– 堆区(new, malloc)
9.5 嵌套过程语言的栈式实现
• Pascal 的过程嵌套 嵌套层次：主程序0层 ······ 采用层数计数器，每逢Proc Begin加1，遇 Proc End则减1。
• 直接外层 • 编译器需要将过程的层数记录到符号表中
2）返回函数结果：累加器、寄存器
··· a:= 3 ··· P(a); Write(a); ···
传地址 8，8 8
举例
Procedure P(x) Begin
x:=x+5; writeln(x,a); End;
传结果 8，3 8
传值 8，3 3
举例
begin
Procedure P(x,y,z) …P(a+b,a,a)
初等类型数据采用确定“字长”，数组按列存放，边界对齐。
这样，可将过程活动单元（局部数据区）直接安排在 过程目标码之后，以便运行时访问。
9.3 Fortran静态存储分配（2）
数据区
返回地址 调用程序返回地址（调用恢复地址）
寄存器保护区 保存调用程序的寄存器运行环境
形式单元 形参
简单变量 数组 临时变量
P －>S －>Q =》R －>R
Program P; var a,x…
Top
R
procedure Q(b)
SP
var i…
R
procedure R(u,v)
动
var c,d…
态
begin… R… end {R} 链
Q
begin … R… end{Q} procedure S

编译原理讲义 9全.ppt

编译原理讲义 9全.ppt

作 ，
全局优化
–在非线性程序段上（含多个基本块）进行的优化
版
权 所
窥孔优化
有
–在目标代码上进行的优化
5
本章主要内容
9.1
9.2
9.3
@ 9.4
李 文 生
制 作 ，
基本块优化 循环优化 窥孔优化 dag的代码优化中的应用 小结 作业
版 权 所 有
6
9.1 基本块优化
基本块的功能：对表达式序列求值，确定该基本 块出口处活动名字的值
(6) t4:=4*i
(7) t5:=b-4
(8) t6:=t5[t4]
(9) t7:=t3*t6
(10) t8:=prod+t7
(11) prod:=t8
(12) t9:=i+1
(13) i:=t9
(14) if i<=20 goto B2
17
一、循环展开
将构成循环体的代码（不包括调节和测试部分） 重复产生多次，而不仅一次。产生的次数可以在 编译时确定。
版
a[t4]:=x
权
所
有
a[t4]:=t1
11
四、删除死代码
如果对一个变量x求值之后却不引用它的值，则称 对x求值的代码为死代码。
如果一个基本块是在某一条件为真时进入执行的，
经数据流分析的结果知该条件恒为假，则此块是
@
死块。
李
文 生
如果一个基本块是在某个条件为假时才进入执行，
制 而该条件却恒为真，则这个块也是死块。
– i和t1是一组归纳变量，在B2块中
有
可以删除i
(1) prod:= 0 B1
(2) i:= 1

廖力编译原理课件第9章

廖力编译原理课件第9章
第九章 代码优化 21
9.1 优化概述
一、中间代码优化分类 3、全局优化简介 • 经过循环优化后，再做局部优化。进行合并已知量、 删除公共子表达式和变量传播等操作。 • 再合并整个程序中的已知量，删除不同块内的公共 子表达式等。
第九章 代码优化 22
(1)j:=1 (2)i:=1 (6)T3:=a-11 (9)T6:=b-11 (4) T1 :=i*10 (7)T4:=i*10 (5)T2:= T1 +j (8)T5:=T4+j (31) R:=10*100 (32) If T1 >R goto (15)
第九章 代码优化 9
9.1 优化概述
一、中间代码优化分类 2、循环优化简介 • 主要方法 – 循环不变运算外提（代码外提） – 降低运算强度 – 变换循环控制变量并删除其自增赋值式
第九章 代码优化 10
• 例如：有如下一段 源程序 • j:=1; • for i=1 to 100 do • A[i,j]:=B[i,j] +2 • 其中数组说明为 – A,B:array[1:100, 1:10] – 假定每个数组元 素占1字编址 • 得其四元式序列
第九章 代码优化 14
(1)j:=1 (2)i:=1 (6)T3:=a-11 (9)T6:=b-11 (4) T1 :=i*10 (7)T4:=i*10 (3) If i>100 goto (15) (5)T2:= T1 +j (8)T5:=T4+j (10)T7:=T6[T5] (11)T8:=T7+2 (12)T3[T2]:=T8 (13)i:=i+1 (4`) T1 := T1 +10 (7`)T4:=T4+10 (14)goto (3)

东北大学秦皇岛分校编译原理课件 第二章第九章

东北大学秦皇岛分校编译原理课件 第二章第九章

说明部分的分析与处理
• 对每个过程说明的对象（变量，常量和过程）造名 字表 –填写标识符的所在层次、属性和分配的相对位置。 标识符的属性不同时，所需填入的信息也不同。 登录信息由ENTER过程完成。
例程序说明部分为： CONST A=35，B=49； Const（常量）无层次 VAR C，D，E； PROCEDURE P； 对应名字表 VAR G ；…
ADR：DX ADR：DX+1 ADR：DX+2 ADR： SIZE：4 ADR：DX ……
名字
类型
层次/值地址存储源自间– 线性查找法 – 二叉树法 – 杂凑技术
符号表的功能
• 收集符号属性
• 上下文语义的合法性检查的依据
• 作为目标代码生成阶段地址分配的依据
符号表的作用和地位-----语义检查的依据 目标代码生成阶段地址分配的依据 在编译程序中符号表用来存放语言程序中出现的 有关标识符的属性信息，符号表中所登记的信 息在编译的不同阶段都要用到。 在语义分析中，符号表所登记的内容将用于语义 检查（如检查一个名字的使用和原先的说明是 否一致）和产生中间代码。 在目标代码生成阶段，当对符号名进行地址分配 时，符号表是地址分配的依据。对一个多遍扫 描的编译程序，不同遍所用的符号表也往往各 有不同。因为每遍所关心的信息各有差异。
第9章 符号表
9.1符号表的作用和地位 9.2符号的主要属性及作用 9.3符号表的组织
• 在编译程序工作的过程中，需要不断收集、记录、查证和使用源 程序中的一些语法符号（简称符号）的类型和特征等相关信息。 • 为方面起见，一般的做法是让编译程序在其工作过程中，建立并 保存一批表格，如常数表、变量名表、数组内情向量表、过程或 子程序表以及符号表等，这些表格统称为符号表或名字表。 • 符号表中每一项包括两个部分，一部分填入名字（标识符）；另 一部分是与次名字有关的信息。这些信息将全面反映各个语法符 号的属性以及它们在编译过程中的特征。 • 几乎在编译程序工作的全过程中，都需要对符号表进行频繁的访 问。访问符号表所耗费的时间在整个编译过程中占有很大的比例。 因此，合理地组织符号表并相应选择好的查、填表方法，是提高 编译程序工作效率的有效方法。 • 通常有三种符号表构造和处理方法：

编译原理课件chap9

第九章运行时存储空间组织
编译程序在完成词法、语法和语义分析后， 编译程序在完成词法、语法和语义分析后，在生成目标代 码之前， 码之前，需要把程序的静态正文和实现这个程序的运行时的 活动联系起来弄清楚将来在代码运行时刻， 活动联系起来弄清楚将来在代码运行时刻，源代码中的各种 变量、常量等用户定义的量是如何存放的，如何去访问它们。 变量、常量等用户定义的量是如何存放的，如何去访问它们。 在程序的执行过程中， 在程序的执行过程中，程序中数据的存取是通过与之对 应的存储单元来进行的。在程序语言中， 应的存储单元来进行的。在程序语言中，程序使用的存储单 元都是由标识符来表示的。它们对应的内存地址都是由编译 元都是由标识符来表示的。 程序在编译时或由其生成的目标程序运行时进行分配。 程序在编译时或由其生成的目标程序运行时进行分配。所以 对于编译程序来说存储组织与管理是一个复杂而又十分重要 的问题。 的问题。这一章就是对目标程序运行时的活动和运行环境进 行讨论，主要讨论存储组织与管理, 行讨论，主要讨论存储组织与管理 包括活动纪录的建立与管 理、存储器的组织与存储分配的策略、非局部名称的访问等 存储器的组织与存储分配的策略、 问题。 问题。
第九章 运行时存储空间组织
9。2。3存储分配策略 。 。 存储分配策略 不同的编译程序关于数据空间的存储分配策略可能 不同。静态分配策略在编译是对所有对象分配固定的 不同。静态分配策略在编译是对所有对象分配固定的 存储单元。且在运行是保持不变。 存储单元。且在运行是保持不变。栈式动态分配策略 在运行时把存储器作为一个栈进行管理，运行时， 在运行时把存储器作为一个栈进行管理，运行时，每 当调用一个过程， 当调用一个过程，它所需要的存储空间就动态的分配 于栈顶，一旦退出，它所占空间就予以释放。堆式动 于栈顶，一旦退出，它所占空间就予以释放。 态存储策略在运行时把存储器组织成堆结构， 态存储策略在运行时把存储器组织成堆结构，以便用 在运行时把存储器组织成堆结构 户关于存储空间的申请与归还（回收），凡申请者分 户关于存储空间的申请与归还（回收），凡申请者分 ）， 给一块，凡释放者退回给堆。 给一块，凡释放者退回给堆。

编译原理第9篇

第36页
编译原理
第37页
编译原理
第38页
编译原理
二、嵌套层次显示表(display)和活动记录
为了提高访问非局部量的速度，还可以引用一个 指针数组，称为嵌套层次显示表。 每进入一个过程后，在建立它的活动记录区的同 时建立一张嵌套层次表display. 假定现进入的过程的层数为i，则它的display表 含有i＋1个单元。 此表本身是一个小找，自顶向下每个单元依次存 放着现行层，直接外层，…，直至最外层（0层， 主程序层）等每一层过程的最新活动记录的基地 址。
第25页
编译原理 进入过程P后所做工作示意
P的数组区
第26页
返回地址
1 0
TOP
SP
P的活动记录 （长度为L)
调用过程
编译原理
(3)过程返回
C语言以及其它一些相似的语言含有return(E)的返 回语句，E为表达式。
假定E值已计算出来并已存放在某临时单元T中，可 将T只传送到某个特定寄存器（调用过程将从这个特 定的寄存器中获得P的结果）。
第14页
编译原理 简单的栈式存贮分配
适用于简单程序语言的实现：语言没有分程序结构， 过程定义不允许嵌套，但允许过程的递归调用，允许 过程含有可变数组。 C语言就是这样一种语言。其局部名称的存储分配， 可以直接采用栈式存储分配策略。
第15页
编译原理
1、栈式存储分配
使用栈式存储分配法意味着把存储组成一个栈。 运行时，每当进入一个过程（一个新的活动开 始）时，就把它的活动记录压入栈，从而形成 过程工作时的数据区，一个过程的活动记录的 体积在编译时是可静态确定的。 当该活动结束（过程退出）时，再把它的活动 记录弹出栈，这样，它在栈顶上的数据区也随 即不复存在。

编译原理编译第九章

整理课件
第二节 回溯分析法
一.一个实例
S→xAy A→ab│a 输入串为xay,说明分析过程
整理课件
S
S
S
x A yx A y x A y
ab
a
整理课件
二. 存在的问题
(1)回溯——公共左因子的存在
A→1| 2 (2)左递归
A→Aα 或 AAα
(3)ε产生式也会引起回溯
S→aAS
+
S→b
A→bAS
整理课件
S→Qc│c
Q→Rb│b
按S、Q、R排列, 代入后
R→Sa│a
S→Qc│c
Q→Rb│b
R→ Rbca│bca│ca│a 消除R中的直接左递归
R→ bcaR’│caR’│aR’
R’→ bcaR’│ 文法产生的语言:(bca|ca|a)(bca)*bc|bc|c
整理课件
按R、Q、S排列, 代入后
FIRST
E
(
i
E’
+
T
(
i
T’
*
F
(
i
整理课件
FOLLOW )# )# +)# +)# *+ ) #
G(E) E→TE’
E’→+TE’│ε
T→FT’
T’→*FT’ │ε
预测分析表
F→(E)│i
i
+
*
(
E E→TE’
E’
E’→+TE’
E→TE’
T T→FT’
T→FT’
T’
T’→ε
T’→*FT’
F F→i
若S * ...A, 则#FOLLOW(A),其中S为开始符号

编译原理精选版演示课件.ppt


预测分析表
3
表驱动的预测分析程序模型
khk
4
实现步骤：
（1） 判断文法是否为LL(1)文法。 如果文法中含有左递归，必须先消除 左递归
（2）构造预测分析表 ： Select(A ) （3）列出预测分析过程
khk
5
第6章：自底向上分析方法
自底向上分析方法，也称移进归约分析法
实现思想（是推导的逆过程）：
对输入符号串自左向右进行扫描，并将输入符逐个 移入一个后进先出栈中，边移入边分析，一旦栈顶 符号串形成某个句型的可归约串时，就用该产生式 的左部非终结符代替相应右部的文法符号串，称为 归约。重复这一过程，直到归约到栈中只剩下文法 的开始符号时，则分析成功。
关键问题
khk
6
移进—规约分析（Shift-reduce parsing)
＋
A a
可得 b <. a
由A→( B 且B＋ ( B… 可得 (<. (
＋
B aa…
可得 (<. a
＋
B Aa )
可得 (<. A
khk
18
A(B(Aa) …)
(3) 求> .关系:
A(B…B
＋
Aa
由S→bAb，且A…) 可得 ) > . b
A＋…B 可得 B > . b
khk
88
例1：文法
SaAcBe A b A Ab B d
输入串abbcde#分析
khk
9
归约分析过程（移进归约）：
步骤 1 2 3 4 5 6 7 8 9 10 1kh1k
符号栈 # #a #ab #aA #aAb #aA #aAc #aAcd #aAcB #aAcBe #S
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
13
嵌套结构型程序设计语言（Pascal）的特点，可采用的办法：
．将其符号表设计为栈符号表，当新的名字出现时总是从栈顶填入。查找操 作从符号表的栈顶往底部查（保证先查最近出现的名字）。因为程序是分 层的，并且一个过程结束时将释放相应的子符号表，因此查找范围与线性 表比相对要小一些。
．引入一个显示（DISPLAY）层次关系表，称为过程的嵌套层次表。其作用 是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函 数）相应的子符号表在栈符号表中的起始位置（相对地址）。DISPLAY 表也是一个栈，栈顶指针为level。当进入一个新过程时，level增加1；每 当退出一个过程时，level减1。DISPLAY(level)总是指向当前正在处理的 最内层的过程的子符号表在栈符号表中的起始位置。
．在符号表的信息栏中引入一个指针域（previous）用以链接它在同一过程 内的前一域名字在表中的下标（相对位置）。每一层的最后一个域名字， 其 previous 之 值 为 0 。 这 样 ， 每 当 需 要 查 找 一 个 新 名 字 时 ， 就 能 通 过 DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈 符号表中的位置。然后，通过previous可以找到同一过程内的所有被说明 的名字。
• 通常有三种符号表构造和处理方法：
– 线性查找法
– 二叉树法
– 杂凑技术
2
符号表的功能
• 收集符号属性 • 上下文语义的合法性检查的依据 • 作为目标代码生成阶段地址分配的依据
3
符号表的作用和地位-----语义检查的依据
目标代码生成阶段地址分配的依据
在编译程序中符号表用来存放语言程序中出现的 有关标识符的属性信息，符号表中所登记的信 息在编译的不同阶段都要用到。
• 对给定名字，查询名字是否已在表中； • 往表中填入一个新的名字； • 对给定名字，访问它的某些信息； • 对给定名字，填写或更新它的某些信息； • 删除一个或一组无用的项。 不同种类的表格所涉及的操作往往也是不同
的。上述五个方面只是一些基本的共同操 作。
6
符号属性(信息）
几种通常都是需要的。 1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符号的其它属性 （１） 数组内情向量 （２） 记录结构型的成员信息 （３） 函
第9章 符号表
9.1符号表的作用和地位 9.2符号的主要属性及作用 9.3符号表的组织
1
• 在编译程序工作的过程中，需要不断收集、记录、查证和使用源 程序中的一些语法符号（简称符号）的类型和特征等相关信息。
• 为方面起见，一般的做法是让编译程序在其工作过程中，建立并 保存一批表格，如常数表、变量名表、数组内情向量表、过程或 子程序表以及符号表等，这些表格统称为符号表或名字表。
在语义分析中，符号表所登记的内容将用于语义 检查（如检查一个名字的使用和原先的说明是 否一致）和产生中间代码。
在目标代码生成阶段，当对符号名进行地址分配 时，符号表是地址分配的依据。对一个多遍扫 描的编译程序，不同遍所用的符号表也往往各 有不同。因为每遍所关心的信息各有差异。
4
5
在整个编译期间，对于符号表的操作大致可 归纳为五类：
数及过程的形参
7
符号表的组织
总体组织和表项属性信息组织 第一种： 把属性种类完全相同的那些符号组
织在一起，构造出表项是分别为等长的多个 符号表 第二种： 把所有语言中的符号都组织在一张 符号表中。组成一张包括了所有属性的庞大 的符号表
第三种折衷方式是根据符号属性相似程度分类 组织成若干张表，每张表中记录的符号都有 比较多的相同属性。
其基本思想是，所有分程序中定义的标识符都集 中在单张符号表中。为了实现分程序构造中标 识符的作用域和可视性规则的要求,在符号表中 可设立一个属性域用来登录符号所在分程序的 层次
进入分程序时，层次要增加一层.在退出一个分 程序时，层次降低一层，且需要把符号表中， 所有在退出的分程序中登录的符号项清除。
11
分表结构的组织管理
其基本思想是，每当编译程序扫描到一个 分程序结构开始时，为该分程序建立一 张符号表，在该分程序中定义的标识符， 都被登录在该符号表中。而当编译程序 扫描到一个分程序的结束时，编译程序 释放为该分程序所建立的符号表。这种 符号表的分表结构与源程序的分程序层 次结构一一对应
12
单表结构的组织管理
8
符号表项的排列
符号表作为一个多元组，表中元组的排列 组织是构造符号表的重要成分。在编译 程序的整个工作过程中，符号表被频繁 地用来建立表项，找查表项，填充和引 用表项的属性。因此表项的排列组织对 该系统运行的效率起着十分重要的作用。 在编译程序中，符号表项的组织传统上 采用三种构造方法。即线性法，二分法 及散列法。
• 符号表中每一项包括两个部分，一部分填入名字（标识符）；另 一部分是与次名字有关的信息。这些信息将全面反映各个语法符 号的属性以及它们在编译过程中的特征。
• 几乎在编译程序工作的全过程中，都需要对符号表进行频繁的访 问。访问符号表所耗费的时间在整个编译过程中占有很大的比例。
因此，合理地组织符号表并相应选择好的查、填表方法，是提高 编译程序工作效率的有效方法。
14
说明部分的分析与处理
• 对每个过程说明的对象（变量，常量和过程）造名 字表 –填写标识符的所在层次、属性和分配的相对位置。 标识符的属性不同时，所需填入的信息也不同。 登录信息由ENTER过程完成。
15
例程序说明部分为：
CONST A=35，B=49；
9
关键字域的组织
符号表的关键字域（段）就是符号名称 等长关键字域（段）符号表
Байду номын сангаас不等长关键字段符号表---采用关键字池的 索引结构。
10
分程序结构的符号表
对于具有分程序型结构的语言程序，不同层次分 程序中定义的标识符号具有不同的作用域和不 同的可视性规则。通常对于具有分程序结构的 语言可用两种方式组织它们的符号表： 一是对 每个分程序建立一个独立的分表结构的符号表； 一是把各分程序符号组织在一张单表结构的符 号表中