Vincent Bel's Blog

PL/0简单编译系统:(零)综述

Post on January 10, 2015

对于有了一些编译原理理论基础的人,自己动手实现一个编译器将会有许多的收获。而一个编译器的构造十分复杂,要实现一个编译器更是十分困难。在这些编译器之中,PL/0 编译系统是一个十分简单的编译系统,十分适合于学习。

这学期学了编译原理这门课程,期末自己动手实现了一个 PL/0 简单编译系统。接下来将记录在实现过程中的心得、遇到的问题和解决办法,如有错误之处,欢迎指正。

PL/0 编译系统介绍

对于一般的编译程序,总有如下典型的编译过程: 典型的编译过程

对于 PL/0 编译系统,也有上述的基本过程。而 PL/0 的编译过程分两个阶段进行:

  1. 将源程序编译成 P-code。
  2. 对 P-code 进行解释执行,得到运行结果。

第一阶段:将源程序编译成 P-code

第一阶段的主要过程如下图。这一阶段将会以语法分析程序为核心,通过语法分析程序调用其它各个模块来实现。生成的 P-code 指令是一种类型与汇编语言的指令。 将源程序编译成 P-code

第二阶段:对 P-code 进行解释执行

这一阶段将对 P-code 解释执行,过程如下图。 对 P-code 进行解释执行

PL/0 语言文法的 EBNF 表示:

<程序> ::= <分程序>.
<分程序> ::= [<常量说明部分>][<变量说明部分>][<过程说明部分>]<语句>
<常量说明部分> ::= const<常量定义>{,<常量定义>};
<常量定义> ::= <标识符>=<无符号整数>
<无符号整数> ::= <数字>{<数字>}
<标识符> ::= <字母>{<字母>|<数字>}
<变量说明部分>::= var<标识符>{,<标识符>};
<过程说明部分> ::= <过程首部><分程序>{;<过程说明部分>};
<过程首部> ::= procedure<标识符>;
<语句> ::= <赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句>|<读语句>|<写语句>|<复合语句>|<重复语句>|<空>
<赋值语句> ::= <标识符>:=<表达式>
<表达式> ::= [+|-]<项>{<加法运算符><项>}
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>|<无符号整数>|'('<表达式>')'
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<条件> ::= <表达式><关系运算符><表达式>|odd<表达式>
<关系运算符> ::= =|<>|<|<=|>|>=
<条件语句> ::= if<条件>then<语句>[else<语句>]
<当型循环语句> ::= while<条件>do<语句>
<过程调用语句> ::= call<标识符>
<复合语句> ::= begin<语句>{;<语句>}end
<重复语句> ::= repeat<语句>{;<语句>}until<条件>
<读语句> ::= read'('<标识符>{,<标识符>}')'
<写语句> ::= write'('<表达式>{,<表达式>}')'
<字母> ::= a|b|...|X|Y|Z
<数字> ::= 0|1|2|...|8|9

PL/0 语言的一个例子:

VAR x, squ;

PROCEDURE square;
BEGIN
   squ:= x * x
END;

BEGIN
   x := 1;
   WHILE x <= 10 DO
   BEGIN
      CALL square;
      ! squ;
      x := x + 1
   END
END.

接下来做什么

整个编译器的实现使用 Java 语言编写。不使用 LexYacc 等编译程序生成工具。语法分析使用简单的递归下降分析法。

同时,将会在 我的 github上使用 commit 的方式对每一个步骤进行跟踪,加深理解。

接下来将从以下 6 部分逐步实现一个 PL/0 编译系统:

  1. 词法分析
  2. 语法分析
  3. 符号表的管理
  4. 出错处理
  5. 目标代码生成
  6. 解释执行

参考资料:

[1] 张莉, 杨海燕, 史晓华等. 编译原理及编译程序构造[M]. 清华大学出版社, 2011:307-327.
[2] jiangnan314 编译实践 - PL/0 编译系统实现
[3] https://en.wikipedia.org/wiki/PL/0