《PL0 编译程序讲解ppt课件.ppt》由会员分享，可在线阅读，更多相关《PL0 编译程序讲解ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。
1、第二章 PL/0编译程序的实现,本章以PL/0编译程序为实例, 使大家对编译程序的实现建立起整体概念，对编译程序的构造得到一些感性认识和初步了解。1 PL/0语言2 PL/0处理机假想栈式机3 PL/0编译程序4 符号表的一般形式讨论5 栈式存储管理的再讨论,1 PL/0语言,PL/0功能简单、结构清晰、可读性强，而又具备了一般高级语言的必备部分，因而其编译程序能充分体现一个高级语言编译程序的基本技术和步骤。PL/0语言：PASCAL语言的子集，用于教学PL/0程序示例PL/0的语法描述图PL/0语言的EBNF表示,PL/0语言是PASCAL语言的子集,过程可嵌套定义，内层可引用包围它的外层定
2、义的标识符,可递归调用数据类型,只有整型数据结构 ,只有简变和常数标识符的有效长度是10语句种类： begin/end、if、while、赋值、read/write、call、const、var、procedure过程无参，最多可嵌套三层13个保留字：if、then、while、do、read、write、call、begin、end、const、var、procedure、odd+、-、*、/、=、=、(、),PL/0程序示例,CONST A=10; （* 常量说明部分 *） VAR B,C; （* 变量说明部分 *） PROCEDURE P; （* 过程说明部分 *） VAR D;（* P
3、的局部变量说明部分 *） PROCEDURE Q; （* P的局部过程说明部分 *） VAR X; BEGIN READ(X); D:=X; IF X#0 DO CALL P; END; BEGIN CALL Q; WRITE(D); END; BEGIN CALL P; END.,递归计算 sum = 1! + 2 ! + . + n!,var n, m, fact, sum; 递规计算 fact = m! procedure factorial;begin if m 0 then begin fact := fact * m; m := m - 1; call factorial; end
4、;end;,begin 读入n read(n); sum := 0; while n 0 do begin m := n; fact := 1; call factorial; sum := sum + fact; n := n - 1; end; 输出n ! write(sum);end.,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,程序,分程序,.,语法图,ident,read,end,;,语句,表达式,：=,begin,语句,语句,),(,ident,PL/0语言的EBNF表示,BNF（BACKUS-
5、NAUR FORM）与EBNF的介绍BNF是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它是从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序。构成EBNF的元素：非终结符，终结符，开始符，规则EBNF的元符号： 用左右尖括号括起来的内容为非终结符=或 读做定义为，的左部由右部定义 | 读做或 表示右部候选内容 表示花括号内的内容可重复任意次或限定次数 表示方括号内的内容为任选项 ( ) 表示圆括号内的内容优先,PL/0语言文法的EBNF表示,程序-分程序.分程序-常量说明部分-CONST常量定义部分，常量定义；无符
6、号整数-数字数字变量说明部分-VAR标识符，标识符；标识符-字母字母|数字 表达式=+|-项（+|-）项项=因子（*|/）因子因子=标识符|无符号整数|（表达式） ,2 PL/0处理机假想栈式机,一、PL/0处理机简介目标代码类p-code:一种栈式机的汇编语言栈式机系统结构:没有累加器和寄存器，只有存储栈指针所有运算都在栈顶（零地址机）两种存储，一个指令寄存器和三个地址寄存器,两种存储指令寄存器-I，放当前正在解释的指令地址寄存器,若有执行调用序列：A-B-C-B -先调用，后结束,二、运行时数据的存储与访问-栈式存储,假设A、C同层，且A中嵌套B,子程序的调用、执行和返回过程被调用时，子程
7、序的每次调用都需在数据栈顶为其分配独立的数据区子程序返回时，需做两件事情：一是代码返回（需记住RA），二是数据区的同步恢复（DL）子程序运行时，要存取外层数据区中的存储单元,当前B数据区须记住：返回地址RA动态链DL记录调用者数据区基地址静态链SL记录定义该过程的直接外层过程数据区的基地址，以便访问外层数据,运行时数据栈S的变化,var m1,m2,m3; Procedure A; var a1; procedure B; var b1,b2; procedure C; C过程call B; r1: B过程call C; r2: A过程call B; r3: 主程序Call A; r4: ,三
8、、PL/0机的指令系统,f: 功能码l: 层次差 （标识符引用层减去定义层）a:根据不同的指令有所区别,f l a,指令格式：,所有运算对栈顶的两个或一个元素进行，并用运算结果代替原来的运算对象。,指令功能表,( 0) jmp 0 8 转向主程序入口( 1) jmp 0 2 转向过程p入口( 2) int 0 3 为过程p开辟空间( 3) lod 1 3( 4) lit 0 10( 5) opr 0 2( 6) sto 1 4( 7) opr 0 0 退栈并返回调用点( 8) int 0 5( 9) opr 0 16 (10) sto 0 3(11) lod 0 3(12) lit 0 0(1
9、3) opr 0 9(14) jpc 0 24 条件不满足转24(15) cal 0 2 (16) lit 0 2(17) lod 0 4(18) opr 0 4(19) opr 0 14(20) opr 0 15 换行(21) opr 0 16(22) sto 0 3(23) jmp 0 11(24) opr 0 0,RA 16,运行栈,const a=10;var b,c;procedure p; begin c:=b+a; end;begin read(b); while b#0 do begin call p; write(2*c); read(b); endend.,SL：静态链DL
10、：动态链RA：返回地址,0,演示执行过程,3 PL/0编译程序的实现,PL/0编译程序的总体设计PL/0编译程序词法分析的设计与实现PL/0编译程序语法分析的设计与实现PL/0编译程序语义分析的设计与实现PL/0编译程序语法错误处理的实现PL/0编译程序代码生成的实现pcode代码解释器的设计与实现,3.1 PL/0编译程序的总体设计,单趟方式以语法、语义分析程序为核心，词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。表格管理程序实现变量，常量和过程标识符的信息的登录与查找。出错处理程序，
11、对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误 性质有关的编号，并进行错误恢复。,PL/0编译程序,PL/0编译程序,类 pcode解释程序,类 pcode代码,PL/0源程序,输入数据,输出数据,PL/0编译程序的结构框架,PL/0编译程序的结构,词法分析程序,语法语义分析程序,代码生成程序,表格管理程序,出错处理程序,PL/0源程序,目标程序,编译系统总体流程图,PL/0编译程序语法、语义分析的核心,3.2 PL/0编译程序词法分析的实现,词法分析函数getsym()所识别的单词：保留字或关键字：如：BEGIN、 END、 IF、 THEN等运算符： 如：+、-、*、/、
12、：=、#、=、=等标识符： 用户定义的变量名、常数名、过程名常数： 如：10、25、100等整数界符： 如：,、. 、; 、( 、)等,词法分析过程:getsym()框图（P19图2.5）,在编译程序中，单词的表示方式：（sym, id/num）,enum symbol nul,ident,number,plus,varsym,procsym；当识别出标识符时先查保留字表保留字及内部表示对应表： char wordnorwal; enum symble wsymnorw;字符对应的单词表： enum symble ssym256; ssym+=plus; ssym-=minus; 词法分析通过
13、三个全程量 symbol sym; char id; int num;将识别出的单词信息传递给语法分析程序。sym：存放单词的类别 如：initial:= 60；中各单词对应的类别为： initial ident, := becomes, 60 number, ; semicolonid：存放用户标识符,对initial（sym-ident，id-initial）num：存放用户定义的数 对60（sym-number,num-60）,用状态转换图实现词法分析程序的设计方法,状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。,表示终态，已识别出一个单
14、词,3.3 PL/0编译程序语法分析,语法分析的设计与实现自顶向下的语法分析递归子程序法（递归下降分析器recursive-descent parser）：对应每个非终结符（语法成分），编一个独立的处理子程序。 由开始，按规则右部(语法描述图箭头方向)进行分析 遇到非终结符，则调用相应的处理过程 遇到终结符，则判断当前读入的单词是否与该终结符相匹配，若匹配，再读取下一个单词继续分析。,程序 pl/0,分程序 block,语句statement,条件condition,表达式expression,项term,因子 factor,语法调用关系图,VAR A;BEGIN READ(A)END., .
15、 VAR ； A BEGIN END READ （ ） A,为文法的开始符号，以开始符号作为根结点存在一棵倒挂着的语法树。递归下降语法分析过程隐含着对对语法树的前序遍历,表达式=+|-项（+|-）项,int expression(bool* fsys, int* ptx, int lev)if(sym=plus | sym=minus) getsymdo; termdo(nxtlev, ptx, lev); /处理项 elsetermdo(nxtlev, ptx, lev); / 处理项 while (sym=plus | sym=minus)getsymdo; termdo(nxtlev,
16、ptx, lev); / 处理项 return 0;,注意一致性：进入每一语法单位处理程序之前，其第一个单词已读出，退出时，应读出下一个语法单位的第一个单词,项=因子（*|/）因子,int term(bool* fsys, int* ptx, int lev)factordo(nxtlev, ptx, lev);/* 处理因子 */ while(sym=times | sym=slash)getsymdo; factordo(nxtlev, ptx, lev);return 0;,因子=标识符|无符号整数|（表达式）,int factor(bool* fsys, int* ptx, int l
17、ev)if(sym = ident)/* 因子为常量或变量 */ getsymdo; else if(sym = number) getsymdo; else if (sym = lparen)/* 因子为表达式 */ getsymdo; expressiondo(nxtlev, ptx, lev); if (sym = rparen) getsymdo; else error(22);/* 缺少右括号 */ return 0;,3.4 PL/0语义分析的设计与实现,说明部分的分析与处理表格管理过程体(语句）的分析与处理,说明部分的分析与处理-登录符号表,对每个过程（含主程序）说明的对象（变量
18、，常量和过程）造符号表登录标识符的属性。标识符的属性:种类，所在层次,值和分配的相对位置。登录信息由ENTER过程完成。,符号表结构enum object constant, variable, procedur;,struct tablestruct char nameal; enum object kind; int val, level, adr, size; tabletxmax;,const a=35;/常量无层次var a1,a2,a3;Procedure P; var b1,b2; procedure P1; var c; procedure P2; var d; ,注意：在单趟
19、编译中，对于并列的函数（或分程序），其相应的符号表不会同时存在。,过程P2在code的入口,(0) jmp 0 0 CX (1) jmp 0 0 (2) jmp 0 0 (k) jmp 0 0,名字 类 值 层次 地址 大小,: :=var， ；,if(sym=varsym)/* 收到变量声明符号，开始处理变量声明 */ getsymdo; dovardeclarationdo( 注意：&tx,变量说明处理,int vardeclaration(int* ptx,int lev,int* pdx)if (sym = ident) enter(variable, ptx, lev, pdx);/
20、填写名字表 getsymdo; else error(4); /* var后应是标识符 */ return 0;,过程ENTER的实现,/* 在名字表中加入一项 * * k: 名字种类const,var or procedure * ptx: 名字表尾指针 * lev: 名字所在的层次,以后所有的lev都是这样 * pdx: 当前应分配变量的相对地址，分配后增加1 */void enter(enum object k, int* ptx,int lev, int* pdx)(*ptx)+; strcpy(table(*ptx).name, id); /* 全局变量id中已存有当前名字的名字 *
21、/ table(*ptx).kind = k;,switch (k) case constant:/* 常量名字 */ if (num amax) error(31);/* 数越界 */ num = 0; table(*ptx).val = num; break; case variable:/* 变量名字 */ table(*ptx).level = lev; table(*ptx).adr = (*pdx); (*pdx)+; break; case procedur:/*过程名字*/ table(*ptx).level = lev; break; ,过程体的处理变量引用的处理,对语句进行
22、语法分析语义分析 当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。语义分析 TABLE表若已有过正确定义，检查引用与说明的属性是否一致，若不一致则错。当语法语义正确时，就生成相应语句功能的目标代码,int position(char* id)int i; strcpy(table0.name, id); i = tx + 1; while(strcmp(table-i.name, id) != 0); return i; / position,思考：在造表和查表过程中，如何保证每个过程的局部量不
23、被它的外层引用？,赋值语句的处理,if (sym = ident) /* 准备按照赋值语句处理 */ i = position(id, *ptx); if (i = 0) error(11);/* 变量未找到 */ elseif(tablei.kind != variable) error(12);/* 赋值语句格式错误 */ i = 0; else. gendo(sto,lev-tablei.level,tablei.adr); . ,因子=标识符|无符号整数|（表达式）,int factor(bool* fsys, int* ptx, int lev) /因子的语义分析if(sym = i
24、dent)/* 因子为常量或变量 */i = position(id, *ptx);/* 查找名字 */ if (i = 0) error(11); /* 标识符未声明 */ else switch (tablei.kind) case constant:/* 名字为常量 */ break; case variable:/* 名字为变量 */ break; case procedur:/* 名字为过程 */ error(21); /* 不能为过程名 */,3.5 编译程序的错误处理,错误处理的原则：尽可能准确指出出错位置，错误性质，尽可能进行校正。PL/0编译程序对语法错误的处理：(1)对于易
25、于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析。(2)对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位,在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后跟符号集合外的所有符号。在语法单位分析结束时，调用TEST,检查当前符号是否属于调用该语法单位时应有的后跟符号集合。若不属于，则滤去后跟符号和开始符号集合外的所有符号。, TEST TEST,开始符号集合 bool declbegsyssymnum,statbegsyssymnum,facbegsyssym
26、num; declbegsys: constsym,varsym,procsym; statbegsys: beginsym,callsym,ifsym,whilesym,readsym,writesym; facbegsys: ident,number,lparen;后跟符号集合fsys作为参数： int test(bool* s1, bool* s2, int n); int block(int lev, int tx, bool *fsys); int statement(bool* fsys, int * ptx, int lev); int expression (bool* fsy
27、s, int * ptx, int lev); int term (bool* fsys, int * ptx, int lev); int factor (bool* fsys, int * ptx, int lev);,为symble的元素数32,后跟符号集,TEST,SYM在S1中?,打印出错编号n,S1:=S1+S2,SYM在S1中?,GETSYM,返回,Y,Y,N,N,TEST测试过程流程图,因子的处理过程,rocedure factor(fsys:symset); var i:integer; begin 入口： test(facbegsys,fsys,24); while sym
28、 in facbegsys do begin if . 出口： test(fsys,facbegsys,23); end end;,Facbegsys,y,处理ident number lparen,test,n,test,后跟符集是逐步补充的，需补充的内容与当前所处小环境有关。对调用expression(fsys); 由于write语句的语法write(,); 所以在write语句中调用expression时后跟符为： expression(rparen,comma+fsys);factor的语法：factor=.|( exp ) 在factor中调用expression时后跟符 expre
29、ssion(rparen+fsys);,3.6 代码生成,代码生成是由过程GEN完成。GEN有3个参数，分别代表目标代码的功能码，层差和位移量。例如 gen(opr,0,16); gen(sto,lev-level,adr) lev：当前处理的过程层次 level：被引用变量或过程所在层次 CX：为目标代码code数组的下标指针,代码结构变换， 地址回填,getsym;condition;if sym=thensym then getsym else error(16);cx1:= cx;gen(jpc,0,0)statement( );codecx1.a:=cx,If c then s,in
30、t main() . if(-1=block(0, 0, nxtlev) . . interpret(); / 调用解释执行程序 .int block(int lev, int tx, bool* fsys) dx=3; tx0=tx; tabletx.adr=cx; gen(jmp,0,0); /生成转向过程体入口的指令 while (sym = procsym) getsymdo(); if(sym=ident) enter(procedur, . if (-1 = block(lev+1, tx, nxtlev) . .,3.7 PL/0分程序的处理子程序-block,初值为fsys,p
31、eriod+declbegsys+statbegsys,下标指针cx，tx和变量dx的作用CX：为目标代码code数组的下标指针。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。tx ：table表的下标指针,是以值参数形式使用的。dx: 计算每个变量在运行栈中相对本过程基地址的偏移量 ，放在table表中的adr域，生成目标代码时再放在code中的a域。,过程体入口时的处理codetabletx0.adr.a=cx; /过程入口地址填写在code中tabletx0.adr=cx; /过程的入口填写在table中tabletx0.size=dx; /过程占的空间填写在table
32、中 cx0=cx; /保留过程在code中的入口地址gen(int,0,dx); /生成过程入口指令,3.8 类pcode解释器,目标代码存放在数组CODE中（程序地址寄存器p）解释程序定义一个一维整型数组S作为运行栈栈顶寄存器（指针）t，基址寄存器（指针）b，指令寄存器i（当前正在解释的目标指令）,目标代码的解释执行,几条特殊指令在code中的位置和功能INT 0 A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。OPR 0 0在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器
33、P中。CAL L A调用过程，填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行,interpret,三个寄存器赋初值t:=0; b:=1; p:=0;,主程序的SL，DL，RA赋初值s1:=0; s2=0; s3=0;,i:=codep;p:=p+1;,P=0?,返回,解释执行的流程图,执行指令i,N,Y,几条特殊指令的解释执行,过程出口opr 0 0,RA DL SL,b,.,t,M,t,b,t=b-1;p=st+3;b=st+2,Q,调用过程-cal l a st+1=base(l, s, b);
34、填写静态链 st+2=b; 填写动态链 st+3=p; 填写返回地址 b=t+1; 被调用过程的基地址 p=a 过程入口地址a送p /t在int中设置,int base(int l, int * s, int b) int b1; b1:=b; /find base l level down while (l0) b1=sb1; l=l-1; return b1; ,4 符号表的一般形式讨论,1、符号表的作用和内容语义检查的依据；目标代码生成阶段地址分配的依据；在编译中，符号表被频繁使用，表的组织方式对编译的效率起着十分重要的作用。符号表中，包括名字、种类、类型、层次、相对地址、存储类别等名字
35、的属性信息，以及动态数组的内情向量、记录结构型的成员信息、函数及过程的形参等结构信息。2、符号表的组织方式：线性表、散列表、树结构，符号表的组织方式必须维持源程序中的作用域信息。,栈符号表：函数或分程序的嵌套结构，使得程序中出现的符号的处理（内层可引用外层符号、同名变量内层优先）与栈的操作相一致。一个过程结束时将释放相应的子符号表-解决作用域检查问题。3、符号表的操作：创建符号表：在编译开始时或进入一个分程序插入表项：定义时（包括变量和形参定义）查询表项：可执行语句使用时修改表项：在获得新的语义值信息时进行删除一个或一组无用的项释放符号表的空间：在编译结束前或退出一个分程序4、符号表的生存期对
36、多遍扫描的编译程序，不同遍所用的符号表也往往不同。编译中的大部分符号表的生存期是编译过程，个别特殊表（动态数组的内情向量等）需保留到运行阶段5、符号表实例-单遍扫描,program sort(input,output) var a: array0.10 of integer; x: integer; procedure readarray; var i: integer; begin . a . end readarray; procedure exchange (i, j: integer); begin x := ai; ai:=aj; aj:=x end ; procedure quic
37、ksort (m, n:integer); var k,v: integer; function partition (y,z: integer): integer; var i, j:integer; begin . a .exchange (i, j); . end; begin . end quicksort; begin . end sort.,P4的符号表：嵌套层次表+二叉查找树,标准名字表（integer,false,）二叉树,当前层 top,同一层内全部名字的标识符记录利用左链和右链连接在一起形成二叉查找树,top,01234,sort,sort a, x readarray()
38、 i exchange (i, j) quicksort (m, n) k,v partition (y,z) i, j,栈-指出当前活动着的各嵌套的过程,const a=1, b=2, c=3; var step;procedure move(n, from, buf, to); begin if n0 /递归总是有条件的 begin cal move(n-1, from, to, buf); write(from, “, to); step:=step+1; cal move(n-1, buf, from, to); end end;begin step:=0; cal move(3, a, b, c); write(step=“, step);end.,作业（P30）： 2、 3、5,给出上面两个盘子已经移到B上，而A上只剩一个盘子时数据栈的状态。,对调用move(3, a, b, c); 上机调试观察调用执行过程，画出调用分解示意图,move(2, a, c, b);,move(1, a, b, c);,move(1, c, a, b);,a-b,move(2, b, a, c);,a-c,
