从零开始的编译器：lexer parser type inference

从零构建编译器：新手无深度知识经验分享

编译器构建分为多个阶段：词法分析器、解析器、类型推断、准备阶段和代码生成。作者此前并无编译器构建经验，通过研究一个语义类似 Rust 的开源 C# 项目入门。他们没有修改现有代码，而是在学习基础知识的同时从头实现所有内容。整个过程并非严格的自顶向下或自底向上——由于各阶段相互依赖，多次进行了重构。

数据流遵循以下方案：源代码 → 令牌 → 抽象语法树 → 类型化抽象语法树 → 准备后的抽象语法树 → LLVM 中间表示。

词法分析器与解析器：处理歧义

词法分析器和解析器改编自一个使用 LR(1) 解析器的外部项目。泛型带来了问题：例如 var a = Test < b > c; 这样的表达式需要向前查看多个令牌，以区分模板参数和比较操作。标准的 LR(1) 解析器在没有上下文的情况下无法处理这种情况。

更复杂的情况是 var a = Test < b > (c);。这类歧义被推迟到类型推断阶段处理。解析器生成抽象语法树节点，如果令牌不符合预期格式，则进行错误处理。

类型推断：多遍抽象语法树遍历

由于不同文件中的声明之间存在依赖关系，类型推断需要对抽象语法树进行多遍遍历。顺序如下：

• 处理顶层类型声明（写入命名空间作用域）。
• 解析泛型参数及其约束。
• 处理继承关系。
• 委托、嵌套类型、函数。
• 字段、属性、初始化器。
• 属性（Attribute）。
• 最后才处理函数体。

泛型是主要难点。递归生成的示例：

public class Test<T> 
{ 
    public static Test<E> GetTest<E>(); 
}

编译器会循环创建无限的 Test<E>。通过约束解决：禁止使用类泛型参数的静态字段/属性（public static T CoolField; 不被允许）。这避免了链接时的冲突。

针对不同类型和虚方法/抽象方法的操作需要进一步优化。

为代码生成准备类型

一个额外的阶段转换抽象语法树，以便更轻松地生成中间表示：

• Lambda 表达式与闭包：生成合成类以捕获上下文。示例：

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        var action = () => 
        { 
            Console.WriteLine($"Result: {a + b}"); 
        };
        return action;
    }
}

转换为：

public class __SyntheticClass0
{
    public int a;
    public int b;
    public void Lambda0()
    {
        Console.WriteLine($"Result: {a + b}"); 
    }
}

public class Test
{
    public Action ReturnFunction(int a, int b)
    {
        __SyntheticClass0 tmpVar = new __SyntheticClass0();
        tmpVar.a = a;
        tmpVar.b = b;
        return tmpVar.Lambda0;
    }
}

• 为属性生成 get/set 方法。
• 将属性访问替换为方法调用。
• 死代码消除（库除外）。
• 静态构造函数。
• 将类转换为指针。
• 添加虚函数表（vtable）。

生成 LLVM 中间表示

通过准备阶段简化了 LLVM 中间表示的生成：平台特定细节（如 setjmp、va_list）已提前解决。主要问题是链接和泛型。

禁止静态泛型字段是合理的，因为库之间存在依赖关系。在方案 A → B(int)、A → C(int) → App 中，每个库生成自己的 SomeType<int>。B 中的更改不会与 C 同步，链接器不知道选择哪个。

其他细节：x86 Windows 中全局名称的下划线（由 LLVM 链接器解决）、虚函数表。在抽象语法树准备后，LLVM 中间表示语法很快就能掌握。

关键要点

• 泛型需要精心设计：解析器中的向前查看、多遍类型推断、对静态元素的约束。
• 生成中间表示前的准备阶段对于指针、Lambda 表达式和死代码至关重要。
• LLVM 简化了跨平台开发，但无法消除链接冲突。
• 并行开发各阶段会导致重写——最好从语言的简单子集开始。
• 为闭包使用合成类可以在不深入理解闭包的情况下保持语义。

— Editorial Team