构建一个简单的 .NET 编译器

• 下载源代码 - 3.4 KB

引言

Microsoft 的 .NET 框架旨在实现多种语言之间的互操作性。为此，其设计者创建了一个“一统所有语言”的语言，这是一种相当底层的语言，可以访问 .NET CLR 的所有功能。它被称为公共中间语言 (Common Intermediate Language, 简称 CIL)；所有其他 .NET 语言都编译成它。如果 .NET 虚拟机字节码是其机器代码，那么 CIL 就是其汇编语言。它无需付出巨大的努力即可阅读，并且比大多数汇编语言更具表现力，使其成为出色的编译目标，即使对于初学者来说也是如此：它几乎就像用一种高级语言编写与另一种高级语言之间的翻译器。

在本文中，我们将构建最简单的 .NET 编译器：一个整数计算器。

为什么是计算器？

计算器没有理由编译成 .NET CIL 或其他任何东西；输入表达式所花费的时间远远超过即使是最天真的解释器花费来评估它们的时间。然而，一个编译型计算器对我们来说是完美的，因为它是一个完整编译器的缩影；我们可以遵循真实语言编译器相同的步骤，而复杂度远低于最简单的编程语言所包含的复杂度。

• 标记化 (将代码分解为其组成符号)
• 解析 (将这些符号转换为语义结构的内部表示)
• 编译 (将内部表示转换为可执行格式，本例中为 CIL)

计算器概述

首先，让我们描述一下计算器的输入格式。我们的格式比任何袖珍计算器都简单：输入仅限于正整数、运算符 +, -, *, ÷ 或 /, ^, % 以及括号。我们将它们组合起来构成表达式，例如

3 * (4 - 1) + 2 ^ 3
2 + 1
15 % 3 + 2

语法非常小 (有关此处的表达方式，请参阅维基百科关于巴科斯-诺尔范式的文章)

expression → ['('] integer [ { operator expression } ] [')']
integer → {digit}
digit → '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
operator → '+' | '-' | '*' | '/' | '÷' | '^' | '%'

我们的计算器需要正确处理运算顺序，以免用户不得不费心重新排列或过度使用括号来表示他们的表达式：运算顺序为 () → % 或 ^ → * 或 / → + 或 -。也就是说，这正是你在小学（如果你有专心听的话）学到的顺序。

实现

我们的输入表达式将由一个具有三个 `private` 方法的 `Program` 对象的构造函数处理

• Tokenize()
• Parse()
• Execute()

`Tokenize()` 将表达式分解成它的组成部分；`Parse()` 处理这些组成部分以创建表达式的内部后缀表示；`Execute()` 将其编译成 CIL，然后立即运行。

分词

我们的标记器将逐个字符地遍历代码，将其分解成标记。标记是（可能是多位数的）数字，或者是单字符运算符或括号；当我们看到任何非数字字符时，我们就知道我们已经读完了一个数字。我们将把生成的标记存储在一个 `string` 列表中。

我们的标记化算法非常简单

for each character c in the code:
    if c is an operator:
        if there's a number being built, add it as a token
        add c as a token
    else if c is whitespace:
        if there's a number being built, add it as a token
    else if c is a digit:
        append c to the number accumulator
    else:
        throw a parsing error
end for

if there's a number left in the accumulator:
    add it as a token

其实现同样简单

private void Tokenize(string expression) {
    // place to accumulate digits
    string number = "";

    // loop by char through code
    foreach (char c in expression) {

        // operators can end tokens as well as being one
        if (IsOperator(c.ToString()) ||
            "()".Contains(c.ToString())) {

            if (number != "") {
                Tokens.Add(number);
                number = "";
            }
            Tokens.Add(c.ToString());
        }
        // spaces end numbers
        else if (c == ' ') {
            if (number != "") {
                Tokens.Add(number);
                number = "";
            }
        }
        // digits can combine, so store each one
        else if ("0123456789".Contains(c.ToString())) {
            number += c;
        }
        else {
                // barf if you encounter something not a digit,
                // space, or operator
                throw new ParseException(
                    "Unexpected character '" + c.ToString() + "'.");
        }
    }

    // add the last token if there is one
    if (number != "") {
        Tokens.Add(number);
    }

    return;
}

请注意，我们使用了最简单的标记实现，每个标记都只是一个 `string`。如果我们想保留解析或编译错误发生的行号和列号信息，我们就必须使用一个携带这些数字的标记对象。对于真正的编程语言，我们必须这样做，但我们的表达式足够短，几乎不需要这样做；如果遇到意外字符就会抛出的 `ParseException` 应该足以指出用户的错误。

