《【教学课件】第2章PL0编译程序的实现.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章PL0编译程序的实现.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理 台州学院 应建健1第第2章章 PL/0编译程序的实现编译程序的实现2.1 2.1 PL/0PL/0语言描述语言描述语言描述语言描述2.2 2.2 PL/0PL/0编译程序的结构编译程序的结构编译程序的结构编译程序的结构2.3 2.3 PL/0PL/0编译程序的词法分析编译程序的词法分析编译程序的词法分析编译程序的词法分析2.4 2.4 PL/0PL/0编译程序的语法分析编译程序的语法分析编译程序的语法分析编译程序的语法分析2.5 2.5 PL/0PL/0编译程序的目标代码结构和代码生成编译程序的目标代码结构和代码生成编译程序的目标代码结构和代码生成编译程序的目标代码结构和代码生成2.
2、6 2.6 PL/0PL/0编译程序的语法错误处理编译程序的语法错误处理编译程序的语法错误处理编译程序的语法错误处理2.7 2.7 PL/0PL/0编译程序的目标代码解释执行时的存编译程序的目标代码解释执行时的存编译程序的目标代码解释执行时的存编译程序的目标代码解释执行时的存储分配储分配储分配储分配编译原理 台州学院 应建健2何为何为PL/0PL/0语言语言?PL/0PL/0语言：语言：PASCALPASCAL语言的子集语言的子集，功能简单，功能简单，结构清晰，可读性强，具备了一般高级语结构清晰，可读性强，具备了一般高级语言的必备部分言的必备部分编译原理 台州学院 应建健3CONST A=10
3、;CONST A=10;VAR B,C;VAR B,C;PROCEDURE P;PROCEDURE P;VAR D;VAR D;PROCEDURE Q;PROCEDURE Q;VAR X;VAR X;BEGINBEGIN READ(X);READ(X);D:=X;D:=X;WHILE X#0 DO CALL P;WHILE X#0 DO CALL P;END;END;BEGIN BEGIN WRITE(D);WRITE(D);CALL Q;CALL Q;END;END;BEGINBEGIN CALL P;CALL P;END.END.PL/0PL/0程序示例程序示例编译原理 台州学院 应建健4
4、PL/0PL/0编译程序编译程序pcodepcode解释解释程序程序PL/0源程序源程序注：此处的注：此处的pcode代码专指代码专指PL/0的的目标码，注意与传统目标码，注意与传统pcode的区别的区别pcode代码代码编译原理 台州学院 应建健5PL/0语言描述：语言描述：PL/0 语言的非形式描述语言的非形式描述PL/0 语言的语言的语法描述图语法描述图PL/0 语言文法的扩充的巴科斯语言文法的扩充的巴科斯-瑙尔范式瑙尔范式（EBNF）表示）表示编译原理 台州学院 应建健6PL/0 PL/0 语言的非形式描述语言的非形式描述语言的非形式描述语言的非形式描述v数据类型只有整型数据类型只有整
5、型v标识符的有效长度是标识符的有效长度是1010，以字母开始，以字母开始的字母数字串的字母数字串v数最多为数最多为1414位位v过程无参，可嵌套（最多三层），可过程无参，可嵌套（最多三层），可递归调用递归调用v变量的作用域同变量的作用域同PASCALPASCAL，常量为全局常量为全局的，无标号的，无标号编译原理 台州学院 应建健7v语句类型：赋值语句，语句类型：赋值语句，if.then.,if.then.,while.do.,read,write,call,while.do.,read,write,call,复复合语句合语句begin.endbegin.end，说明语句：说明语句：const.
6、,var.,procedureconst.,var.,procedurev1313个保留字：个保留字：if,then,while,do,if,then,while,do,read,write,call,begin,end,const,read,write,call,begin,end,const,varvar,procedure,odd,procedure,odd编译原理 台州学院 应建健8PL/0 PL/0 语言的语法描述图语言的语法描述图语言的语法描述图语言的语法描述图（书本9-11页）编译原理 台州学院 应建健9PL/0 PL/0 语言文法的语言文法的语言文法的语言文法的 EBNF EB
7、NF 表示表示表示表示BNFBNF与与EBNFEBNF的介绍：的介绍：BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根据美国的是根据美国的John W.BackusJohn W.Backus与丹麦的与丹麦的Peter NaurPeter Naur来命名来命名的，它从语法上描述程序设计语言的的，它从语法上描述程序设计语言的元语言元语言。采用采用BNFBNF就可说明哪些符号序列是对于某给就可说明哪些符号序列是对于某给定语言定语言在语法上在语法上有效的程序。有效的程序。编译原理 台州学院 应建健10BNFBNF引入的符号：引入的符号：用左右尖括号括起来的字表示语法
8、构造成分，用左右尖括号括起来的字表示语法构造成分，或称或称语法单位语法单位，为，为非终结符非终结符非终结符非终结符=定义为定义为|或或EBNFEBNF引入的符号：引入的符号：表示花括号内的语法成分表示花括号内的语法成分可重复可重复 表示方括号内的语法成分为表示方括号内的语法成分为任选项任选项()()表示圆括号内的成分表示圆括号内的成分优先优先编译原理 台州学院 应建健11一个用一个用EBNFEBNF描述的例子：描述的例子：=+|-=+|-=0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9=+|-=+|-|0|0=1|2|3|4|5|6|7|8|9=1|2|3|4|
9、5|6|7|8|9 =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9编译原理 台州学院 应建健12PL/0PL/0语言文法的语言文法的EBNFEBNF表示：表示：程序程序=分程序分程序.分程序分程序=常量说明部分常量说明部分变量说明部分变量说明部分过程说过程说明部分明部分 语句语句常量说明部分常量说明部分=CONSTCONST常量定义部分常量定义部分，常量定义，常量定义；无符号整数无符号整数=数字数字 数字数字 变量说明部分变量说明部分=VARVAR标识符标识符，标识符，标识符；标识符标识符=字母字母 字母字母|数字数字 编译原理 台州学院 应建健13PL/0编
10、译程序的结构编译程序的结构其编译过程采用其编译过程采用一趟扫描一趟扫描方式方式以以语法分析语法分析程序为核心程序为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一程序都作为一个独立的过程，当语法分析需要读单词个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调正确需要生成相应的目标代码时，则调用代码生成程序。用代码生成程序。编译原理 台州学院 应建健14用用表格管理表格管理程序建立变量，常量和过程程序建立变量，常量和过程标识符的说明与引用之间的信息联系。标识符的说明与引用之间的信息联系。用用出错处
11、理出错处理程序对词法和语法分析遇到程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错的错误给出在源程序中出错的位置和错误性质。误性质。编译原理 台州学院 应建健15语法语义分析程序语法语义分析程序词法分析程词法分析程序序表格管理程序表格管理程序出错处理程序出错处理程序代码生成程序代码生成程序PL/0 PL/0 源程序源程序目标程序目标程序PL/0 PL/0 编译程序的结构图编译程序的结构图编译程序的结构图编译程序的结构图编译原理 台州学院 应建健162幅图：P.13编译原理 台州学院 应建健17PL/0PL/0编译程序的词法分析编译程序的词法分析z所需识别的单词：所需识别的单词：y基本
12、字（保留字）：基本字（保留字）：BEGINBEGIN、ENDEND、IFIF、THENTHEN等等y运算符：运算符：如如+、-、*、/、：、：=、#、=、=等等y标识符：标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名y常数：常数：如如1010、2525、100100等整数等整数y界符：界符：如如,、.、;、(、)等等编译原理 台州学院 应建健18词法分析过程词法分析过程GETSYMGETSYM所要完成的任务所要完成的任务滤空格滤空格识别保留字识别保留字识别标识符识别标识符拼数拼数拼复合词拼复合词输出源程序输出源程序编译原理 台州学院 应建健19z通过三个全程量将识别出
13、的单词信息传递给通过三个全程量将识别出的单词信息传递给语法分析程序，语法分析程序，SYMSYM，IDID，NUMNUMySYMSYM：存放单词的类别存放单词的类别,如如 beginsymbeginsym,identident,numbernumberyIDID：存放用户所定义的标识符的值存放用户所定义的标识符的值yNUMNUM：存放用户定义的数存放用户定义的数编译原理 台州学院 应建健20 程序程序 pl0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factorPL/0语语法法调调用用关关系系图图编译原
14、理 台州学院 应建健21编编译译程程序序总总体体流流程程图图编译原理 台州学院 应建健22说明部分的分析说明部分的分析对每个过程说明的对象（变量，常量和过对每个过程说明的对象（变量，常量和过程）造名字表程）造名字表填写所在层次，标识符的属性和分配的相对位填写所在层次，标识符的属性和分配的相对位置。标识符的属性不同时，所需填入的信息也置。标识符的属性不同时，所需填入的信息也不同。登录信息由不同。登录信息由ENTERENTER过程完成。过程完成。表格管理表格管理过程体的分析过程体的分析编译原理 台州学院 应建健23 名字名字 类型类型 层次层次/值值 地址地址 存储空间存储空间CONST A=35
15、CONST A=35，B=49B=49；VAR CVAR C，D D，E E；PROCEDURE PPROCEDURE P；VAR GVAR G表格管理表格管理编译原理 台州学院 应建健24目标代码目标代码 PCODEPCODE目标代码目标代码pcodepcode是是一种假想一种假想栈式栈式计算机的汇计算机的汇编语言。编语言。指令格式指令格式f l af l af f功能码功能码l l层次差层次差a a根据不同的指令有所区别根据不同的指令有所区别编译原理 台州学院 应建健25编译原理 台州学院 应建健260 jmp0 81 jmp0 22 int 0 33 lod 1 34 lit0 105
16、opr 0 2 次栈顶与栈顶相加次栈顶与栈顶相加6 sto 1 47 opr 0 08 int 0 5 在运行栈中申请在运行栈中申请5个栈空间个栈空间9 opr 0 16 从命令行读入输入置于栈顶从命令行读入输入置于栈顶10 sto 0 3 将栈顶值存入变量将栈顶值存入变量11 cal 0 2 调用过程调用过程12 lod 0 4 将变量取至栈顶将变量取至栈顶13 opr 0 14 栈顶值输出至屏幕栈顶值输出至屏幕14 opr 0 15 换行换行15 opr 0 0SL 0DL 0RA 0变量变量1变量变量2RA 12SL 0DL 0运行栈运行栈Const a=10;Const a=10;va
17、r b,c;var b,c;procedure p;procedure p;begin begin c:=b+a;c:=b+a;end;end;beginbegin read(b);read(b);call p;call p;write(c);write(c);end.end.SL：静态链静态链DL：动态链动态链RA：返回地址返回地址0编译原理 台州学院 应建健27PL/0PL/0语言的代码生成是由过程语言的代码生成是由过程GENGEN完成。完成。GENGEN有三个参数，分别代表目标代码的功能有三个参数，分别代表目标代码的功能码，层差和位移量。码，层差和位移量。gengen(opropr,0,
18、16);,0,16);gengen(stosto,levlev-level,-level,adradr)生成的代码顺序放在数组生成的代码顺序放在数组CODECODE中。中。CODECODE为一维数组，数组元素为记录型数据。每为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。一个记录就是一条目标指令。CXCX为指令的指针，为指令的指针，由由0 0开始顺序增加。实际上目标代码的顺序是开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。内层过程的在前边，主程序的目标代码在最后。PL/0PL/0编译程序代码生成编译程序代码生成编译原理 台州学院 应建健28PL/0
19、PL/0编译程序语法错误处理编译程序语法错误处理对语法错误的两种处理方法：对语法错误的两种处理方法：(1)(1)对于易于校正的错误，如丢了逗号，分对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续号等，指出出错位置，加以校正，继续进行分析。进行分析。(2)(2)对于难于校正的错误，给出错误的位对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单下一个可以进行正常语法分析的语法单位。位。编译原理 台州学院 应建健29在进入某个语法单位时，调用在进入某个语法单位时，调用TESTTEST滤去滤去开开始
20、符号始符号前的所有符号。前的所有符号。在语法单位分析结束时，调用在语法单位分析结束时，调用TESTTEST滤去当滤去当前符号到前符号到后继符号后继符号之间的所有符号。之间的所有符号。TEST TESTTEST TEST编译原理 台州学院 应建健30开始符号集合与后继符号集合开始符号集合与后继符号集合编译原理 台州学院 应建健31TESTSYM在在S1中中?打印出错编号打印出错编号nS1:=S1+S2SYM在在S1中中?GETSYM返回返回YYNNTEST 测测试试过过程程流流程程图图编译原理 台州学院 应建健32pcodepcode代码解释器的实现代码解释器的实现pcode解释器的结构解释器的
21、结构解释执行的流程图解释执行的流程图目标代码解释执行时的存储分配目标代码解释执行时的存储分配编译原理 台州学院 应建健33pcodepcode解释器的结构解释器的结构目标代码存放在数组目标代码存放在数组CODECODE中。中。解释程序定义的一维整型数组解释程序定义的一维整型数组S S作为运行栈作为运行栈栈项寄存器栈项寄存器t t，基址寄存器基址寄存器b b，程序地址寄程序地址寄存器存器p p，指令寄存器指令寄存器i i编译原理 台州学院 应建健34interpret三个寄存器赋初值三个寄存器赋初值t:=0;b:=1;p:=0;主程序的主程序的SL，DL，RA赋初值赋初值s1:=0;s2=0;s
22、3=0;i:=codep;p:=p+1;执行指令执行指令iP=0?返回返回解解释释执执行行的的流流程程图图编译原理 台州学院 应建健35目标代码解释执行时的存储分配目标代码解释执行时的存储分配几条典型指令的存储分配几条典型指令的存储分配INT 0 AINT 0 A位于过程目标程序的入口，开辟位于过程目标程序的入口，开辟A A个单元的数个单元的数据段。据段。A A为局部变量个数为局部变量个数+3+3OPR 0 0OPR 0 0位于过程目标程序的出口，释放数据段（退栈）位于过程目标程序的出口，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段，恢复调用该过程前正在运行的过程的数据段基址寄存器基址寄存器B B和栈顶寄存器和栈顶寄存器T T的值，并将返回地的值，并将返回地址送到指令地址寄存器址送到指令地址寄存器P P中，以使调用前的程中，以使调用前的程序从断点开始继续执行序从断点开始继续执行编译原理 台州学院 应建健36CAL L ACAL L A调用过程，还完成填写静态链、动态链、返回调用过程，还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址地址，给出被调用过程的基地址值，送入基址寄存器寄存器B B中，目标程序的入口地址中，目标程序的入口地址A A的值送指令的值送指令地址寄存器地址寄存器P P中，使指令从中，使指令从A A开始执行。开始执行。