编译原理讲义

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

2、之间的映射它们之间的映射步骤步骤2 2、 PL/0PL/0编译程序的总体设计编译程序的总体设计步骤步骤3 3、 PL/0PL/0编译程序词法分析的设计与实编译程序词法分析的设计与实现现步骤步骤4 4、 PL/0PL/0编译程序语法语义分析的设计编译程序语法语义分析的设计与实现与实现编译原理讲义5第二章第二章 PL/0PL/0编译程序的实现编译程序的实现步骤步骤5 5、 PL/0PL/0编译程序代码生成的实现编译程序代码生成的实现步骤步骤6 6、 PL/0PL/0编译程序语法错误处理的实现编译程序语法错误处理的实现步骤步骤7 7、 pcodepcode代码解释器的设计与实现代码解释器的设计与实现

3、编译原理讲义6步骤步骤1 1、认识源语言、认识源语言PL/0PL/0与目标与目标代码代码pcodepcode及它们之间的映射及它们之间的映射何为何为PL/0PL/0语言语言? ?认识目标代码认识目标代码pcodepcodePL/0PL/0程序到程序到pcodepcode代码的映射代码的映射编译原理讲义7何为何为PL/0PL/0语言语言? ?PL/0PL/0语言：语言：PASCALPASCAL语言的子集，功能简单，结语言的子集，功能简单，结构清晰，可读性强，具备了一般高级语言的必构清晰，可读性强，具备了一般高级语言的必备部分备部分PL/0PL/0程序示例程序示例PL/0PL/0的非形式描述的非形

4、式描述PL/0PL/0的语法描述图的语法描述图PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示编译原理讲义8PL/0PL/0程序示例程序示例CONST A=10;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; BEGIN BEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 DO CALL P; WHILE X#0 DO CALL P; END; END; BEGIN WRITE(D

5、); CALL Q; END;BEGIN CALL P;END.编译原理讲义9PL/0PL/0非形式描述非形式描述数据类型只有整型数据类型只有整型标识符的有效长度是标识符的有效长度是1010，以字母开始的字母数，以字母开始的字母数字串字串数最多为数最多为1414位位过程无参，可嵌套（最多三层），可递归调用过程无参，可嵌套（最多三层），可递归调用变量的作用域同变量的作用域同PASCALPASCAL，常量为全局的，无标，常量为全局的，无标号号编译原理讲义10PL/0PL/0非形式描述非形式描述语句类型：赋值语句，语句类型：赋值语句，if.then., if.then., while.do., re

6、ad, write, call, while.do., read, write, call, 复合语复合语句句begin. endbegin. end， 说明语句：说明语句： const., const., var., procedurevar., procedure1313个保留字：个保留字：if, then, while, do, read, if, then, while, do, read, write, call, begin, end, const, var, write, call, begin, end, const, var, procedure, oddprocedure,

7、 odd编译原理讲义11PL/0PL/0的语法描述图的语法描述图语句constidentnumbervaridentprocedureident分程序分程序分程序程序编译原理讲义12PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示BNFBNF与与EBNFEBNF的介绍的介绍BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根据美国的与丹）是根据美国的与丹麦的麦的Peter NaurPeter Naur来命名的，它从语法上描述程来命名的，它从语法上描述程序设计语言的元语言。采用序设计语言的元语言。采用BNFBNF就可说明哪些就可说明哪些符号序列是对于某

8、给定语言在语法上有效的程符号序列是对于某给定语言在语法上有效的程序。序。编译原理讲义13PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示BNFBNF与与EBNFEBNF的介绍的介绍BNFBNF引入的符号：引入的符号： 用左右尖括号括起来的语法成分为非终结符用左右尖括号括起来的语法成分为非终结符= = 定义为定义为| | 或或EBNFEBNF引入的符号：引入的符号： 表示花括号内的语法成分可重复表示花括号内的语法成分可重复 表示方括号内的语法成分为任选项表示方括号内的语法成分为任选项( ) ( ) 表示圆括号内的成分优先表示圆括号内的成分优先编译原理讲义14PL/0PL/0语言文法的

9、语言文法的EBNFEBNF表示表示BNFBNF与与EBNFEBNF的介绍的介绍一个用一个用EBNFEBNF描述的例子：描述的例子： =+|-=+|- =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9编译原理讲义15PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示BNFBNF与与EBNFEBNF的介绍的介绍 =+|-=+|-|0|0 =1|2|3|4|5|6|7|8|9 =1|2|3|4|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编译原理讲义16PL/0PL/0语言文法的语言文法的EBNFEBN

