当前位置：文档之家 › [编译原理][课件][第08章][符号表]

[编译原理][课件][第08章][符号表]

  • 格式：ppt
  • 大小：125.00 KB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

编译原理chapter8符号表(2016)分析

编译原理chapter8符号表(2016)分析

...
...
...
n1
available
SYM1
...
n2 SYM2
available
...
n3 SYM3
...
NULL
...
...
n1
...
...
...
n...2
编译原理
8.3 名字的作用范围
chapter8 符号表
最近嵌套作用域规则：即对每个过程指定一个唯一的 编号，以便跟踪过程里的局部名字。
（1）对给定名字，查询此名是否已在表中； （2）往表中填入一个新名字； （3）对给定名字，访问它的相关信息； （4）对给定名字，往表中填写或更新它的某些信息; （5）从表中删除一个或一组名字。
编译原理
chapter8 符号表
符号表的组织方式NAME
INFORMATION
1、各项各栏所占•存储单元的长度固定 2、间接方式安排•名字栏
（2）若要查找的项小于中项，则继续在1〜[n/2]的各项 中去查找。
（3）若要查找的项大于中项，则就到[n/2]+2〜n的各项 中去查找。
平均查找次数 1+log2n
编译原理
chapter8 符号表
二叉树的形成过程如下：
令第一个碰到的名字作为“根”结点，它的左、右 指示器均置为空，当要加入新结点时，首先把它和根 结点的值作比较，小者放在右枝上，大者放在左枝上。 如果根结点的左（右） 枝已成子树，则让新结点和子 树的根再作比较。重复上述步 骤，直至把新结点插入 使它成为二叉树的一个端末结点（叶）为止。
让链头指向最新项，含有这种链条的线性表叫做自适应线性表。
编译原理
二、对折查找与二叉树
chapter8 符号表

第八章 符号表 编译原理-国防科技大学课件

第八章 符号表 编译原理-国防科技大学课件

(4) +
M
1
(5) +
N
4
(6) :=
K
(7) return
RESULT
M N K M N
2020/11/11
8.2 整理和查找
1. 线性查找 • 按关键字出现的顺序填写各项。 • 填表快，查找慢。 • 结构简单，节省空间，效率低，查找时间
复杂度：O(n)。
• 改进：自适应线性表
2020/11/11
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K; END.
表 0.3 入口名表 ENT
NAME INFORMATION
(1) INCWAP 二目子程序,
入口四元式:1
2020/11/11
PROCEDURE INCWAP(M，N:INTEGER);
LABEL START;
VAR
K:INTEGER;
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
表 0.2 常 数 表 CT
END.
值
(VALUE)
(1) 1
(2) 4
2020/11/11
PROCEDURE INCWAP(M，N:INTEGER);
LABEL START;
VAR
K:INTEGER;
K 整型，变量
表 0.2 常 数 表 CT 值
(VALUE) (1) 1 (2) 4
表 0.3 入口名表 ENT NAME INFORMATION
(1) INCWAP 二目子程序, 入口四元式:1

编译原理蒋宗礼课件第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)

《编译原理》课件

《编译原理》课件
代码生成
编译器可以将高级语言编写的源代码转换成机器语言或低级语言，以便在特定的硬件平台上运行。编 译器还可以生成可执行文件或动态链接库等二进制文件。
编译器在人工智能领域的应用
机器学习编译器
机器学习编译器可以将机器学习模型转换成可执行代码，以便在嵌入式设备或边缘计算 设备上运行。这种编译器可以优化模型的计算性能和内存占用，提高模型的运行效率。
3
缺点
对于某些复杂文法，可能导致大量的无用推导和 状态爆炸。
自底向上的语法分析
分析步骤
从输入符号序列的最后一个符号开始，逐步向上构建语法树，直 到找到与文法中的某个产生式右部匹配的符号串。
优点
可以充分利用已知信息，避免不必要的推导和状态爆炸。
缺点
对于某些复杂文法，可能导致大量的无用归约和状态爆炸。
04
中间代码生成
中间代码生成的定义和任务
定义
中间代码生成是编译器的一个阶段，将源代码转换成中间代码的过程。
任务
将源代码转换成一种中间表示形式，以便进行后续的优化和目标代码生成。
三地址代码的生成
01
三地址代码是一种中间代码形 式，由一系列的三元式组成。
02
三元式的形式为(op, arg1, arg2)，表示执行一个操作(op) 并产生一个结果，操作数arg1 和arg2来自寄存器、常数或之 前的计算结果。
语义分析
检查AST是否有语义错误，如类型错 误、未定义的变量等。
中间代码生成
将AST转换为中间代码，通常是三地 址代码。
代码优化
对中间代码进行优化，提高执行效 率。
代码生成
将中间代码转换为机器语言代码， 能够在特定硬件上执行。
编译器的分类

