PL0编译程序.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,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,；,查到时找到相应的,内部表示,Wsym1:=,beginsym,;wsym2:=,callsym,；,wsym13:=,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 tabletx do,(*,开域,语句*）,begin,name,:=,id,;(*,表示,tabletx.,name,:=,id,;*,）,kind,:=,k,;(*,表示,tabletx.,kind,:=,k,;*),过程,ENTER,的实现,case,k,of,constant,:,begin if,num,amax then,begin error(31);,num,:=0;end;,val,:=,num,;(*,tabletx.,val,:=,num,;*)end;,过程,ENTER,的实现,variable,:,begin,level,:=,lev,;,（*表示,tabletx.,level,:=,lev,*,）,adr,:=,dx,;,（*表示,tabletx.,adr,:=,dx,*,）,dx:=dx+1;end;,procedur,:,level,:=,lev,(*,表示,tabletx.,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 codecx do,begin,f,:=,x,;,（*表示,codecx.,f,:=,x,;*),l,:=,y,;,（*表示,codecx.,l,:=,y,;*),a,:=,z,;,（*表示,codecx.,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,表,指针值,）,tabletx.,adr,:=,cx,;,（,保留当前,code,指针值到过程名,的,adr,域,）,gen(jmp,0,0);,（生成转向,过程体入口的指令，该指令的地址 为,cx,已保留在过程名的,adr,域，,等生成,过程 体入口的指令时，再由,tabletx.,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,页,