編譯原理北大compile

上次課主要內(nèi)容2021/7/71綁定（Binding）存儲(chǔ)組織與分配內(nèi)存劃分、靜態(tài)分配、動(dòng)態(tài)分配(棧、堆)參數(shù)傳遞四種傳遞方式：值、地址、復(fù)制恢復(fù)、換名符號(hào)表管理關(guān)鍵字表、層次表、符號(hào)表（過(guò)程表、變量表、標(biāo)號(hào)表）、常數(shù)表線性表（排序表）、散列表第七章

說(shuō)明與過(guò)程語(yǔ)句翻譯2021/7/72說(shuō)明語(yǔ)句翻譯組合數(shù)據(jù)說(shuō)明的翻譯過(guò)程調(diào)用翻譯7.1

說(shuō)明語(yǔ)句的翻譯2021/7/73高級(jí)語(yǔ)言中的說(shuō)明語(yǔ)句(Declarations)用于對(duì)程序中規(guī)定范圍內(nèi)使用的各類變量、常數(shù)、過(guò)程進(jìn)行說(shuō)明類型基本類型/內(nèi)部類型（built-in)用戶定義類型——結(jié)構(gòu)描述作用域一般：說(shuō)明所在的分程序、過(guò)程類型的作用2021/7/74引入數(shù)據(jù)抽象、隱蔽數(shù)據(jù)的基本表示用戶無(wú)需注明字節(jié)數(shù)規(guī)定可用的運(yùn)算類型檢查數(shù)據(jù)精度控制規(guī)定存儲(chǔ)單元的字節(jié)數(shù)，優(yōu)化空間管理文法描述2021/7/75P

→

DD

→ D;

DD

→ id

:

TT

→

integerT

→

realT

→ array[num]

of

T1T

→

^T1例如：a:integer;

b:real;c:array[10]of

real變量說(shuō)明的翻譯2021/7/76在符號(hào)表中填寫變量的屬性種別、類型、相對(duì)地址、作用域……等相對(duì)地址全局變量表示為靜態(tài)數(shù)據(jù)區(qū)的偏移值(offset)局部變量表示為局部數(shù)據(jù)域(活動(dòng)記錄的部分）的偏移值例7-1：相對(duì)地址舉例名字 相對(duì)地址x

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

x[8];i,

j;integer……end屬性、過(guò)程、與全局量2021/7/78類型T的屬性type

類型width占用的字節(jié)數(shù)基本子程序

insert：設(shè)置變量的類型和地址

array：數(shù)組類型處理全局量offset：已分配空間字節(jié)數(shù)9說(shuō)明語(yǔ)句的翻譯模式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

組合數(shù)據(jù)說(shuō)明的翻譯2021/7/711分類同結(jié)構(gòu)的組合數(shù)據(jù)(同質(zhì)數(shù)據(jù)結(jié)構(gòu))數(shù)組、集合異結(jié)構(gòu)的組合數(shù)據(jù)(異質(zhì)數(shù)據(jù)結(jié)構(gòu))記錄、結(jié)構(gòu)、聯(lián)合抽象數(shù)據(jù)類型類、模塊數(shù)組的引用與分配策略2021/7/712B.h.j操作元素的引用、修改:A[i,j,…,k]

,結(jié)構(gòu)的引用、修改:A

,

B分配策略靜態(tài)：直接完成相應(yīng)的分配工作動(dòng)態(tài)：構(gòu)造代碼，以在運(yùn)行時(shí)調(diào)用分配過(guò)程數(shù)組說(shuō)明的翻譯2021/7/713符號(hào)表及有關(guān)表格(內(nèi)情向量)處理維數(shù)、下標(biāo)上界、下標(biāo)下界空間分配首地址、需用空間計(jì)算存放方式按行存放、按列存放——影響具體元素地址的計(jì)算動(dòng)態(tài)分配方案下數(shù)組說(shuō)明的代碼結(jié)構(gòu)2021/7/714D

→id:array

[low1:up1

,

……,

lown:upn]

of

Tup1.code送工作單元W12low1.code送工作單元W……upn.code送工作單元W2n-1lown.code送工作單元W2n動(dòng)態(tài)分配子程序其它參數(shù)(n,type)轉(zhuǎn)動(dòng)態(tài)分配子程序入口? D

→id:array

[num]

of

T數(shù)組元素的引用2021/7/715數(shù)組元素的翻譯完成上下界檢查生成代碼完成相對(duì)地址的計(jì)算目標(biāo)x:=y[i]和y[i]:=xy為數(shù)組地址的固定部分，i是相對(duì)地址，不是數(shù)組下標(biāo)數(shù)組元素地址計(jì)算-按行存放2021/7/716一維數(shù)組A[low1:up1]

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

low1)*w=(base-

low1*w)+i*w=c+i*w二維數(shù)組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相當(dāng)于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)}記錄說(shuō)明的翻譯2021/7/718空間分配設(shè)置首地址和各元素的相對(duì)地址大于所需的空間（對(duì)齊）例：struct

Node

{float

x,

y;struct

node

*next;}

node;xyn

e

x

