PL0编译程序的实现ppt课件.ppt

《PL0编译程序的实现ppt课件.ppt》由会员分享，可在线阅读，更多相关《PL0编译程序的实现ppt课件.ppt（58页珍藏版）》请在三一办公上搜索。

1、第2章 PL/0编译程序的实现,本章目的：以PL/0语言的编译程序为实例,学习一个编译程序实现的基本步骤和相关技术,“PL/0语言的编译程序”是世界著名计算机科学家N.Wirth先生编写的。由于PL/0语言功能简单、结构清晰、可读性强，又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤，是一个非常合适的编译程序教学模型。,PL/0编译程序,类 pcode解释程序,类 pcode代码,PL/0源程序,输入,输出,PL/0编译程序功能的框架,第2章 PL/0编译程序的实现,步骤1. 源语言PL/0与目标代码类pcode 之间的映射步骤2.

2、PL/0编译程序的总体设计步骤3. PL/0编译程序词法分析的设计与实现步骤4. PL/0编译程序语法语义分析的设计与实现步骤5. PL/0编译程序代码生成的实现*步骤6. PL/0编译程序错误处理的实现步骤7. 类pcode代码解释器的设计与实现,步骤1 PL/0程序到类pcode代码的映射,目标代码类pcode是一种假想栈式计算机的汇编语言。 指令格式,f l a,f功能码l层次差 （标识符的引用层减去它的定义层）a根据不同的指令有所区别,假想栈式计算机的运行栈T是栈顶指针B是基地址：分配给一个过程数据空间的开始位置,T,B,每个过程被调用时分配一段数据空间，变量的位置从3开始（每个变量占

3、用一个单元）。运行结束释放该数据空间,SL,DL,RA,210,步骤1 PL/0程序到类pcode代码的映射,下面给出 PL/0程序到类pcode代码的映射。（编译过程是按源程序顺序进行分析的）（常量、变量的说明部分不产生目标代码）,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入口,为过程

4、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

5、 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 结束退栈,步骤2 PL/0编译程序的总体设计,词法分析程序,语法语义分析程序,代码生成程序,表格管理程序,出错处理程序,PL/0源程序,目标程序,步骤2 PL/0编译程序的总体设计,其编

6、译过程采用一趟扫描方式 以语法、语义分析程序为核心 词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。,步骤2 PL/0编译程序的总体设计,表格管理程序：建立变量，常量和过程标识符的说明与引用之间的信息联系。出错处理程序：对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和错误性质。下面将介绍某些部分实现的关键技术。,步骤3 PL/0编译程序词法分析的 设计与实现,词法分析过程:GETSYM框图（见教材15页图2.5）程序文本（见教材290-292页）当识别到标识符时先查关键字表

7、（关键字表是按第1个字母的大小顺序排列的，用二分法查找）关键字表：（见教材304页主程序）word1:=begin ;word2:=call ； .word13:=write ;,步骤3 PL/0编译程序词法分析的 设计与实现,查到时找到关键字相应的内部表示wsym1:=beginsym; wsym2:=callsym; wsym13:=writesym;字符对应的单词表：ssym+:=plus; ssym-:=minus; ssym;:=semicolon;,步骤3 PL/0编译程序词法分析的 设计与实现,词法分析如何把单词传递给语法分析单词定义（见教材288页）type symbol=(n

8、ul,ident,number,plus, varsym,procsym); （ 定义纯量/枚举类型，类似C的enum）sym:symbol;id:alfa;(type alfa=packed array1.al of char) al=10;num:integer;,步骤3 PL/0编译程序词法分析的 设计与实现,通过三个全程量 SYM 、ID和NUM 将识别出的单词信息传递给语法分析程序。SYM：存放单词的类别 如：begin beginsym, initial ident, 60 numberID： 存放用户所定义的标识符的值 如： initial （在SYM中放ident，在ID中放i

9、nitial）NUM：存放用户定义的数 如：60 （在SYM中放number，在NUM中放60）,步骤4 PL/0编译程序语法、语义 分析的设计与实现,语法分析的设计与实现自顶向下的语法分析递归子程序法,自顶向下的语法分析,现以读语句为例：VAR A;BEGIN READ(A)END.,PL/0语言文法的EBNF表示（部分）,程序:=分程序. 分程序=常量说明部分变量说明部分过程说明部分语句 变量说明部分=VAR标识符，标识符；标识符=字母字母|数字 语句=赋值语句|条件语句|当型循环语句|过程调用语句|读语句|写语句|复合语句|空复合语句=BEGIN 语句；语句 END读语句=READ（标识

