广东工业大学PL0编译器的实现文档.docx
《广东工业大学PL0编译器的实现文档.docx》由会员分享，可在线阅读，更多相关《广东工业大学PL0编译器的实现文档.docx（53页珍藏版）》请在冰点文库上搜索。
广东工业大学PL0编译器的实现文档
第二章PL/0编译程序的实现
【课前思考】
复习第1章介绍的一个高级程序设计语言编译程序的功能和实现的步骤。
编译程序就是一个语言的翻译程序，通常是把一种高级程序设计语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。
换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。
编译程序实现的必要步骤有词法、语法、语义分析和代码生成。
此外必需有符号表管理程序和出错处理程序。
本章介绍的PL/0编译程序的实现是用PASCAL语言书写的
【学习目标】
本章目的：
以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，为后面的原理学习打下基础。
◇了解并掌握用语法图和扩充的巴科斯-瑙尔范式（EBNF）对PL/0语言的形式描述。
◇了解并掌握PL/0语言编译程序构造和实现的基本技术和步骤。
◇了解并掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。
【学习指南】
◇要求读者阅读PL/0语言编译程序文本，了解一个编译程序构造的必要步骤和实现技术。
一个编译程序的实现比较复杂，读懂一个典型的程序从设计思想到实现技术也有一定难度，特别是入门开始需要耐心。
一但读懂，不仅了解编译程序的实现方法和技术，还可学到许多编程技巧和好的编程风格。
◇阅读PL/0语言编译程序文本时，应从整体结构开始逐步细化，弄清楚每个过程的功能和实现方法及过程之间的相互关系。
◇建议用一个PL/0源程序的例子为导引作为阅读PL/0语言编译程序文本的入门，然后再逐步全面读懂。
◇通过对PL/0语言编译程序某些指定功能的扩充，加深对编译程序构造步骤和实现技术的理解，并能在实践中应用。
【难重点】
重点：
◇弄清源语言（PL/0）、目标语言（类pcode）与实现语言（C）这3个语言之间的关系和作用。
◇掌握用语法图和扩充的巴科斯-瑙尔范式（EBNF）对一个高级程序设计语言的形式描述。
◇了解PL/0语言编译程序的语法分析技术采用的是自顶向下递归子程序法。
◇掌握PL/0语言编译程序的整体结构和实现步骤，并弄清词法分析、语法分析、语义分析、代码生成及符号表管理每个过程的功能和相互联系。
◇掌握PL/0语言编译程序的目标程序在运行时采用栈式动态存储管理的实现技术。
难点：
◇符号表管理起着编译期间和目标程序运行时信息联系的纽带，符号表的建立并不困难，但信息之间的关系往往需要反复学习才能理解。
【知识结构】
为了使读者在系统地学习本教材以下各章节之前，对编译程序的构造得到一些感性认识和初步了解，本章推荐了世界著名计算机科学家N.Wirth编写的"PL/0语言的编译程序"，并对其实现过程作了概括的分析说明，作为读者阅读PL/0语言编译程序文本的提示。
对PL/0语言文法的表示只给出语法图和扩充的巴科斯-瑙尔范式（EBNF）的描述形式，不作文法理论上的讨论。
由于PL/0语言功能简单、结构清晰、可读性强，而又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤。
因此，"PL/0语言编译程序"是一个非常合适的小型编译程序的教学模型。
所以，阅读"PL/0语言编译程序"文本后，可帮助读者对编译程序的实现建立起整体概念。
2.1PL/0语言和类pcode的描述
在上一章中已介绍过，编译程序的功能是把一种高级程序设计语言的程序翻译成某种等价功能的低级语言的程序。
PL/0语言的编译程序就是要把PL/0语言程序翻译成为一种称为类pcode的假想的栈式计算机汇编语言程序。
这种汇编语言与机器无关，若需要在某一机器上实现PL/0语言程序，只需用机器上配置的任何语言对类pcode语言程序进行解释执行。
那么PL/0语言是什么样的语言？
类pcode语言又是什么样的结构？
它们之间是如何映射的？
只有在明确了这些问题之后，才能确定如何构造这个翻译程序。
就像一个翻译要把汉语翻译成英语，必须对汉语和英语的单词、语法结构都很精通，才有可能翻译得准确无误。
另外，编译程序既然是为了完成这种功能的一个程序，就存在用什么语言来编写这个程序的问题。
这些问题在本节将逐步介绍。
现对PL/0语言编译程序的功能用“T”型图（“T”型图将在第13章详细介绍）表示，并用图形概括描述PL/0编译程序的结构框架。
本节将用语法图和扩充的巴科斯-瑙尔范式（BACKUS-NAURFORM）（EBNF）两种形式给出PL/0语言的语法描述。
对类pcode代码给出指令的结构形式和含义。
巴科斯-瑙尔范式（BACKUS-NAURFORM）是根据美国的JohnW.Backus与丹麦的PeterNaur命名的。
2.1.1PL/0语言的语法描述图
用语法图描述语法规则的优点是直观、易读。
在图2.1的语法图中用椭圆和圆圈中的英文字表示终结符，用长方形内的中文字表示非终结符。
所谓终结符，是构成语言文法的单词，是语法成分的最小单位，而每个非终结符也是一个语法成分。
但非终结符可由其它文法符号定义，终结符不能由其它文法符号定义。
例如，程序是由非终结符'分程序'和终结符"."组成的串定义的。
由于对某些非终结符可以递归定义，如图2.1（b）、2.1（c）、2.1（e）中：
分程序、表达式和语句。
第一个非终结符'程序'为文法的开始符号。
注意在书写语言程序时非终结符并不出现，程序是由终结符串构成。
图2.1（a）程序语法描述图
图2.1（b）分程序语法描述图
图2.1（c）语句语法描述图
图2.1（d）条件语法描述图
图2.1（e）表达式语法描述图
图2.1（f）项语法描述图
图2.1（g）因子语法描述图
画语法图时要注意箭头方向和弧度，语法图中应该无直角，如图2.1给出的PL/0语法描述图。
沿语法图分析时不能走尖狐线。
2.1.2PL/0语言文法的EBNF表示
EBNF表示的符号说明。
〈〉：
用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。
∷=：
该符号的左部由右部定义，可读作'定义为'。
|：
表示'或'，为左部可由多个右部定义。
{}：
花括号表示其内的语法成分可以重复。
在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。
如：
{*}表示*重复任意次，{*}38表示*重复3-8次。
[]：
方括号表示其内的成分为任选项。
（）：
表示圆括号内的成分优先。
例：
用EBNF描述<整数>文法的定义：
<整数>∷=[+|-]<数字>{<数字>}
<数字>∷=0|1|2|3|4|5|6|7|8|9
或更好的写法
<整数>∷=[+|-]<非零数字>{<数字>}|0
<非零数字>∷=1|2|3|4|5|6|7|8|9
<数字>∷=0|<非零数字>
PL/0语言文法的EBNF表示为：
〈程序〉∷=〈分程序〉．
〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉
〈常量说明部分〉∷=CONST〈常量定义〉{，〈常量定义〉}；
〈常量定义〉∷=〈标识符〉=〈无符号整数〉
〈无符号整数〉∷=〈数字〉{〈数字〉}
〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；
〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉}
〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}；
〈过程首部〉∷=PROCEDURE〈标识符〉；
〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|
〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉
〈赋值语句〉∷=〈标识符〉∶=〈表达式〉
〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END
〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉
〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}
〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}
〈因子〉∷=〈标识符〉|〈无符号整数〉|'（'〈表达式〉'）'
〈加法运算符〉∷=+|-
〈乘法运算符〉∷=*|/
〈关系运算符〉∷=#|=|＜|＜=|＞|＞=
〈条件语句〉∷=IF〈条件〉THEN〈语句〉
〈过程调用语句〉∷=CALL〈标识符〉
〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉
〈读语句〉∷=READ'（'〈标识符〉{，〈标识符〉}'）'
〈写语句〉∷=WRITE'（'〈表达式〉{，〈表达式〉}'）'
〈字母〉∷=a|b|…|X|Y|Z
〈数字〉∷=0|1|2|…|8|9
用语法图描述语言的语法与EBNF描述相比较：
语法图描述：
直观，易读，易写。
EBNF表示：
形式化强，易机器识别。
无论用语法图或EBNF作为描述程序设计语言语法的工具，对描述的语法可以检查哪些符号序列是所给语言的合法程序，一个程序设计语言如C或JAVA，用户可用它写出成千上万个不同的程序，但C或JAVA它们各自的语法只有一个，这就使得无穷的句子集可用有穷的文法（语法）描述。
练习：
下面给出一个PL/0语言的程序，请学员对应PL/0语言的语法描述图与EBNF，检查该程序的语法是否正确。
CONSTA=10;
VARB,C;
PROCEDUREP;
VARD;
PROCEDUREQ;
VARX;
BEGIN
READ（X）;
D:
=D*C+X;WRITE（D）;
WHILEX#0DOCALLP;
END;
BEGIN
READ（D,C）;
CALLQ;
END;
BEGIN
CALLP;
END.
PL/0编译程序的使用限制
◇标识符的有效长度是10
◇数字最多为14位
◇过程最多可嵌套三层，可递归调用
◇标识符的作用域同PASCAL，内层可引用包围它的外层定义的标识符（如：
变量名，过程名，常量名）
2.1.3类pcode代码指令的结构
PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它不依赖任何具体计算机，其指令集极为简单，指令格式也很单纯，其格式如下：
f
l
a
其中f代表功能码，l表示层次差，也就是变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差。
a的含意对不同的指令有所区别，对存取指令表示位移量，而对其它的指令则分别有不同的含义，见下面对每条指令的解释说明。
目标指令有8条：
①LIT：
将常量值取到运行栈顶。
a域为常数值。
②LOD：
将变量放到栈顶。
a域为变量在所说明层中的相对位置,l为调用层与说明层的层差值。
③STO：
将栈顶的内容送入某变量单元中。
a,l域的含意同LOD指令。
④CAL：
调用过程的指令。
a为被调用过程的目标程序入口地址，l为层差。
⑤INT：
为被调用的过程（或主程序）在运行栈中开辟数据区。
a域为开辟的单元个数。
⑥JMP：
无条件转移指令，a为转向地址。
⑦JPC：
条件转移指令，当栈顶的布尔值为非真时，转向a域的地址，否则顺序执行。
⑧OPR：
关系运算和算术运算指令。
将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令，具体操作由a域值给出。
（详见解释执行程序）。
类pcode代码指令的详细解释（指令功能表）
认识目标代码类pcode
目标代码类pcode是一种假想栈式计算机的汇编语言。
指令格式：
f
l
a
f功能码
l层次差（标识符引用层减去定义层）
a根据不同的指令有所区别
指令功能表
LIT0a
将常数值取到栈顶，a为常数值
LODla
将变量值取到栈顶，a为偏移量，l为层差
STOla
将栈顶内容送入某变量单元中，a为偏移量，l为层差
CALla
调用过程，a为过程地址，l为层差
INT0a
在运行栈中为被调用的过程开辟a个单元的数据区
JMP0a
无条件跳转至a地址
JPC0a
条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行
OPR00
过程调用结束后,返回调用点并退栈
OPR01
栈顶元素取反
OPR02
次栈顶与栈顶相加，退两个栈元素，结果值进栈
OPR03
次栈顶减去栈顶，退两个栈元素，结果值进栈
OPR04
次栈顶乘以栈顶，退两个栈元素，结果值进栈
OPR05
次栈顶除以栈顶，退两个栈元素，结果值进栈
OPR06
栈顶元素的奇偶判断，结果值在栈顶
OPR07
OPR08
次栈顶与栈顶是否相等，退两个栈元素，结果值进栈
OPR09
次栈顶与栈顶是否不等，退两个栈元素，结果值进栈
OPR010
次栈顶是否小于栈顶，退两个栈元素，结果值进栈
OPR011
次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈
OPR012
次栈顶是否大于栈顶，退两个栈元素，结果值进栈
OPR013
次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈
OPR014
栈顶值输出至屏幕
OPR015
屏幕输出换行
OPR016
从命令行读入一个输入置于栈顶
一个PL/0程序与目标代码类pcode指令的映射例子:
2.2PL/0编译程序的结构
由2.1节可知，PL/0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。
PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。
PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。
其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。
此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。
用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。
当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。
其编译和解释执行的结构图如图2.2（a）和2.2（b）所示。
PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配置有PASCAL语言的任何机器上实现。
读者也可用其它语言改写PL/0编译程序，也可以用另一种语言编写目标代码类pcode的解释执行程序。
PL/0编译程序的编译过程是按源程序顺序进行分析的，常量变量说明部分不产生目标代码。
图2.2（a）PL/0编译程序的结构图
图2.2（b）PL/0的解释执行结构
PL/0编译程序是用PASCAL语言书写的，整个编译程序（包括主程序）是由18个嵌套及并列的过程或函数组成，下面分别简要给出这些函数的功能及它们的层次结构。
这些过程或函数的嵌套定义层次结构如图2.3所示。
图2.3PL/0编译程序过程与函数定义层次结构图
由于PL/0编译程序采用一趟扫描方法，所以语法分析过程BLOCK是整个编译过程的核心。
下面我们将在图2.4中先给出编译程序的总体流程，以弄清BLOCK过程在整个编译程序中的作用。
在流程图2.4中可以看出，主程序置初值后先调用读单词过程GETSYM取一个单词，然后再调用语法分析过程BLOCK，直到遇源程序的结束符"．"为止。
语法分析过程BLOCK是整个编译过程的核心，是指开始由主程序调用GETSYM取一个单词，再调用语法分析过程BLOCK，BLOCK由当前单词根据语法规则再调用其它过程，如说明处理、代码生成或出错处理等过程进行分析，当分析完一个单词后，BLOCK再调用GETSYM取下一个单词，一直重复到当前单词为结束符"．"表明源程序已分析结束。
若未取到结束符"．"，而源程序已没有输入符号，这时表明源程序有错误，无法再继续分析。
图2.4PL/0编译程序总体流程图
2.3PL/0编译程序的词法分析
PL/0的词法分析程序GETSYM（图2.5）是一个独立的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。
为此PL/0编译程序设置了三个全程量的公用单元如下：
SYM：
存放每个单词的类别，用内部编码形式表示。
ID：
存放用户所定义的标识符的值。
即标识符字符串的机内表示。
NUM：
存放用户定义的数。
单词的种类有五种。
基本字：
也可称为保留字或关键字，如BEGIN，END，IF，THEN等。
运算符：
如：
+、-、*、／、∶=、#、＞=、＜=等。
标识符：
用户定义的变量名、常数名、过程名。
常数：
如：
10，25，100等整数。
界符：
如：
'，'、'.'、'；'、'（'、'）'等。
如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词。
那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM中，而对用户定义的单词（标识符或常数）既给类别又给值，其类别放在SYM中，值放在ID或NUM中，全部单词种类由编译程序定义的纯量类型SYMBOL给出，也可称为语法的词汇表。
如下面提到的IFSYM，THENSYM，IDENT，NUMBER均属SYMBOL中的元素。
词法分析过程图2.5的GETSYM框图对应程序见PL/0编译程序文本中proceduregetsym，其中对标识符和关键字（保留字）的识别方式为：
当识别到字母开头的字母数字串时，先查关键字表。
若查不到则为标识符，查到则为关键字。
PL/0编译程序文本中主程序开始对关键字表置初值如下：
关键字表为：
word[1]:
='begin'；word[2]:
='call'；
...
word[13]:
='write'；
每个数组元素的字符长度为10，不满10个字符时，以空格补满。
查到时找到关键字相应的内部表示为：
Wsym[1]:
=beginsym;wsym[2]:
=callsym；
…
wsym[13]:
=writesym；
PL/0编译程序文本中开始对类型的定义中给出单词定义为：
typesymbol=（nul,ident,number,plus,…,varsym,procsym）；
定义单词是纯量/枚举类型，又定义了3个全程量为：
sym:
symbol;
id:
alfa;
num:
integer;
因此词法分析程序GETSYM将完成下列任务：
（1）滤空格：
空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以必须滤掉。
（2）识别保留字：
设有一张保留字表。
对每个字母打头的字母、数字字符串要查此表。
若查着则为保留字，将对应的类别放在SYM中。
如IF对应值IFSYM，THEN对应值为THENSYM。
若查不着，则认为是用户定义的标识符。
（3）识别标识符：
对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中。
（4）拼数：
当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值存放在NUM中。
（5）拼复合词：
对两个字符组成的算符
如：
＞=、∶=、＜=等单词，识别后将类别送SYM中。
（6）输出源程序：
为边读入字符边输出（可输出在文件中）。
由于一个单词往往是由一个或几个字符组成的，所以在词法分析过程GETSYM中又定义了一个取字符过程GETCH（见图2.6），由词法分析需要取字符时调用。
图2.6取字符过程GETCH
GETCH所用单元说明：
CH：
存放当前读取的字符，初值为空。
LINE：
为一维数组，其数组元素是字符，界对为1∶80。
用于读入一行字符的缓冲区。
LL和CC为计数器，初值为0。
GETSYM流程图的工作单元说明：
A：
一维数组，数组元素为字符，界对[1∶10]。
ID：
同A。
WORD：
保留字表，一维数组，数组元素是以字符为元素的一维数组。
界对为[1∶13]。
查表方式采用二分法。
单个字符对应的单词表的建立是，首先在主程序中定义了下标为字符的数组ssym，数组ssym的元素为单词，主程序开始对下标为字符的所有数组元素置初值为nul，对PL/0语言用到的单个字符为单词的，将其字符作为数组下标的元素置初值为对应的单词。
如：
ssym['+']:
=plus;ssym['-']:
=minus;
…
ssym[';']:
=semicolon;
2.4PL/0编译程序的语法分析
PL/0编译程序语法、语义分析是整个编译程序设计与实现的核心部分,要求学员努力学习掌握实现技术和方法。
现分别说明语法分析实现的主要思想方法和语义分析的实现。
语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。
PL/0语言的文法规则已在2.1节中给出。
本节将以语法图描述的语法形式为依据，给出语法分析过程的直观思想。
PL/0编译程序的语法分析采用了自顶向下的递归子程序法。
什么是自顶向下的语法分析？
可形象地对该程序自顶向下构造一棵倒挂着的语法分析树，其构造方法是：
（1）由开始符号非终结符'程序'作为分析树的根结点，由非终结符'程序'规则的右部为子结点。
（2）对分析树中的每个非终结符结点，选择它规则的一个右部为子结点构造分析树的下一层。
（3）重复
（2）直到分析树中的末端结点只有终结符。
（4）若分析树中的末端结点从左到右连接的终结符号串刚好是输入的程序终结符号串，则说明所给程序在语法上是正确的。
可用下面简单的PL/0程序为例构造其语法分析树
图2.7PL/0语法调用关系图
粗略地说：
自顶向下的递归子程序法就是对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。
语法分析从读入第一个单词开始由非终结符'程序'即开始符号出发，沿语法描述图箭头所指出的方向进行分析。
当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）。
再读取下一个单词继续分析。
遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若都不匹配时，可能是进入下一非终结符语法单位或是出错。
如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符'.'，这时就说所输入的程序是正确的。
对于正确的语法分析做相应的语义翻译，最终得出目标程序。
升级会员 