第二章 PL0编译程序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章,PL/0,编译程序,2.1,PL/0,语言和,类,pcode,的,描述,2.2,PL/0,编译程序的结构,2.3,PL/0,编译程序的语法语义分析,2.4,PL/0,编译程序的,错误处理,2.5,类,pcode,代码解释器,本章目的：以,PL/0,为实例,学习编译程序实现的基本步骤和相关技术,PL/0,编译程序,PL/0,编译,程序,PL/0,语言程序,类,pcode,代吗,源语言(,PL/0,),目标语言(,类,pcode,),实现语言（,pascal,),PL/0,类,pcode,pascal,PL/0,编译程序,类,pcode,解释,程序,类,pcode,代码,PL/0,源程序,输入,输出,PL/0,编译系统的结构框架,PL/0,语言,PL/0,程序示例,PL/0,的,语法描述图,PL/0,语言,文法的,EBNF,表示,PL/0,语言：,PASCAL,语言的,子集,PL/0,程序示例,CONST A=10;,（*,常量说明部分*）,VAR B,C;,（*,变量,说明部分*）,PROCEDURE,P;,（*,过程,说明部分*）,VAR D;PROCEDURE,Q;,VAR X;,BEGIN READ(X);,D:=X;,WHILE X#0,DO CALL P;END;,BEGIN WRITE(D);CALL Q;END;,BEGIN CALL P;END.,Q,的过程体,p,的过程体,主,程序,体,程序,分程序,.,内的文字表示,非终结符,或,内的文字或符号表示,终结符,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,PL/0,语言文法的,EBNF,表示,EBNF,引入的符号(元符号)：用左右尖括号括起来的语法成分为,非终结符,=(),定义为,=()的,左部由,右部,定义,|,或,表示花括号内的语法成分,可重复,任意次或限,定次数,表示方括号内的语法成分为,任选项,()表示圆括号内的成分,优先,例：用,EBNF,描述的定义：=+|-=0|1|2|3|4|5|6|7|8|9,或更好的写法,=+|-|0=1|2|3|4|5|6|7|8|9=0|,PL/0,语言是,PASCAL,语言的,子集,同,PASCAL,作用域规则（内层,可引用包围它的外层定义的,标识符），上下文约束，,过程可,嵌套定义,，,可递归调用,子集,数据类型,只有整型,数据结构,只有简变和常数,数字最多为14位,标识符的有效长度是10,语句种类,过程最多可,嵌套,三层,目标代码,类,pcode,目标代码,类,pcode,是,一种,假想栈式计算机,的,汇编语言,。,指令格式：,f l a,f,功能码,l,层次差,（,标识符,引用,层,减去,定义,层,）,a,根据不同的指令有所区别,指,令,功,能,表,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.,(0),jmp,0 8,转向,主程序入口,(1),jmp,0 2,转向,过程,p,入口,(2),int,0 3,过程,p,入口,为过程,p,开辟空间,(3),lod,1,3,取变量,b,的值到栈顶,(4),lit 0 10,取常数10到栈顶,(5),opr,0 2,次栈顶与栈顶相加,(6),sto,1,4,栈顶值送变量,c,中,(7),opr,0 0,退栈并返回调用点,(16),(8),int,0 5,主程序入口开辟5个栈空间,(9),opr,0 16,从命令行读入值置于栈顶,(10),sto,0 3,将栈顶值存入变量,b,中,(11),lod,0 3,将变量,b,的值取至栈顶,(12),lit 0 0,将常数值0进栈,(13),opr,0 9,次栈顶与栈顶是否不等,(14),jpc,0 24,等时转(24)（,条件不满足转,）,(15),cal 0 2,调用过程,p,(16)lit 0 2,常数值2进栈,(17),lod,0,4,将变量,c,的值取至栈顶,(18),opr,0 4,次栈顶与栈顶相乘(2,*,c),(19),opr,0 14,栈顶值输出至屏幕,(20),opr,0 15,换行,(21),opr,0 16,从命令行读取值到栈顶,(22),sto,0,3,栈顶值送变量,b,中,(23),jmp,0 11,无条件转到循环入口(11),(24),opr,0 0,结束退栈,PL/0,编译程序的结构,词法分析程序,语法语义分析程序,代码生成程序,表格管理程序,出错处理程序,PL/0,源程序,目标程序,PL/0,编译程序的总体设计,其编译过程采用,一趟扫描方式,以语法,、,语义分析,程序,为核心,词法分析,程序和,代码生成,程序都作为一个,过程,，当语法分析需要读单词时就调用词法分析程序，而当语法,、,语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。,表格管理,程序实现,变量,，,常量,和,过程,标识符的,信息的登录与查找,。,出错处理,程序，对词法和语法,、,语义分析遇到的错误给出在源程序中,出错的位置,和与,错误,性质有关,的编号，并进行错误恢复。,PL/0,编译程序词法分析的设计与实现,识别的单词：,保留字或关键字：如：,BEGIN、END、IF、THEN,等,运算符,：如：+、-、*、/、：=、#、=、=等,标识符,：用户定义的变量名、常数名、过程名,常数,：如：10、25、100等整数,界符,：如：,、.、;、(、)等,词法分析过程,GETSYM,所要完成的任务：,读源程序（,getch,),滤空格,识别,保留字,识别标识符,拼数,识别单字符单词,拼双字符单词,词法分析过程,:,GETSYM,框图（见教材图2.5）,程序（,procedure,getsym,）,当识别到标识符时先查,保留字,表,保留,字,表：（,begin (*main*)）,word1:=,begin,；word2:=,call,；,.,word13:=,write,；,查到时找到相应的,内部表示,Wsym,1:=,beginsym,;,wsym,2:=,callsym,；,wsym,13:=,writesym,；,字符对应的,单词表：,ssym,+:=,plus,;,ssym,-:=,minus,;,ssym,;:=,semicolon,;,词法分析如何把单词传递给语法分析,type symbol=(,nul,ident,number,plus,varsym,procsym,)；,3个,全程量,sym,:symbol;,id,:,alfa,;,num,:integer;,通过三个,全程量,SYM,、,ID,和,NUM,将识别出的单词信息,传递,给,语法分析,程序。,SYM,：,存放单词的类别,如：有程序段落为：,begin initial:=60；end,对应单词,翻译后变为：,begin,beginsym,initial,ident,:=,becomes,60,number,；,semicolon,，,end,endsym,。,ID,：,存放用户所定义的标识符的值 如：,initial（,在,SYM,中放,ident,，,在,ID,中,放,initial）,NUM,：,存放用户定义的数 如：60,（,在,SYM,中放在,number,在,NUM,中,放,60）,使用状态转换图实现词法分析程序的设计方法,词法分析程序的设计-使用状态转换图实现,表示,状态,，对应每个状态编一段程序，,每个状态,调用,取字符,程序，根据当前字符,转到不同的状态，并做相应操作。,表示,终态,，已,识别出一个,单词,。,PL/0,编译程序语法语义分析,PL/0,编译程序语法分析的设计与实现,自顶向下,的语法分析,递归子程,序法,程序,分程序,.,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,ident,read,end,;,语句,表达式,：=,begin,语句,语句,),(,ident,自顶向下的语法分析,VAR A;,BEGIN,READ(A),END.,.,VAR,；,A,BEGIN,END,READ,（,）,A,为文法的,开始符号,，以开,始符号作为根结,点构造一棵倒挂,着的语法树。,递归子程序法,递归子程序法,：,对应,每个非终结符,语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符,（,即开始符）出发，沿语法描述图,箭头,所指出的方向进行分析。当遇到非终结符时，则,调用,相应的,处理过程,，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是,终结符,时，则判断当前读入的单词是否与图中的终结符,相匹配,，若匹配，再读取下一个单词继续分析。遇到,分支点,时，将当前的单词与分支点上多个终结符,逐个相比较,，若都不匹配时可能是进入下一个非终结符语法单位或是出错。,例：如何用递归子程序法实现表达式的语法分析,项,表达式,+,-,项,+,-,项,因子,因子,*,/,语法图,因子的语法图,因子,ident,number,(,表达式,),表达式的,EBNF,表达式,=,+|-项（+|-）项项,=,因子（*|/）因子因子,=,标识符|无符号整数|,（,表达式,）,表达式,的,递归子程序,实现,procedure,expr,;begin if sym in,plus,minus,then begin,getsym,;,term,;end else,term,;while sym in,plus,minus,do begin,getsym,;,term,;endend;,项,的,递归子程序,实现,procedure,term,;begin,factor,;while sym in,times,slash,do begin,getsym,;,factor,;endend;,因子,的,递归子程序,实现,procedure,factor,;begin,if sym,ident,then begin if sym,number,then begin,if sym=,(,then,begin,getsym,;,expr,;if sym=,),then,getsym,else error,end else error,end,end,end;,=,begin（*main*),(*initialize*),(*r/w file set*),getsym,;block();,if,sym,period then error.end.,。,程序,pl0,分程序,block,语句,statement,条件,condition,表达式,expression,项,term,因子,factor,语,法,调,用,关,系,图,编译程序总体流程图,PL/0,编译程序语义分析的设计与实现,PL/0,编译程序语法,、,语义分析的的核心,程序是,BLOCK,过程，,说明部分的分析,与处理,表格管理,过程体(语句）的分析,与处理,说明部分的分析,与处理,对每个过程（含主程序）,说明的对象,（,变量,，,常量,和,过程,）,造符号表,登录,标识符的,属性,。,标识符的属性:种类，所在,层次,值,和分配的,相对位置,。,登录信息由,ENTER,过程完成。,说明部分的分析,与处理,（,程,序）,说明种类的定义：,object=(,constant,variable,procedur,),（,定义,纯量,/,枚举,类型）,符号表的定义,table,:array0.,txmax,of record,name:,alfa,;,case,kind,:object of,constant,:(,val,:integer);,variable,:,procedur,:(,level,adr,size,:,integer);,例程序说明部分为：,CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G；,符号表,名字 种类 层次/值 地址 存储空间,对应名字表,tx,：table,表,的下标指针,是以,值参数,形式使用的。,dx,:,计算每个变量在运行栈中相对本,过程,基地址,的偏移量,，,放在,table,表,中的,adr,域，,生成,目标代码,时再,放在,code,中的,a,域,变量定义语句的处理,语法：:=,var,，,；,程序：,if sym=,varsym,then begin,getsym,;repeat,vardeclaration,;(*,变量说明处理,*),while sym=,comma,do,begin,getsym,;,vardeclaration,end;if sym=,semicolon,then,getsym,else error(5)until sym,ident,;end;,变量说明处理,procedure,vardeclaration,;,begin,if sym=,ident,then,begin,enter,(,variable,);,getsym,end else error(4)end(*,vardeclaration,*);,过程,ENTER,的实现,tx,：table,表,的指针,procedure,enter,(,k,:object);begin (*enter object into table*),tx,:=,tx,+1;,with table,tx,do,(*,开域,语句*）,begin,name,:=,id,;(*,表示,table,tx,.,name,:=,id,;*）,kind,:=,k,;(*,表示,table,tx,.,kind,:=,k,;*),过程,ENTER,的实现,case,k,of,constant,:,begin if,num,amax,then,begin error(31);,num,:=0;end;,val,:=,num,;(*,table,tx,.,val,:=,num,;*)end;,过程,ENTER,的实现,variable,:,begin,level,:=,lev,;,（*,表示,table,tx,.,level,:=,lev,*）,adr,:=,dx,;,（*,表示,table,tx,.,adr,:=,dx,*）,dx,:=,dx,+1;end;,procedur,:,level,:=,lev,(*,表示,table,tx,.,level,:=,lev,;*）,end(*,case,*);,end,end(*enter*);,过程体的处理,对,语句进行,语法,分析,语义分析,当遇到,标识符的引用时,就调用,POSITION,函数,查,TABLE,表,，看是否,有,过,正确定义,，若已有，则从表中,取相应,的有关,信息,，供代码的生成使用。,若无定义则错,。,当,语法语义正确时,，就,生成,相应语句功能的,目标代码,赋值,语句的,处理,if,sym,=,ident,then,begin,i:=position(id);,if i=0 then error(11),else if tablei.kind variable,then,begin error(12);,i:=0,end;,getsym,;,if,sym,=becomes then,getsym,else error(13);,expression(,fsys,);,if i 0 then,with table i do,gen,(,sto,lev,-level,adr,),end,代码生成,代码生成是由过程,GEN,完成。,GEN,有,3,个,参数,，分别代表目标代码的,功能码,，,层差,和,位移量,。例如,gen,(,opr,0,16);,gen,(,sto,lev,-,level,adr,),lev,：,当,前,处理的,过程,层次,level,：,被,引用变量或过程所在,层次,CX,：,为目标代码,code,数组的下标指针,结构变换，地址返填,If c then s,getsym,;,condition;,if,sym,=,thensym,then,getsym,else error(16);,cx1:=,cx,;,gen,(,jpc,0,0),statement();,codecx1.a:=,cx,PL/0,编译程序错误处理的实现,对语法错误的两种处理方法：(1)对于,易于校正,的错误，如丢了逗号，分号等，指出出错位置，,加以校正,，继续进行分析。(2)对于,难于校正,的错误，给出错误的位置与性质，,跳过后面的一些单词,，,直到下一个可以进行正常语法分析的语法单位。,在,进入,某个,语法单位,时，调用,TEST,检查当前符号是否属于该,语法单位的开始符号集合,。若不属于，则,滤去,开始,符号,和,后继,符号,集合外,的所有符号。,在,语法单位,分析结束,时，调用,TEST,检查当前符号是否属于调用该语法单位时应有的,后继,符号集合。若不属于，则,滤去,后继,符号和,开始,符号,集合外,的所有符号,。,TEST TEST,开始符号集合与后继符号集合,开始符号,集合,symset,=,set,of,symbol,;,declbegsys,statbegsys,facbegsys,:,symset,;,开始符号集合（*主程序*,）,declbegsys,:=,constsym,varsym,procsym,;,statbegsys,:=,beginsym,callsym,ifsym,whilesym,readsym,writesym,;,facbegsys,:=,ident,number,lparen,;,后继符,号集合,fsys,作为参数：,procedure,test,(,s1,s2,:,symset,;n:integer);,procedure,block,(,lev,tx,:integer;,fsys,:,symset,);,procedure,statement,(,fsys,:,symset,);,procedure,expression,(,fsys,:,symset,);,procedure,term,(,fsys,:,symset,);,procedure,factor,(,fsys,:,symset,);,READ,语句的语法语义分析处理,if sym=,readsym,then,begin,getsym,;,if sym,lparen,then error(34),else,repeat,getsym,;,READ,语句的语法语义分析处理,if sym=,ident,then i:=,position,(id),else i:=0;,if i=0 then error(35),else,with tablei do,begin,gen,(,opr,0,16);,gen,(,sto,lev,-,level,adr,),end,;,READ,语句的语法语义分析处理,getsym,until,sym,comma,;,if sym,rparen,then,begin,error(33);,while not(sym in,fsys,),do,getsym,end,else,getsym,end,出错处理,跳过不应出现的符号,正确,出,口,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,);,类,pcode,代码解释器的实现,类,pcode,解释器的结构,目标代码解释执行时,数据栈的布局,（运行栈的存储分配）,类,pcode,解释器的结构,目标代码存放在数组,CODE,中。,解释程序定义一个一维整型数组,S,作为,运行栈,栈顶寄存器,（指针）,t,，,基址寄存器,（指针）,b,，,程序地址寄存器,p,，,指令寄存器,i,目标代码解释执行时数据栈的布局（运行栈的存储分配）,在每个过程调用时在栈顶分配,3,个联系单元：,SL,：,静态链,，指向,定义,该过程的,直接外过程,（或主程序）运行时,最新,数据段的基地址,。,DL,：,动态链,，指向,调用,该过程前正在运行过 程的数据段基地址。,RA,：,返回地址,，记录调用该过程时,目标程序的,断点,，即调用过程指令的下一条指令的地址。,目标代码的解释执行 运行栈,S,M,调用过程,Q,RA,DL,SL,b,.,.,t,t,b,Q,M,目标代码的解释执行,几条,特殊指令,在,code,中的,位置,和,功能,INT 0 A,在,过程,目标程序的,入口处,，,开辟,A,个单元的数据段。,A,为,局部变量,的,个数,+,3,。,OPR 0 0,在,过程,目标程序的,出口处,，,释放数据段,（退栈），,恢复调用,该过程,前,正在运行的过程,的数据段,基址寄存器,B,和,栈顶寄存器,T,的值，并将,返回地址,送,到指令地址寄存器,P,中，以使调用前的程序从,断点,开始,继续执行,。,目标代码的解释执行,几条,特殊,指令在,code,中的,位置,和,功能,CAL L A,调用过程,，还完成,填写,静态链,、,动态链,、,返回地址,，给出,被调,用,过程,的,基地址,值，,送,入基址寄存器,B,中，目标程序的,入口,地址,A,的值,送,指令地址寄存器,P,中，使指令从,A,开始执行。,附,PL/0,编译程序代码生成的实现,CX,：,为目标代码,code,数组的下标指针。,code,为一维数组，数组元素为,记录型数据,。每一个记录就是一条目标指令。,CX,为整数变量，由,0,开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。,tx,：table,表,的下标指针,是以,值参数,形式使用的。,dx,:,计算每个变量在运行栈中相对本,过程,基地址,的偏移量,，,放在,table,表,中的,adr,域，,生成,目标代码,时再,放在,code,中的,a,域,。,附,PL/0,编译程序代码生成的实现,下标指针,cx,，,tx,和,变量,dx,的作用,code,cx,table,tx,s,t,(,运行栈,),cx tx,t,(,运行时栈指,针,),(0),jmp,0 0,(1),int,0 7,.,.,(,cx,).,(0),name,adr,.,(1),b,(,dx,),.,(,tx,),q,p,m,b,附,PL/0,编译程序代码生实现,Table,表的,下标指针,tx,补充说明：,主程序,BLOCK,第,1,次,调用,block,BLOCK（,0,，,0,，）,0,0,.,BLOCK,BLOCK（,LEV+1,TX,，）,(,递归,进入,分程序),LEV,tx,LEV,tx,（,6,）,6,（,9,）,1,tx,是,BLOCK,的,实际,值参,附,PL/0,编译程序代码生成的实现,procedure,gen,(,x,:,fct,;,y,z,:integer);begin if,cx,cxmax,then（*,指针越界*）,begin,write(,program too long,);,close(fin);（*,关闭文件*）,writeln,;,exit,end;,附,PL/0,编译程序代码生成的实现,with code,cx,do,begin,f,:=,x,;（*,表示,code,cx,.,f,:=,x,;*),l,:=,y,;（*,表示,code,cx,.,l,:=,y,;*),a,:=,z,;（*,表示,code,cx,.,a,:=,z,;*),end;,cx,:=,cx,+1end(*,gen,*);,附,PL/0,编译程序代码生成的实现,对,分程序的定义（,见教材292页）,procedure block(,lev,tx,:integer;,fsys,:,symset,);,var,dx,:integer;(*data,allocationindex,*),tx0,:integer;(*initial table index*),cx0,:integer;(*initial code index*),（,tx0,，,cx0,是,tx,，,cx,的初值）,附,PL/0,编译程序代码生成的实现,对,分程序,体,人口的处理（见程序文本,block,的过程体,）,begin(*block*),dx,:=,3,;,tx0:=,tx,;（,保留当前,table,表,指针值,）,table,tx,.,adr,:=,cx,;（,保留当前,code,指针值到过程名,的,adr,域,）,gen,(,jmp,0,0);（,生成转向,过程体入口的指令，该指令的地址 为,cx,已,保留在过程名的,adr,域，,等生成,过程 体入口的指令时，再由,table,tx,.,adr,中取出,cx,将,过程体入口返填到,cx,中，即 （,jmp,0,0,）,的第3,区域。,（,注意,dx,，,tx,，,cx,的作用）,CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G,附,table,表格管理,名字 类型 层次/值 地址 存储空间,(0),jmp,0 0,CX,(1),jmp,0 0,.,.,记录,过程在,code,的,入,口到,table,中的,adr,域,附,PL/0,编译程序代码生成的实现,过程,体,入口,时的处理,codetable,tx0,.,adr,.,a,:=,cx,;,（,过程入口地址填 写在,code,中,）,with tabletx0 do,begin,adr,:=,cx,;（,过程的,入口,填 写在,table,中,）,size,:=,dx,;（,过程,占的空间,填 写在,table,中,）,end;,cxo,:=,cx,;（,保留,过程在,code,中的,入口地址）,gen,(,int,0,dx,);（,生成,过程,入口指令,）,附,PL/0,编译程序代码生成的实现,第,1,次,调用,block（,见教材305页）,block(,0,0,period+,declbegsys,+,statbegsys,)；,(,0,0,是,tx,lev,的实际,值参,，第,1,次,调用时为0,以后,调用时的参数为,lev,+1,tx,),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,主程序,的,RA s3=0,附,目标代码的解释执行,几条,特殊指令,的,解释执行,：,过程,入口,：,开辟,a,个单元,（,见教材304页）,int,:t:=t+a;（t,是当前,栈顶值）,过程,出口,：,释放数据段,（退栈）（,见教材302页）,opr,:case,a,of (*operator*),0,:begin(*return*),t,:=b-1;,恢复调用前栈顶,p,:=st+3;,送返回地址到,p,b,:=st+2,恢复调用前基地址,end;,附,目标代码的解释执行,过程,出口,RA,DL,SL,b,.,.,t,M,t,b,t,:=b-1;,p,:=st+3;,b,:=st+2,Q,附,目标代码的解释执行,调用过程,：,cal,:begin(*,generat,new block mark*),st+1:=,base,(,l,);,填写,静态链,st+2:=,b,;,填写,动态链,st+3:=,p,;,填写,返回地址,b,:=,t+1,;,被调用过程的基地址,p,:=,a,过程入口地址,a,送,p,end;,附,目标代码的解释执行,function,base,(l:integer):integer;,var,b1:integer;,begin,b1,:=,b,;(*find base l level down*),while,l0,do,begin,b1,:=s,b1,;l:=l-1;,end;,base,:=,b1,end(*base*);,附,目标代码的解释执行,base,(,l,:integer):integer;,b,b,b,m,p,0,b,b,q,附,运行时数据栈,S,的变化状态,教材25页,