10、F表示表示PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示程序程序=分程序分程序. .分程序分程序=常量说明部分常量说明部分变量说明部变量说明部分分过程说明部分过程说明部分 语句语句常量说明部分常量说明部分=CONST=CONST常量定义部分常量定义部分 ，常常量定义量定义 ；无符号整数无符号整数=数字数字 数字数字 变量说明部分变量说明部分=VAR=VAR标识符标识符 ，标识符标识符 ；标识符标识符=字母字母 字母字母| |数字数字 编译原理讲义17认识目标代码认识目标代码pcodepcode目标代码目标代码pcodepcode是一种假想栈式计算机的汇编是一种假想栈式计算机的汇编

11、语言。语言。指令格式指令格式f l af功能码l层次差a根据不同的指令有所区别编译原理讲义0 jmp0 81 jmp0 22 int 0 33 lod 1 34 lit0 105 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运行栈c

12、onst a=10;v a r b , c ;procedure p; begin c : = b + a ; end;begin r e a d ( b ) ; c a l l p ; w r i t e ( c ) ;end.SL：静态链DL：动态链RA：返回地址0编译原理讲义19PL/0PL/0程序到程序到pcodepcode代码的映射代码的映射const a=10;const a=10;var b,c;var b,c;procedure p;procedure p; begin begin c:=b+a; c:=b+a; end; end;beginbegin read(b); rea

13、d(b); while b#0 do while b#0 do begin begin call p; call p; write(2 write(2* *c);c); read(b); read(b); end endend.end.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

14、 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编译原理讲义20步骤步骤2 PL/02 PL/0编译程序的总体设编译程序的总体设计计语法语义分析程序词法分析程序表格管理程序出错处理程序代码生成程序PL/0源程序目标程序编译原理讲义21步骤步骤2 PL/02 PL/0编译程序的总体设编译程序的总体设计计其编译过程采用一趟扫描方式其编译过程采用一趟扫描方式以语法分析程序为核心以语法分析程序为核心 词法分析程

15、序和代码生成程序都作为一个独词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。的目标代码时，则调用代码生成程序。编译原理讲义22步骤步骤2 PL/02 PL/0编译程序的总体设编译程序的总体设计计用表格管理程序建立变量，常量和过程标识符用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误用出错处理程序对词法和语法分析遇到的错误给出在

16、源程序中出错的位置和错误性质。给出在源程序中出错的位置和错误性质。编译原理讲义23步骤步骤3 PL/03 PL/0编译程序词法分析编译程序词法分析的设计与实现的设计与实现所需识别的单词所需识别的单词基本字（保留字）：基本字（保留字）：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等运算符：运算符： 如如+ +、- -、* *、/ /、：、：= =、# #、=、=等等标识符：标识符： 用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名常数：常数： 如如1010、2525、100100等整数等整数界符：界符： 如如,、. . 、; ; 、( ( 、)等等编译原

17、理讲义24步骤步骤3 PL/03 PL/0编译程序词法分析编译程序词法分析的设计与实现的设计与实现词法分析过程词法分析过程GETSYMGETSYM所要完成的任务所要完成的任务滤空格滤空格识别保留字识别保留字识别标识符识别标识符拼数拼数拼复合词拼复合词输出源程序输出源程序编译原理讲义25步骤步骤3 PL/03 PL/0编译程序词法分析编译程序词法分析的设计与实现的设计与实现通过三个全程量将识别出的单词信息传递给语法分析程通过三个全程量将识别出的单词信息传递给语法分析程序，序，SYMSYM，IDID，NUMNUMSYMSYM：存放单词的类别：存放单词的类别, ,如如beginsym, ident,

