《编译原理讲义》PPT课件.ppt

1,编译原理讲义,清华大学计算机科学与技术系赖辉旻,2000.9,2,第二章 PL/0编译程序的实现,本章目的：以PL/0为例学习编译程序实现的基本步骤和相关技术，熟悉并理解编译程序的基本原理和概念。,PL/0编译程序,pcode解释程序,PL/0源程序,4,第二章 PL/0编译程序的实现,步骤1、认识源语言PL/0与目标代码pcode及它们之间的映射步骤2、PL/0编译程序的总体设计步骤3、PL/0编译程序词法分析的设计与实现步骤4、PL/0编译程序语法语义分析的设计与实现,5,第二章 PL/0编译程序的实现,步骤5、PL/0编译程序代码生成的实现步骤6、PL/0编译程序语法错误处理的实现步骤7、pcode代码解释器的设计与实现,6,步骤1、认识源语言PL/0与目标代码pcode及它们之间的映射,何为PL/0语言?认识目标代码pcodePL/0程序到pcode代码的映射,7,何为PL/0语言?,PL/0语言：PASCAL语言的子集，功能简单，结构清晰，可读性强，具备了一般高级语言的必备部分PL/0程序示例PL/0的非形式描述PL/0的语法描述图PL/0语言文法的EBNF表示,8,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.,9,PL/0非形式描述,数据类型只有整型标识符的有效长度是10，以字母开始的字母数字串数最多为14位过程无参，可嵌套（最多三层），可递归调用变量的作用域同PASCAL，常量为全局的，无标号,10,PL/0非形式描述,语句类型：赋值语句，if.then.,while.do.,read,write,call,复合语句begin.end，说明语句：const.,var.,procedure13个保留字：if,then,while,do,read,write,call,begin,end,const,var,procedure,odd,11,PL/0的语法描述图,12,PL/0语言文法的EBNF表示,BNF与EBNF的介绍BNF（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序。,13,PL/0语言文法的EBNF表示,BNF与EBNF的介绍BNF引入的符号：用左右尖括号括起来的语法成分为非终结符=定义为|或EBNF引入的符号：表示花括号内的语法成分可重复 表示方括号内的语法成分为任选项()表示圆括号内的成分优先,14,PL/0语言文法的EBNF表示,BNF与EBNF的介绍一个用EBNF描述的例子：=+|-=0|1|2|3|4|5|6|7|8|9,15,PL/0语言文法的EBNF表示,BNF与EBNF的介绍=+|-|0=1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9,16,PL/0语言文法的EBNF表示,PL/0语言文法的EBNF表示程序=分程序.分程序=常量说明部分变量说明部分过程说明部分语句常量说明部分=CONST常量定义部分，常量定义；无符号整数=数字数字变量说明部分=VAR标识符，标识符；标识符=字母字母|数字,17,认识目标代码pcode,目标代码pcode是一种假想栈式计算机的汇编语言。指令格式,f l a,f功能码l层次差a根据不同的指令有所区别,0 jmp0 81 jmp0 22 int 0 33 lod 1 34 lit0 105 opr0 2 次栈顶与栈顶相加6 sto1 47 opr0 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 0,RA 12,运行栈,const a=10;var b,c;procedure p;begin c:=b+a;end;begin read(b);call p;write(c);end.,SL：静态链DL：动态链RA：返回地址,0,20,PL/0程序到pcode代码的映射,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.,jmp 0 8jmp 0 2int 0 3lod 1 3lit 0 10opr 0 2 次栈顶与栈顶相加sto 1 4opr 0 0int 0 5 在运行栈中申请5个栈空间opr 0 16 从命令行读入输入置于栈顶sto 0 3 将栈顶值存入变量lod 0 3 将变量取至栈顶lit 0 0 将常值0进栈opr 0 9 次栈顶与栈顶是否不等jpc 0 24,cal 0 2 调用过程lit 0 2 常值2进栈lod 0 4 将变量取至栈顶opr 0 4 次栈顶与栈顶相乘opr 0 14 栈顶值输出至屏幕opr 0 15 换行opr 0 16 从命令行读取输入sto 0 3 jmp 0 11opr 0 0,21,步骤2 PL/0编译程序的总体设计,语法语义分析程序,PL/0源程序,目标程序,22,步骤2 PL/0编译程序的总体设计,其编译过程采用一趟扫描方式以语法分析程序为核心 词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。,23,步骤2 PL/0编译程序的总体设计,用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。,24,步骤3 PL/0编译程序词法分析的设计与实现,所需识别的单词基本字（保留字）：BEGIN、END、IF、THEN等运算符：如+、-、*、/、：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数：如10、25、100等整数界符：如,、.、;、(、)等,25,步骤3 PL/0编译程序词法分析的设计与实现,词法分析过程GETSYM所要完成的任务滤空格识别保留字识别标识符拼数拼复合词输出源程序,26,步骤3 PL/0编译程序词法分析的设计与实现,通过三个全程量将识别出的单词信息传递给语法分析程序，SYM，ID，NUMSYM：存放单词的类别,如beginsym,ident,numberID：存放用户所定义的标识符的值NUM：存放用户定义的数,27,步骤3 PL/0编译程序词法分析的设计与实现,词法分析程序的设计-使用状态转换图,28,步骤4 PL/0编译程序语法语义分析的设计与实现,语法分析的设计与实现自顶向下的语法分析递归子程序法如何用递归子程序法来实现表达式的语法分析,29,自顶向下的语法分析,VAR A;BEGIN READ(A)END.,30,递归子程序法,递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始由非终结符程序即开始符出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。,31,如何用递归子程序法来实现表达式的语法分析,表达式的EBNF表达式=+|-项（+|-）项项=因子（*|/）因子因子=标识符|无符号整数|（表达式）,32,如何用递归子程序法来实现表达式的语法分析,表达式的实现procedure expr;begin if sym in plus,minus then begin getsym;term;end else term;while sym in plus,minus do begin getsym;term;endend;,33,如何用递归子程序法来实现表达式的语法分析,项的实现procedure term;begin factor;while sym in times,slash do begin getsym;factor;endend;,34,如何用递归子程序法来实现表达式的语法分析,因子的实现procedure factor;begin if sym#ident then begin if sym#number then begin if sym=(then begin getsym;expr;if sym=)then getsym else error end else error end endend;,程序 pl0,分程序 block,语句 statement,条件 condition,表达式expression,项 term,因子 factor,PL/0语法调用关系图,编译程序总体流程图,37,程序BLOCK过程的流程图,见课本18页,38,语义分析与处理,说明部分的分析对每个过程说明的对象（变量，常量和过程）造名字表填写所在层次，标识符的属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成。表格管理过程体的分析,CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G,表格管理,名字 类型 层次/值 地址 存储空间,变量定义语句的处理,if sym=varsym thenbegin getsym;repeat vardeclaration;while sym=comma do begin getsym;vardeclaration end;if sym=semicolon then getsym else error(5)until symident;end;,41,变量定义语句的处理,procedure vardeclaration;begin if sym=ident then begin enter(variable);getsym end else error(4)end(*vardeclaration*);,42,过程ENTER的实现,procedure enter(k:objects);begin(*enter object into table*)tx:=tx+1;with tabletx do begin name:=id;kind:=k;case k of constant:begin if numamax then begin error(31);num:=0;end;val:=num end;,variable:begin level:=lev;adr:=dx;dx:=dx+1;end;procedur:level:=lev end endend(*enter*);,43,过程体的分析,从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。例：READ语句的语法语义分析处理=READ(，),44,READ语句的语法语义分析处理,if sym=readsym then begin getsym;if symlparen then error(34)else repeat getsym;if sym=ident then i:=position(id)else i:=0;if i=0 then error(35)else with tablei do begin gen(opr,0,16);gen(sto,lev-level,adr)end;getsym until symcomma;if symrparen then begin error(33);while not(sym in fsys)do getsym end else getsym end,45,步骤5、PL/0编译程序代码生成的实现,PL/0语言的代码生成是由过程GEN完成。GEN有三个参数，分别代表目标代码的功能码，层差和位移量。gen(opr,0,16);gen(sto,lev-level,adr)生成的代码顺序放在数组CODE中。CODE为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。CX为指令的指针，由0开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。,46,步骤5、PL/0编译程序代码生成的实现,procedure gen(x:fct;y,z:integer);begin if cxcxmax then begin write(program too long);close(fin);writeln;exit end;,with codecx do begin f:=x;l:=y;a:=z end;cx:=cx+1end(*gen*);,47,步骤6、PL/0编译程序语法错误处理的实现,对语法错误的两种处理方法：(1)对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析(2)对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。,48,步骤6、PL/0编译程序语法错误处理的实现,在进入某个语法单位时，调用TEST滤去开始符号前的所有符号。在语法单位分析结束时，调用TEST滤去当前符号到后继符号之间的所有符号。,TEST TEST,49,开始符号集合与后继符号集合,TEST,SYM在S1中?,打印出错编号n,S1:=S1+S2,SYM在S1中?,GETSYM,返回,Y,Y,N,N,TEST测试过程流程图,51,因子的处理过程,见课本294页procedure factor(fsys:symset);,52,步骤7、pcode代码解释器的实现,pcode解释器的结构解释执行的流程图目标代码解释执行时的存储分配,53,pcode解释器的结构,目标代码存放在数组CODE中。解释程序定义的一维整型数组S作为运行栈栈项寄存器t，基址寄存器b，程序地址寄存器p，指令寄存器i,interpret,三个寄存器赋初值t:=0;b:=1;p:=0;,主程序的SL，DL，RA赋初值s1:=0;s2=0;s3=0;,i:=codep;p:=p+1;,执行指令i,P=0?,返回,解释执行的流程图,55,目标代码解释执行时的存储分配,在每个过程调用时在栈顶分配三个联系单元：SL：静态链，指向定义该过程的直接外过程（或主程序）运行时数据段的基地址。DL：动态链，指向调用该过程前正在运行过程的数据段基地址。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。,56,目标代码解释执行时的存储分配,几条典型指令的存储分配INT 0 A位于过程目标程序的入口，开辟A个单元的数据段。A为局部变量个数+3OPR 0 0位于过程目标程序的出口，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行,57,目标代码解释执行时的存储分配,几条典型指令的存储分配CAL L A调用过程，还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。,58,运行时数据栈S的变化状态,见课本26页,