您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 招聘面试 > PL0 编译程序讲解
第二章PL/0编译程序的实现本章以PL/0编译程序为实例,使大家对编译程序的实现建立起整体概念,对编译程序的构造得到一些感性认识和初步了解。§1PL/0语言§2PL/0处理机—假想栈式机§3PL/0编译程序§4符号表的一般形式讨论§5栈式存储管理的再讨论§1PL/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程序示例CONSTA=10;(*常量说明部分*)VARB,C;(*变量说明部分*)PROCEDUREP;(*过程说明部分*)VARD;(*P的局部变量说明部分*)PROCEDUREQ;(*P的局部过程说明部分*)VARX;BEGINREAD(X);D:=X;IFX#0DOCALLP;END;BEGINCALLQ;WRITE(D);END;BEGINCALLP;END.递归计算sum=1!+2!+...+n!varn,m,fact,sum;{递规计算fact=m!}procedurefactorial;beginifm0thenbeginfact:=fact*m;m:=m-1;callfactorial;end;end;begin{读入n}read(n);sum:=0;whilen0dobeginm:=n;fact:=1;callfactorial;sum:=sum+fact;n:=n-1;end;{输出n!}write(sum);end.constidentnumber=,;varident,;;procedureident;分程序语句分程序程序分程序.语法图identreadend;语句表达式:=begin语句语句)(ident,PL/0语言的EBNF表示BNF(BACKUS-NAURFORM)与EBNF的介绍BNF是根据美国的JohnW.Backus与丹麦的PeterNaur来命名的,它是从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序。构成EBNF的元素:非终结符,终结符,开始符,规则EBNF的元符号:用左右尖括号括起来的内容为非终结符∷=或→读做‘定义为’,→的左部由右部定义|读做‘或’表示右部候选内容{}表示花括号内的内容可重复任意次或限定次数[]表示方括号内的内容为任选项()表示圆括号内的内容优先PL/0语言文法的EBNF表示〈程序〉-〈分程序〉.〈分程序〉-[常量说明部分][变量说明部分][过程说明部分]语句〈常量说明部分〉-CONST〈常量定义部分〉{,〈常量定义〉};〈无符号整数〉-〈数字〉{〈数字〉}〈变量说明部分〉-VAR〈标识符〉{,〈标识符〉};〈标识符〉-〈字母〉{〈字母〉|〈数字〉}……表达式〉∷=[+|-]〈项〉{(+|-)〈项〉}〈项〉∷=〈因子〉{(*|/)〈因子〉}〈因子〉∷=〈标识符〉|〈无符号整数〉|‘(’〈表达式〉‘)’……§2PL/0处理机—假想栈式机一、PL/0处理机简介目标代码类p-code:一种栈式机的汇编语言栈式机系统结构:没有累加器和寄存器,只有存储栈指针所有运算都在栈顶(零地址机)两种存储,一个指令寄存器和三个地址寄存器,运算在栈顶进行栈数据存储被解释执行程序存储S[]s[]CODE两种存储指令寄存器----I,放当前正在解释的指令地址寄存器B-PT基址寄存器指令指向下一条执行的目标程序地址寄存器栈顶地址寄存器若有执行调用序列:A-B-C-B---先调用,后结束B区A区B区C区BT二、运行时数据的存储与访问----栈式存储假设A、C同层,且A中嵌套B子程序的调用、执行和返回过程被调用时,子程序的每次调用都需在数据栈顶为其分配独立的数据区子程序返回时,需做两件事情:一是代码返回(需记住RA),二是数据区的同步恢复(DL)子程序运行时,要存取外层数据区中的存储单元当前B数据区须记住:①返回地址RA②动态链DL—记录调用者数据区基地址③静态链SL—记录定义该过程的直接外层过程数据区的基地址,以便访问外层数据运行时数据栈S的变化varm1,m2,m3;ProcedureA;vara1;procedureB;varb1,b2;procedureC;…C过程callB;r1:……B过程callC;r2:……A过程callB;r3:……主程序CallA;r4:…B的局部变量RADLSL…C的局部变量RADLSL…B的局部变量RADLSL…A的局部变量RADLSL…主程序变量区000TBB的临时单元b2=120b1=50RA:r1DL:115SL:106RA:r2DL:110SL:110b2=25b1=20RA:r3DL:106SL:106a1=15RA:r4DL:100SL:100m3=118m2=472m1=335RA:0DL:0TBSL:0100三、PL/0机的指令系统f:功能码l:层次差(标识符引用层减去定义层)a:根据不同的指令有所区别fla指令格式:所有运算对栈顶的两个或一个元素进行,并用运算结果代替原来的运算对象。LIT0a将常数值取到栈顶,a为常数值LODla将变量值取到栈顶,a为偏移量,l为层差STOla将栈顶内容送入某变量单元中,a为偏移量,l为层差CALla调用过程,a为过程地址,l为层差INT0a在运行栈中为被调用的过程开辟a个单元的数据区JMP0a无条件跳转至a地址JPC0a条件跳转,当栈顶布尔值非真则跳转至a地址,否则顺序执行OPR00过程调用结束后,返回调用点并退栈OPR01栈顶元素取反OPR02次栈顶与栈顶相加,退两个栈元素,结果值进栈OPR03次栈顶减去栈顶,退两个栈元素,结果值进栈OPR04次栈顶乘以栈顶,退两个栈元素,结果值进栈OPR05次栈顶除以栈顶,退两个栈元素,结果值进栈OPR06栈顶元素的奇偶判断,结果值在栈顶OPR07OPR08次栈顶与栈顶是否相等,退两个栈元素,结果值进栈OPR0kk分别为9-不等,10-小于,11-大于等于,12-大于,13-小于等于OPR014栈顶值输出至屏幕OPR015屏幕输出换行OPR016从命令行读入一个输入置于栈顶指令功能表(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)opr00SL0DL0RA0变量b变量cRA16SL0DL0运行栈consta=10;varb,c;procedurep;beginc:=b+a;end;beginread(b);whileb#0dobegincallp;write(2*c);read(b);endend.SL:静态链DL:动态链RA:返回地址0演示执行过程§3PL/0编译程序的实现PL/0编译程序的总体设计PL/0编译程序词法分析的设计与实现PL/0编译程序语法分析的设计与实现PL/0编译程序语义分析的设计与实现PL/0编译程序语法错误处理的实现PL/0编译程序代码生成的实现pcode代码解释器的设计与实现3.1PL/0编译程序的总体设计单趟方式以语法、语义分析程序为核心,词法分析程序和代码生成程序都作为一个过程,当语法分析需要读单词时就调用词法分析程序,而当语法、语义分析正确,需要生成相应的目标代码时,则调用代码生成程序。表格管理程序实现变量,常量和过程标识符的信息的登录与查找。出错处理程序,对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编号,并进行错误恢复。PL/0编译程序PL/0编译程序类p-code解释程序类p-code代码PL/0源程序输入数据输出数据PL/0编译程序的结构框架PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序表格管理程序出错处理程序PL/0源程序目标程序编译系统总体流程图启动置初值调用getsym取单词调用block过程当前单词是否为源程序结束符'.'?出错源程序中是否有错误?调用解释过程interpret解释执行目标程序打印错误结束NYYNPL/0编译程序语法、语义分析的核心3.2PL/0编译程序词法分析的实现词法分析函数getsym()所识别的单词:保留字或关键字:如:BEGIN、END、IF、THEN等运算符:如:+、-、*、/、:=、#、=、=等标识符:用户定义的变量名、常数名、过程名常数:如:10、25、100等整数界符:如:‘,’、‘.’、‘;’、‘(’、‘)’等词法分析过程:getsym()框图(P19图2.5)在编译程序中,单词的表示方式:(sym,id/num)enumsymbol{nul,ident,number,plus,…,varsym,procsym};当识别出标识符时先查保留字表保留字及内部表示对应表:charword[norw][al];enumsymblewsym[norw];字符对应的单词表:enumsymblessym[256];ssym[‘+’]=plus;ssym[‘-’]=minus;…词法分析通过三个全程量symbolsym;charid[];intnum;将识别出的单词信息传递给语法分析程序。sym:存放单词的类别如:initial:=60;中各单词对应的类别为:initialident,‘:=‘becomes,60number,‘;’semicolonid:存放用户标识符,对initial(sym-ident,id-initial)num:存放用户定义的数对60(sym-number,num-60)用状态转换图实现词法分析程序的设计方法状态,对应每个状态编一段程序,每个状态调用取字符程序,根据当前字符转到不同的状态,并做相应操作。表示终态,已识别出一个单词1235141312109786411空格字母字母数字非字母数字数字数字非数字:==非==非=,+-(……3.3PL/0编译程序语法分析语法分析的设计与实现自顶向下的语法分析递归子程序法(递归下降分析器recursive-descentparser):对应每个非终结符(语法成分),编一个独立的处理子程序。由程序开始,按规则右部(语法描述图箭头方向)进行分析遇到非终结符,则调用相应的处理过程遇到终结符,则判断当前读入的单词是否与该终结符相匹配,若匹配,再读取下一个单词继续分析。程序pl/0分程序block语句statement条件condition表达式expression项term因子factor语法调用关系图VARA;BEGINREAD(A)END.程序分程序.变量说明部分语句VAR标识符;复合语句ABEGIN语句END读语句READ(标识符)A程序为文法的开始
本文标题:PL0 编译程序讲解
链接地址:https://www.777doc.com/doc-4002572 .html