10、符 ，标识符）,读语句的自左向右推导过程,程序分程序. 变量说明部分语句. VAR标识符；语句. VAR A ；语句. VAR A ；复合语句. VAR A ；BEGIN语句END . VAR A ；BEGIN读语句END . VAR A ；BEGIN READ（标识符）END . VAR A ；BEGIN READ（ A）END .,推导和语法树的构造规则,自左向右推导每一步是对最左边的非终结符用规则右部的某一候选替换它。语法树的构造是自顶向下，自左向右，若以EBNF某一规则的左部为父结点，那么它的右部的某一候选为子结点。 EBNF中红色为推导和构造例子语法树时所选文法规则的右部。,自顶向下

11、的语法分析树,VAR A;BEGIN READ(A)END., . VAR ； A BEGIN END READ （ ） A,为文法的开始符号，以开始符号作为根结点,构造一棵倒挂着的语法树。树的末端结点刚好为输入的终结符号串。,规则的左部为父结点，它的右部的某一候选为子结点,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,从语法图看自顶向下分析思想,从语法图看自顶向下分析思想,(,ident,begin,),；,语句,end,read,，,复合语句,读语句,语句,ident,.,.,.,从语法图看自顶向下分析思

12、想,因子,ident,number,(,表达式,),递归子程序法,实现自顶向下分析用递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元（这个语法单元可能是递归进入），再沿当前所进入的语法单元所指箭头方向继续进行分析。,递归子程序法,当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序），再读取下一个单词继续分析。遇到分支点时，将当前的单词

13、与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。,编译程序总体流程图,语义分析与处理,说明部分的分析表格管理 过程体的分析,说明部分的分析,对每个过程说明的对象（变量，常量和过程）造名字表填写标识符的所在层次、属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成。,说明部分的分析（程序）,object= (constant, variable,procedur)（定义纯量/枚举类型用以区分标识符的属性）Table:array0.txmax of record name:alfa; case kind:object o

14、f constant:(val:integer); variable:procedur:(level,adr,size: integer); end;,Table的数组元素为变体记录型,相当C的union,分程序的定义（程序）,对分程序的定义（见教材292页） procedure block(lev,tx:integer;fsys:symset); var dx:integer; (*data allocationindex*) tx0:integer; (*initial table index*) cx0:integer; (*initial code index*)（ tx0是保留本过程

15、名在名字表中的位置； cx0 是保留本过程目标代码的起始位置）lev：本过程所在层次（主程序为0层）tx+1： 本过程的标识符在Table表中的起始位置fsys：出错处理用,分程序体人口的处理（程序）,对分程序体人口的处理（见教材300页block 的过程体） begin (*block*) dx:=3; （为该过程变量分配存储空间的起始位置，也就是相对基地址的偏移量） tx0:=tx; （保留当前table表指针值，是该过程名在table表中的位置） tabletx.adr:=cx;（保留当前code指针值到过程名的adr域） gen(jmp,0,0);（生成转向过程体入口的指令，地址待回填

16、）,分程序体人口的处理（程序）,其中： cx 已保留在过程名的adr域，等生成 过程体入口的指令时，再由tabletx.adr中找到 cx将过程体入口返填到cx中，即 （ jmp,0,0）的第3区域。同时将过程体入口填到过程名的tabletx.adr中。,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

17、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)（条件不满

18、足转）(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 结束退栈,CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G,分程序人口的处理,名字 类型 层次/值 地址 存储空间,(0) j

19、mp 0 0 CX：(1 ) jmp 0 0,tabletx.adr:=cx;记录 过程在code的入口到table中的adr域,tx,过程体入口时的处理,过程体入口时的处理codetabletx0.adr.a:=cx; （回填过程入口地址到code的a中）with tabletx0 do begin adr:=cx; （过程的入口填 写在table中） size:=dx; （过程占的空间填 写在table中） end; cxo:=cx; gen(int,0,dx);（生成过程入口指令）,保留过程在code中的入口地址，打印目标代码用,CONST A=35;B=49; VAR C，D，E;PR

20、OCEDURE P;VAR G,过程体入口时的处理,名字 类型 层次/值 地址 存储空间,(0) jmp 0 0(1 ) jmp 0 0 . . . ( cx ) int 0 4,codetabletx0.adr .a:=cx; tabletx0.adr :=cx;填写过程在code和table中的入口地址,tx0,过程体的分析,从语法上要对语句逐句分析。当语法正确时，就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。,步骤5 PL/0编译程序代码生成的实现,CX：为

21、目标代码code数组的下标指针。 code为一维数组，数组元素为记录型数据。code:array0.cxmax of instructioninstruction=packed record f:fct; l:0.levmax; a:0.amax; end; fct=（lit,opr,lod,sto,cal,int,jmp,jpc),步骤5 PL/0编译程序代码生成的实现,每一个记录就是一条目标指令。CX使用时为整数变量，由0开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。dx: 计算每个变量在运行栈中相对本过程基地址的偏移量 ，放在table表中的adr域，生成

