东北大学秦皇岛分校编译原理课件第二章.ppt

上传人:小飞机 文档编号:5907641 上传时间:2023-09-02 格式:PPT 页数:45 大小:248KB
返回 下载 相关 举报
东北大学秦皇岛分校编译原理课件第二章.ppt_第1页
第1页 / 共45页
东北大学秦皇岛分校编译原理课件第二章.ppt_第2页
第2页 / 共45页
东北大学秦皇岛分校编译原理课件第二章.ppt_第3页
第3页 / 共45页
东北大学秦皇岛分校编译原理课件第二章.ppt_第4页
第4页 / 共45页
东北大学秦皇岛分校编译原理课件第二章.ppt_第5页
第5页 / 共45页
点击查看更多>>
资源描述

《东北大学秦皇岛分校编译原理课件第二章.ppt》由会员分享,可在线阅读,更多相关《东北大学秦皇岛分校编译原理课件第二章.ppt(45页珍藏版)》请在三一办公上搜索。

1、第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程序示

2、例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,=,;

3、,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 作用域规则(内层可引用包围它的外层定义的标识符),上下文约束,过程

4、可嵌套定义,可递归调用子集数据类型,只有整型数据结构,只有简变和常数数字最多为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

5、转向过程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

6、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编译程序的总体设计,其编译过程采用一趟扫描方式以语法、语义分析程序为核心 词

7、法分析程序和代码生成程序都作为一个过程,当语法分析需要读单词时就调用词法分析程序,而当语法、语义分析正确,需要生成相应的目标代码时,则调用代码生成程序。表格管理程序实现变量,常量和过程标识符的信息的登录与查找。出错处理程序,对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误 性质有关的编号,并进行错误恢复。,PL/0编译程序词法分析的设计与实现,识别的单词:保留字或关键字:如:BEGIN、END、IF、THEN等运算符:如:+、-、*、/、:=、#、=、=等标识符:用户定义的变量名、常数名、过程名常数:如:10、25、100等整数界符:如:,、.、;、(、)等,词法分析过程GET

8、SYM所要完成的任务:读源程序(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;词法分析如何把单词传递给语法分析 ty

9、pe 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

10、)NUM:存放用户定义的数 如:60(在SYM中放在number在NUM中放60),使用状态转换图实现词法分析程序的设计方法,词法分析程序的设计-使用状态转换图实现,表示状态,对应每个状态编一段程序,每个状态调用取字符程序,根据当前字符转到不同的状态,并做相应操作。,表示终态,已识别出一个单词。,PL/0编译程序语法语义分析 PL/0编译程序语法分析的设计与实现,自顶向下的语法分析递归子程序法,程序,分程序,.,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,ident,read,end,;,语句,表达式,:=

11、,begin,语句,语句,),(,ident,自顶向下的语法分析,VAR A;BEGIN READ(A)END.,.VAR;A BEGIN END READ()A,为文法的开始符号,以开始符号作为根结点构造一棵倒挂着的语法树。,递归子程序法,递归子程序法:对应每个非终结符语法单元,编一个独立的处理过程(或子程序)。语法分析从读入第一个单词开始,由非终结符(即开始符)出发,沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时,则调用相应的处理过程,从语法描述图看,也就进入了一个语法单元,再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时,则判断当前读入的单词是否与图中的

12、终结符相匹配,若匹配,再读取下一个单词继续分析。遇到分支点时,将当前的单词与分支点上多个终结符逐个相比较,若都不匹配时可能是进入下一个非终结符语法单位或是出错。,程序 pl0,分程序 block,语句 statement,条件 condition,表达式expression,项 term,因子 factor,语法调用关系图,编译程序总体流程图,PL/0编译程序语义分析的设计与实现,PL/0编译程序语法、语义分析的的核心程序是BLOCK过程,说明部分的分析与处理表格管理过程体(语句)的分析与处理,说明部分的分析与处理,对每个过程(含主程序)说明的对象(变量,常量和过程)造符号表 登录标识符的属性

13、。标识符的属性:种类,所在层次,值和分配的相对位置。登录信息由ENTER过程完成。,例程序说明部分为:CONST A=35,B=49;VAR C,D,E;PROCEDURE P;VAR G;,符号表,名字 种类 层次/值 地址 存储空间,对应名字表,tx:table表的下标指针,是以值参数形式使用的。dx:计算每个变量在运行栈中相对本过程基地址的偏移量,放在table表中的adr域,生成目标代码时再放在code中的a域,过程体的处理,对语句进行语法分析语义分析 当遇到标识符的引用时就调用POSITION函数查TABLE表,看是否有过正确定义,若已有,则从表中取相应的有关信息,供代码的生成使用。

14、若无定义则错。当语法语义正确时,就生成相应语句功能的目标代码,代码生成,代码生成是由过程GEN完成。GEN有3个参数,分别代表目标代码的功能码,层差和位移量。例如 gen(opr,0,16);gen(sto,lev-level,adr)lev:当前处理的过程层次 level:被引用变量或过程所在层次CX:为目标代码code数组的下标指针,PL/0编译程序错误处理的实现,对语法错误的两种处理方法:(1)对于易于校正的错误,如丢了逗号,分号等,指出出错位置,加以校正,继续进行分析。(2)对于难于校正的错误,给出错误的位置与性质,跳过后面的一些单词,直到下一个可以进行正常语法分析的语法单位。,在进入

15、某个语法单位时,调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于,则滤去开始符号和后继符号集合外的所有符号。在语法单位分析结束时,调用TEST,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于,则滤去后继符号和开始符号集合外的所有符号。,TEST TEST,类pcode代码解释器的实现,类pcode解释器的结构目标代码解释执行时数据栈的布局(运行栈的存储分配),类pcode解释器的结构,目标代码存放在数组CODE中。解释程序定义一个一维整型数组S作为运行栈栈顶寄存器(指针)t,基址寄存器(指针)b,程序地址寄存器p,指令寄存器i,目标代码解释执行时数据栈的布

16、局(运行栈的存储分配),在每个过程调用时在栈顶分配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开始执行。,附 运行时数据栈S的变化状态,教材25页,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号