从零开始写一个 CX 编译器(编译原理作业)

关于学校中的作业,我向来是不屑于写博客的。这一次,我决定尝试一下,而且恐怕之后也不会再有了。

另外呢,这篇文章对各位同学而言,可能并没有什么参考价值,至于为何,你很快就会明白了。

作业要求

这部分来源于老师提供的作业要求。

补充说明:必须编译为中间代码 P-Code。

惯用的词法

  1. 下面是语言的关键字包括: int bool if else while write read,所有的关键字都是保留字,并且必须是小写

  2. 专用符号:+ - * / < <= > >= == != = || && ! ; ( ) { } /* */

  3. 其他标记:

    标识符:字母打头,后接字母或数字,识别出的标识符用 ID 标记,区分大小写字母

    无符号整数:由数字组成,用 NUM 标记

    1
    2
    3
    4
    <ID>∷=<letter>|<ID><letter>|<ID><digit>
    <NUM>∷=<digit>|<NUM><digit>
    <letter>∷= a|b|…|z|A|B|…|Z
    <digit>∷=1|2|…|9|0
  4. 空格由空白、换行符和制表符组成。空格分开 ID、NUM 关键字

  5. 注释用 /*….*/ 括起,可以放在任何空白出现的位置,可以超过一行,注释不能嵌套

语法和语义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1)<program> ∷= <block>
2)<block> ∷= {<decls> <stmts>}
3)<decls> ∷=<decls> <decl> | ε
4)<decl> ∷= int <aid>; | bool <bid>;
5)<aid> ∷= <ID>
6)<bid> ∷= <ID>
7)<stmts> ∷= <stmts> <stmt> | ε
8)<stmt> ∷= <aid> = <aexpr>; | <bid> = <bexpr>; | if (<bexpr>) <stmt>; | if (<bexpr>) <stmt> else <stmt>; | while (<bexpr>) <stmt>; | write <aexpr>; | read <aid>; | <block>
9)<aexpr> ∷= <aterm> + <aterm> | <aterm> - <aterm> | <aterm>
10)<aterm> ∷= <afactor> * <afactor> | <afactor> / <afactor> | <afactor>
11)<afactor> ∷= <aid> | NUM | (<aexpr>)
12)<bexpr> ∷= <bexpr> || <bterm> | <bterm>
13)<bterm> ∷= <bterm> && <bfactor> | <bfactor>
14)<bfactor> ∷= <bid> | true | false | ! <bfactor> | (<bexpr>) | <rel>
15)<rel> ∷= (<aid>|NUM) (< | <= | > | >= | == | !=) <aexpr>

注意:规则2)中的符号“{”” 、“}”为终结符号,不是元符号,规则8)、11)、14)中出现的符号“(”和“)”也是终结符号,不是元符号

关于语义有几点说明:

  1. 变量应该先声明后使用。变量声明如果和上一层{}中的变量重名,认作是最近的{}声明的变量处理
  2. If 语句存在悬挂 else 二义性,使用“最近嵌套”非二义性规则解决:else 部分作为当前if的一个子结构立即分析
  3. 符号 / 表示整数除,任何余数都被截去

评分规则

  1. 文档、程序、测试用例齐全,并完成所在分组的指定扩展点,成绩为合格(60分)。

  2. 根据用户界面的友好程度给予加分。满分为10分,必须支持目标代码单步执行时查看数据栈的功能。只支持命令行运行的不给加分。

  3. 根据分组检查时间的先后给予时间分。共计有8次检查,时间分依次为 8、6、5、4、3、2、1、0 分。

  4. 对给出的 CX 语法,可以作如下的扩展或修改(但不限于这些)。必须在说明文档中给出扩展点的语法定义。

    1. 增加运算符

      1. 求余运算符 %(2分)
      2. 异或运算符 XOR(2分)
      3. 判断整数的奇偶 ODD(2分)
      4. 自增++,自减--(3分)
    2. 增加语句,语法参照 C 语言

      1. case 语句(6分)
      2. for 语句(6分)
      3. break 语句(4分)
      4. continue 语句(4分)
      5. exit 语句(4分)
      6. do…while 语句(2分)
      7. repeat…until 语句(2分)
    3. 增加基本数据类型

      1. 可扩充到支持实数数据类型,实现 +、-、*、/ 等运算。可以采用两种方案:一种是整数类型和实数类型等不允许“混合使用”,但存在两种数据类型的转换操作符;另一种是允许“混合使用”,如当运算结果赋给整型变量时候则自动取整。(10分)
      2. 还可以增加如字符等数据类型(视实际情况给分)
    4. 增加常量(const)的定义与使用(4分)

      区分变量与常量,可以参考PL/0语言中的实现方法

    5. 扩充数组功能(10分左右,视实际情况给分)

      增加由任何数据类型构造的确定性一维数组,如整型数据数组。允许定义数组、对数组元素赋值、在表达式中引用数组元素等。

    6. 允许调用 (call) 过程(8分左右,视实际情况给分)

      可以参考 PL/0 语言中的实现方法,也可以参考C语言中的实现方法

    7. 扩充带参数、返回值的过程(15分左右,视实际情况给分)

      比较容易实现的一种模式是数值参数(call by value):调用的实际参数是表达式,它在调用时被算出具体的值。形式参数表示过程的局部变量,它在调用时被赋予相应的实际参数值。此外还可以使用地址参数(call by reference)。过程还可以有返回值。

    8. 增加记录(结构)(10分左右,视实际情况给分)

    9. 允许并鼓励在编译器的实现当中(部分)使用 Lex 和 Yacc 等自动工具。

    注意:上面的这些要求有时会相互影响,也可能需要对语法定义作一定的修改。

建议与决策

以下仅仅是我个人的理解,或许会对同样需要完成这份作业的你有所启发。

首先意识到书上和课上教的是不足以足量完成作业的,相信大家不会只求通过课程。

然后我们需要完成的是一个类 C 语言的编译器,编译出来的中间代码是 PCode。

在自己写的过程中,最好是有代码可以参考,而且是 C 编译器的实现。

然而网上的代码往往原地解释执行或者编译成 ASM,和作业要求不符。

所以目标可以分解为

  1. 写一个 Parser 把代码转成 AST (或者先转成 token 序列,然后再转成 AST)
  2. 把 AST 翻译为 P-Code
  3. 写一个 P-Code 虚拟机

目标 1

有两种选择:

  • 代码生成(如 lex + yacc)
  • 编译组合子 Parser Combinator

两者各有优劣,对于我来说倾向于后者,主要是因为更加优雅,而且不用担心,常见的语言都会有 Parser Combinator 的库,建议看一看它的例子,挑一个喜欢就好了。

目标 2

这一部分,不需要借助外部的库,无论你用什么语言,都是相通的。我相信稍微看几个把 AST 转成中间代码的例子,就能优雅地实现出来。

这里是一个很好的可供参考的例子,而且我决定使用和它一样的 P-Code(见 目标3)

目标 3

提供的 Pascal 代码中已经有 P-Code 解释器了,但是肯定还要重写。因为我们必须对已有的 P-Code 进行扩展,否则不足以支撑 CX 语言的复杂程度。这部分应该算是整个作业中最容易的部分(除非你决定要写调试界面)。

提供的 P-Code 有诸多弊病,由于它是为 PS/0 语言(一款极其简陋的语言)设计的,并不适合类 C 语言(比如没有类型)。我很幸运在网上找到了适合 C 语言的 P-Code,链接,是安特卫普大学(一所位于比利时的大学)的课程作业所提供的,完成度相当之高,同时提供了对应的 P-Machine 的源码。我决定基于此完成这个编译器。

在这里多说两句,这一所大学的知名度似乎也不是很高,这里的 P-Machine 也是在 2001 年就有了。我校使用的 07 年的教材(使用至今)远不及此,而且编译原理还是我校的特色精品课程,有些滑稽。

我的选择

为什么选择 Scala?

  • 甜到腻的语法糖,虽然有人不喜欢这个,但是我太喜欢了
  • 自由的运算符重载(此处 diss 一下 Java)
  • 强大的类型系统
  • 好用的模式匹配(通常与 FP 一同出现)正适合用来处理 AST

使用的库为 scala-parser-combinators,理由如下:

  • 代码像诗歌
  • 网上能找到一个完整的编程语言例子
  • 自信

语言特性的取舍

由于有些语言特性比较繁琐,与其实现这些,不如用这些时间实现一些别的特性。

以下按照完全体作业要求:

放弃的特性:

  • 结构体:结构体套结构体,结构体数组
  • 指针:解引用,指针套指针,常指针,指针运算
  • 数组(部分特性):多维数组只给定若干维当低维数组或者指针使用
  • 界面:我想问一下,你有没有见过编译器还自带界面的?写这个就偏离了这门课的初衷了。
  • 浮点数:如果不是因为这个 P-Code 太垃圾了,我肯定会加入这个特性的。 现在这个 P-Code 很强。

增加的特性:

  • 声明和语句混合:不一定要把所有声明放在 block 的最前面
  • 多维数组:需要计算地址
  • 函数:参数列表可能挺困难的
  • C 语言提供的循环 (for, while ... do ..., do ... while ...):没什么难度

从表达式开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class CXParser extends StandardTokenParsers {
lexical.delimiters ++= List("+", "-", "*", "/", "%")

def expr: Parser[Expr] =
factor ~ opt(("+" | "-") ~ factor) ^^ {
case a ~ None => a
case a ~ Some(op ~ b) => new Operator(op, a, b)
}

def term: Parser[Expr] =
factor ~ opt(("*" | "/" | "%") ~ factor) ^^ {
case a ~ None => a
case a ~ Some(op ~ b) => new Operator(op, a, b)
}

def factor: Parser[Expr] =
numericLit ^^ { a => Num(a.toInt) } |
ident ^^ { new Identifier(_) } |
"(" ~> expr <~ ")" ^^ identity

def parseAll[T](p: Parser[T], in: String): ParseResult[T] = {
phrase(p)(new lexical.Scanner(in))
}
}

注:Expr 和调用 parser 代码附在之后。

我相信只要对照要求中给出的语法就能很容易地看懂这份代码。稍微提一下几个运算符的含义:

  • rule ^^ block 在应用这条规则之后执行代码块
  • ~ 连接,~> 连接并只保留右侧结果,<~ 连接并只保留左侧结果

测试结果:

1
2
3
4
5
6
7
8
1 + 1
Operator(+,Num(1),Num(1))

1 + 1 + 1
failed to parse CX input (line 1, column 2):
end of input expected
1 + 1 + 1
^

我以为我写错了,但实际上是文法根本不支持 1 + 1 + 1。但是作为一个完美主义者,不可能接受一个连 1 + 1 + 1 都要报语法错误的语言。随后我发邮件询问了老师,老师表示可以自行扩展文法。

于是将文法修改为(保证了无二义以及优先级的正确性):

1
2
3
9) <aexpr> ∷= <aexpr> + <aterm> | <aexpr> - <aterm> | <aterm>
10) <aterm> ∷= <aterm> * <afactor> | <aterm> / <afactor> | <afactor>
11) <afactor> ∷= <aid> | NUM | (<aexpr>)

修改后直接运行代码,会发现 StackOverFlow 了。原因很简单,左递归了(从而猜测库的实现是递归下降)。消除左递归都学过,只要引入一条新的规则即可,如:

1
2
9) <aexpr> ∷= <aterm> | <aexprtail>
9.5) <aexprtail> ∷= + <aterm> <aexprtail> | - <aterm> <aexprtail> | ε

但是不得不说,有点丑陋。于是我试图寻找能够自动解决左递归的方法。随后发现库中提供了名为 PackratParsers 的特质。说明如下:

PackratParsers is a component that extends the parser combinators provided by Parsers with a memoization facility (Packrat Parsing).

Packrat Parsing is a technique for implementing backtracking, recursive-descent parsers, with the advantage that it guarantees unlimited lookahead and a linear parse time. Using this technique, left recursive grammars can also be accepted.

配合 WikiPedia 中的信息,我们能明确这个东西在 lookahead 的同时,用记忆化的方式以空间的代价换来了线性的 parse 时间,因而对文法本身的限制更少(比如左递归)。

之后重写关于 exprterm 的 parser 为:

1
2
3
4
5
6
7
8
9
10
11
12
class CXParser extends StandardTokenParsers with PackratParsers {
// ...
lazy val expr: PackratParser[Expr] =
expr ~ ("+" | "-") ~ term ^^ {
case a ~ op ~ b => new Operator(op, a, b)
} | term ^^ identity

lazy val term: PackratParser[Expr] =
term ~ ("*" | "/" | "%") ~ factor ^^ {
case a ~ op ~ b => new Operator(op, a, b)
} | factor ^^ identity
// ...

以下为 Expr 和调用 parser 代码:

1
2
3
4
5
6
7
class Expr

case class Num(value: Int) extends Expr

case class Operator(op: String, var left: Expr, right: Expr) extends Expr

case class Identifier(name: String) extends Expr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import scala.io.Source

object Run extends App {
val inputFile = Source.fromFile("src/test/cx/expr.cx")
val inputSource = inputFile.mkString

val parser = new CXParser
parser.parseAll(parser.expr, inputSource) match {
case parser.Success(r, n) =>
println(r)
case parser.NoSuccess(err, next) =>
println("failed to parse CX input " +
"(line " + next.pos.line + ", column " + next.pos.column + "):\n" +
err + "\n" +
next.pos.longString)
}
}

更完善的表达式

考虑到有各种一元二元运算符,数组取下标等优先级复杂的运算,决定直接参考 C 语言的设计。

这里有一份 C 语言的 BNF 语法,在删去一些暂且不打算实现的东西(如位运算,指针)完成新的 parser。

有一些坑,比如用 | 连接的规则会优先使用前面的,所以得把左递归的规则放在前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
  def type_name: Parser[String] = "int" | "bool"

def build_binary_op(x: Expr ~ String ~ Expr): BinaryOp =
x match { case a ~ op ~ b => BinaryOp(op, a, b) }

lazy val expression: PackratParser[Expr] = assignment_expression

lazy val assignment_expression: PackratParser[Expr] =
(ident <~ "=") ~ assignment_expression ^^ { case i ~ e => AssignExpr(Identifier(i), e)} |
constant_expression

def build_binary_op_expr(old_expr: PackratParser[Expr], op: Parser[String]): PackratParser[Expr] = {
lazy val new_expr: PackratParser[Expr] =
new_expr ~ op ~ old_expr ^^ { case a ~ op ~ b => BinaryOp(op, a, b) } |
old_expr
new_expr
}

lazy val constant_expression: PackratParser[Expr] = List[Parser[String]](
"*" | "/" | "%",
"+" | "-",
"<" | ">" | "<=" | ">=",
"==" | "!=",
"&&",
"||").foldLeft(cast_expression)(build_binary_op_expr)

lazy val cast_expression: PackratParser[Expr] =
unary_expression |
("(" ~> type_name <~ ")") ~ cast_expression ^^ { case tp ~ e => CastExpr(tp, e) }

lazy val unary_expression: PackratParser[Expr] =
postfix_expression |
("++" | "--") ~ unary_expression ^^ { case op ~ e => UnaryOp(op, e) } |
("+" | "-" | "~" | "!") ~ cast_expression ^^ { case op ~ e => UnaryOp(op, e) }

lazy val postfix_expression: PackratParser[Expr] =
primary_expression |
postfix_expression ~ ("++" | "--") ^^ { case e ~ op => UnaryOp("_" + op, e) } |
postfix_expression ~ ("[" ~> expression <~ "]") ^^ { case a ~ b => BinaryOp("[]", a, b) }

lazy val primary_expression: PackratParser[Expr] =
numericLit ^^ { a => Num(a.toInt) } |
ident ^^ { Identifier } |
"(" ~> expression <~ ")"

最后完成一些测试,总不能每次修改代码后测试 1 + 2 能不能正常解析吧?

用的库是 ScalaTest,大概长这样。以前只知道单元测试和 TDD(测试驱动开发),却不知道还有 BDD(行为驱动开发),而这个库属于 BDD。具体差别可以自行搜索。

1
2
3
4
5
6
7
8
9
10
11
class ExprSpec extends FlatSpec {
behavior of "Expr parser"

val parser = new CXParser

it should "parse 1 + 2" in {
parser.parseAll(parser.expression, "1 + 2") match {
case parser.Success(r, _) => assert(r == BinaryOp("+", Num(1), Num(2)))
}
}
}

然而可以发现有大量重复代码,所以重构一下,把几个基本运算重新组合一下,并顺利通过测试。

P-Code 虚拟机

本来这里我用 Scala 翻译了一下提供的 Pascal 代码中的 P-Code 解释器的部分,但是由于我更换了 P-Code 所以这部分删掉了。

这里是新的 P-Code 的链接,包含了指令的说明,实现的说明,实现的源码及二进制文件。

注:没有提供 Linux 下的二进制文件(提供的 Windows 二进制文件不支持 Win10),但是直接 make 会有错误,需要对一些文件稍作修改。另外我根据作业的需要,增加了一些指令,修改后的 P-Machine 放在了 Github 上,如有需要请自取。

对于提供的 P-Machine 指令说明,我补充一下几个指针的含义,另外这里也许能给你一些启发:

  • SP: 栈指针
  • PC: 当前指令指针
  • MP: 动态链,也就是当前活跃栈帧的起点
  • EP: Extreme Pointer,当前栈的最高可能位置,换句话说,就是这个函数调用过程中,栈指针的最大的可能位置,有助于检测栈溢出。
  • NP: 堆指针

Compiler Design: Virtual Machines 的第二章对于理解 P-Machine 很有帮助,强烈推荐!

实现编译器

这部分我就不贴代码了,我会把最终版本放到 Github 上(估计不会带本地 commit 历史,需要的话可以问我要),接下来我就叙述一下实现的阶段和一些难点。

实现阶段:

  • 实现了输出一个表达式的值(包括类型和类型转换),如:{ write (1 + 2) * 3; }
  • 实现了变量与赋值(包括常量,作用域,符号表,空间预分配),如: { int x = 1; x = x + 1; write x; }
  • 实现了 if 语句
  • 实现了函数及函数调用(包括函数表,返回语句,参数传递),然后就可以求 GCD 和阶乘了。
  • 写了一些源代码到运行结果的测试,因为 parser 代码比较少,就没写 parser 的测试。