编译原理讲义

1、编译原理讲义编译原理讲义2第二章 PL/0编译程序的实现本章目的：以PL/0为例学习编译程序实现的基本步骤和相关技术，熟悉并理解编译程序的基本原理和概念。编译原理讲义PL/0编译程序pcode解释程序PL/0源程序pcode代码注：此处的pcode代码专指PL/0的目标码，注意与传统pcode的区别编译原理讲义4第二章 PL/0编译程序的实现步骤1、 认识源语言PL/0与目标代码pcode及它们之间的映射步骤2、 PL/0编译程序的总体设计步骤3、 PL/0编译程序词法分析的设计与实现步骤4、 PL/0编译程序语法语义分析的设计与实现编译原理讲义5第二章 PL/0编译程序的实现步骤5、 PL/

2、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表示编译原理讲义8PL/0程序示例CONST A=10;VAR B,C;PROCEDURE P; VAR D; PROCEDURE

3、 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.编译原理讲义9PL/0非形式描述数据类型只有整型标识符的有效长度是10，以字母开始的字母数字串数最多为14位过程无参，可嵌套（最多三层），可递归调用变量的作用域同PASCAL，常量为全局的，无标号编译原理讲义10PL/0非形式描述语句类型：赋值语句，if.then., while.do., read, write, call, 复合语句begin. end， 说明语句： const., va

4、r., procedure13个保留字：if, then, while, do, read, write, call, begin, end, const, var, procedure, odd编译原理讲义11PL/0的语法描述图语句constidentnumbervaridentprocedureident分程序分程序分程序程序编译原理讲义12PL/0语言文法的EBNF表示BNF与EBNF的介绍BNF（BACKUS-NAUR FORM）是根据美国的与丹麦的Peter Naur来命名的，它从语法上描述程序设计语言的元语言。采用BNF就可说明哪些符号序列是对于某给定语言在语法上有效的程序。编译

5、原理讲义13PL/0语言文法的EBNF表示BNF与EBNF的介绍BNF引入的符号： 用左右尖括号括起来的语法成分为非终结符= 定义为| 或EBNF引入的符号： 表示花括号内的语法成分可重复 表示方括号内的语法成分为任选项( ) 表示圆括号内的成分优先编译原理讲义14PL/0语言文法的EBNF表示BNF与EBNF的介绍一个用EBNF描述的例子：=+|-=0|1|2|3|4|5|6|7|8|9编译原理讲义15PL/0语言文法的EBNF表示BNF与EBNF的介绍=+|-|0=1|2|3|4|5|6|7|8|9 =0|1|2|3|4|5|6|7|8|9编译原理讲义16PL/0语言文法的EBNF表示PL

6、/0语言文法的EBNF表示程序=分程序.分程序=常量说明部分变量说明部分过程说明部分语句常量说明部分=CONST常量定义部分，常量定义；无符号整数=数字数字变量说明部分=VAR标识符，标识符；标识符=字母字母|数字编译原理讲义17认识目标代码pcode目标代码pcode是一种假想栈式计算机的汇编语言。指令格式f l af功能码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 从命令行读

7、入输入置于栈顶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;var b,c;procedure p; begin c:=b+a; end;begin read(b); call p; write(c);end.SL：静态链DL：动态链RA：返回地址0编译原理讲义19PL/0程序到pcode代码的映射const a=10;var b,c;procedure p;

8、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

9、将变量取至栈顶opr 0 4 次栈顶与栈顶相乘opr 0 14 栈顶值输出至屏幕opr 0 15 换行opr 0 16 从命令行读取输入sto 0 3 jmp 0 11opr 0 0编译原理讲义20步骤2 PL/0编译程序的总体设计语法语义分析程序词法分析程序表格管理程序出错处理程序代码生成程序PL/0源程序目标程序编译原理讲义21步骤2 PL/0编译程序的总体设计其编译过程采用一趟扫描方式以语法分析程序为核心 词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。编译原理讲义22步骤2 PL/0

