Mini Compiler Project

Building a compiler is often considered a rite of passage for computer science students and enthusiasts. It is a project that bridges the gap between high-level human logic and low-level machine execution. In this guide, we will walk through the systematic implementation of a Mini Compiler.

The goal of this project is to create a functional compiler capable of transforming a simplified arithmetic expression language—such as int a = 3 + 4 * (5 - 2);—into a target machine representation (specifically LLVM IR).
Before diving into the code, it is essential to understand the standard stages of a compiler. Our mini-compiler will follow these five core phases:

1. Lexical Analysis (Lexer): The raw stream of characters from the source code is broken down into meaningful units called Tokens (e.g., identifiers, keywords, operators, and literals).
2. Syntax Analysis (Parser): The sequence of tokens is organized into a hierarchical structure called an Abstract Syntax Tree (AST) based on a Context-Free Grammar (CFG).
3. Semantic Analysis: The compiler traverses the AST to ensure the code makes sense. This includes type checking, scope management via a symbol table, and constant folding.
4. Intermediate Representation (IR) Generation: The high-level AST is flattened into a platform-independent instruction set, such as Three-Address Code (TAC), which simplifies optimization.
5. Code Generation: The IR is translated into the final target language, such as x86-64 assembly or LLVM IR.

Pro Tip: For a mini-compiler, we can skip complex optimization passes to focus on the structural correctness of the pipeline.

2. Project Architecture

A clean directory structure is vital for managing the various components of the compiler. We will use C++ as our implementation language, leveraging Flex for lexing, Bison for parsing, and LLVM for the backend.

mini-compiler/
├── src/
│   ├── lexer.l          // Flex lexical rules
│   ├── parser.y         // Bison grammar rules
│   ├── ast.hpp          // AST node definitions
│   ├── semantic.cpp     // Semantic analysis implementation
│   ├── ir.hpp           // Three-address code structures
│   ├── codegen.cpp      // LLVM IR generation logic
│   └── main.cpp         // Compiler entry point
├── CMakeLists.txt
└── README.md

3. Implementation Details

3.1 Lexical Analysis with Flex

The lexer scans the input and identifies tokens. In Flex, we define patterns using regular expressions.

%option noyywrap

DIGIT   [0-9]
ID      [a-zA-Z_][a-zA-Z0-9_]*
WS      [ \t\r\n]+

%%

{WS}                ;               // Ignore whitespace
"int"               { return INT; }
"+"                 { return PLUS; }
"-"                 { return MINUS; }
"*"                 { return MUL; }
"/"                 { return DIV; }
"="                 { return ASSIGN; }
";"                 { return SEMI; }
"("                 { return LPAREN; }
")"                 { return RPAREN; }
{DIGIT}+            { yylval.intVal = atoi(yytext); return INT_LITERAL; }
{ID}                { yylval.strVal = new std::string(yytext); return IDENT; }
.                   { fprintf(stderr, "Unknown character: %s\n", yytext); exit(1); }
%%

3.2 Syntax Analysis with Bison

The parser takes the tokens from the lexer and applies grammar rules to build the AST. We define the precedence of operators (like multiplication over addition) directly within the Bison file.

%union {
    int    intVal;
    std::string* strVal;
    ASTNode*    ast;
}

%token <intVal> INT_LITERAL
%token <strVal> IDENT
%token INT PLUS MINUS MUL DIV ASSIGN SEMI LPAREN RPAREN

%type <ast> program stmt_list stmt expr term factor

%%

program
    : stmt_list               { /* Root node generation */ }
    ;

stmt_list
    : stmt_list stmt          { /* Link statements */ }
    | /* empty */             { }
    ;

stmt
    : INT IDENT ASSIGN expr SEMI
                              { $$ = new DeclAssignNode(*$2, $4); }
    | IDENT ASSIGN expr SEMI
                              { $$ = new AssignNode(*$1, $3); }
    ;

expr
    : expr PLUS term          { $$ = new BinaryOpNode('+', $1, $3); }
    | expr MINUS term         { $$ = new BinaryOpNode('-', $1, $3); }
    | term                    { $$ = $1; }
    ;

term
    : term MUL factor         { $$ = new BinaryOpNode('*', $1, $3); }
    | term DIV factor         { $$ = new BinaryOpNode('/', $1, $3); }
    | factor                  { $$ = $1; }
    ;

factor
    : INT_LITERAL             { $$ = new IntLiteralNode($1); }
    | IDENT                   { $$ = new VariableNode(*$1); }
    | LPAREN expr RPAREN      { $$ = $2; }
    ;
%%

3.3 The Abstract Syntax Tree (AST)

To decouple the tree structure from the operations performed on it (like printing or code generation), we use the Visitor Pattern.

// ast.hpp
struct ASTNode {
    virtual ~ASTNode() = default;
    virtual void accept(Visitor& v) = 0;
};

