PL0 编译程序讲解PPT课件

精选,1,第二章PL/0编译程序的实现,本章以PL/0编译程序为实例,使大家对编译程序的实现建立起整体概念，对编译程序的构造得到一些感性认识和初步了解。1PL/0语言2PL/0处理机假想栈式机3PL/0编译程序4符号表的一般形式讨论5栈式存储管理的再讨论,精选,2,1PL/0语言,PL/0功能简单、结构清晰、可读性强，而又具备了一般高级语言的必备部分，因而其编译程序能充分体现一个高级语言编译程序的基本技术和步骤。PL/0语言：PASCAL语言的子集，用于教学PL/0程序示例PL/0的语法描述图PL/0语言的EBNF表示,精选,3,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+、-、*、/、=、=、(、),精选,4,PL/0程序示例,CONSTA=10;（*常量说明部分*）VARB,C;（*变量说明部分*）PROCEDUREP;（*过程说明部分*）VARD;（*P的局部变量说明部分*）PROCEDUREQ;（*P的局部过程说明部分*）VARX;BEGINREAD(X);D:=X;IFX#0DOCALLP;END;BEGINCALLQ;WRITE(D);END;BEGINCALLP;END.,精选,5,递归计算sum=1!+2!+.+n!,varn,m,fact,sum;递规计算fact=m!procedurefactorial;beginifm0thenbeginfact:=fact*m;m:=m-1;callfactorial;end;end;,begin读入nread(n);sum:=0;whilen0dobeginm:=n;fact:=1;callfactorial;sum:=sum+fact;n:=n-1;end;输出n!write(sum);end.,精选,6,const,ident,number,var,ident,procedure,ident,分程序,语句,分程序,程序,分程序,.,语法图,精选,7,ident,read,end,语句,表达式,：=,begin,语句,语句,),(,ident,精选,8,PL/0语言的EBNF表示,BNF（BACKUS-NAURFORM）与EBNF的介绍BNF是根据美国的JohnW.Backus与丹麦的PeterNaur来命名的，它是从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序。构成EBNF的元素：非终结符，终结符，开始符，规则EBNF的元符号：用左右尖括号括起来的内容为非终结符=或读做定义为，的左部由右部定义|读做或表示右部候选内容表示花括号内的内容可重复任意次或限定次数表示方括号内的内容为任选项()表示圆括号内的内容优先,精选,9,PL/0语言文法的EBNF表示,程序-分程序.分程序-常量说明部分-CONST常量定义部分，常量定义；无符号整数-数字数字变量说明部分-VAR标识符，标识符；标识符-字母字母|数字B-C-B-先调用，后结束,二、运行时数据的存储与访问-栈式存储,假设A、C同层，且A中嵌套B,子程序的调用、执行和返回过程被调用时，子程序的每次调用都需在数据栈顶为其分配独立的数据区子程序返回时，需做两件事情：一是代码返回（需记住RA），二是数据区的同步恢复（DL）子程序运行时，要存取外层数据区中的存储单元,当前B数据区须记住：返回地址RA动态链DL记录调用者数据区基地址静态链SL记录定义该过程的直接外层过程数据区的基地址，以便访问外层数据,精选,12,运行时数据栈S的变化,varm1,m2,m3;ProcedureA;vara1;procedureB;varb1,b2;procedureC;C过程callB;r1:B过程callC;r2:A过程callB;r3:主程序CallA;r4:,精选,13,三、PL/0机的指令系统,f:功能码l:层次差（标识符引用层减去定义层）a:根据不同的指令有所区别,fla,指令格式：,所有运算对栈顶的两个或一个元素进行，并用运算结果代替原来的运算对象。,精选,14,指令功能表,精选,15,(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03为过程p开辟空间(3)lod13(4)lit010(5)opr02(6)sto14(7)opr00退栈并返回调用点(8)int05(9)opr016(10)sto03(11)lod03(12)lit00(13)opr09(14)jpc024条件不满足转24(15)cal02(16)lit02(17)lod04(18)opr04(19)opr014(20)opr015换行(21)opr016(22)sto03(23)jmp011(24)opr00,RA16,运行栈,consta=10;varb,c;procedurep;beginc:=b+a;end;beginread(b);whileb#0dobegincallp;write(2*c);read(b);endend.,SL：静态链DL：动态链RA：返回地址,0,演示执行过程,精选,16,3PL/0编译程序的实现,PL/0编译程序的总体设计PL/0编译程序词法分析的设计与实现PL/0编译程序语法分析的设计与实现PL/0编译程序语义分析的设计与实现PL/0编译程序语法错误处理的实现PL/0编译程序代码生成的实现pcode代码解释器的设计与实现,精选,17,3.1PL/0编译程序的总体设计,单趟方式以语法、语义分析程序为核心，词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。表格管理程序实现变量，常量和过程标识符的信息的登录与查找。出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编号，并进行错误恢复。,精选,18,PL/0编译程序,PL/0编译程序,类pcode解释程序,类pcode代码,PL/0源程序,输入数据,输出数据,PL/0编译程序的结构框架,精选,19,PL/0编译程序的结构,词法分析程序,语法语义分析程序,代码生成程序,表格管理程序,出错处理程序,PL/0源程序,目标程序,精选,20,编译系统总体流程图,PL/0编译程序语法、语义分析的核心,精选,21,3.2PL/0编译程序词法分析的实现,词法分析函数getsym()所识别的单词：保留字或关键字：如：BEGIN、END、IF、THEN等运算符：如：+、-、*、/、：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数：如：10、25、100等整数界符：如：,、.、;、(、)等,词法分析过程:getsym()框图（P19图2.5）,在编译程序中，单词的表示方式：（sym,id/num）,精选,22,enumsymbolnul,ident,number,plus,varsym,procsym；当识别出标识符时先查保留字表保留字及内部表示对应表：charwordnorwal;enumsymblewsymnorw;字符对应的单词表：enumsymblessym256;ssym+=plus;ssym-=minus;词法分析通过三个全程量symbolsym;charid;intnum;将识别出的单词信息传递给语法分析程序。sym：存放单词的类别如：initial:=60；中各单词对应的类别为：initialident,:=becomes,60number,;semicolonid：存放用户标识符,对initial（sym-ident，id-initial）num：存放用户定义的数对60（sym0)b1=sb1;l=l-1;returnb1;,精选,55,4符号表的一般形式讨论,1、符号表的作用和内容语义检查的依据；目标代码生成阶段地址分配的依据；在编译中，符号表被频繁使用，表的组织方式对编译的效率起着十分重要的作用。符号表中，包括名字、种类、类型、层次、相对地址、存储类别等名字的属性信息，以及动态数组的内情向量、记录结构型的成员信息、函数及过程的形参等结构信息。2、符号表的组织方式：线性表、散列表、树结构，符号表的组织方式必须维持源程序中的作用域信息。,精选,56,栈符号表：函数或分程序的嵌套结构，使得程序中出现的符号的处理（内层可引用外层符号、同名变量内层优先）与栈的操作相一致。一个过程结束时将释放相应的子符号表-解决作用域检查问题。3、符号表的操作：创建符号表：在编译开始时或进入一个分程序插入表项：定义时（包括变量和形参定义）查询表项：可执行语句使用时修改表项：在获得新的语义值信息时进行删除一个或一组无用的项释放符号表的空间：在编译结束前或退出一个分程序4、符号表的生存期对多遍扫描的编译程序，不同遍所用的符号表也往往不同。编译中的大部分符号表的生存期是编译过程，个别特殊表（动态数组的内情向量等）需保留到运行阶段5、符号表实例-单遍扫描,精选,57,programsort(input,output)vara:array0.10ofinteger;x:integer;procedurereadarray;vari:integer;begin.a.endreadarray;procedureexchange(i,j:integer);beginx:=ai;ai:=aj;aj:=xend;procedurequicksort(m,n:integer);vark,v:integer;functionpartition(y,z:integer):integer;vari,j:integer;begin.a.exchange(i,j);.end;begin.endquicksort;begin.endsort.,精选,58,P4的符号表：嵌套层次表+二叉查找树,标准名字表（integer,false,）二叉树,当前层top,同一层内全部名字的标识符记录利用左链和右链连接在一起形成二叉查找树,top,01234,sort,sorta,xreadarray()iexchange(i,j)quicksort(m,n)k,vpartition(y,z)i,j,栈-指出当前活动着的各嵌套的过程,精选,59,consta=1,b=2,c=3;varstep;proceduremove(n,from,buf,to);beginifn0/递归总是有条件的begincalmove(n-1,from,to,buf);write(from,“,to);step:=step+1;calmov