第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
PL0编译器源程序分析.doc
PL/0编译器源程序分析
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 程序是不合法的，输出出错提示即可。
下面按各语法单元分析 PL/0 编译程序的运行机制。
分程序处理过程：
1
语法分析开始后，首先调用分程序处理过程（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 层的主程序来说，就是程序运行完成，退出）。
常量定义过程：
通过循环，反复获得标识符和对应的值，存入符号表。符号表中记录下标识符的名字和
它对应的值。
变量定义过程：
与常量定义类似，通过循环，反复获得标识符，存入符号表。符号表中记录下标识符的
名字、它所在的层及它在所在层中的偏移地址。
语句处理过程：
语句处理过程是一个嵌套子程序，通过调用表达式处理、项处理、因子处理等过程及
递归调用自己来实现对语句的分析。语句处理过程可以识别的语句包括赋值语 句、read 语
句、write 语句、call 语句、if 语句、while 语句。当遇到 begin/end 语句时，就递归调用自己
来分析。分析的同时生成相 应的类 PCODE 指令。
赋值语句的处理：
首先获取赋值号左边的标识符，从符号表中找到它的信息，并确认这个标识符确为变 量
名。然后通过调用表达式处理过程算得赋值号右部的表达式的值并生成相应的指令保证这个
值放在运行期的数据栈顶。最后通过前面查到的左部变量的位置信息， 生成相应的 sto 指
令，把栈顶值存入指定的变量的空间，实现了赋值操作。
read 语句的处理：
确定 read 语句语法合理的前提下（否则报错），生成相应的指令：第一条是 16 号操作
的 opr 指令，实现从标准输入设备上读一个整数值，放在数据栈顶。第二条是 sto 指令，把
栈顶的值存入 read 语句括号中的变量所在的单元。
2
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 所指的条件跳转指令的跳转位置改成当前代码段分配位置。
表达式、项、因子处理：
根据 PL/0 语法可知，表达式应该是由正负号或无符号开头、由若干个项以加减号连接
而成。而项是由若干个因子以乘除号连接而成，因子则可能是一个标识符 或一个数字，或
是一个以括号括起来的子表达式。根据这样的结构，构造出相应的过程，递归调用就完成了
表达式的处理。把项和因子独立开处理解决了加减号与乘 除号的优先级问题。在这几个过
程的反复调用中，始终传递 fsys 变量的值，保证可以在出错的情况下跳过出错的符号，使
分析过程得以进行下去。
逻辑表达式的处理：
首先判断是否为一元逻辑表达式：判奇偶。如果是，则通过调用表达式处理过程分析
计算表达式的值，然后生成判奇指令。如果不是，则肯定是二元逻辑运算符， 通过调用表
达式处理过程依次分析运算符左右两部分的值，放在栈顶的两个空间中，然后依不同的逻辑
运算符，生成相应的逻辑判断指令，放入代码段。
3
判断单词合法性与出错恢复过程分析：
本过程有三个参数，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 上编译运行通过。
*******************************************************************************
*****
4
program pl0(fa,fa1,fa2); (* PL/0 编译程序与代码生成解释运行程序 *)
(* PL/0 compiler with code generation *)
label 99; (* 声明出错跳转标记 *)
(* 在 Turbo Pascal 7.0 中已不允许跨过程的 GOTO 转移，因此后面的 GOTO 语句均被我去
除了，因此这里的 label 也没有意义了 *)
const (* 常量定义 *)
norw = 13;
txmax = 100;
nmax = 14;
al = 10;
amax = 2047;
levmax = 3;
cxmax = 200;
type (* 类型定义 *)
symbol = (nul, ident, number, plus, minus, times, slash, oddsym,
(* size of code array *) (* 类 PCODE 目标代码数组长度（可容纳代码行数）*)
(* max depth of block nesting *) (* 最大允许的块嵌套层数 *)
(* length of identifier table *) (* 标识符表的长度（容量） *)
(* max number of digits in numbers *) (* 数字允许的最长位数 *)
(* of reserved words *) (* 保留字的个数 *)
(* length of identifiers *) (* 标识符最长长度 *)
(* maximum address *) (* 寻址空间 *)
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; (* alfa 类型用于标识符 *)
object1 = (constant, variable, procedur); (* object1 为三种标识符的类型 *)
(* 原程序在此使用 object 作为类型名称，在支持面向对象的 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;
(* function code *)
l: 0..levmax; (* level *)
a: 0..amax;
end; (* 类 PCODE 指令类型，包含三个字段：指令 f、层差 l 和另一个操作数 a *)
(*
lit 0, a load constant a
opr 0, a execute opr a
lod l, a load variable l, a
sto l, a store variable l, a
cal l, a call procedure a at level l
int 0, a increment t-register by a
jmp 0, a jump to a
jpc 0, a jump conditional to a
*)
(* displacement addr *)
5
var (* 全局变量定义 *)
fa: text; (* 文本文件 fa 用于列出源程序 *)
fa1, fa2: text; (* 文本文件 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; (* character count *) (* 行缓冲区指针 *)
ll: integer; (* line length *) (* 行缓冲区长度 *)
kk: integer; (* 引入此变量是出于程序性能考虑，见 getsym 过程注释 *)
cx: integer; (* code allocation index *) (* 代码分配指针，代码生成模块总在 cx 所指位置生成
新的代码 *)
line: array[1..81] of char; (* 行缓冲区，用于从文件读出一行，供词法分析获取单词时之用 *)
a: alfa; (* 词法分析器中用于临时存放正在分析的词 *)
code: array[0..cxmax] of instruction; (* 生成的类 PCODE 代码表，存放编译得到的类 PCODE
代码 *)
word: array[1..norw] of alfa; (* 保留字表 *)
wsym: array[1..norw] of symbol; (* 保留字表中每一个保留字对应的 symbol 类型 *)
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 *)
6
(* 参数：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;
(* 读取原程序中下一个字符过程 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; (* 行缓冲区长度置 0 *)
cc := 0; (* 行缓冲区指针置行首 *)
write(cx: 4, ' '); (* 输出 cx 值，宽度为 4 *)
write(fa1, cx: 4, ' '); (* 输出 cx 值，宽度为 4 到文件 *)
while not eoln(fin) do (* 当未到行末时 *)
begin
ll := ll + 1; (* 行缓冲区长度加一 *)
read(fin, ch); (* 从文件读入一个字符到 ch *)
write(ch); (* 在屏幕输出 ch *)
write(fa1, ch); (* 把 ch 输出到文件 *)
line[ll] := ch; (* 把读到的字符存入行缓冲区相应的位置 *)
end;
(* 可见，PL/0 源程序要求每行的长度都小于 81 个字符 *)
writeln;
ll := ll + 1; (* 行缓冲区长度加一，用于容纳即将读入的回车符 CR *)
7
read(fin, line[ll]);(* 把#13(CR)读入行缓冲区尾部 *)
read(fin, ch); (* 我添加的代码。由于 PC 上文本文件换行是以#13#10(CR+LF)表示的，
所以要把多余的 LF 从文件读出，这里放在 ch 变量中是由于 ch 变量的
值在下面即将被改变，把这个多余值放在 ch 中没有问题 *)
writeln(fa1);
end;
cc := cc + 1; (* 行缓冲区指针加一，指向即将读到的字符 *)
ch := line[cc] (* 读出字符，放入全局变量 ch *)
end (* getch *);
begin (* getsym *)
while (ch = ' ') or (ch = #13) do (* 我修改的代码：这句原来是用于读一个有效的字符
(跳过读出的字符中多余的空格)，但实际上还要跳
过多余的回车 *)
getch;
if ch in ['a'..'z'] then (* 如果读出的字符是一个字母，说明是保留字或标识符 *)
begin
k := 0; (* 标识符缓冲区指针置 0 *)
repeat (* 这个循环用于依次读出源文件中的字符构成标识符 *)
if k < al then (* 如果标识符长度没有超过最大标识符长度(如果超过，就取前面一部分，把多
余的抛弃) *)
begin
k := k + 1;
a[k] := ch;
end;
getch (* 读下一个字符 *)
until not (ch in ['a'..'z','0'..'9']); (* 直到读出的不是字母或数字，由此可知 PL/0 的标识符构成规
则是:
以字母开头，后面跟若干个字母或数字 *)
if k >= kk then (* 如果当前获得的标识符长度大于等于 kk *)
kk := k (* 令 kk 为当前标识符长度 *)
else
repeat (* 这个循环用于把标识符缓冲后部没有填入相应字母或空格的空间用空格补足 *)
a[kk] := ' ';
kk := kk - 1
until kk = k;
(* 在第一次运行这个过程时，kk 的值为 al，即最大标识符长度，如果读到的标识符长度小
于 kk，
就把 a 数组的后部没有字母的空间用空格补足。
这时，kk 的值就成为 a 数组前部非空格字符的个数。以后再运行 getsym 时，如果读到的标
识符长度大于等于 kk，
就把 kk 的值变成当前标识符的长度。
这时就不必在后面填空格了，因为它的后面肯定全是空格。反之如果最近读到的标识符长度
小于 kk，那就需要从 kk 位置向前，
把超过当前标识长度的空间填满空格。
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