struct IntLiteralNode : ASTNode {
    int value;
    explicit IntLiteralNode(int v) : value(v) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

struct VariableNode : ASTNode {
    std::string name;
    explicit VariableNode(const std::string& n) : name(n) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

struct BinaryOpNode : ASTNode {
    char op; 
    ASTNode* lhs;
    ASTNode* rhs;
    BinaryOpNode(char o, ASTNode* l, ASTNode* r) : op(o), lhs(l), rhs(r) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

struct DeclAssignNode : ASTNode {
    std::string varName;
    ASTNode* initExpr;
    DeclAssignNode(const std::string& n, ASTNode* e) : varName(n), initExpr(e) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

3.4 Semantic Analysis and Symbol Tables

During semantic analysis, we must ensure that variables are declared before use and that they exist within the correct scope. A Symbol Table tracks variable names and their corresponding memory offsets.

class SymbolTable {
    std::unordered_map<std::string, int> table; // Name -> Memory Offset
    int nextOffset = 0;
public:
    void declare(const std::string& name) {
        if (table.count(name)) throw std::runtime_error("Redeclaration of: " + name);
        table[name] = nextOffset;
        nextOffset += 4; // Assuming 4-byte integers
    }
    int lookup(const std::string& name) const {
        auto it = table.find(name);
        if (it == table.end()) throw std::runtime_error("Undeclared variable: " + name);
        return it->second;
    }
};

3.5 Intermediate Representation (IR) Generation

We convert the AST into Three-Address Code (TAC). Each instruction typically has at most one operator and three operands (two sources and one destination).

struct TAC {
    std::string op;   // e.g., "add", "sub", "mul"
    std::string dst;
    std::string src1;
    std::string src2;
};

class IRBuilder : public Visitor {
    std::vector<TAC> code;
    int tempCount = 0;
    SymbolTable& symTab;
    std::string currentResult;

public:
    explicit IRBuilder(SymbolTable& s) : symTab(s) {}

    std::string newTemp() { return "%t" + std::to_string(tempCount++); }

    void visit(BinaryOpNode& n) override {
        n.lhs->accept(*this);
        std::string left = currentResult;
        n.rhs->accept(*this);
        std::string right = currentResult;
        std::string dst = newTemp();
        code.push_back({opFromChar(n.op), dst, left, right});
        currentResult = dst;
    }
    // ... other visit methods
};

3.6 Target Code Generation (LLVM)

Finally, we map our TAC instructions to the LLVM API to produce high-quality machine code.

void generateLLVM(const std::vector<TAC>& tac) {
    llvm::LLVMContext ctx;
    llvm::Module* module = new llvm::Module("mini", ctx);
    llvm::IRBuilder<> builder(ctx);
    
    // Define main function
    llvm::FunctionType* ft = llvm::FunctionType::get(builder.getInt32Ty(), false);
    llvm::Function* mainFn = llvm::Function::Create(ft, llvm::Function::ExternalLinkage, "main", module);
    llvm::BasicBlock* entry = llvm::BasicBlock::Create(ctx, "entry", mainFn);
    builder.SetInsertPoint(entry);

    std::unordered_map<std::string, llvm::Value*> valueMap;
    for (const auto& instr : tac) {
        llvm::Value* lhs = valueMap[instr.src1];
        llvm::Value* rhs = valueMap[instr.src2];
        llvm::Value* result = nullptr;

        if (instr.op == "add") result = builder.CreateAdd(lhs, rhs, instr.dst);
        else if (instr.op == "sub") result = builder.CreateSub(lhs, rhs, instr.dst);
        else if (instr.op == "mul") result = builder.CreateMul(lhs, rhs, instr.dst);
        else if (instr.op == "div") result = builder.CreateSDiv(lhs, rhs, instr.dst);
        
        valueMap[instr.dst] = result;
    }
    builder.CreateRet(llvm::ConstantInt::get(builder.getInt32Ty(), 0));
    module->print(llvm::outs(), nullptr);
}

4. Running the Compiler

Given a source file test.mc:

int a = 3 + 4 * (5 - 2);
int b = a - 7;

You can build and run the project using the following workflow:

# 1. Generate Lexer and Parser
flex src/lexer.l -o src/lex.yy.c
bison -d src/parser.y -o src/parser.tab.c

# 2. Build with CMake
mkdir build && cd build
cmake ..
make

# 3. Execute
./mini-compiler ../test.mc -o out.ll

The resulting out.ll will contain the LLVM IR, which can be executed via lli out.ll.

5. Debugging and Common Pitfalls

• Lexical Conflicts: In Flex, the order of rules matters. Always place specific keywords (like int) before general patterns (like ID) to prevent them from being misidentified.
• Shift/Reduce Conflicts: If Bison reports these, check your grammar for ambiguity. Using the -v flag generates a .output file that helps you visualize where the parser is confused.
• Memory Management: Since AST nodes are created on the heap, ensure you use smart pointers (std::unique_ptr) or a dedicated destructor to prevent memory leaks.
• LLVM Linking: When using CMake, ensure you link against the necessary LLVM components (e.g., LLVMCore, LLVMSupport) and enable RTTI if required by your system's LLVM build.

6. Future Extensions

Once the core pipeline is working, you can expand the project in several directions: