Compiler from scratch: lexer parser type inference

Building a Compiler from Scratch: A Beginner's Experience Without Deep Knowledge

A compiler is built in stages: lexer, parser, type inference, preparation, and code generation. The author, with no prior experience in compiler construction, started by studying an open-source C# project with semantics similar to Rust. Instead of modifying existing code, they implemented everything from scratch while learning the basics. The process wasn't strictly top-down or bottom-up—stages were reworked multiple times due to interdependencies.

The data flow follows this scheme: source code → tokens → AST → typed AST → prepared AST → LLVM IR.

Lexer and Parser: Handling Ambiguities

The lexer and parser were adapted from an external project with an LR(1) parser. Issues arose with generics: expressions like var a = Test < b > c; require lookahead of more than one token to distinguish template parameters from comparisons. Standard LR(1) can't handle this without context.

A more complex case is var a = Test < b > (c);. Such ambiguities are deferred to the type inference stage. The parser generates AST nodes with error handling if tokens don't match the expected format.

Type Inference: Multi-Pass AST Traversal

Type inference requires multiple passes over the AST due to dependencies between declarations across different files. The sequence:

• Processing top-level type declarations (writing to namespace scope).
• Parsing generic parameters and their constraints.
• Handling inheritance.
• Delegates, nested types, functions.
• Fields, properties, initializers.
• Attributes.
• Only then—function bodies.

Generics caused the main difficulties. Example of recursive generation:

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

The compiler looped, creating infinite Test<E>. Solved with constraints: static fields/properties with class generic parameters are prohibited (public static T CoolField; is not allowed). This prevents conflicts during linking.

Operations for different types and virtual/abstract methods required refinements.

Preparing Types for Code Generation

An additional stage transforms the AST for easier IR generation:

• Lambdas and Closures: Synthetic classes are generated to capture context. Example:

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

Transformed into:

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;
    }
}

• Generating get/set for properties.
• Replacing property accesses with calls.
• Dead code elimination (except for libraries).
• Static constructors.
• Converting classes to pointers.
• Adding virtual tables (vtables).

Code Generation to LLVM IR

LLVM IR generation is simplified by preparation: platform-specific details (setjmp, va_list) are resolved early. Main issues are linking and generics.

Prohibiting static generic fields is justified by library dependencies. In the scheme A → B(int), A → C(int) → App, each library generates its own SomeType<int>. Changes in B aren't synchronized with C, and the linker doesn't know which to choose.

Other nuances: underscores in global names for x86 Windows (solved by the LLVM linker), vtables. LLVM IR syntax is quickly mastered after AST preparation.

Key Takeaways

• Generics require careful design: lookahead in the parser, multi-pass type inference, constraints on static elements.
• The preparation stage before IR is critical for pointers, lambdas, and dead code.
• LLVM simplifies cross-platform development but doesn't eliminate linking conflicts.
• Parallel development of stages leads to rewrites—it's better to start with a simple subset of the language.
• Synthetic classes for closures preserve semantics without deep knowledge of closures.

— Editorial Team