t048記錄說(shuō)明的翻譯2021/7/719符號(hào)表及有關(guān)表格處理各元素的名字、類型、字節(jié)數(shù)生成代碼，完成元素的相對(duì)地址的計(jì)算目標(biāo)x:=y[i]和x[i]:=y

x是記錄名，i是相對(duì)地址7.3

過(guò)程調(diào)用2021/7/720過(guò)程(procedure)子程序(subroutine)、函數(shù)(function)過(guò)程的定義與調(diào)用形參和實(shí)參的結(jié)合：參數(shù)計(jì)算與傳遞調(diào)用與返回工作方式調(diào)用方：當(dāng)前環(huán)境的保存與恢復(fù)被調(diào)方：構(gòu)造環(huán)境，參數(shù)綁定Main(

){Sub1(

10

)}Sub1(

x

){Sub2(

x

+

1

)}Sub2(

y

){Sub3(

)}2021/7/721過(guò)程調(diào)用實(shí)現(xiàn)2021/7/722簡(jiǎn)單過(guò)程調(diào)用實(shí)在參數(shù)的計(jì)算和保存控制轉(zhuǎn)移、返回地址的保存實(shí)在參數(shù)和形式參數(shù)的結(jié)合(多種結(jié)合方式)局部變量的處理返回值的處理遞歸過(guò)程調(diào)用與過(guò)程參數(shù)每層過(guò)程調(diào)用信息的保存與相應(yīng)信息的查找回憶：活動(dòng)記錄中過(guò)程所用信息用于表達(dá)式的計(jì)算局部數(shù)據(jù)寄存器、程序計(jì)數(shù)器（返回地址）保存實(shí)在參數(shù)的值或地址存放返回值保存調(diào)用者活動(dòng)記錄地址等(SP)用于存取非局部名(Display)臨時(shí)變量局部變量機(jī)器狀態(tài)實(shí)在參數(shù)返回值

控制鏈

訪問鏈2021/7/723回憶：例7-3：函數(shù)的活動(dòng)記錄2021/7/7int

sub(

i,

p

)int

i;char

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

=

*(p

+

i);return

i

+

1;}臨時(shí)變量:

t1,t2,t3局部變量：buf[32]機(jī)器狀態(tài)：R0,…,

R9,SP,PC,

PS參數(shù)：i,

p返回值控制鏈Display24過(guò)程說(shuō)明語(yǔ)句的翻譯2021/7/725分析參數(shù)的類型、分配地址統(tǒng)計(jì)參數(shù)和返回值的空間需求與調(diào)用語(yǔ)句配合完成形/實(shí)參數(shù)的結(jié)合符號(hào)表處理完成過(guò)程名的屬性登記過(guò)程說(shuō)明語(yǔ)句代碼結(jié)構(gòu)2021/7/726說(shuō)明語(yǔ)句：Procedure

id(X1,X2,…,Xn)代碼結(jié)構(gòu)按參數(shù)傳遞要求實(shí)現(xiàn)參數(shù)X1的傳遞，或者完成傳遞準(zhǔn)備；按參數(shù)傳遞要求實(shí)現(xiàn)參數(shù)X2的傳遞，或者完成傳遞準(zhǔn)備；X1.codeX2.code……Xn.code按參數(shù)傳遞要求實(shí)現(xiàn)參數(shù)Xn的傳遞，或者完成傳遞準(zhǔn)備；完成動(dòng)態(tài)存儲(chǔ)分配相關(guān)的工作；進(jìn)入過(guò)程體。過(guò)程調(diào)用語(yǔ)句的代碼結(jié)構(gòu)過(guò)程調(diào)用語(yǔ)句1

2

nid(E

,E

,

…

,E

)代碼結(jié)構(gòu)

E1.codea1:=E1.place…En.codean:=En.place動(dòng)態(tài)存儲(chǔ)分配相關(guān)工作goto

pc+n+1param

a1…

param

ancall

id.place，n需要一個(gè)隊(duì)列存放a1,a2,…,an，以生成2021/7/727過(guò)程調(diào)用的實(shí)現(xiàn)2021/7/728在過(guò)程f中調(diào)用過(guò)程g時(shí)f對(duì)實(shí)在參數(shù)求值，將結(jié)果存入g的活動(dòng)記錄參數(shù)域在g的活動(dòng)記錄中存放返回地址和當(dāng)前棧頂指針按照活動(dòng)記錄的大小，上移棧頂指針控制轉(zhuǎn)到g的入口e.g存放寄存器值和其它狀態(tài)信息2021/7/729f.執(zhí)行過(guò)程體從過(guò)程g返回：對(duì)應(yīng)return語(yǔ)句g在返回值域中保存返回值恢復(fù)原棧頂指針和其它寄存器按返回地址返回調(diào)用者過(guò)程調(diào)用語(yǔ)句的制導(dǎo)翻譯定義2021/7/730產(chǎn)生式S

→

call

id

(

Elist

)語(yǔ)義規(guī)則{ S.code

:=

Elist.code

||gen(‘goto

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

→

Efor

隊(duì)列q中的每一項(xiàng)p

do

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

:=

1;

Elist