18、 numberbeginsym, ident, numberIDID： 存放用户所定义的标识符的值存放用户所定义的标识符的值NUMNUM：存放用户定义的数：存放用户定义的数编译原理讲义26步骤步骤3 PL/03 PL/0编译程序词法分析编译程序词法分析的设计与实现的设计与实现词法分析程序的设计词法分析程序的设计-使用状态转换图使用状态转换图1 12 23 35 514141313121210109 97 78 86 64 41111空格空格字母字母字母数字字母数字非字母数字非字母数字数字数字数字数字非数字非数字：= = = =非非= =, + - ( 编译原理讲义27步骤步骤4 PL/04 P

19、L/0编译程序语法语义编译程序语法语义分析的设计与实现分析的设计与实现语法分析的设计与实现语法分析的设计与实现自顶向下的语法分析自顶向下的语法分析递归子程序法递归子程序法如何用递归子程序法来实现表达式的语法分析如何用递归子程序法来实现表达式的语法分析编译原理讲义28自顶向下的语法分析自顶向下的语法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END.VAR；ABEGINENDREAD （ ）A编译原理讲义29递归子程序法递归子程序法递归子程序法递归子程序法：对应每个非终结符语法单元，编一个独立对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。

20、语法分析从读入第一个单词开的处理过程（或子程序）。语法分析从读入第一个单词开始由非终结符始由非终结符程序程序即开始符出发，沿语法描述图箭头即开始符出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行

21、相应的语义程序（就中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）。再读取下一个单词继续分析。遇到分支点是翻译程序）。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上多个终结符逐个相比较，若都时将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。不匹配时可能是进入下一个非终结符语法单位或是出错。编译原理讲义30如何用递归子程序法来实现表达如何用递归子程序法来实现表达式的语法分析式的语法分析表达式的表达式的EBNF表达式表达式=+|-=+|-项项 （+|-+|-）项项 项项=因子因子 （* *|/|/）因子因子 因子因子=标

22、识符标识符| |无符号整数无符号整数|（表达式表达式）编译原理讲义31如何用递归子程序法来实现表达如何用递归子程序法来实现表达式的语法分析式的语法分析 表达式表达式的实现的实现procedure expr;procedure expr;beginbegin if sym in plus, minus then if sym in plus, minus then begin begin getsym; term; getsym; term; end end else term; else term; while sym in plus, minus do while sym in plus,

23、minus do begin begin getsym; term; getsym; term; end endend;end;编译原理讲义32如何用递归子程序法来实现表达如何用递归子程序法来实现表达式的语法分析式的语法分析项项的实现的实现procedure term;procedure term;beginbegin factor; factor; while sym in times, slash do while sym in times, slash do begin begin getsym; factor; getsym; factor; end endend;end;编译原理讲义

24、33如何用递归子程序法来实现表达如何用递归子程序法来实现表达式的语法分析式的语法分析 因子因子的实现的实现procedure factor;procedure factor;begin begin if sym # ident then if sym # ident then begin begin if sym # number then if sym # number then begin begin if sym = ( then if sym = ( then begin begin getsym; getsym; expr; expr; if sym = ) then getsym

25、if sym = ) then getsym else error else error end end else error else error end end end endend;end;编译原理讲义 程序 pl0分程序 block语句 statement条件 condition表达式expression项 term因子 factorPL/0语法调用关系图编译原理讲义编译程序总体流程图编译程序总体流程图启动启动置初值置初值调用G E TSYM取 单 词调用G E TSYM取 单 词调用B L OCK过 程调用B L OCK过 程当前单词当前单词是否为源程序结束符是否为源程序结束符.？.

26、？出错出错源程序中源程序中是否有错误？是否有错误？调用解释过程I N T E R P RET调用解释过程I N T E R P RET解释执行目标程序解释执行目标程序打印错误打印错误结束结束N NY YY YN N编译原理讲义36程序程序BLOCKBLOCK过程的流程图过程的流程图见课本18页编译原理讲义37语义分析与处理语义分析与处理说明部分的分析说明部分的分析对每个过程说明的对象（变量，常量和过程）对每个过程说明的对象（变量，常量和过程）造名字表造名字表填写所在层次，标识符的属性和分配的相对位填写所在层次，标识符的属性和分配的相对位置。标识符的属性不同时，所需填入的信息也置。标识符的属性不

27、同时，所需填入的信息也不同。登录信息由不同。登录信息由ENTERENTER过程完成。过程完成。 表格管理表格管理过程体的分析过程体的分析编译原理讲义NAMENAME：A ANAMENAME：B BNAMENAME：C CNAMENAME：D DNAMENAME：E ENAMENAME：P PKINDKIND：CONSTANTCONSTANTKINDKIND：CONSTANTCONSTANTKINDKIND：VARIABLEVARIABLEKINDKIND：VARIABLEVARIABLEKINDKIND：VARIABLEVARIABLEKINDKIND：PROCEDURPROCEDURVALV

28、AL：3535VALVAL：4949LEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVADRADR：DXDXADRADR：DX+1DX+1ADRADR：DX+2DX+2ADRADR：SIZESIZE：4 4NAMENAME：G G KINDKIND：VARIABLEVARIABLELEVELLEVEL：LEV+1LEV+1ADRADR：DXDXCONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G表格管理表格管理 名字 类型 层次/值 地址 存储空间编译原理讲义变量定义语句的处

29、理变量定义语句的处理 if sym=varsym then if sym=varsym thenbeginbegin getsym; getsym; repeat repeat vardeclaration; vardeclaration; while sym=comma do while sym=comma do begin begin getsym; getsym; vardeclaration vardeclaration end; end; if sym=semicolon then getsym if sym=semicolon then getsym else error(5) e

30、lse error(5) until symident; until symident;end;end;编译原理讲义40变量定义语句的处理变量定义语句的处理 p r o c e d u r e v a r d e c l a r a t i o n ; p r o c e d u r e v a r d e c l a r a t i o n ; begin begin i f s y m = i d e n t t h e n i f s y m = i d e n t t h e n begin begin e n t e r ( v a r i a b l e ) ; e n t e r

