PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 1 -
PL/0 语言编译程序分析
PL/0 语言是 Pascal 语言的一个子集,我们这里分析的 PL/0 的编译程序包括了对 PL/0
语言源程序进行分析处理、编译生成类 PCODE 代码,并在虚拟机上解释运行生成的类
PCODE 代码的功能。
PL/0 语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码
生成作为独立的子程序供语法分析程序调用。语法分析的同时,提供了出错报告和出错
恢复的功能。在源程序没有错误编译通过的情况下,调用类 PCODE 解释程序解释执行
生成的类 PCODE 代码。
词法分析子程序分析:
词法分析子程序名为 getsym,功能是从源程序中读出一个单词符号(token),把它
的信息放入全局变量 sym、id 和 num 中,语法分析器需要单词时,直接从这三个变量中
获得。(注意:语法分析器每次用完这三个变量的值就立即调用 getsym 子程序获取新的
单词供下一次使用。而不是在需要新单词时才调用 getsym 过程)。getsym 过程通过反复
调用 getch 子过程从源程序过获取字符,并把它们拼成单词。getch 过程中使用了行缓冲
区技术以提高程序运行效率。
词法分析器的分析过程:调用 getsym 时,它通过 getch 过程从源程序中获得一个字
符。如果这个字符是字母,则继续获取字符或数字,最终可以拼成一个单词,查保留字
表,如果查到则为保留字,把 sym 变量赋成相应的保留字类型值;如果没有查到,则这
个单词应是一个用户自定义的标识符(可能是变量名、常量名或是过程的名字),把 sym
置为 ident,把这个单词存入 id 变量。查保留字表时使用了二分法查找以提高效率。如
果 getch 获得的字符是数字,则继续用 getch 获取数字,并把它们拼成一个整数,然后把
sym 置为 number,并把拼成的数值放入 num 变量。如果识别出其它合法的符号(比如:
赋值号、大于号、小于等于号等),则把 sym 则成相应的类型。如果遇到不合法的字符,
把 sym 置成 nul。
语法分析子程序分析:
语法分析子程序采用了自顶向下的递归子程序法,语法分析同时也根据程序的语意
生成相应的代码,并提供了出错处理的机制。语法分析主要由分程序分析过程(block)、
常量定义分析过程(constdeclaration)、变量定义分析过程(vardeclaration)、语句分析
过程(statement)、表达式处理过程(expression)、项处理过程(term)、因子处理过程
(factor)和条件处理过程(condition)构成。这些过程在结构上构成一个嵌套的层次结
构。除此之外,还有出错报告过程(error)、代码生成过程(gen)、测试单词合法性及
出错恢复过程(test)、登录名字表过程(enter)、查询名字表函数(position)以及列出
类 PCODE 代码过程(listcode)作过语法分析的辅助过程。
由 PL/0 的语法图可知:一个完整的 PL/0 程序是由分程序和句号构成的。因此,本
编译程序在运行的时候,通过主程序中调用分程序处理过程 block 来分析分程序部分(分
程序分析过程中还可能会递归调用 block 过程),然后,判断最后读入的符号是否为句号。
如果是句号且分程序分析中未出错,则是一个合法的 PL/0 程序,可以运行生成的代码,
否则就说明源 PL/0 程序是不合法的,输出出错提示即可。
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 2 -
下面按各语法单元分析 PL/0 编译程序的运行机制。
分程序处理过程 block:
语法分析开始后,首先调用分程序处理过程(block)处理分程序。过程入口参数置
为:0 层、符号表位置 0、出错恢复单词集合为句号、声明符或语句开始符。进入 block
过程后,首先把局部数据段分配指针设为 3,准备分配 3 个单元供运行期存放静态链 SL、
动态链 DL 和返回地址 RA。然后用 tx0 记录下当前符号表位置并产生一条 jmp 指令,准
备跳转到主程序的开始位置,由于当前还没有知到主程序究竟在何处开始,所以 jmp 的
目标暂时填为 0,稍后再改。同时在符号表的当前位置记录下这个 jmp 指令在代码段中
的位置。在判断了嵌套层数没有超过规定的层数后,开始分析源程序。首先判断是否遇
到了常量声明,如果遇到则开始常量定义,把常量存入符号表。接下去用同样的方法分
析变量声明,变量定义过程中会用 dx 变量记录下局部数据段分配的空间个数。然后如果
遇到 procedure 保留字则进行过程声明和定义,声明的方法是把过程的名字和所在的层
次记入符号表,过程定义的方法就是通过递归调用 block 过程,因为每个过程都是一个
分程序。由于这是分程序中的分程序,因此调用 block 时需把当前的层次号 lev 加一传递
给 block 过程。分程序声明部分完成后,即将进入语句的处理,这时的代码分配指针 cx
的值正好指向语句的开始位置,这个位置正是前面的 jmp 指令需要跳转到的位置。于是
通过前面记录下来的地址值,把这个 jmp 指令的跳转位置改成当前 cx 的位置。并在符号
表中记录下当前的代码段分配地址和局部数据段要分配的大小(dx 的值)。生成一条 int
指令,分配 dx 个空间,作为这个分程序段的第一条指令。下面就调用语句处理过程
statement 分析语句。分析完成后,生成操作数为 0 的 opr 指令,用于从分程序返回(对
于 0 层的主程序来说,就是程序运行完成,退出)。
常量定义过程 constdeclaration:
通过循环,反复获得标识符和对应的值,存入符号表。符号表中记录下标识符的名
字和它对应的值。
变量定义过程 vardeclaration:
与常量定义类似,通过循环,反复获得标识符,存入符号表。符号表中记录下标识
符的名字、它所在的层及它在所在层中的偏移地址。
语句处理过程 statement:
语句处理过程是一个嵌套子程序,通过调用表达式处理、项处理、因子处理等过程
及递归调用自己来实现对语句的分析。语句处理过程可以识别的语句包括赋值语句、read
语句、write 语句、call 语句、if 语句、while 语句。当遇到 begin/end 语句时,就递归调
用自己来分析。分析的同时生成相应的类 PCODE 指令。
赋值语句的处理:
首先获取赋值号左边的标识符,从符号表中找到它的信息,并确认这个标识符确为
变量名。然后通过调用表达式处理过程算得赋值号右部的表达式的值并生成相应的指令
保证这个值放在运行期的数据栈顶。最后通过前面查到的左部变量的位置信息,生成相
应的 sto 指令,把栈顶值存入指定的变量的空间,实现了赋值操作。
read 语句的处理:
确定 read 语句语法合理的前提下(否则报错),生成相应的指令:第一条是 16 号操
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 3 -
作的 opr 指令,实现从标准输入设备上读一个整数值,放在数据栈顶。第二条是 sto 指
令,把栈顶的值存入 read 语句括号中的变量所在的单元。
write 语句的处理:
与 read 语句相似。在语法正确的前提下,生成指令:通过循环调用表达式处理过程
分析 write 语句括号中的每一个表达式,生成相应指令保证把表达式的值算出并放到数
据栈顶并生成 14 号操作的 opr 指令,输出表达式的值。最后生成 15 号操作的 opr 指令
输出一个换行。
call 语句的处理:
从符号表中找到 call 语句右部的标识符,获得其所在层次和偏移地址。然后生成相
应的 cal 指令。至于调用子过程所需的保护现场等工作是由类 PCODE 解释程序在解释
执行 cal 指令时自动完成的。
if 语句的处理:
按 if 语句的语法,首先调用逻辑表达式处理过程处理 if 语句的条件,把相应的真假
值放到数据栈顶。接下去记录下代码段分配位置(即下面生成的 jpc 指令的位置),然后
生成条件转移 jpc 指令(遇 0 或遇假转移),转移地址未知暂时填 0。然后调用语句处理
过程处理 then 语句后面的语句或语句块。then 后的语句处理完后,当前代码段分配指针
的位置就应该是上面的 jpc 指令的转移位置。通过前面记录下的 jpc 指令的位置,把它的
跳转位置改成当前的代码段指针位置。
begin/end 语句的处理:
通过循环遍历 begin/end 语句块中的每一个语句,通过递归调用语句分析过程分析并
生成相应代码。
while 语句的处理:
首先用 cx1 变量记下当前代码段分配位置,作为循环的开始位置。然后处理 while
语句中的条件表达式生成相应代码把结果放在数据栈顶,再用 cx2 变量记下当前位置,
生成条件转移指令,转移位置未知,填 0。通过递归调用语句分析过程分析 do 语句后的
语句或语句块并生成相应代码。最后生成一条无条件跳转指令 jmp,跳转到 cx1 所指位
置,并把 cx2 所指的条件跳转指令的跳转位置改成当前代码段分配位置。
表达式 expression、项 term、因子 factor 处理:
根据 PL/0 语法可知,表达式应该是由正负号或无符号开头、由若干个项以加减号连
接而成。而项是由若干个因子以乘除号连接而成,因子则可能是一个标识符或一个数字,
或是一个以括号括起来的子表达式。根据这样的结构,构造出相应的过程,递归调用就
完成了表达式的处理。把项和因子独立开处理解决了加减号与乘除号的优先级问题。在
这几个过程的反复调用中,始终传递 fsys 变量的值,保证可以在出错的情况下跳过出错
的符号,使分析过程得以进行下去。
逻辑表达式的处理:
首先判断是否为一元逻辑表达式:判奇偶。如果是,则通过调用表达式处理过程分
析计算表达式的值,然后生成判奇指令。如果不是,则肯定是二元逻辑运算符,通过调
用表达式处理过程依次分析运算符左右两部分的值,放在栈顶的两个空间中,然后依不
同的逻辑运算符,生成相应的逻辑判断指令,放入代码段。
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 4 -
判断单词合法性与出错恢复过程 test 分析:
本过程有三个参数,s1、s2 为两个符号集合,n 为出错代码。本过程的功能是:测
试当前符号(即 sym 变量中的值)是否在 s1 集合中,如果不在,就通过调用出错报告过
程输出出错代码 n,并放弃当前符号,通过词法分析过程获取一下单词,直到这个单词
出现在 s1 或 s2 集合中为止。
这个过程在实际使用中很灵活,主要有两个用法:
在进入某个语法单位时,调用本过程,检查当前符号是否属于该语法单位的开始符
号集合。若不属于,则滤去开始符号和后继符号集合外的所有符号。
在语法单位分析结束时,调用本过程,检查当前符号是否属于调用该语法单位时应
有的后继符号集合。若不属于,则滤去后继符号和开始符号集合外的所有符号。
通过这样的机制,可以在源程序出现错误时,及时跳过出错的部分,保证语法分析
可以继续下去。
语法分析过程中调用的其它子过程相对比较简单,请参考源程序的注释。
类 PCODE 代码解释执行过程分析:
这个过程模拟了一台可以运行类 PCODE 指令的栈式计算机。它拥有一个栈式数据
段用于存放运行期数据、拥有一个代码段用于存放类 PCODE 程序代码。同时还拥用数
据段分配指针、指令指针、指令寄存器、局部段基址指针等寄存器。
解释执行类 PCODE 代码时,数据段存储分配方式如下:
对于源程序的每一个过程(包括主程序),在被调用时,首先在数据段中开辟三个空
间,存放静态链 SL、动态链 DL 和返回地址 RA。静态链记录了定义该过程的直接外过
程(或主程序)运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程
的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说,
SL、DL 和 RA 的值均置为 0。静态链的功能是在一个子过程要引用它的直接或间接父过
程(这里的父过程是按定义过程时的嵌套情况来定的,而不是按执行时的调用顺序定的)
的变量时,可以通过静态链,跳过个数为层差的数据段,找到包含要引用的变量所在的
数据段基址,然后通过偏移地址访问它。
在过程返回时,解释程序通过返回地址恢复指令指针的值到调用前的地址,通过当
前段基址恢复数据段分配指针,通过动态链恢复局部段基址指针。实现子过程的返回。
对于主程序来说,解释程序会遇到返回地址为 0 的情况,这时就认为程序运行结束。
解释程序过程中的 base 函数的功能,就是用于沿着静态链,向前查找相差指定层数
的局部数据段基址。
这在使用 sto、lod 等访问局部变量的指令中会经常用到。
类 PCODE 代码解释执行的部分通过循环和简单的 case 判断不同的指令,做出相应
的动作。当遇到主程序中的返回指令时,指令指针会指到 0 位置,把这样一个条件作为
终至循环的条件,保证程序运行可以正常的结束。
以下源程序是以清华大学出版社《编译原理》中的源代码为基础作了少量改动而成。
程序在 Turbo Pascal 7.0 上编译运行通过。
program pl0(fa,fa1,fa2); (* PL/0 编译程序与代码生成解释运行程序 *)
(* PL/0 compiler with code generation *)
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 5 -
label 99; (* 声明出错跳转标记 *)
(* 在 Turbo Pascal 7.0 中不允许跨过程的 GOTO 转移,
因此后面的 GOTO 语句均被已去除,这里的 label 已没有意义 *)
const (***** 常量定义 *****)
(* of reserved words 保留字的个数 *)
norw = 13;
txmax = 100; (* length of identifier table 标识符表的长度(容量) *)
nmax = 14;
al = 10;
amax = 2047; (* maximum address 寻址空间 *)
levmax = 3;
cxmax = 200;
(* max depth of block nesting 最大允许的块嵌套层数 *)
(* size of code array 类 PCODE 目标代码数组长度 *)
(* max number of digits in numbers 数允许的最长位数 *)
(* length of identifiers 标识符最长长度 *)
type (***** 类型定义 *****)
symbol = ( nul, ident, number, plus, minus, times, slash, oddsym,
eql, neq, lss, leq, gtr, geq, lparen, rparen, comma,
semicolon, period, becomes, beginsym, endsym, ifsym,
thensym, whilesym, writesym, readsym, dosym, callsym,
constsym, varsym, procsym
);
(* symobl 类型枚举了不同类型的词汇 *)
alfa = packed array[1..al] of char;
object1 = (constant, variable, procedur); (* object1 枚举三种标识符 *)
(* 原程序在此使用 object 作为类型名称,
(* alfa 类型用于标识符 *)
在支持面向对象的 Turbo Pascal 7.0 中编译不能通过 *)
(* wirth used the word "procedure" there, whick won't work! *)
(* 上面一行是课本上的程序清单中的注释,说本程序的原作者
Wirth 在这里用了 procedure 这个词作为标识符类型,是不可以的。
事实上 Wirth 原本在这里用的词是 prozedure,是可以的。 *)
symset = set of symbol; (* symset 是 symbol 类型的一个集合类型,
可用于存放一组 symbol *)
fct = (lit, opr, lod, sto, cal, int, jmp, jpc);
(* fct 类型分别标识类 PCODE 的各条指令 *)
instruction = packed record
f: fct;
l: 0..levmax;
a: 0..amax;
(* function code *)
(* level *)
(* displacement addr *)
end;
(* 类 PCODE 指令类型,
包含三个字段:指令 f、层差 l 和另一个操作数 a *)
(*
lit 0, a
load constant a
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 6 -
opr 0, a
lod l, a
sto l, a
cal l, a
int 0, a
jmp 0, a
jpc 0, a
execute opr a
load variable l, a
store variable l, a
call procedure a at level l
increment t-register by a
jump to a
jump conditional to a
*)
var (***** 全局变量定义 *****)
fa: text;
fa1, fa2: text;
(* 文本文件 fa 用于列出源程序 *)
(* 文本文件 fa1 用于列出类 PCODE 代码、
fa2 用于记录解释执行类 PCODE 代码的过程 *)
listswitch: boolean;
(* true set list object code *)
(* 如果本变量置 true,程序编译后将为列出类 PCODE 代码,
否则不列出类 PCODE 代码 *)
ch: char; (* last char read *)
(* 用于词法分析器,存放从文件中读出的最新字符 *)
sym: symbol;
(* last symbol read *)
(* 词法分析器输出结果之用,
存放最近一次识别出来的 token 的类型 *)
id: alfa;
(* last identifier read *) (* 词法分析器输出结果之用,
存放最近一次识别出来的标识符的名字 *)
num: integer;
(* last number read *)
(* 词法分析器输出结果之用,
cc: integer;
ll: integer;
kk: integer;
cx: integer;
存放最近一次识别出来的数字的值 *)
(* character count 行缓冲区指针 *)
(* line length 行缓冲区长度 *)
(* 此变量是出于程序性能考虑,见 getsym 过程注释 *)
(* code allocation index *)
(* 代码分配指针,
line: array[1..81] of char;
代码生成模块总在 cx 所指位置生成新的代码 *)
(* 行缓冲区,用于从文件读出一行,
供词法分析获取单词时之用 *)
(* 词法分析器中用于临时存放正在分析的词 *)
a: alfa;
code: array[0..cxmax] of instruction;
(* 生成的类 PCODE 代码表,
word: array[1..norw] of alfa;
wsym: array[1..norw] of symbol; (* 保留字表中每一个保留字
存放编译得到的类 PCODE 代码 *)
(* 保留字表 *)
对应的 symbol 类型 *)
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 7 -
ssym: array[' '..'^'] of symbol;
(* 一些符号对应的 symbol 类型表 *)
(* wirth uses "array[char]" here *)
mnemonic: array[fct] of packed array[1..5] of char;
(* 类 PCODE 指令助记符表 *)
declbegsys, statbegsys, facbegsys: symset;
(* 声明开始、表达式开始和项开始符号集合 *)
table: array[0..txmax] of record (* 符号表 *)
name: alfa;
case kind: object1 of
(* 符号的名字 *)
(* 符号的类型 *)
constant:
(* 如果是常量名 *)
(val: integer);
(* val 中放常量的值 *)
variable, procedur:
(* 如果是变量名或过程名 *)
(level, adr, size: integer)
(* "size" lacking in orginal. I think it belons here *)
(* 存放层差、偏移地址和大小 *)
end;
fin, fout: text;
(* fin 文本文件用于指向输入的源程序文件,
fout 程序中没有用到 *)
fname: string;
(* 存放 PL/0 源程序文件的文件名 *)
(* 修改的代码:原程序在此处使用 alfa 类型,
无法在 Turbo Pascal 7.0 中通过,
readln 函数的参数不能为 alfa 型 *)
err: integer;
(* 出错总次数 *)
(***** 出错处理过程 error *****)
(* 参数:n:出错代码 *)
procedure error(n: integer);
begin
writeln('****', ' ': cc-1, '!', n:2);
(* 在屏幕 cc-1 位置显示!与出错代码提示,
由于 cc 是行缓冲区指针,所以!所指位置即为出错位置 *)
writeln(fa1, '****', ' ': cc-1, '!', n:2);
(* 在文件 cc-1 位置输出!与出错代码提示 *)
err := err + 1
end (* error *);
(* 出错总次数加一 *)
(***** 词法分析过程 getsym *****)
procedure getsym;
var
i, j, k: integer;
PL0 语言编译程序分析和详细注释(Pascal 版).doc
- 8 -
(***** 读取原程序中下一个字符过程 getch *****)
procedure getch;
begin
if cc = ll then (* 如果行缓冲区指针指向行缓冲区
最后一个字符就从文件读一行到行缓冲区 *)
begin
if eof(fin) then (* 如果到达文件末尾 *)
begin
write('Program incomplete'); (* 出错,退出程序 *)
close(fa);
close(fa1);
close(fin);
halt(0);
{goto 99}
(* 修改的代码,由于 Turbo Pascal 7.0 中不允许
跨过程的 goto,就只能用上面的方法退出程序了。 *)
end;
ll := 0;
cc := 0;
write(cx: 4, ' ');
write(fa1, cx: 4, ' ');
while not eoln(fin) do
begin
ll := ll + 1;
read(fin, ch);
write(ch);
write(fa1, ch);
line[ll] := ch;
(* 行缓冲区长度置 0 *)
(* 行缓冲区指针置行首 *)
(* 输出 cx 值,宽度为 4 *)
(* 输出 cx 值,宽度为 4 到文件 *)
(* 当未到行末时 *)
(* 行缓冲区长度加一 *)
(* 从文件读入一个字符到 ch *)
(* 在屏幕输出 ch *)
(* 把 ch 输出到文件 *)
(* 把读到的字符存入行缓冲区相应的位置 *)
end;
(* 可见,PL/0 源程序要求每行的长度都小于 81 个字符 *)
writeln;
ll := ll + 1; (* 行缓冲区长度加一,
用于容纳即将读入的回车符 CR *)
read(fin, line[ll]);(* 把#13(CR)读入行缓冲区尾部 *)
read(fin, ch);
(* 添加的代码。由于 PC 上文本文件换行是以
#13#10(CR+LF)表示的,所以要把多余的 LF 从文件
读出,这里放在 ch 变量中是由于 ch 变量的值在下面
即将被改变,把这个多余值放在 ch 中没有问题 *)