PL0-编译程序讲解资料讲解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 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,语言的,子集,过程可,嵌套定义，内层,可引用包围它的外层定义的,标识符,可递归调用,数据类型,只有整型,数据结构,只有简变和常数,标识符的有效长度是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的局部变量,说明部分*）,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;,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-NAUR FORM）,与EBNF的介绍,BNF,是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它是从语法上描述程序设计语言的,元语言,。采用BNF就可说明哪些符号序列是对于某给定语言,在语法上,有效的程序。,构成EBNF的元素：非终结符，终结符，开始符，规则,EBNF,的元符号：,用左右尖括号括起来的内容为,非终结符,=或 读做定义为，的,左部由,右部,定义,|读做或 表示右部候选内容,表示花括号内的内容,可重复,任意次或限定次数,表示方括号内的内容为,任选项,()表示圆括号内的内容,优先,PL/0语言文法的EBNF表示,程序-分程序.,分程序-,常量说明部分-CONST,常量定义部分，常量定义；,无符号整数-数字数字变量说明部分-VAR标识符，标识符；标识符-字母字母|数字 ,B-C-B-先调用，后结束,B区,A区,B区,C区,B,T,二、运行时数据的存储与访问-栈式存储,假设A、C同层，且A中嵌套B,子程序的调用、执行和返回,过程被调用时，子程序的每次调用都需在数据栈顶为其分配,独立,的数据区,子程序返回时，需做两件事情：一是代码返回（需记住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:,三、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,(13)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,SL 0,DL 0,RA 0,变量b,变量c,RA 16,SL 0,DL 0,运行栈,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：动态链,RA：返回地址,0,演示执行过程,3,PL/0编译程序的实现,PL/0编译程序的总体设计,PL/0编译程序词法分析的设计与实现,PL/0编译程序语法分析的设计与实现,PL/0编译程序语义分析的设计与实现,PL/0编译程序语法错误处理的实现,PL/0编译程序代码生成的实现,pcode代码解释器的设计与实现,3.1 PL/0编译程序的总体设计,单趟方式,以语法,、,语义分析,程序,为核心，词法分析,程序和,代码生成,程序都作为一个,过程,，当语法分析需要读单词时就调用词法分析程序，而当语法,、,语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。,表格管理,程序实现,变量,，,常量,和,过程,标识符的,信息的登录与查找,。,出错处理,程序，对词法和语法,、,语义分析遇到的错误给出在源程序中,出错的位置,和与,错误,性质有关,的编号，并进行错误恢复。,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等,运算符,：如：+、-、*、/、：=、#、=、=等,标识符,：用户定义的变量名、常数名、过程名,常数,：如：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,;,词法分析通过三个,全程量,symbol,sym,;char id;int,num,;将识别出的单词信息,传递,给,语法分析,程序。,sym,：存放单词的类别,如：initial:=60；中各单词对应的类别为：,initial,ident,:=,becomes,60,number,;,semicolon,id,：存放用户标识符,对initial（,sym-,ident,，,id-,initial）,num,：存放用户定义的数 对60（,sym-,number,num-,60）,用状态转换图实现词法分析程序的设计方法,状态,，对应每个状态编一段程序，,每个状态,调用,取字符,程序，根据当前字符,转到不同的状态，并做相应操作。,表示,终态,，已,识别出一个,单词,3.3 PL/0编译程序语法分析,语法分析的设计与实现,自顶向下的语法分析,递归子程序法,（递归下降分析器,recursive-descent,parser,）,：,对应,每个非终结符,（语法成分），,编一个独立的处理子程序。,由,开始，按规则右部(语法描述图,箭头,方向)进行分析,遇到,非终结符,，则,调用,相应的,处理过程,遇到,终结符,，则判断当前读入的单词是否与该终结符,相匹配,，若匹配，再读取下一个单词继续分析。,程序 pl/0,分程序 block,语句,statement,条件condition,表达式expression,项term,因子 factor,语,法,调,用,关,系,图,VAR A;,BEGIN,READ(A),END.,.,VAR,；,A,BEGIN,END,READ,（,）,A,为文法的,开始符号,，以开,始符号作为根结,点存在一棵倒挂,着的语法树。,递归下降语法分析过程隐含着对对语法树的前序遍历,表达式,=,+|-项（+|-）项,int expression(bool*fsys,int*ptx,int lev),if(sym=plus|sym=minus),getsymdo;,termdo(nxtlev,ptx,lev);/处理项,else,termdo(nxtlev,ptx,lev);/处理项,while(sym=plus|sym=minus),getsymdo;,termdo(nxtlev,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 lev),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语义分析的设计与实现,说明部分的分析,与处理,表格管理,过程体语句）的分析,与处理,说明部分的分析,与处理-,登录符号表,对每个过程（含主程序）,说明的对象,（,变量,，,常量,和,过程,）,造符号表,登录,标识符的,属性,。,标识符的属性:种类，所在,层次,值,和分配的,相对位置,。,登录信息由,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;,注意：在单趟编译中，对于并列的函数（或分程序），其相应的符号表不会同时存在。,过程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(,while(sym=comma),getsymdo;,vardeclarationdo(,if(sym=semicolon),getsymdo;,else error(5);,while(sym=ident);,注意：&tx,变量说明处理,int vardeclaration(int*ptx,int lev,int*pdx),if(sym=ident),enter(variable,ptx,lev,pdx);/填写名字表,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中已存有当前名字的名字*/,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;,过程体的处理,变量引用的处理,对,语句进行,语法,分析,语义分析,当遇到,标识符的引用时,就调用,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,思考：在造表和查表过程中，如何保证每个过程的局部量不被它的外层引用？,赋值,语句的处理,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=ident)/*因子为常量或变量*/,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)对于,易于校正,的错误，如丢了逗号，分号等，指出出错位置，,加以校正,，继续进行分析。(2)对于,难于校正,的错误，给出错误的位置与性质，,跳过后面的一些单词,，,直到下一个可以进行正常语法分析的语法单位,在,进入,某个,语法单位,时，调用,TEST,检查当前符号是否属于该,语法单位的开始符号集合,。若不属于，则,滤去,开始,符号,和,后跟,符号,集合外,的所有符号。,在,语法单位,分析结束,时，调用,TEST,检查当前符号是否属于调用该语法单位时应有的,后跟,符号集合。若不属于，则,滤去,后跟,符号和,开始,符号,集合外,的所有符号。,TEST TEST,开始符号,集合,bool declbegsyssymnum,statbegsyssymnum,facbegsyssymnum,;,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*fsys,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测试过程流程图,因子的处理过程,procedure factor(fsys:symset);,var i:integer;,begin,入口：,test,(,facbegsys,fsys,24);,while,sym,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时,后跟符,expression(,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,int 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,&tx,lev,.,if(-1=block(lev+1,tx,nxtlev),.,.,3.7 PL/0,分程序的处理子程序,-block,初值为fsys,period+declbegsys+statbegsys,下标指针,cx,，,tx,和,变量,dx,的作用,CX,：为目标代码,code,数组的下标指针。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。,tx,：table表的下标指针,是以,值参数,形式使用的。,dx,:,计算每个变量在运行栈中相对本,过程,基地址,的偏移量，放在,table,表,中的,adr,域，,生成,目标代码,时再放在,code,中的,a,域,。,过程,体,入口,时的处理,codetable,tx0,.,adr,.,a,=,cx,;/,过程入口地址填写在,code,中,tabletx0.,adr,=,cx,;/,过程的,入口,填写在,table,中,tabletx0.,size,=,dx,;/,过程,占的空间,填写在,table,中,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,的值，并将,返回地址,送,到指令地址寄存器,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,);,填写,静态链,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,=s,b1,;l=l-1;,return b1;,4,符号表的一般形式讨论,1符号表的作用和内容,语义检查的依据；,目标代码生成阶段地址分配的依据；,在编译中，符号表被频繁使用，表的组织方式对编译的,效率,起着十分重要的作用。,符号表中，包括名字、种类、类型、层次、相对地址、存储类别等名字的属性信息，以及动态数组的内情向量、记录结构型的成员信息、函数及过程的形参等结构信息。,2、符号表的组织方式：线性表、散列表、树结构，,符号表的组织方式必须,维持源程序中的作用域信息,。,栈符号表：函数或分程序的嵌套结构，使得程序中出现的符号的处理（内层可引用外层符号、同名变量内层优先）与栈的操作相一致。一个过程结束时将释放相应的子符号表-解决作用域检查问题。,3、符号表的操作：,创建符号表：在编译开始时或进入一个分程序,插入表项：定义时（包括变量和形参定义）,查询表项：可执行语句使用时,修改表项：在获得新的语义值信息时进行,删除一个或一组无用的项,释放符号表的空间：在编译结束前或退出一个分程序,4、符号表的生存期,对多遍扫描的编译程序，不同遍所用的符号表也往往不同。,编译中的大部分符号表的生存期是编译过程，个别特殊表（动态数组的内情向量等）需保留到运行阶段,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 quicksort(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,0,1,2,3,4,y,i,z,j,m,k,n,v,partion,sort,a,x,readarray,exchange,quicksort,sort,a,x,readarray(),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,A B C,给出上面两个盘子已经移到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,