解析

.NET CIL 大多数操作都使用堆栈；也就是说，你将操作数推入堆栈，然后发出操作它们的指令。堆栈机器最自然的数学表示是后缀表示法，其中运算符跟在操作数之后；即 3 + 4 → 3 4 +，或 12 / (3 + 1) → 12 3 1 + /。这种表示法允许你在它们出现的顺序上将操作数推入堆栈，并在遇到它们时应用操作。唯一的诀窍是重新排列标记以获得正确的顺序，处理运算顺序和带括号的表达式。

与许多情况一样，有一个高效且易于实现的算法，由杰出的 Edsger W. Dijkstra 构思；我自己可能无法得出这个算法。它被称为移位-输出算法 (shunting-yard algorithm)，它大致如下：

移位-输出算法

给定一个标记流，创建一个运算符**堆栈**和一个标记的**输出列表**。

for each token in the stream
    if token is operator:
        while (stack.peek has higher precedence or
               (stack.peek has equal precedence and
                stack.peek is left-associative)) and
              stack.peek is not '(':
            pop from stack to end of output list
        push token to stack
    else if token is '(':
        push token to stack
    else if token is ')':
        while stack.peek is not '(':
            pop from stack to end of output list
        pop '(' from stack and discard
    else if token is numeric:
        append to output list
end for

while stack has operators:
    pop from stack to end of output list

我们的实现几乎直接对应于上面的伪代码。为了提高可读性，我们将所有将运算符从堆栈弹出到输出列表的逻辑移动到一个单独的方法 `PopOperators(string token)` 中，当遇到新运算符时执行。

 private void Parse() {

      foreach (string token in Tokens) {
          if (IsOperator(token)) {
              PopOperators(token);
              OperatorStack.Push(token);
          }
          else if (token == "(") {
              // parens only go on stack temporarily, 
              // as they're not ops
              OperatorStack.Push(token);
          }
          else if (token == ")") {
              while (OperatorStack.Peek() != "(") {
                  Postfix.Add(OperatorStack.Pop());
              }
              OperatorStack.Pop();
          }
          else if (int.TryParse(token, out int throwaway)) {
              Postfix.Add(token);
          }
          else {
              throw new ParseException(
                  "Unrecognized token: " + token + ".");
          }
      }

      while (OperatorStack.Count > 0) {
          Postfix.Add(OperatorStack.Pop());
      }
  }

`PopOperators(token)` 方法有点丑陋，因为我们的算法会将括号推入运算符堆栈；如果我们尝试将它们解析为运算符，将会失败。我们将化繁为简，并利用此条件来检测括号。

private static bool GreaterPrecedence(Operator a, Operator b) {
    return (a.Precedence > b.Precedence) ||
        ((a.Precedence == b.Precedence) &&
         (b.Associativity == Associativities.Left));
}

private void PopOperators(string token) {
    Operator cur = OperatorFromString(token);

    // if there are no operators, get out
    if (OperatorStack.Count == 0) {
        return;
    }

    try {
        for (Operator top = OperatorFromString(OperatorStack.Peek());
             (OperatorStack.Count > 0 && GreaterPrecedence(top, cur));
             top = OperatorFromString(OperatorStack.Peek())) {
            Postfix.Add(OperatorStack.Pop());
        }
    }
    catch (ParseException) {
        // it's a parenthesis, which can't be parsed as an operator
        return;
    }
}

我不确定我是否为这个感到自豪，但它简短而有效。

无论如何，一旦 `Parse()` 完成，我们就得到了一个后缀表示法的操作数和运算符列表，当消费程序调用 `Execute()` 方法时，即可编译和运行。

编译

在我们这里，编译一点也不难。由于我们已经在处理后缀表示法，我们会按正确的顺序遇到操作数和运算符；我们可以逐个将它们翻译成 CIL。

for each token in postfix:
    if token is an integer:
        emit CIL to push it to the stack
    else if token is an operator:
        emit CIL to consume operands and push result to the stack
    else:
        throw a compilation exception about an unrecognized token

所以，例如，如果用户输入表达式

3 * (4 + 2)

它将被解析成后缀表示法，即 3 4 2 + *。当我们编译它时，我们将发出指令来

1. 将 3 推入堆栈
2. 将 4 推入堆栈
3. 将 2 推入堆栈
4. 将堆栈顶部的两个数字（2 和 4）相加，并将结果（6）推入堆栈 — 此时堆栈为 [3 6]。
5. 将堆栈顶部的两个数字（3 和 6）相乘，并将结果（18）推入堆栈

