编译原理课程实验指导书-PL0语言及其编译器

第二部分 上机实验具体要求

“编译原理”的上机实验要求对PL语言及其编译器进行实现、扩充和修改。每个扩充或修改方式可得到不同的分数，满分为100分。

完成上机作业后，必须提交下列文档：

(1) 修改后的PL语言文本。包含词法分析（正规式），语法分析（BNF）。 (2) 有关修改后的PL编译/解释器的说明。详细说明你的编译器是如何编译新的PL语言程序的。指出你的程序中最精彩的部分，以及你为什么这样做，你是如何控制和恢复语义错误的。

(3) 给出你所改动后的编译器源程序清单，并标记出你所修改的部分。比较你的编译器和原来的编译器之间的差别。

(4) 说明你的编译器中可能存在的错误。

(5) 总结经验与教训，如果重做一遍，你会有哪些新的改进？

对现存的PL编译程序可做如下修改或扩充，其中（1）、（2）、（11）和（12）必须完成，剩余的均可任意选择，但总分必须超过40分。

(1) 注释（5分）

注释由(*和*)包含，不允许嵌套。 (2) 布尔类型的数据（10分）

布尔类型的BNF为：

var_option → ε| var var_decl_list

var_decl_list → var_decl | var_decl_list var_decl var_decl → ident_list : data_type data_type → integer | boolean

这种修改包括： （i） 区别整型与布尔型变量、常量和表达式。

（ii） 增加按严格计算的布尔类型运算符and、or和not。这些算符以

及己有的运算符的优先级与Pascal语言相同。

（iii） 能够使用布尔常量true和false。

（iv） 把PL语言中的“条件”概念一般化为Pascal语言那样。 （v） 布尔表达式可以比较大小：false < true (3) 布尔表达式的短路计算（5分） 增加布尔类型（见（2），除（2）的（ii）外），但对and和or采取短路计算。 (4)数组（10分）

增加由任何数据类型构造的一维数组。数组的下标限于纯量类型。

注意：数组可以由其它的数组来构造，因而必须考虑多维数组的情况。数组的上下界可为任意的纯量常数。

数组的定义如下：

data_type → integer | boolean | array [const..const] of data_type

const → ident | number

19

语言中允许有数组说明，对数组元素赋值，在表达式中引用数组元素。为了便于解释执行，可能要增加新的PL机器操作指令。

(5) 参数（10分） 语法同Pascal，采用值-结果方式传递（不用var声明）。 (6) 函数（10分）语法同Pascal。 (7) else子句和repeat语句（5分）

(8) for语句，语法参照Pascal或C语言（5分）

(9) exit语句（退出当前执行过程）和break语句（跳出包含它的最内层循环），（5分）

(10) 记录（结构）,语法同Pascal语言（10分）。 (11) 更有力的语法错误恢复机制（20分） (12) 分离解释和编译器（5分）

注意：上面的这些要求有时会互相影响：例如实现布尔类型数据，则数组和参数就应该能处理其相互组合的情况，如布尔型数组（包括多维数组）、布尔型作为下标的数组、布尔型作为参数传递。甚至能够实现数组作为参数传递等。 另外，为了实现以上功能，你可任意增加PL处理机的指令。但要注意指令的简单与合理。

选做题：此题不计入总分，仅做为学生在有余力的情况下的进一步练习。 实现PL语言的输入、输出语句。其语法、语义定义和Pascal语言相同。可以仅仅实现一次输入或输出一个值的语句——语句参数固定；也可以实现完全和Pascal语言一样，能够接受任意个数参数的输入或输出语句。

20

第三部分 PL语言编译器源程序与示例

1．示例与结果表示

1.1 PL语言源程序

下面我们给出一个PL语言写的二数相乘、除并求最大公约数的算法：

const m = 7, n = 85; var x, y, z, q, r;

procedure multiply; var a, b; begin

a := x; b := y; z := 0; while b > 0 do begin

if odd b then z := z + a; a := 2 * a; b := b / 2; end end;

procedure divide; var w; begin

r := x; q := 0; w := y; while w > y do begin

q := 2 * q; w := w / 2; if w <= r then begin

r := r - w; q := q + 1; end; end end;

procedure gcd; var f, g; begin

21

f := x; g := y;

while f <> g do begin

if f < g then g := g – f; if g < f then f := f – g; end end;

begin

x := m; y := n; call multiply; x := 25; y := 3; call divide; x := 34; y := 36; call gcd; end.

调试结果下：

22