从零开始写一个 CX 编译器（编译原理作业）

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

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

作业要求

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

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

惯用的词法

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

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

3. 其他标记：

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

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

   <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)<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 ...)：没什么难度

从表达式开始

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 + 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 都要报语法错误的语言。随后我发邮件询问了老师，老师表示可以自行扩展文法。

于是将文法修改为（保证了无二义以及优先级的正确性）：

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

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

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 时间，因而对文法本身的限制更少（比如左递归）。

之后重写关于 expr 和 term 的 parser 为：

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 代码：

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

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。

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

  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。具体差别可以自行搜索。

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 的测试。
• 实现了一些循环语句
• 实现了数组
• 补全了循环语句和运算符

已开源 https://github.com/zerolfx/CX-Compiler 还是带了本地 commit 历史，课程作业而已，需要的话随便看看就好。