教程案例成果

2014/继承属性的模拟求类型检符号运行 组中间代码生1 2014/从上面的讨论可知，分析栈中继承属性的是通 2014/SaA{C.i:=A.s}CbAB{C.i:=A.s}Cc{C.s:=若直接应用上述复写规则的处理方法，则在使Cc进行约时，C.i的值或存在栈顶（top-1），或存在次栈顶（top-一种可行的做法是引入新的非终结符M，将以上翻译方案改造为SaA{C.i:=A.s}CbAB{M.i:=A.s}M{C.i:=M.s}Cc{C.s:=Mε{M.s:=M.i这样，在使用Cc进行归约时，C.i的值就一定可以通过次栈2014/SaA{C.i:=f(A.s)}这里，继承C.i不是通过复写规则来求值，而是通过普通函数f(A.s)调用来计算.在计算C.i时，A.s在语义栈上，但f(A.s)并未同样，一种做法是引入新的非终结符M，将以上翻译方案SaA{M.i:=A.s}M{C.i:=M.s}Mε{M.s:=这样，就解决了上述注：从翻译方案中去掉嵌在产生式中间的语义规则集时，若语义

2014/ 2014/ 2014/静态语义分析的主要工类型检查（type控制流检查（flow-of-control控制流语句必须使控制转移到合法的地方（如唯一性检查（uniquenesschecks）很多场合要求对名字相关检查（name-related（如，一些名字可能被要求配对出现 2014/语义处理的环符号表（symbol类型检查 生器记号 语法 语法 表生器 2014/Chapter 2014/符号表的作符号表的常见属关于符号表的操符号表的实2014/符号表的作 符号表的常见属 2014/关于符号表的操

2014/符号表的实标号表,等等 符号表的实Hash符号表的实classlocal作用域的符号 (1)class

global作用域的符号

作用作用域Mac类的描Mac类成员符号Computer类的描Computer类成员符号略略(7)

intvoidCrash(intnTimes){inti;…}classMacextendsComputerint}voidmain()(15)

classMacpowerbook;…2014/运行 组织的作用与任程序在器中的布分配策活动记回收 运行 组织的作用与任数据表示分配表达式计 如何组织表达式的计过程实现数据表成分（component），偏移地址（offset），数据表示举char1integer4float8boolean1bit/1指针4数组一块连续 结构/记录所有域（field)存放在一块连续 对象 2014/StackHeapFreeStaticStackHeapFreeStatic

LowestHighest2014/分配策在编译期间将数据对象的运行 按照栈的方式来管从数据段的堆空间分配和释放数据对象的静 分如汇编语言，FORTRAN语可静态分配的数据对象如大小固定且在程序执行期间可全程的全局变量，以及程序中的常量，cstans）如C语言中的static和extern栈 分堆 分灵活数据对象 分配和释放不限时间和次显式的分配或释放（explicitallocation 隐式的分配或释放（implicitallocation 堆 分 最先适应算法（选择最先找到的足够大 块碎片整理算 压缩合并小 块，使其更可（部分内容可参考数据结构和操作系统课程+偏移地址+偏移地址（通常存于某寄存器中活动记voidp()q();

q被第二次激活时运qqqpmainvoidq()q();}intmainp(}活动记

TOP（栈顶寄存器SP（基址寄存器活动记解决对非局部量 （存取采用Display为活动记录增加静态链2014/活动记采用DisplayDisplay寄存器表（简称Display表）记录各嵌套层当前过程的活动记录在运行栈上的起始位置（址）当前激活过程的层次为（主程序的层次设为），则对应的spy表含有K+1个单元，依次存放着现行层，直接外层直至最外层的每一过程的动记录的址嵌套作用域规则确保每一时刻DisplayDisplay表的大小（即最多嵌套的层数）取决于实活动记Display表方案R被第一次激活后运行Display寄存D[i的情S的活动记Q的活动记R的活动记

programMain(I,O)；procedureP;procedureQ;procedureR; …R;… …Q;… procedureS;…P;… …S;… 活动记Display表的（过程被调用和返回时的保存和恢复 的方法是把整个Display表存入活动记录若过程为第n层，则需要保存D[0]~D[n]）一个过程被调用时，从调用过程的Display表中自下向上抄录n个SP值，再加上本层的SP值方法二只在活动记录保存一个Display活动记Display表 举保存完整的全局DisplayR的活R的活动记录全局DisplayQ的活动记录P的活动记录S的活动记

programMain(I,O)；procedureP;procedureQ;procedureR; …R;… …Q;… procedureS;…P;… …S;… 活动记采用静态链（staticDisplay表的方法要用到多个寄存器，有时并不情愿这样做（寄存器资源很宝贵）一种可选的方法是采用静态链，只保留一个寄存器（即SP）指向当前AR所有活动记录都增加一个静态链（如在offset0处）AR要被撤销。为回卷（unwind）（静态链/链：SL，动态链/控制链：DL活动记采用静态链的方法

programMain(I,O)；procedureP;procedureQ;procedureR; …R;

R的活动记录Q的活动记录P的活动记录S的活动记录

态…Q;态 procedure…P;… …S;… 2014/器记号 器–用语法制导定义和翻译方案的方法来2014/中间代中间代码的形 syntaxtree，抽象语法树DAG（DirectedAcyclicGraph,有向无圈图TAC（Three-addresscode,三地址码，四元式P-code（特别用于Pascal语言实现 2014/三地址码顺序的语句序列其语句一般具有如下x:=yop(op为操作码，y和z为操作符，x为结果 xyz翻译成的三地址语句序列是t1:=yzt2:=x+ 2014/中间代码举算术表达式AB*CDECDTAC（Three-addresscode,三地址码，四元式CDT1:=CDT1:=C-BT2:=B*ACD或T3:=A+T4:=C-((NT5NT5:=T4^ET6:=E/T7:=T3+((20142014/ 过程中说明语句的语法制导翻id的词法名字（符号表中的名字T.typeT.width数据宽度（字节数offset:相对于过程数据区基址的下一个可用的相enter(,T.type,offset): typeT.type,20142014/过程中说明语句的语法制导翻P{offset:=0}D;SDD1;D2Did offset:=offset+T.widthTTTTarray[num]ofT1TT1S

{T.type:=char;T.width:=1{T.type:=integer;T.width:=4{T.type:=real;T.width:=8{T.type:=array(num.val,T1.type);T.width:=num.valT1.width}{T.type:=pointer(T1.type)T.width:=4 2014/赋值语句的语法制导翻id的词法名字（符号表中的名字E.place用来存放EE.code:E求值的TAC的项，返回存放相应值的指针，若无该项，则返回genTACnewtempt 2014/产生 语义规Sid:=EE1+E2EE1E-E(E1E

S.code:=E.code||gen(‘:=‘E.place:=E.code:=E1.code||E2.codegen(E.place‘:=‘E1.place‘+’E2.place)E.place:=newtemp;E.code:=E1.code||E2.codegen(E.place‘:=‘E1.place‘’E.place:=newtemp; E.code:=E1.code||gen(E.place‘:=‘‘uminus‘E1.place)E.place:=E1.place;E.code:=E1.codeE.place:=id.place;E.code:=2014/符号表中的名Sid:= {p:=ifpnilemit(p,‘:=’,E.place)elseerror}EE1+{E.place:=emit(E.place,‘:=’,E1.place,‘+’,E2.place)EE1{E.place:=emit(E.place,‘:=’,‘uminus’,E1.place)E(E1){E.place:=E1.placeE {p:=ifpnilthenE.place:=pelseerror 数组元素的地址计

2014/一维数组A的第i个元素的地址计base+(ilow)iw+(baselow2014/A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,base+((i1low1)n2+(i2low2))（其中n2high2low21）((i1n2i2w+(base((low1n2)+low2)A[i1i2ik]((…((i1n2+i2)n3+i3)…)nk+ik)+base((…((low1n2+low2)n3+low3)…)nklowk)数组的向量（dove元中，称为“向量”.对于静态数组， 例：对于静态数组说明A[l1:u1,l2:u2,…,ln:un]，可以在符

li:第i维的下ui:第i维的上界type:数组元素的类型 n:数组维数C随后解例：对于静态数组A[l1:u1,l2:u2,…,ln:un]，若数组布局采用行优先的连续布局，数组首元素的地址为a，则数组元素A[i1,i2,…,in]的地址D可以如下计算:D=a+(i1-l1)(u2-l2)(u3-l3)…(un-+…+(in-1-ln-1)(un-ln)+(in-重新整理后得:DaCVC=(…(l1(u2-l2)+l2)(u3-l3)+l3)(u4-l4)+…+ln-1)(un-ln)+V=(…((i1(u2-l2)+i2)(u3-l3)+i3)(u4-l4)+……+in-1)(un-ln)+（这里的C即为前页向量中的类型转x:=y+it1:=iintt2:=inttorealt1t3:=yreal+t2x:=EE1+E.place:=ifE1.type=integerandE2.type=integerthenE.type=integerelseifE1.type=integerandE2.type=realthenu:=emit(u,‘:=’,‘inttoreal’,emit(E.place,‘:=’,u,‘real+’,E.type:=..20142014/布尔表达式的语法制导翻例如:可以用数值“1”表示true用数值“0”表示优点：方便实现控制流语句中E1or ifE1thentrueel