31、 ( v a r i a b l e ) ; getsym getsym end end else error(4) else error(4) end( end(* *vardeclarationvardeclaration* *););编译原理讲义41过程过程ENTERENTER的实现的实现 procedure enter(k:objects ); procedure enter(k:objects ); begin( begin(* *enter object into tableenter object into table* *) ) tx:=tx+1; tx:=tx+1; with

32、 tabletx do with tabletx do begin begin name:=id; name:=id; kind:=k; kind:=k; case k of case k of constant: begin constant: begin if numamax then if numamax then begin begin error(31); error(31); num:=0; num:=0; end; end; val:=num val:=num end; end;variable: begin level:=lev; adr:=dx; dx:=dx+1; end;

33、 procedur: level:=lev end endend(*enter*);编译原理讲义42过程体的分析过程体的分析从语法上要对语句逐句分析。从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用当遇到标识符的引用时就调用POSITIONPOSITION函数查函数查TABLETABLE表，表，看是否有过正确定义，若已有，则从表中取相应的有关看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。信息，供代码的生成使用。若无定义则错。例：例：READREAD语句的语法语义分析处

34、理语句的语法语义分析处理 =READ(=READ(， )编译原理讲义43READREAD语句的语法语义分析处理语句的语法语义分析处理 if sym=readsym then if sym=readsym then begin begin getsym; getsym; if symlparen then error(34) if symlparen then error(34) else else repeat repeat getsym; getsym; if sym=ident then i:=position(id) if sym=ident then i:=position(id) e

35、lse i:=0; else i:=0; if i=0 then error(35) if i=0 then error(35) else else with tablei do with tablei do begin begin gen(opr,0,16); gen(opr,0,16); gen(sto,lev-level,adr) gen(sto,lev-level,adr) end; end; getsym getsym until symcomma; until symcomma; if symrparen then if symrparen then begin begin err

36、or(33); error(33); while not(sym in fsys) do getsym while not(sym in fsys) do getsym end end else getsym else getsym end end编译原理讲义44步骤步骤5 5、 PL/0PL/0编译程序代码生编译程序代码生成的实现成的实现PL/0PL/0语言的代码生成是由过程语言的代码生成是由过程GENGEN完成。完成。GENGEN有三个参数，分别代表目标代码的功能码，有三个参数，分别代表目标代码的功能码，层差和位移量。层差和位移量。gen(opr,0,16); gen(sto,lev-le

37、vel,adr)gen(opr,0,16); gen(sto,lev-level,adr)生成的代码顺序放在数组生成的代码顺序放在数组CODECODE中。中。 CODECODE为一维数组，数组元素为记录型数据。每为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。一个记录就是一条目标指令。CXCX为指令的指针，为指令的指针，由由0 0开始顺序增加。实际上目标代码的顺序是内开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。层过程的在前边，主程序的目标代码在最后。编译原理讲义45步骤步骤5 5、 PL/0PL/0编译程序代码生编译程序代码生成的实现成的实现 p

38、rocedure gen(x:fct;y, z:integer); procedure gen(x:fct;y, z:integer); begin begin if cxcxmax then if cxcxmax then begin begin write(program too long); write(program too long); close(fin); close(fin); writeln; writeln; exit exit end; end;with codecx do begin f:=x; l:=y; a:=z end; cx:=cx+1end (*gen*);编

39、译原理讲义46步骤步骤6 6、 PL/0PL/0编译程序语法错编译程序语法错误处理的实现误处理的实现对语法错误的两种处理方法：对语法错误的两种处理方法：(1)(1)对于易于校正的错误，如丢了逗号，分号对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析等，指出出错位置，加以校正，继续进行分析(2)(2)对于难于校正的错误，给出错误的位置与对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。进行正常语法分析的语法单位。编译原理讲义47步骤步骤6 6、 PL/0PL/0编译程序语法错

40、编译程序语法错误处理的实现误处理的实现在进入某个语法单位时，调用在进入某个语法单位时，调用TESTTEST滤去开始符号滤去开始符号前的所有符号。前的所有符号。在语法单位分析结束时，调用在语法单位分析结束时，调用TESTTEST滤去当前符号滤去当前符号到后继符号之间的所有符号。到后继符号之间的所有符号。 TEST TEST编译原理讲义48开始符号集合与后继符号集合开始符号集合与后继符号集合非终结符名非终结符名开始符号集合开始符号集合后继符号集合后继符号集合分程序分程序const var procedureconst var procedureident if call beginident if

41、 call beginwhile read writewhile read write. ;. ;语句语句ident call beginident call beginif while read writeif while read write. ; end. ; end条件条件odd + - (odd + - (ident numberident numberThen doThen do表达式表达式+ - (+ - (ident numberident number. ; ) rop. ; ) ropend then doend then do项项ident number (ident number (. ; ) rop + -. ; ) rop + -end then doend then do因子因子ident number (ident number (. ; ) rop + -. ; ) rop + -* / end then do*