1
附录
附录一 PL/0 语言及其实现
1.1 PL/0 语言简介
PL/0 语言是 Pascal 语言的一个子集，是 Pascal 语言的设计者 Niklaus Wirth 在其专著
Algorithms + Data Structures = Programs 一书（译著书名：算法＋数据结构＝程序）中给出的。
PL/0 是一个小巧的高级语言。虽然它只有整数类型，但它是相当完全的可嵌套的分程
序（block）的程序结构，分程序中可以有常量定义、变量声明和无参过程声明，过程体又
是分程序。PL/0 有赋值语句、条件语句、循环语句、过程调用语句、复合语句和空语句。
由于上面这些语言概念已为大家熟知，因此不再进行语义解释。下面用习题 3.7 所介绍
的扩展方式来给出 PL/0 语言的文法。
Program → Block .
Block → [ConstDecl] [VarDecl][ProcDecl] Stmt
ConstDecl → const ConstDef {, ConstDef} ;
ConstDef → ident = number
VarDecl → var ident {, ident} ;
ProcDecl → procedure ident ; Block ; {procedure ident ; Block ;}
Stmt → ident := Exp | call ident | begin Stmt {; Stmt} end |
if Cond then Stmt | while Cond do Stmt | ε
Cond → odd Exp | Exp RelOp Exp
RelOp → = | <> | < | > | <= | >=
Exp → [+ | − ] Term {+ Term | − Term}
Term → Factor {∗ Factor | / Factor}
Factor → ident | number | ( Exp )
其中的标识符 ident 是字母开头的字母数字串，number 是无符号整数，begin、call、const、
do、end、if、odd、procedure、then、var、while 是保留字。
用 PL/0 语言写的一个程序如下，它有 3 个过程，分别计算两个整数相乘、相除和求最
大公约数。
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;