执行这些指令后，堆栈上唯一剩下的数字就是结果 18。在 CIL 中，指令将是

ldc.i4 3
ldc.i4 4
ldc.i4 2
add
mul

这些指令可能看起来有点晦涩，但它们都很容易理解并且文档齐全。`ldc.i4` 将其数字参数作为 32 位整数加载到堆栈；`add` 和 `mul` 分别执行加法和乘法。

预编译准备工作

我们将使用 `Reflection.Emit 命名空间` 的内容来生成 CIL。它是一种简洁、高效、可读的方式，可以动态创建程序集。它还消除了运行 `ilasm` 处理已保存的 CIL 和执行外部可执行文件的责任，正如你将看到的：我们可以加载和运行程序集，而无需将其写入磁盘。

我们需要做的第一件事是创建一个与当前程序集在同一应用程序域中运行的程序集。

// create everything needed to start writing CIL
AppDomain domain = AppDomain.CurrentDomain;
AssemblyName name = new AssemblyName();
name.Name = "CalculatorExpression";
// make a run-only assembly (can't save as .exe)
AssemblyBuilder asm = domain.DefineDynamicAssembly(
    name, AssemblyBuilderAccess.Run);

(请注意，我们可以轻松创建可以保存到磁盘作为单独可执行文件的持久性程序集 — 为此，我们将使用 `AssemblyBuilderAccess.Save`。就我们而言，创建、执行和丢弃程序集是最容易的。)

现在我们有了程序集，我们将向其中添加一个模块，创建一个类型来表示我们的表达式，并添加一个 `WriteValue()` 方法，该方法将计算表达式的值并将其写入控制台。

ModuleBuilder module = asm.DefineDynamicModule(
    "CalculatorExpressionModule");
TypeBuilder tpb = module.DefineType(
    "ExpressionExecutor", TypeAttributes.Public);
// the method that will hold our expression code
MethodBuilder meth = tpb.DefineMethod(
    "WriteValue", MethodAttributes.Public | MethodAttributes.Static);

除了类型和方法之外，所有其他名称对我们来说都不重要；我们不会再次引用它们。请注意，该方法是 `static` 的；对于一个计算，不需要实例化一个类。

为了编写构成我们新方法的 CIL，我们创建一个新的 `ILGenerator`。

// thing that writes CIL to the method
ILGenerator il = meth.GetILGenerator();

现在我们可以使用我们的 `ILGenerator` 将我们想要的任何 CIL 写入 `WriteValue` 方法。

编译表达式

我们将遍历我们后缀表示法中的标记，并按顺序处理它们。我们尝试将一个整数解析到一个输出变量；如果成功，我们就发出 CIL 将结果推入堆栈。

// push ints onto the stack
if (int.TryParse(token, out intToken)) {
    il.Emit(OpCodes.Ldc_I4, intToken);
}

如果该标记不是整数，则应为运算符。在这种情况下，我们将根据运算符的类型发出一个或多个 CIL 指令。对于基本四种指令，即 +、-、* 和 / 或 ÷，以及模运算符 %，操作是一条指令。

else if (IsOperator(token)) {
    switch (token) {
        case "+":
            il.Emit(OpCodes.Add);
            break;
        case "-":
            il.Emit(OpCodes.Sub);
            break;
        case "*":
            il.Emit(OpCodes.Mul);
            break;
        case "/":
        case "÷":
            il.Emit(OpCodes.Div);
            break;
        case "%":
            il.Emit(OpCodes.Rem);
            break;
        …

幂运算符 ^ 有所不同；没有简单的操作码可以将整数提升到整数幂。事实上，`mscorlib` 中也没有直接执行此操作的方法；我们需要使用 `Math.Pow`，它需要两个 `float64` 并返回一个。这意味着我们需要先定义一个局部变量来保存堆栈上的一个值，将另一个转换为 `float64`，将变量的值推入堆栈，然后将其转换为 `float64`。然后我们可以调用 `Math.Pow`。最后，我们需要将其返回值转换为 `int32`。代码中更清晰。

        case "^":

            // convert top two values to float64, since that's 
            // what Math.Pow expects

            // create a temp variable
            LocalBuilder tmp = il.DeclareLocal(typeof(int)); 

            il.Emit(OpCodes.Stloc, tmp); // pop into temp variable
            il.Emit(OpCodes.Conv_R8);    // convert remaining value
            il.Emit(OpCodes.Ldloc, tmp); // push temp variable to stack
            il.Emit(OpCodes.Conv_R8);    // convert pushed value

            // call Math.Pow
            il.EmitCall(OpCodes.Call, 
                        typeof(Math).GetMethod("Pow"), null);

            // convert the float64 return value to int32
            il.Emit(OpCodes.Conv_I4);

            break;
            …

如果运算符未在上方列出，我们将抛出错误：我们尚未实现它。最后，如果该标记既不是整数也不是运算符，则表达式可能包含不平衡的括号。

            …
            default:
                throw new CompileException(
                    "Unknown operator: '" + token + "'.");
        }

    }
    else {
        // if the token's not an integer or an operator, 
        // barf appropriately
        if ("()".Contains(token)) {
            throw new CompileException("Unbalanced parentheses.");
        }
        else {
            throw new CompileException(
                "Unable to compile expression; unknown token '" +
                token + "'.");
        }
    }
}

