利用 C# 的强类型力量：构建一个类型安全的 Brainfuck 编译器

jnjqb45071

520人浏览 · 2025-09-09 15:03:18

jnjqb45071 · 2025-09-09 15:03:18 发布

利用 C# 的强类型力量：构建一个类型安全的 Brainfuck 编译器

C# 拥有一个强大而丰富的类型系统，旨在帮助我们构建健壮、可维护且意图清晰的应用程序。我们通常用它来处理业务实体、Web 请求或复杂的游戏逻辑。但如果我们将其用于一个看似完全不同的领域——比如，构建一门极其简单的 Brainfuck 语言的编译器——会发生什么？

这篇文章将带你经历一次思想实验：如何利用 C# 的类型、记录（record）、模式匹配等特性，并非仅仅“实现”一个 Brainfuck 解释器，而是“建模”一个编译器，并在编译过程中尽可能多地捕获错误。

Brainfuck 速成课

Brainfuck 由 8 个极其简单的命令组成，操作一个字节数组（通常为 30,000 字节）和一个数据指针：

> : 指针加一
< : 指针减一
+ : 指针所指字节的值加一
- : 指针所指字节的值减一
. : 输出指针所指字节（ASCII）
, : 输入一个字节到指针所指位置
[ : 如果指针所指字节为 0，跳转到匹配的 ] 之后
] : 如果指针所指字节不为 0，跳转到匹配的 [ 之后

任何其他字符都被视为注释而被忽略。

第 1 步：用类型表示抽象语法树 (AST)

传统的解释器可能会直接遍历字符串并执行操作。但一个编译器首先会将源代码解析成一个中间表示——抽象语法树 (AST)。C# 的类型系统非常适合为此定义数据结构。

我们将使用一个** discriminated union **（在 C# 中通常通过继承和模式匹配实现）来表示 AST 节点。

csharp

// 基类，代表一个AST节点
public abstract partial record Statement;

// 简单的命令节点
public sealed record MovePointerRightStatement : Statement;
public sealed record MovePointerLeftStatement : Statement;
public sealed record IncrementDataStatement : Statement;
public sealed record DecrementDataStatement : Statement;
public sealed record OutputStatement : Statement;
public sealed record InputStatement : Statement;

// 循环节点包含一个子语句列表，这形成了树的嵌套结构
public sealed record LoopStatement(IReadOnlyList<Statement> Body) : Statement;

为什么选择 record？
record 类型提供了基于值的相等性，这对于编译过程中的分析和优化非常有用。它们也是不可变的，这符合 AST 在解析后不应改变的理念。

第 2 步：解析：从文本到类型化 AST

解析器的任务是将原始的字符串（充满可能无效的字符）转换为我们定义的良好类型的 AST。

csharp

public class Parser
{
    public static IReadOnlyList<Statement> Parse(string code)
    {
        int position = 0;
        var statements = new List<Statement>();

        // 解析顶层语句，遇到 '[' 则递归解析循环体
        while (position < code.Length)
        {
            switch (code[position])
            {
                case '>': statements.Add(new MovePointerRightStatement()); break;
                case '<': statements.Add(new MovePointerLeftStatement()); break;
                case '+': statements.Add(new IncrementDataStatement()); break;
                case '-': statements.Add(new DecrementDataStatement()); break;
                case '.': statements.Add(new OutputStatement()); break;
                case ',': statements.Add(new InputStatement()); break;
                case '[':
                    // 找到匹配的 ']' 并递归解析循环体
                    int loopStart = position;
                    int depth = 1;
                    position++;
                    while (position < code.Length && depth > 0)
                    {
                        if (code[position] == '[') depth++;
                        else if (code[position] == ']') depth--;
                        position++;
                    }
                    if (depth != 0) throw new ArgumentException("Unmatched '['");
                    string loopBodyCode = code.Substring(loopStart + 1, position - loopStart - 2);
                    var loopBody = Parse(loopBodyCode);
                    statements.Add(new LoopStatement(loopBody));
                    continue; // `position` 已经在 `]` 之后，所以不要再次递增
                case ']':
                    throw new ArgumentException("Unmatched ']'");
                // 其他字符忽略，不添加到 AST
            }
            position++;
        }
        return statements;
    }
}

解析器的成功执行意味着我们成功地将一团“字符串”转换为了一个结构良好、由 C# 编译器进行类型检查的对象树。任何无效的循环结构都会在解析阶段抛出异常。

第 3 步：编译：从 AST 到 C# 代码

现在，我们有了类型化的 AST，可以将其转换为另一种语言。这里我们选择将其编译成 C# 源代码，然后使用 .NET 的 CSharpCodeProvider 动态编译并执行它。

这个阶段是类型系统大放异彩的地方。我们可以使用 Visitor 模式 或 模式匹配 来遍历 AST 并生成对应的 C# 代码。

csharp

public static class Compiler
{
    public static string CompileToCSharp(string programName, IReadOnlyList<Statement> statements)
    {
        var sb = new StringBuilder();

        // 生成 C# 程序骨架
        sb.AppendLine($$"""
            using System;
            public static class {{programName}}
            {
                public static void Run()
                {
                    byte[] memory = new byte[30000];
                    int pointer = 0;
            """);

        // 递归生成对应语句的 C# 代码
        GenerateStatementsCode(sb, statements, 3); // 3 层缩进

        // 结束程序骨架
        sb.AppendLine("    }");
        sb.AppendLine("}");

        return sb.ToString();
    }

    private static void GenerateStatementsCode(StringBuilder sb, IReadOnlyList<Statement> statements, int indentLevel)
    {
        string indent = new string(' ', indentLevel * 4);
        foreach (var stmt in statements)
        {
            // 基于 AST 节点的具体类型生成代码
            switch (stmt)
            {
                case MovePointerRightStatement:
                    sb.AppendLine($"{indent}pointer = (pointer + 1) % 30000;");
                    break;
                case MovePointerLeftStatement:
                    sb.AppendLine($"{indent}pointer = (pointer == 0) ? 29999 : pointer - 1;");
                    break;
                case IncrementDataStatement:
                    sb.AppendLine($"{indent}memory[pointer]++;");
                    break;
                case DecrementDataStatement:
                    sb.AppendLine($"{indent}memory[pointer]--;");
                    break;
                case OutputStatement:
                    sb.AppendLine($"{indent}Console.Write((char)memory[pointer]);");
                    break;
                case InputStatement:
                    sb.AppendLine($"{indent}var key = Console.ReadKey(true);");
                    sb.AppendLine($"{indent}memory[pointer] = (byte)key.KeyChar;");
                    break;
                case LoopStatement loop:
                    sb.AppendLine($"{indent}while (memory[pointer] != 0)");
                    sb.AppendLine($"{indent}{{");
                    GenerateStatementsCode(sb, loop.Body, indentLevel + 1);
                    sb.AppendLine($"{indent}}}");
                    break;
                default:
                    throw new ArgumentOutOfRangeException(nameof(stmt), $"Unknown statement type: {stmt.GetType()}");
            }
        }
    }
}

类型系统的优势在这里体现得淋漓尽致：

** exhaustiveness checking：switch 表达式要求我们处理 Statement 的所有已知子类型。如果我们未来添加了一个新的语句类型（例如 DebugStatement）但忘记在编译器中处理它，C# 编译器会警告我们**，从而防止了运行时错误。
安全性：我们永远不会错误地尝试将 LoopStatement 当作 OutputStatement 来生成代码。类型系统在编译时保证了这一点。

第 4 步：执行

最后，我们将生成的 C# 代码传递给 C# 编译器，将其编译成程序集并执行。

csharp

class Program
{
    static void Main(string[] args)
    {
        string brainfuckCode = ">++++++++[<+++++++++>-]<.>++++[<+++++++>-]<+.+++++++..+++.>>++++++[<+++++++>-]<++.------------.>++++++[<+++++++++>-]<+.<.+++.------.--------.>>>++++[<++++++++>-]<+."; // 输出 "Hello, World!"

        try
        {
            // 1. 解析
            var ast = Parser.Parse(brainfuckCode);
            Console.WriteLine("Parsing successful!");

            // 2. 编译到 C#
            string csharpCode = Compiler.CompileToCSharp("BrainfuckProgram", ast);
            // Console.WriteLine(csharpCode); // 可以查看生成的代码

            // 3. 使用 CSharpCodeProvider 编译并运行
            var provider = new Microsoft.CSharp.CSharpCodeProvider();
            var compilerParams = new System.CodeDom.Compiler.CompilerParameters
            {
                GenerateInMemory = true,
                GenerateExecutable = false
            };

            var results = provider.CompileAssemblyFromSource(compilerParams, csharpCode);

            if (results.Errors.Count > 0)
            {
                foreach (var error in results.Errors) Console.WriteLine(error);
            }
            else
            {
                var program = results.CompiledAssembly.GetType("BrainfuckProgram");
                var runMethod = program.GetMethod("Run");
                runMethod.Invoke(null, null); // 输出：Hello, World!
            }
        }
        catch (Exception ex)
        {
            Console.WriteLine($"Error: {ex.Message}");
        }
    }
}

总结：类型系统的力量

通过这个项目，我们看到了 C# 类型系统在非常规领域的应用价值：

领域建模：我们用类型精确地建模了 Brainfuck 语言的语法结构。LoopStatement 包含一个 Statement 列表，这个递归定义完美地捕捉了循环嵌套的语义。
正确性保证：解析阶段产生的 AST 是强类型的。这确保了后续阶段（如代码生成）不可能生成无效的结构（例如，一个没有循环体的循环）。错误在解析阶段就被捕获。
可扩展性：如果我们要为 Brainfuck 添加扩展（例如，一个调试语句 #），我们只需：
- 定义一个新的 DebugStatement : Statement。
- 在 Parser 中处理 # 字符。
- 在 Compiler 的 switch 表达式中为 DebugStatement 添加生成逻辑。C# 编译器会指导我们完成所有必要的更改，防止遗漏。
清晰度：代码的意图非常清晰。AST 的定义本身就是最好的文档。