编译原理第六章

mcy
2
语义分析的任务：
计算各类语法成分的语义信息(属性信息)，一般将收集
的语义信息存放到相应的信息表中，在编译程序中符号 表是用来存放源程序中标示符相关属性(语义)信息的一 种信息表。 静态语义检查
类型检查：指类型相容问题的检查，如果操作符作用于不相容的操作数， 则编译器应该报错。 上下文有关问题的检查：当某个对象出现时，要求它必须在前面的某个 适当位置已经出现过。 唯一性检查：有时，要求某个对象只能被定义一次。 控制流检查：引起控制流从某个结构中跳转出来的语句，必须能够决定 控制流转向的目标地址。
（1）所采用的语法分析方法
（2）属性的计算次序。 语法分析方法都要求从左向右处理输入程 序，等价于要求属性能通过从左向右遍历 分析树进行赋值。
mcy
44
定义属性a1,...,ak 的一个属性文法是L-属性(Lattributed)文法，如果满足
mcy
37
num→digit
num.val=digit.val digit.base=num.base digit.val=0 digit.val=1 digit.val=7
digit→0 digit→1 ...... digit→7
mcy
38
digit→8
digit→9
if digit.base=8 then digit.val=error else digit.val= 8 if digit.base=8 then digit.val= error else digit.val 9
mcy
29
文法规则
语义规则 var-list.dtype = type.dtype type.dtype = integer type.dtype = real

29
(12）CHARACTER FUNCTION PRDUCE（）
（13) CHARACTER * 80 BUFFER
（14） INTEGER NEXT
（15） SAVE BUFFER，NEXT
(16) DATA NEXT／81／
（17） IF(NEXT.GT.80）THEN
（18) READ（*，'（A)')BUFFER
15
environment
state
名字
存储单元
值
l-value
r-value
存储分配
程序运行
图6.5 从名字到值的两个阶段映射
16
静态概念 过程定义 名字说明 说明的作用域
动态对应 过程活动 名字的绑定 活动的生存期
17
6.1.6 提出的问题
编译程序组织存储分配所采用策略和方法主
要取决于对源程序中下面的问题的回答。
可能有几处说明，语言的作用域规则规定：
在语句序列中引用的一个名字是在何处说
明的名字。
3 . 编译时，处理说明把名字及其属性信息填
写进符号表(add(id.entry,id.vul)); 处理引用
名字时，查找这个名字的属性信息
（lookup(id)),符号表管理程序根据语 言的
作用域规则，使 lookup(id)返回id的作用域
3. 栈:Pascal,c 4. 堆: Pascal,c
21
6.2.2 活动记录 把过程的一个活动所需要的信息组织成一
块连续的存储单元，称为活动记录。 一个活动所需要的信息的每个数据项有相
同的生存期，因此，组织成一个活动记录是 很自然的。
对于pascal语言来说，运行过程中，当调用 一个过程时，在栈顶构筑它的活动记录；当 这个过程的活动执行完后，把它从栈顶弹出。

尽管上面这些映射函数都不包含一个以上的对偶，但这个PDA 仍是非确定的。其中，前五个转换函数用于把输入符号移进栈 。接下来的六个用于完成归约工作，该PDA恰好识别L(G).
1 2 3 4 5 6
考虑输入串a*a+a,只 有下面的移动序列 才能够到达终止状 态： (q,$,a*a+a)├ (q,$a,*a+a)├ (q,$F,*a+a)├ (q,$T,*a+a)├ (q,$T*,a+a)├ (q,$T*a,+a)├
例6.5 考虑算术表 达式文法G3[E]： E→E+T E→T T→TF T→F F→(E) F→a
该文法的PDA映射函数δ为 δ(q,ε,a)={(q,a)} 根据规则6(①) δ(q,ε,+)={(q,+)} δ(q,ε,*)={(q,*)} δ(q,ε,‘(’)={(q,‘(’)} δ(q,ε,‘)’)={(q,‘)’)} δ(q,E+T,ε)={(q,E)} 根据规则6(②) δ(q, T,ε)={(q,E)} δ(q,T*F,ε)={(q,T)} δ(q,F,ε)={(q,T)} δ(q,(E),ε)={(q,F)} δ(q,a,ε)={(q,F)} δ(q,$E,ε)={(r,ε)} 根据规则6(③)
7 (q,$T*F,+a)├ 8 (q,$T,+a)├ 9 (q,$E,+a)├ 10 (q,$E+,a)├ 11 (q,$E+a,ε)├ 12 (q,$E+F,ε)├ 13 (q,$E+T,ε)├ 14 (q,$E,ε)├ 15 (r,ε,ε)├
E→E+T E→T T→TF T→F F→(E) F→a
关系积记为r1r2xr1r2y当且仅当存在w使得xr1w与wr2y传递闭包关系r的传递闭包记为rxyxry当且仅当存在n0使得xrny自反传递闭包关系r的传递闭包记为rxyxry当且仅当存在n0使得xrny其中r0为恒等布尔矩阵和关系?关系可用集合定义也可用布尔矩阵表示xry当且仅当mxy1?定理61mrtmrt?定理62mr1r2mr1mr2?定理63mr1r2mr1mr2?定理64mrmr传递闭包的warshall算法forj