22、目标代码时再放在code中的a域。目标代码生成时所用到的变量地址和层差等信息是由名字表table提供的，而名字表的信息是在说明时填写的。,变量在code cx 、tabletx和st之间的信息联系,下标指针cx，tx和变量dx的作用code cx tabletx s t (运行栈) t(运行时栈指针),(0) jmp 0 0(i ) int 0 7 . (n)sto 0 dx (cx ) .,(0) name adr.(i ) a (dx) . ( tx),pa,m,dx,b,t,步骤6 PL/0编译程序语法错误处理的实现,对语法错误的两种处理方法：(1) 对于易于校正的错误，如丢了逗号，分号

23、等，指出出错位置，加以校正，继续进行分析。(2) 对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。 为了实现第(2)种处理方法，需引入文法的开始符号集合与后继符号集合。,步骤6 PL/0编译程序语法错误处理的实现,在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。在语法单位分析结束时，调用TEST,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于，则滤去后继符号和开始符号集合外的所有符号。, TEST TEST,TEST,SYM在S1中?,

24、打印出错编号n,S1:=S1+S2,SYM在S1中?,GETSYM,返回,Y,Y,N,N,TEST测试过程流程图,test(s1,s2:symset;n:integer);,步骤7 类pcode代码解释器的实现,类pcode解释器的结构解释执行的流程图目标代码解释执行时数据栈的布局（运行栈的存储分配）,类pcode解释器的结构,目标代码存放在数组CODE中。解释程序定义一个一维整型数组S作为运行栈栈顶寄存器（指针）t，基址寄存器（指针）b，程序地址寄存器p，指令寄存器i当一个过程被调用时，就在运行栈（数据栈）分配相应的空间，过程执行结束就释放被分配的空间。,Interpret,3个寄存器赋初值

25、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,主程序看成0层分程序，P=0相当返回调用主程序的断点，即执行结束。,目标代码解释执行时数据栈的布局（运行栈的存储分配）,在每个过程被调用时在栈顶分配3个联系单元：SL： 静态链，指向定义该过程的直接外过程 （或主程序）运行时最新数据段的基地址。DL： 动态链，指向调用该过程前正在运行过 程的数据段基地址。RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的

26、地址。,目标代码的解释执行,几条特殊指令在code中的位置和功能cal l a调用过程，并完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器b中，目标程序的入口地址a的值送指令地址寄存器P中，使指令从a开始执行。,目标代码的解释执行,调用过程：cal: begin (*generat new block mark*) st+1:=base(l); 填写静态链 st+2:=b; 填写动态链 st+3:=p; 填写返回地址 b:=t+1; 被调用过程的基地址 p:=a 过程入口地址a送p end;,调用过程指令的解释执行示意图,调用过程： 运行栈S(t) cal l a,R

27、A DL SL,b,.,t,M,t,b,指令格式： cal l ast+1:= base(l)*见后st+2:=b;st+3:=p;b:=t+1;p:=at的修改由int完成,Q,例：M定义Q并调用Q,目标代码的解释执行,几条特殊指令在code中的位置和功能int 0 a在过程目标程序的入口处，开辟a个单元的数据段。a为局部变量的个数+3。opr 0 0在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器b和栈顶寄存器t的值，并将返回地址送到指令地址寄存器p中，以使调用前的程序从断点开始继续执行。,目标代码的解释执行,几条特殊指令的解释执行：过程入口：开

28、辟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;,过程出口指令的解释执行示意图,过程出口 运行栈S(t)opr 0 0,RA DL SL,b,.,t,M,t,b,t:=b-1;p:=st+3;b:=st+2,Q,函数 base(l:integer)执行的示意图,base (l:integer): integer; 运行栈S

29、(t),b,b,b,m,h,SL=0,SL=b,SL=b,q,例：q引用m的变量时层次差 l为2，所以需寻找 m的基地址b。由q 的SL找到h 的基地址b 再由h 的SL找到m 的基地址b 。,var a;proc h; var c; proc q; a:=8; . call q; . .call h;,m h q,a,函数 base(l:integer)程序,function base(l:integer): integer; var b1:integer; begin b1:=b; (*find base l level down*) while l0 do begin b1:=sb1;

30、l:=l-1; end; base:=b1 end (*base*);,的语法语义处理,已知PL/0语言的的语法图和EBNF如下： 语法图: (while) (do) EBNF为： ：= while do 试在下面方框中填入相应程序（或用文字说明）以完成它的语法语义处理程序。,条件,语句,的流程图,条件,t,语句,Jmp入口,f,循环出口,循环入口,if sym = whilesym then begin cx1:=cx; （保留循环入口地址） getsym; condition(dosym + fsys); cx2:=cx; （保留条件假出口地址） gen(jpc,0,0); if sym = dosym then getsym else error()； statement(fsys);（条件真时应执行的语句） gen(jmp,0,cx1); （无条件转向循环入口） codecx2.a:=cx; （回填条件假出口） end;,