当循环完成时，所有的代码都已写入以计算表达式的值，但我们需要将其输出。我们的 `ILGenerator` 有一个方便的 `WriteLine` 方法，它要求我们将该值赋给一个变量。

// result needs a variable so we can WriteLine it
LocalBuilder result = il.DeclareLocal(typeof(int));
il.Emit(OpCodes.Stloc, result);

// print and return
il.EmitWriteLine(result);

最后，我们可以从方法返回。

il.Emit(OpCodes.Ret); // this will err if values left on stack

收尾和执行

编译就是这样。不过，还有一些收尾工作要做。现在我们已经添加了所有需要的指令，我们需要最终确定类型定义。

// bake the type definition
tpb.CreateType();

完成此操作后，我们就无法再修改我们的程序集了。

我们已经创建了我们的程序集，其中包含一个带有计算方法的类型。现在，我们需要运行它。由于它是 `static` 的，我们无需实例化类；我们只需创建一个空的参数数组（因为它不需要任何参数），然后调用它。

// empty argument array
object[] noArgs = new object[0];

// call the method we wrote (on a null object because we don't
// need one for static method)
asm.GetType("ExpressionExecutor").GetMethod(
    "WriteValue").Invoke(null, noArgs);

这就是我们功能简陋的编译器。让我们将其与一些用户输入连接起来。

将所有内容整合

用户可以输入要编译和执行的表达式。如果用户输入空白行或标准输入关闭，程序将退出；它将报告一个无法解析或无法编译的表达式。

class MainClass {

    private static string PromptExpression() {
        Console.WriteLine("Enter an integer arithmetic expression: ");
        return Console.ReadLine();
    }

    public static void Main(string[] args) {

        try {

            string expr;

            while ((expr = PromptExpression()) != "") {
                Program program = new Program(expr);
                program.Execute();
            }

        }
        catch (NullReferenceException) {
            // stdin EOF
            return;
        }
        catch (ParseException e) {
            Console.WriteLine(
                "Unparseable expression: " + e.Message);
        }
        catch (CompileException e) {
            Console.WriteLine(
                "Unable to compile expression: " + e.Message);
        }
    }
}

这是一个示例运行

Enter an integer arithmetic expression: 32 - 2 ^ 4
16
Enter an integer arithmetic expression: 16 - 2 ^ (2 + 2)
0
Enter an integer arithmetic expression: 12 / 2 ^ 2
3
Enter an integer arithmetic expression: 18 % 4
2
Enter an integer arithmetic expression: 18 % (2 + 3)
3
Enter an integer arithmetic expression: 
12 * (2 + 1
Unable to compile expression: Unbalanced parentheses.

未完成的部分

我们的计算器有几个问题，会导致它无法用于任何实际目的。

1. 即使在我们有限的输入语法范围内，也有可能在解析器中滑过无效输入，这本不应该发生。例如，无意义的表达式 `3 3 + 4` 将被转换为无意义的后缀表示法，并传递给编译器，编译器将生成 CIL，当它尝试返回时，堆栈上仍然有一个值，从而抛出异常。（修复很简单：确保所有表达式都以整数开头，并且（忽略括号）整数和运算符交替出现。但是，添加此功能会掩盖我们实现中更具教育意义的特性。）
2. 没有浮点数，`/` 几乎没有用。
3. 即使我们不允许浮点数，有符号整数也是必需的。
4. 几种类型的错误未被处理。
5. 整数溢出被毫不犹豫地接受，这几乎从来都不是正确的决定。

但正如我们已经同意的，我们的计算器不是编写计算器的实用方法，让我们为它教会我们的编译器知识而感到高兴吧。