运行时存储空间组织和符号表
3
当前活动记录一般包含如下内容： 连接数据： ①返回地址 ②动态链：指向调用该过程前的运行活动记录地 址的指针。运行时，使运行栈上各数据区按动态 建立的次序连成链。链头为栈顶起始位置。 ③静态链：指向静态直接外层最新活动记录地址 的指针，用来访问非局部数据。 形式单元：存放相应实在参数的地址或值。 局部数据区：局部数据、内情向量、临时单元。 ( P164 图6.7 )
2013-6-28
运行时存储空间组织和符号表
35
1
14
例：n=13 32
2013-6-28
运行时存储空间组织和符号表
36
三、 名字的作用范围 1、Fortran的符号表组织
2013-6-28
运行时存储空间组织和符号表
37
2、Pascal符号表组织
最近嵌套作用域原则：一个名字的作用 域是那个包含了这个名字的说明的最小 函数。 设计符号表： ①采用栈符号表：新的名字从栈顶填入， 每当进入一个过程时建立一张子符号表， 退出时释放。 ②引入过程的嵌套层次表（DISPLAY）
2013-6-28
运行时存储空间组织和符号表
14
§2 静态存储分配
FORTRAN77采用的是静态存储分配，它 的程序是段结构，整个程序由主程序段和若 干个子程序段组成，它的每个数据名所需的 存储空间大小都是常量，并且不允许递归调 用，这样，整个程序所需存储空间的总量在 编译时就能完全确定，所以，可以采用静态 存储分配方式。
2013-6-28
运行时存储空间组织和符号表
42
2013-6-28
运行时存储空间组织和符号表
43
2013-6-28
运行时存储空间组织和符号表

类型的内部表示
类型的种类：标准、子界、枚举、数组、记录、 类型的种类：标准、子界、枚举、数组、记录、
集合、文件、指针类型等等。 集合、文件、指针类型等等。 TypeKind=(intTy,boolTy,charTy,realTy,enumTy, subTy,arrayTy,recordTy,setTy,fileTy,pointerTy)
符号表的实现
用局部符号表实现 proc p:x,y,z proc p1:x,y1,z1 proc p2:y y,z x,y1,z1,y proc p3:z,a x,y,a x,z
符号表的实现
用全局符号表实现 proc p0:x,y proc p1:x,z y proc p2:x1,y1 y x,z
语义分析和符号表
主要内容： 主要内容： 语义分析概述(必要性、功能、描述方法) 语义分析概述(必要性、功能、描述方法) 符号表 类型表达式 声明和程序体的语义分析
语义分析的必要性
语法和语义的区别； 语法和语义的区别； 语法： 语法：关于什么样的字符串才是该语言 在组成ห้องสมุดไป่ตู้构上合法的程序的法则。 在组成结构上合法的程序的法则。 语义： 语义：关于结构上合法的程序的意义的 法则。 法则。
内部表示（ 内部表示（AttributeIR）： ）：
常量： 常量： 类型： 类型： 变量： 变量： 域名*： 域名 ： 过函： 过函：
TypePtr TypePtr Kind Kind Value Forward Access Off Off Level Parm Class Code Size Forward Level Off
TypePtr Kind TypePtr Kind
HostType

