第二章edsl2.ppt

第2章 PL/0编译程序,本章目的：以PL/0编译程序为实例,学习编译程序实现的基本步骤和相关技术1 PL/0编译程序的结构2 PL/0编译程序的分析工作(词法，语法和语义）实现3 PL/0编译程序的错误处理方法4 目标代码生成和类pcode代码解释器,1.PL/0编译程序的结构,PL/0编译程序,PL/0 语言程序,类 pcode 代码,源语言(PL/0)目标语言(类 pcode)实现语言（pascal/C),PL/0,类 pcode,pascal/C,PL/0编译程序,类 pcode解释程序,类 pcode代码,PL/0源程序,输入数据,输出数据,PL/0编译系统的结构框架,PL/0语言,PL/0语言：PASCAL语言的子集 PL/0程序示例 PL/0的语法描述图 PL/0语言的EBNF表示,PL/0程序示例,CONST A=10;（*常量说明部分*）VAR B,C;（*变量说明部分*）PROCEDURE P;（*过程说明部分*）VAR D;（*P的局部变量说明部分*）PROCEDURE Q;（*P的局部过程说明部分*）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过程体,主程序体,输入圆柱的半径和高，计算一些面积、体积等,var r,h,len,a1,a2,volumn;beginread(r);read(h);len:=2*3*r;a1:=3*r*r;a2:=a1+a1+len*h;volumn:=a1*h;write(len);write(a1);write(a2);write(volumn);end.,计算最大公约数,var m,n,r,q;计算m和n的最大公约数 procedure gcd;begin while r#0 do begin q:=m/n;r:=m-q*n;m:=n;n:=r;endend;,begin read(m);read(n);为了方便，规定m=n if m n then begin r:=m;m:=n;n:=r;end;begin r:=1;call gcd;write(m);end;end.,pl/0程序-递规调用,var n;procedure rec;begin if n#0 then begin write(n);n:=n-1;call rec;end;end;begin read(n);call rec;end.,计算 sum=1!+2!+.+n!,n从控制台读入,var n,m,fact,sum;递规计算 fact=m!procedure factorial;begin if m 0 then begin fact:=fact*m;m:=m-1;call factorial;end;end;,begin 读入n read(n);sum:=0;while n 0 do begin m:=n;fact:=1;call factorial;sum:=sum+fact;n:=n-1;end;输出n!write(sum);end.,程序,分程序,.,内的文字表示语法成分（短语）,或,内的文字表示单词符号,程序,.,内的文字表示语法成分（短语）,语法图,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,PL/0语言的EBNF表示,构成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 作用域规则（内层可引用包围它的外层定义的标识符），上下文约束，过程可嵌套定义，可递归调用子集数据类型,只有整型数据结构,只有简变和常数数字最多为14位标识符的有效长度是10语句种类过程无参，最多可嵌套三层,目标代码类p-code,目标代码类p-code是一种栈式机的汇编语言。栈式机系统结构:没有累加器和寄存器，只有存储栈指针 所有运算都在栈顶（零地址机）指令格式：,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 转向过程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 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编译程序的总体设计,以语法、语义分析程序为核心 词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。表格管理程序实现变量，常量和过程标识符的信息的登录与查找。出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误 性质有关的编号，并进行错误恢复。,第2章 PL/0编译程序,本章目的：以PL/0编译程序为实例,学习编译程序实现的基本步骤和相关技术1 PL/0编译程序的结构2 PL/0编译程序的分析工作(词法，语法和语义）实现3 PL/0编译程序的错误处理方法4 目标代码生成和类pcode代码解释器,2 PL/0编译程序的分析工作(词法，语法和语义）2.1PL/0编译程序词法分析的实现,识别的单词：保留字或关键字：如：BEGIN、END、IF、THEN等运算符：如：+、-、*、/、：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数：如：10、25、100等整数界符：如：,、.、;、(、)等,词法分析过程GETSYM所要完成的任务：从源程序读字符（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;词法分析如何把单词传递给语法分析 type 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）NUM：存放用户定义的数 如：60（在SYM中放number,在NUM中放60）,使用状态转换图实现词法分析程序的设计方法,词法分析程序的设计-使用状态转换图实现,表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。,表示终态，已识别出一个单词。,2.2 PL/0编译程序语法分析,自顶向下的语法分析 递归子程序法,（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。对于一个给定的文法，要想判定一个符号串是否为该文法的句子，需要考察是否可以从该文法的开始符号派生出（推导出）此符号串。编译程序的语法分析工作。,分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,语法分析（从概念上讲）建立一棵与输入串相匹配的语法树。语法树推导的几何表示,句型aabbaa的可能推导序列和语法树,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,两种方法反映了语法树的两种构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,