10、编译程序的总体设计用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。编译原理讲义23步骤3 PL/0编译程序词法分析的设计与实现所需识别的单词基本字（保留字）：BEGIN、 END、 IF、 THEN等运算符： 如+、-、*、/、：=、#、=、=等标识符： 用户定义的变量名、常数名、过程名常数： 如10、25、100等整数界符： 如,、. 、; 、( 、)等编译原理讲义24步骤3 PL/0编译程序词法分析的设计与实现词法分析过程GETSYM所要完成的任务滤空格识别保留字识别标识符拼数拼复合词输出源程序

11、编译原理讲义25步骤3 PL/0编译程序词法分析的设计与实现通过三个全程量将识别出的单词信息传递给语法分析程序，SYM，ID，NUMSYM：存放单词的类别,如beginsym, ident, numberID： 存放用户所定义的标识符的值NUM：存放用户定义的数编译原理讲义26步骤3 PL/0编译程序词法分析的设计与实现词法分析程序的设计-使用状态转换图编译原理讲义27步骤4 PL/0编译程序语法语义分析的设计与实现语法分析的设计与实现自顶向下的语法分析递归子程序法如何用递归子程序法来实现表达式的语法分析编译原理讲义28自顶向下的语法分析VAR A;BEGIN READ(A)END.VAR；A

12、BEGINENDREAD （ ）A编译原理讲义29递归子程序法递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始由非终结符程序即开始符出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或

13、是出错。编译原理讲义30如何用递归子程序法来实现表达式的语法分析表达式的EBNF表达式=+|-项（+|-）项项=因子（*|/）因子因子=标识符|无符号整数|（表达式）编译原理讲义31如何用递归子程序法来实现表达式的语法分析表达式的实现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;编译原理讲义32如何用递归子程序法来实现表达式的语法分析项的实现procedure ter

14、m;begin factor; while sym in times, slash do begin getsym; factor; endend;编译原理讲义33如何用递归子程序法来实现表达式的语法分析因子的实现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分程序 bloc

15、k语句 statement条件 condition表达式expression项 term因子 factorPL/0语法调用关系图编译原理讲义编译程序总体流程图编译原理讲义36程序BLOCK过程的流程图见课本18页编译原理讲义37语义分析与处理说明部分的分析对每个过程说明的对象（变量，常量和过程）造名字表填写所在层次，标识符的属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成。 表格管理过程体的分析编译原理讲义CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G表格管理 名字 类型 层次/值 地址 存储空间编译原理讲义变

16、量定义语句的处理 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;编译原理讲义40变量定义语句的处理 procedure vardeclaration; begin if sym=ident then begin enter(variable); getsym end else error(4) end(*

17、vardeclaration*);编译原理讲义41过程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: leve

18、l:=lev end endend(*enter*);编译原理讲义42过程体的分析从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。例：READ语句的语法语义分析处理=READ(，)编译原理讲义43READ语句的语法语义分析处理 if sym=readsym then begin getsym; if symlparen then error(34) else repeat getsym; if sym=ident then i:

19、=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编译原理讲义44步骤5、 PL/0编译程序代码生成的实现PL/0语言的代码生成是由过程GEN完成。GEN有三个参数，分别代表目标代码的功能码，层差和

20、位移量。gen(opr,0,16); gen(sto,lev-level,adr)生成的代码顺序放在数组CODE中。 CODE为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。CX为指令的指针，由0开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。编译原理讲义45步骤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 code

21、cx do begin f:=x; l:=y; a:=z end; cx:=cx+1end (*gen*);编译原理讲义46步骤6、 PL/0编译程序语法错误处理的实现对语法错误的两种处理方法：(1)对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析(2)对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。编译原理讲义47步骤6、 PL/0编译程序语法错误处理的实现在进入某个语法单位时，调用TEST滤去开始符号前的所有符号。在语法单位分析结束时，调用TEST滤去当前符号到后继符号之间的所有符号。 TEST TEST编译原理讲义48开始符号集合与后继符号集合编译原理讲义TESTSYM在S1中?打印出错编号nS1:=S1+S2SYM在S1中?GETSYM返回YYNNTEST测试过程流程图编译原理讲义50因子的处理过程见课本294页procedure