编译原理第8章

编译原理第8章
第八章 符号表
6、翻译模式
P:说明语句,D:类型说明语句,id:标识符(变量名),T:类型 T T T T integer {T.type:=integer;T.width:=4} 变量名及 real {T.type:=real;T.width:=8} 其性质填 T1 {T.type:=pointer(T1.type);T.width:=4} 入符号表 array[num] of T1 {T.type:=array(num.val,T1.type); offset T.width:=num.val*T1.width} D id:T {Enter(,T.type,offset); offset:=offset+T.width} offset D D;D P D {offset:=0} 内存用户区 语义子程序(语义动作) 产生式
* a * b * @b * @ b * @
c c c c b d a+a*(b-c)+(b-c)*d的DAG a:=b*-c+b*-c的语法树 a:=b*-c+b*-c的DAG
第八章 符号表
3、与后缀式的关系：表达式的抽象语法树形式的中间代码与后 缀式等价，后缀式是抽象语法树的线性表现形式，是树的结点 序列(每个结点都在其所有子结点之后立即出现 )。
第八章 符号表
符号表的作用和地位 符号的主要属性及作用 符号表的组织
第八章 符号表
一、符号表的作用和地位
一、本章主要内容： 静态语义检查和翻译中间代码； 二、静态语义检查的内容： 类型检查、控制流检查、一致性检查、相关名字检查、 名字的作用域分析等； 三、翻译产生中间代码的优点： 便于进行与机器无关的代码优化工作、使编译程序改变目标 机更容易、使编译程序的结构在逻辑上更为简单明确； 四、静态语义检查和中间代码产生在编译程序中的地位：

第08章 符号表

第08章 符号表

7
概括地说，符号表的每一项 (或称入口) 包含 两大栏(或称区段、字域)，即名字栏 信息栏 名字栏和信息栏 名字栏 信息栏。 表格的形式如下：
信息栏 (INFORMATION)
名字栏(NAME) 第1项(入口1) 第2项(入口2)
…
第(入口n)
8
信息栏包含许多子栏和标志位，记录相应 名字的种种不同属性。由于查填符号表一般是 通过匹配名字来实现的，故名字栏也称主栏 主栏， 主栏 其内容称为关键字 关键字(keyword) 。 关键字 符号表中每一项都是关于名字的说明。因 为所保存的关于名字的信息取决于名字的用途， 所以各表项的格式不一定统一，为使表中的每 个记录格式统一，可采用指针技术，在记录中 设置指针，把某些信息放在表的外边，用指针 指向存放另外信息的空间。
22
INCWAP(M， PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; 表 0.2 常数表 CT END. 值 (VALUE) (1) 1 (2) 4
23
INCWAP(M， PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; 表 0.3 入口名表 ENT END.
表 0.4 标号表 LT NAME INFORMATION (1)START 四元式:(4)
26
INCWAP(M， PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; 表 0.5 四元式表 QT BEGIN START: OPR OPN1 OPN2 RESULT K:=M+1; (1) link M:=N+4; N:=K; (2) par INCWAP 1 M END. (3) par INCWAP 2 N (4) + M 1 K (5) + N 4 M (6) := K N (7) return

《编译原理符号表》PPT课件


精选课件ppt
26
符号表的总体组织
属性3栏与属性4栏冗余，可将其合并；
增加了符号表管理和运行的复杂性，但减少了空间开销；
精选课件ppt
27
符号表的总体组织
总结：
为便于符号表的组织管理，每张符号表的表长通常为定 长是合理的；
每张符号表可以看作是一个多元组，每个元组由若干属 性组成，元组之间有相同的成员个数和一致的排列；
下推链域的组织
精选课件ppt
40
等长属性值域组织
可以取相应的数据类型表达属性值
符号布尔性质的属性域
defined 1(true) 表示已定义
defined 0(false) 表示未定义
表示符号的基本数据类型
Data-type 3个bit位（整型值）
Char
0 0 0 (0)
short
散列组织
对符号进行某种函数操作（杂凑函数）所得的函数值确 定它在符号表的位置；
Vhash = fhash（符号代码值）
改进：Lhash = mod（Vhash，N） ……….. …a…… ……..b.. …..a….. ……..d.. …c……. ……b….
精选课件ppt
33
符号表项的排列
▪ 函数外表示文件可视性，函数内表示所在函数可视；
动态存储区：生命周期是定义该变量的局部范围；
精选课件ppt
15
标识符符号的属性(信息）
具体位置：
按该变量在存储区类分别依出现先后的次序排列下 相对该存储区表头的相对位移量来表示的；
… Int a; …. float b; … Struct cc{
元组之间的区分由表项中“符号”一栏区分；
精选课件ppt

编译原理第八章 符号表

• 需要做作用域分析！
8.3 名字的作用范围（Fortran）
• Fortran 局部、全局
• 执行时过程（函数）不
Name
Information
嵌套，局部区域只有一
···
局
个现行段；
···
部 • 编译时，尽管查填符号
表过程只限于局部，但
考虑到地址分配的全局
性，需将每个程序段符
号表保存在外存中，采
• 定长方式 • 间接方式 （1）名字的间接存储 （2）信息的间接存储
Name ● ●
Information
如何组织
方式
6 S A MP L E 3 S U M
Name
Information ● ●
数组信息表 维数 首地址 维1
内情向量表
··· ···
以数组为例 维n
如何组织
• 对于名称：把所有标识符都存放在一个 独立的字符串数组，主栏只放一个指示 器和一个整数（名字的长度）
var f, g: real; procedure B3(y:real) const b=5; procedure B4 … end B4 end B3
end B2 end B1
8.3 名字的作用范围 （Pascal）
top
（14）…
B4 （13）…
0
h （12）… 13
sp b （11）…
12
y （10）…
最近使用优先查找 （链头）
较难
中 排序整理 折半查找
二叉树
较难
中 构造排序树，查找时 依子树次序逼近。
杂凑(哈希
难
表）
高 杂凑函数： 名称于位置的映射 基于计算的查找。
数据结构的知识

编译原理08符号表

线性符号表 项 数 1 2 3 4 AVAILABLE→ NAME BC I J1 XYZ INFORMATION … … … …
对这种顺序化的表格可采用对折法查找
15
对一遍扫描的编译程序来说，对折法用处不大。 对一遍扫描的编译程序来说，对折法用处不大。因 符号表是边填边引用的， 为，符号表是边填边引用的，每填进一个新项都得 顺序化符号表， 顺序化符号表，极费时间 可采用二叉树来组织符号表，令每项为一结点， 可采用二叉树来组织符号表，令每项为一结点，每 个结点附设两个指示器栏，一栏为LEFT，另一栏 个结点附设两个指示器栏，一栏为 ， 为RIGHT，主栏内码值作为该结点的值 ， 任何结点p右枝的所有结点值均小于 的值， 右枝的所有结点值均小于p的值 任何结点 右枝的所有结点值均小于 的值，而左枝 的任何结点值均大于p的值 的任何结点值均大于 的值
14
NAME J1 XYZ I BC
INFORMATION … … … …
3.2 对折查找与二叉树
为提高查表速度，在造表同时把表格中的项按名字的“大小” 为提高查表速度，在造表同时把表格中的项按名字的“大小” 顺序整理排列 名字的“大小”指名字的内码二进制，如规定值小者在前， 名字的“大小”指名字的内码二进制，如规定值小者在前， 值大者在后
11
四元式表QT 四元式表 OPR （1） ） LINK INCWAP INCWAP M N K INCWAP INCWAP 1 2 1 2 1 4 M N K M N M N （2） actpar ） （3） actpar ） （4） ） （5） ） （6） ） + + := AGR1 AGR2 RESULT //保护返回地址及有关寄存器 保护返回地址及有关寄存器 //把第一个实参值传给 把第一个实参值传给M 把第一个实参值传给 //把第二个实参值传给 把第二个实参值传给N 把第二个实参值传给 //K:=M+1 //M:=N+4 //N:=K //把M的值回送给第一个实参 把 的值回送给第一个实参 //把N的值回送给第二个实参 把 的值回送给第二个实参 //恢复寄存器，控制返回调用段 恢复寄存器， 恢复寄存器

编译原理 第八章——符号表


Program B1(input,output); const a=10; var b,c:integer;
NAM E
TOP→7
INFOR PREVIOU MATION S …… …… …… …… …… …… …… …… 7 0 5 4 3 2
e:real; Program B2(); var f:int; ……
…… f B2 e c b a
6 5 4 3 2 1 SP→
6 1
DISPLAY
线性查找、二叉树和杂凑技术
1.线性表 每一项按先来者先填。查找时从表的第一项开始 顺序查找。 要填进新名字时，先查找表格，已在表中则不填， 报重名错；若不在表中，填进AVAILABLE所在位 置，AVAILABLE指向下一空白项。 一张含n项的线性表，查找其中某项，平均做n/2 次比较。 自适应线性表，添加指示器，将所有项按“最新 最近”访问原则连成一条链。
符号表的组织与作用
一张符号表的每一项（入口）包含两大栏（区域、字段）： 名字栏和信息栏。 名字栏称主栏，主栏的内容称为关键字，一般不允许重名。
名字栏 （NAME）
第1项（入口1） 第2项（入口2）
信息栏 （INFORMATION）
……
第n项（入口n）
符号表的组织方式
1.各项各栏所占存储单元 的长度都是固定的，每栏 的内容可直接填写在有关 区段。
3.杂凑技术 构造地址函数H。对任何名字SYM， H(SYM)取值0～N-1之间，从H(SYM)获得 SYM在表中的位置。 如：可取N为质数， H(SYM)定义为SYM/N 的余数。 如何解决“地址冲突”? 可使用一张杂凑（链）表将所有相同杂凑 值的符号名连成一串过程相联系。 <名字，过程编号> FORTRAN的符号表组织 将局部名登记在表格区的一端，全局名登记在表格区的另 一端。 Pascal的符号表组织 ——将其符号表设计为栈符号表，当新的名字出现总是从 栈顶填入。 ——引入一个显示（DISPLAY）层次关系表，称为过程的 嵌套层次表。其作用是为了描述过程的嵌套层次，指出当 前正在活动着的各嵌套的过程（或函数）相应的子符号表 在栈符号表中的起始位置（相对地址）。 ——在符号表的信息栏中引入一个指针域（previous）用 以链接它在同一过程内的前一域名字在表中的下标（相对 位置）。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第八章 符号表
BEGIN …IF e<0 THEN p (f); ….. END; {q} BEGIN …. Q (e); … END; {p} PROCEDURE t ; j: real; BEGIN … p (e); … END; {t} BEGIN … WHILE c>0 DO …; p (d); … END. {main}
第八章 符号表
解:在编译过程中,当进入某过程体时,每引用一次 在编译过程中,当进入某过程体时, 标识符便需要查找栈符号表,查找范围由DISPLAY栈 标识符便需要查找栈符号表,查找范围由DISPLAY栈 顶值和TOP 的值控制,首先在栈符号表内的(TOP顶值和TOP 的值控制,首先在栈符号表内的(TOP- 1 ) DISPLAY栈顶值这样一个范围内查找 若找到了, 栈顶值这样一个范围内查找, 至DISPLAY栈顶值这样一个范围内查找,若找到了, 便可以从中取出该标识符的有关属性;若未查到, 便可以从中取出该标识符的有关属性;若未查到,则 需要继续在它的嵌套外层中查找,一直到最外层;如 需要继续在它的嵌套外层中查找,一直到最外层; 果引用的某标识符一直查到主程序还查不到它的说明 或某些属性不相符,则说明语义不正确, 或某些属性不相符,则说明语义不正确,处理程序将 向用户报告出错信息. 向用户报告出错信息. 下面给出了元程序在编译的不同时刻符号表
第八章 符号表
第八章 符号表
�
第八章 符号表
例题与习题解答
[例8.1] 在编译过程中,嵌套调用的过程间寻址问题如何解决? 在编译过程中,嵌套调用的过程间寻址问题如何解决? 下面是一个示意性元程序, 下面是一个示意性元程序,请给出编译期间栈式符号 表的变化情况. 表的变化情况. PROGRAM main a=10; b,c: integer; d,e: real; PROCEDURE p ( x:real ); f:real; PROCEDURE q (y:real); g=5; n:boolean;
第八章 符 号 表
编译过程中编译程序需要不断汇集和反复查证出现在 源程序中各种名字的属性和特征等有关信息. 源程序中各种名字的属性和特征等有关信息.这些信息通 常记录在一张或几张符号表中. 常记录在一张或几张符号表中.符号表的每一项包括两部 一部分是名字(标识符); );另一部分是此名字的有关 分:一部分是名字(标识符);另一部分是此名字的有关 信息.每个名字的有关信息是指种属(如简单变量,数组, 信息.每个名字的有关信息是指种属(如简单变量,数组, 过程等),类型(如整,实,布尔等).这些信息将用于 过程等),类型(如整, 布尔等).这些信息将用于 ),类型 ). 语义检查, 语义检查,产生中间代码以及最终生成目标代码等不同阶 乎在编译程序工作的全过程中, 段.几乎在编译程序工作的全过程中,都需要对符号表进 行频繁访问,可以认为查表或填表等操作, 行频繁访问,可以认为查表或填表等操作,在编译程序的 编译过程中是很大的一笔开销.因此,合理地组织符号表, 编译过程中是很大的一笔开销.因此,合理地组织符号表, 并相应地选择好查表和填表的方法,是提高编译序工作效 并相应地选择好查表和填表的方法, 率的重要一环. 率的重要一环.