23
3.3 语法分析器
语法分析器的任务：分析语言的结构 1. 为句子构造语法树； 2. 检查输入序列中的错误。 主要工作： 1. 设计SQL语言的文法； 2. 设计语法树的节点，用于存放表达式的语法树； 3. 利用YACC工具分析SQL语句，并构造语句的语法树； 4. 设计测试程序和测试用例，检验分析器是否正确。
19
3.2 词法分析器
SQL语句中的记号： [例] CREATE TABLE Student ( Sno CHAR(9), Sname CHAR(20), Ssex CHAR(2), Sage INT ); 上边的SQL语句包括哪些记号？ 关键字：CREATE TABLE CHAR INT 标示符：Student Sno Sname Ssex Sage 数字： 9，20，2 其他符号：' ( ' ' ) ' ' , ' ' ; '
11
12
3.1 数据库存储结构设计
综上所述，建立一个表时有以下2步： 1. 将表对应的表字典表的数据插入.dat文件中，也就是向表 字典表中添加一条记录。 例如：
Students 表名 1 表id 4 列数 35 列总长度 1 起始块 NULL 保留
2. 将表对应的列字典表的数据插入.dat文件中，即向列字典 表中添加表的各列对应的记录。 例如： 1 1 Sno 1 9 0 NULL
20
LEX源程序基本结构如下： [声明]%% 翻译规则 [%% 用户定义子程序]
21
3.2 词法分析器
用正则式识别记号 CREATE TABLE对应的LEX源程序:
CREATE TABLE CHAR INT {return CREATE;} {return TABLE;} {return CHAR;} {return INT;}

3
CH.6 属性文法和语法制导翻译
• 在分析-综合模式的编译器中,语义分析是分 析过程的最后一个步骤，只有在这一步才真 正开始考虑程序语言的意义，并着手把它们 翻译成某种中间代码。这一过程通常采用的 方法是属性文法和语法制导翻译方法。 • 语法制导翻译方法的基本思想是，根据翻译 的需要设置文法符号的属性，用属性描述语 法结构的语义，用属性的计算完成翻译。 • 属性文法使文法符号属性值的计算和产生式 相联系。随着语法分析的进行，执行属性值 的计算，从而完成语义分析和翻译的任务。
37
抽象语法树：简例
• 例，为下面文法的句子 a-4+c 建立抽象语法树。 E E+T | E－T | T T (E) T id | num • 为每个运算量或运算符号都建立一个结点。 E • 可以根据表达式的运算顺序自下而上的构造 --+ 语法树 E + T 手工构造。 抽象语法树

9
属性文法、语义规则(2)
• 属性文法的形式： 产生式 语义规则 . 综合属性 A b:=f(c1,c2,…,ck) – 例如 P137.表6.1的属性文法: 继承属性 • EE1+ T E.val := E1.val+ T.val 综合属 – 例如 P139.表6.2的属性文法: 性 DTL L.in := T.type LL1 , id L .in := L.in 1 继承属性 继承属性
10
• 例, P137.
假设：
产生式 ABC
语义规则 A.b:=A.a+B.c C.d:=B.c+1 A有综合属性b和继承属性a B有综合属性c C有继承属性d
继承属性A.a和综合属性B.c在其他适当的地方计算。

合并已知量 删除公共子表达式(删除多余的运算)
删除无用赋值
第6部分 代码优化
循环优化
是指对循环中的代码进行优化。
循环优化包括:

代码外提 删除归纳变量 强度削弱
第6部分 代码优化
全局优化
是在整个程序范围内进行的优化, 需 进行数据流分析, 花费代价很高。
第6部分 代码优化
第6部分 代码优化
6.1.2 基本块的DAG表示
DAG(Directed Acyclic Graph)是一种有向图，
常常用来对基本块进行优化。 一个基本块的DAG是一种其结点带有下述标记 或附加信息的DAG：
第6部分 代码优化
(1) 图的叶结点(无后继的结点)以一标识符(变量名)或 常数作为标记，表示该结点代表该变量或常数的值。 如果叶结点用来表示一变量A的地址，则用addr(A) 作为该结点的标记。通常把叶结点上作为标记的标 识符加上下标0，以表示它是该变量的初值。 (2) 图的内部结点(有后继的结点)以一运算符作为标记， 表示该结点代表应用该运算符对其直接后继结点所 代表的值进行运算的结果。 (3) 图中各个结点上可能附加一个或多个标识符，表 示这些变量具有该结点所代表的值。 一个基本块由一个四元式序列组成，且每一个 四元式都可以用相应的DAG结点表示。
(1) G中四元式(2)和(6)都是已知量和已知量的 运算，G'已合并；
(2) G中四元式(5)是一种无用赋值，G'已将它 删除； (3) G中四元式(3)和(7)的R+r是公共子表达 式, G'只对它们计算了一次，即删除了多余的R+r 运算。 因此，G‘是对G实现上述三种优化的结果。
第6部分 代码优化
第6部分 代码优化

Chapter 6 Type Checking Section 2 Specification of a Simple Type Checker 3. Type Checking of Statements – S while E do S1 – {S.type= if (E.type==boolean) S1.type else type_error} – S S1;S2 – {S.type= if (S1.type==void) && (S2.type== void) void else type_error}
Chapter 6 Type Checking Section 3 Equivalence of type expressions s for type expression type link=^cell 3.Cycles in representations of types type link=^cell; cell=record info:integer; next :link end;
Chapter 6 Type Checking Section 2 Specification of a Simple Type Checker 1. A simple language 1)Grammar for source language – PD;E – DD;D | id:T – T char | integer | array [num] of T | ^T – E literal | num | id | E mod E | E[E] | E^
Chapter 6 Type Checking Section 2 Specification of a Simple Type Checker 2. Type Checking of Expressions – E E1[E2] – {E.type= if (E2.type==integer) && (E1.type==array(s,t) t else type_error} – E E1^ – {E.type= if (E1.type==pointer(t)) t else type_error}

if f(x)是一个表达式 then 对于某些类型α和β，f的类型为α β且x的类型为α
41
函数/运算符的重载
通过查看参数来解决函数重载问题 E f(E1)
{ if f.typeset = { si ti | 1 <= i <= n } and E1.type = sk then E.type = tk
数组引用的文法和地址计算相关联
假定数组编号从0开始，基于宽度来计算相对地址 数组引用相关文法
非终结符号L生成数组名，加上一个下标表达式序列
34
数组引用生成代码的翻译方案 (1)
非终结符号L的三个综合属性
L.array是一个指向数组名字对应的符号表条目的指针 (L.array.base为该数组的基地址)
类型构造算子array作用于数字和类型表达式得到 类型表达式，record作用于字段名和相应的类型 得到类型表达式
类型构造算子→可得到函数类型的类型表达式 如果s, t是类型表达式，其笛卡尔积s t也是类型
表达式
如：struct { int a[10]; float f; } st; 对应于：record((a array(0..9, int)) (f real))
变量的类型信息保存在符号表中
24
计算T的类型和宽度的SDT
• 综合属性：type, width
• 全局变量t和w用于将类型和宽度信息从B传递到C ε • 相当于C的继承属性 (也可以把t和w替换为C.t和C.w)
{
{
;}
25
SDT运行的例子
输入：int [2][3]
26
声明序列的SDT (1)
L.addr指示一个临时变量，计算数组引用的偏移量 L.type是L生成的子数组的类型

如：假定在一个基本块里有语句：
（1）T1 := A * B
（6）T4 := A * B
四元式（1）和（6）中，它们的运算相同 而且值不变，因此（6）的运算是多余的， 可将它等价变换为：（6'）T4 := T1
3.消除无用赋值
消除无用赋值是指对程序中的无用赋值 予以消除 。
如：（5）C := 2
（6）T4 := A * B
（7）T5 := 18 + C
（8）T6 := 4 * T5
（9）Y := T6
4. 代数变换 对基本块中求值的表达式，用代数上等价的形式 替换，以期使复杂运算变成简单运算。我们称这 种变换为代数变换。
如：语句
x := y ** 2
中的乘方运算，通常需要调用一个函数来实现。 可以用代数上等价的形式，用简单的运算替换。
0
1 2 0 1 2 3 4 5 6 0 3 4 5 6
执行DAG中无结点其左后继为NODE(R)，右后继为NODE(r)， 2 * NODE(2)无定义，构造一个标记为2的结点 T0 DAG中无结点其左后继为NODE(T )， ，新得到常数6.28 ,NODE(2) 是处理当前代码时 执行2 * T0 ，得到6.28， 5 NODE(B)无定义，将B附加到结点n6上， NODE(B)已定义，故将B从NODE(B)结点（当前为n6） NODE(2)无定义，构造一个标记为2的结点n7， NODE(T1)已定义，当前代码为2型， DAG中无结点其左后继为NODE(R))，右后继为NODE(T4)，= DAG中结点n6其左后继为NODE(T附加在结点n2上 当前代码为2型，NODE(r) 无定义， 新构造出来的，删除之，NODE(6.28)无定义，构造一个标记 DAG中结点n5其左后继为NODE(R)，右后继为NODE(r), NODE(T5)无定义，故将T附加在结点n5上， NODE(T2)无定义，将T2附加到结点n5上， NODE(A)无定义，将A附加到结点n6上， NODE(T1)无定义，将T1附加到结点n6上， NODE(T3)已定义，当前代码为2型， NODE(R)已定义，当前代码为2型， NODE(R)已定义，当前代码为2型， DAG中无结点其左后继为NODE(T，故构造一个结点n5， NODE(T)无定义，将T5附加在结点n1上 NODE(T3)无定义，将T3附加到NODE(6.28)上， 所有代码处理完毕，构造过程结束 NODE(T不是标记为常数的结点，转3（2） 4 0 5)已定义，当前代码为2型， 4 0 3 1)，故构造结点n6， NODE(R)无定义，构造一个标记为R的结点n3，令NODE(R) NODE(T 不是标记为常数的叶结点 ，转3（2） NODE(R)不是标记为常数的叶结点，转3（2） NODE(A)已定义，当前代码为0型，转4 NODE(R))不是标记为常数的结点，转3（2） NODE(2)和NODE(T0)都为标记为常数的结点，转2（4） NODE(3.14)无定义，构造一个标记为3.14的结点 当前代码为0型，记NODE(3.14)的值为n1,转4 当前代码为2型，NODE(T0 n8，转处理下一条代码 NODE(2) 和NODE(T0)均已定义，转2（4） NODE(2)是处理当前代码时构造出来的，删除之； 故构造结点n8，使其左后继为NODE(T5)， 将B附加到n8上，令NODE(B) =)已定义，转2（2） NODE(R)不是标记为常数的叶结点，转3（2） NODE(T 当前代码为2型，NODE(T 且标记为 4-5 1；故构造结点n7，使其左后继为NODE(R)， NODE(T6NODE(T))不是标记为常数的叶结点，转3（2） )无定义，将T令NODE(2) 0)已定义，转2（2） 为6.28的结点n2，置NODE(6.28) = n2，转4 6附加到结点n7上，转处理下一条代码 令NODE(B))，故将n6作为当前结点，转4 中的附加标识符集中删除 NODE(T=)已定义，转2（2） n4，转2（2） 构造一个标记为r的结点n4，令NODE(r) = 2)，转4 其左后继为NODE(R)，右后继为 NODE(r)，转4 且标记为 4) 6，故将n5作为当前结点，转4 且其标记为*1+ 4=2 1n2，转处理下一条代码 令NODE(T 0转处理下一条代码 令NODE(T2) ) 已定义 = n7 令NODE(T ) = n5 n3 ，转2（2） 令NODE(A) )已定义，转2（2） NODE(T NODE(r)已定义，转2（2） n5，转处理下一条代码 ，转处理下一条代码 NODE(r)已定义，转2（2） 其左后继为NODE(Tn6，转处理下一条代码 NODE(T n1，转处理下一条代码 )，右后继为NODE(T 即附加到n2上，转处理下一条代码 文法G的最终DAG如上图所示 令NODE(T = n6，转处理下一条代码 NODE(6.28)已有定义n2，转4 右后继为NODE(T6)，且标记为 * ，转4 右后继为NODE(r)，且标记为 -

…a
a >b
24
由定义直接构造：
预备知识：
定义两个集合：
+ + FIRSTVT(B)={b|B b…或B Cb…},
+ + LASTVT(B)={b|B …b或B …bC}
即最后一个终结符 即第一个终结符
25
三种优先关系的计算为： a)≡关系 条件：A…ab... A…aBb… b) <关系 条件:A…aB… bFIRSTVT(B) 结论:a<b c) >关系 条件:A…Bb… aLASTVT(B) 结论:a>b
20
定义：设G是不含产生式的算符文法,若G中任何两个终 结符号之间至多有一种优先关系存在，则G是一个算符 优先文法OPG。 注：不允许有ab、 a≡b、 ab 中的两种同时存在 要完成运算符间优先级的比较，最简单的办法是先定义 各种可能相继出现的运算符的优先级，并将其表示成矩 阵形式，即得到一个算符优先关系表。在分析过程中通 过查询矩阵元素而获得算符间的优先关系。
了解算符优先分析法的优缺点和实际应用中的局限性
2
【学习指南】
算符优先分析法是自下而上语法分析的一种，它的算
法简单、直观、易于理解，故通常作为学习其它自下 而上语法分析的基础。在学习前，应复习有关语法分 析的知识，如：什么是语言、文法、句子、句型、短 语、简单短语、句柄、最右推导、规范归约基本概念
S
A
A→Ab
最右推导 句型
abbcde
句柄 归约用规则 b A→b
S→aAcBe
aAbcde
Ab
d
A→Ab
B→d
A
A→b
B
B→d
aAcde