编译原理北大compile

上次课主要内容2021/7/71绑定（Binding）存储组织与分配内存划分、静态分配、动态分配(栈、堆)参数传递四种传递方式：值、地址、复制恢复、换名符号表管理关键字表、层次表、符号表（过程表、变量表、标号表）、常数表线性表（排序表）、散列表第七章

说明与过程语句翻译2021/7/72说明语句翻译组合数据说明的翻译过程调用翻译7.1

说明语句的翻译2021/7/73高级语言中的说明语句(Declarations)用于对程序中规定范围内使用的各类变量、常数、过程进行说明类型基本类型/内部类型（built-in)用户定义类型——结构描述作用域一般：说明所在的分程序、过程类型的作用2021/7/74引入数据抽象、隐蔽数据的基本表示用户无需注明字节数规定可用的运算类型检查数据精度控制规定存储单元的字节数，优化空间管理文法描述2021/7/75P

→

DD

→ D;

DD

→ id

:

TT

→

integerT

→

realT

→ array[num]

of

T1T

→

^T1例如：a:integer;

b:real;c:array[10]of

real变量说明的翻译2021/7/76在符号表中填写变量的属性种别、类型、相对地址、作用域……等相对地址全局变量表示为静态数据区的偏移值(offset)局部变量表示为局部数据域(活动记录的部分）的偏移值例7-1：相对地址举例名字 相对地址x

06468X[1]X[2]……X[8]ij2021/7/7708566468Beginreal

x[8];i,

j;integer……end属性、过程、与全局量2021/7/78类型T的属性type

类型width占用的字节数基本子程序

insert：设置变量的类型和地址

array：数组类型处理全局量offset：已分配空间字节数9说明语句的翻译模式P335P

→ {

offset

:=

0

}

DD

→ D

;

DD

→ id

:

T {insert(

id.entry,

T.type,

offset

);offset

:=

offset

+

T.width}T

→

integer {T.type

:=

integer; T.width

:=

4}T

→

real {T.type

:=

real; T.width

:=

8}T

→ array[

num

]

of

T1T

→

^T12021/7/7{T.type

:=

array(

num.val,

T1.type);T.width

:=

num.val

*

T1.width}{T.type

:=

pointer(

T1.type);T.width

:=

4}id:realTD;id:integerTDP2021/7/710例7-2：x:real;i:integer的翻译insert(x,real,0)offset=0Doffset=8T.type=realT.width=8offset=12T.type=integerT.width=4insert(i,integer,8)7.2

组合数据说明的翻译2021/7/711分类同结构的组合数据(同质数据结构)数组、集合异结构的组合数据(异质数据结构)记录、结构、联合抽象数据类型类、模块数组的引用与分配策略2021/7/712B.h.j操作元素的引用、修改:A[i,j,…,k]

,结构的引用、修改:A

,

B分配策略静态：直接完成相应的分配工作动态：构造代码，以在运行时调用分配过程数组说明的翻译2021/7/713符号表及有关表格(内情向量)处理维数、下标上界、下标下界空间分配首地址、需用空间计算存放方式按行存放、按列存放——影响具体元素地址的计算动态分配方案下数组说明的代码结构2021/7/714D

→id:array

[low1:up1

,

……,

lown:upn]

of

Tup1.code送工作单元W12low1.code送工作单元W……upn.code送工作单元W2n-1lown.code送工作单元W2n动态分配子程序其它参数(n,type)转动态分配子程序入口? D

→id:array

[num]

of

T数组元素的引用2021/7/715数组元素的翻译完成上下界检查生成代码完成相对地址的计算目标x:=y[i]和y[i]:=xy为数组地址的固定部分，i是相对地址，不是数组下标数组元素地址计算-按行存放2021/7/716一维数组A[low1:up1]

(nk=upk-lowk)Addr(A[i])=base+(i-

low1)*w=(base-

low1*w)+i*w=c+i*w二维数组A[low1:up1

,

low2:up2]~A[i1,i2]Addr(A[i1,i2])=base+((i1-

low1)*n1+

(i2-low2))*w=

base+(i1-

low1)*n1*w+(i2-low2)*w=

base-

low1*

n1*w-low2*w

+i1

*

n1*w+

i2*w=

base-(low1*

n1

-low2)*w

+(i1

*

n1

+

i2)*w=c+(i1*n1+

i2)*wid[i1,i2,…,in]（ih相当于Eh的值）P345~3472021/7/717S→L:=EE→L{if

L.offset=null

then

gen(L.place’:=’E.place)else

gen(L.place[L.offset]’:=’E.place}{if

L.offset=null

then

E.place:=L.place

elseL→id{E.place:=newtemp;gen(E.place’:=’L.place[L.offset]}}{L.place:=id.place;

L.offset:=null}Elist→id[E{Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place}Elist→Elist1,E{t:=newtemp;m:=Elist1.ndim+1;gen(t’:=’Elist1.place’*’limit(Elist.array,m);gen(t’:=’t’+’E.place);

Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m}L→Elist]{L.place:=newtemp;L.offset:=newtemp;gen(L.place’:=’

c);gen(L.offset’:=’Elist.place*w)}记录说明的翻译2021/7/718空间分配设置首地址和各元素的相对地址大于所需的空间（对齐）例：struct

Node

{float

x,

y;struct

node

*next;}

node;xyn

e

x

t048记录说明的翻译2021/7/719符号表及有关表格处理各元素的名字、类型、字节数生成代码，完成元素的相对地址的计算目标x:=y[i]和x[i]:=y

x是记录名，i是相对地址7.3

过程调用2021/7/720过程(procedure)子程序(subroutine)、函数(function)过程的定义与调用形参和实参的结合：参数计算与传递调用与返回工作方式调用方：当前环境的保存与恢复被调方：构造环境，参数绑定Main(

){Sub1(

10

)}Sub1(

x

){Sub2(

x

+

1

)}Sub2(

y

){Sub3(

)}2021/7/721过程调用实现2021/7/722简单过程调用实在参数的计算和保存控制转移、返回地址的保存实在参数和形式参数的结合(多种结合方式)局部变量的处理返回值的处理递归过程调用与过程参数每层过程调用信息的保存与相应信息的查找回忆：活动记录中过程所用信息用于表达式的计算局部数据寄存器、程序计数器（返回地址）保存实在参数的值或地址存放返回值保存调用者活动记录地址等(SP)用于存取非局部名(Display)临时变量局部变量机器状态实在参数返回值

控制链

访问链2021/7/723回忆：例7-3：函数的活动记录2021/7/7int

sub(

i,

p

)int

i;char

*p;{charbuf[32];buf[i]

=

*(p

+

i);return

i

+

1;}临时变量:

t1,t2,t3局部变量：buf[32]机器状态：R0,…,

R9,SP,PC,

PS参数：i,

p返回值控制链Display24过程说明语句的翻译2021/7/725分析参数的类型、分配地址统计参数和返回值的空间需求与调用语句配合完成形/实参数的结合符号表处理完成过程名的属性登记过程说明语句代码结构2021/7/726说明语句：Procedure

id(X1,X2,…,Xn)代码结构按参数传递要求实现参数X1的传递，或者完成传递准备；按参数传递要求实现参数X2的传递，或者完成传递准备；X1.codeX2.code……Xn.code按参数传递要求实现参数Xn的传递，或者完成传递准备；完成动态存储分配相关的工作；进入过程体。过程调用语句的代码结构过程调用语句1

2

nid(E

,E

,

…

,E

)代码结构

E1.codea1:=E1.place…En.codean:=En.place动态存储分配相关工作goto

pc+n+1param

a1…

param

ancall

id.place，n需要一个队列存放a1,a2,…,an，以生成2021/7/727过程调用的实现2021/7/728在过程f中调用过程g时f对实在参数求值，将结果存入g的活动记录参数域在g的活动记录中存放返回地址和当前栈顶指针按照活动记录的大小，上移栈顶指针控制转到g的入口e.g存放寄存器值和其它状态信息2021/7/729f.执行过程体从过程g返回：对应return语句g在返回值域中保存返回值恢复原栈顶指针和其它寄存器按返回地址返回调用者过程调用语句的制导翻译定义2021/7/730产生式S

→

call

id

(

Elist

)语义规则{ S.code

:=

Elist.code

||gen(‘goto

‘pc+Elist.num+1)||Elist

→

Efor

队列q中的每一项p

do

gen(’param’p)||gen(‘call’id.place’,’Elist.num)}{Elist.num

:=

1;

Elist