Belajar LLVM - Mini Language: Lexer & Parser (Kaleidoscope Style)

#Pendahuluan

Setelah di episode 9 kita memahami Core API LLVM — Value, User, Instruction, IRBuilder — pada episode ini kita mulai membangun sesuatu yang nyata: bahasa pemrograman mini dari nol.

Kita akan mengikuti semangat tutorial Kaleidoscope dari LLVM — tutorial resmi yang mengajarkan cara membangun language front-end lengkap dengan LLVM. Mini language kita mendukung ekspresi matematika, fungsi, if/else, dan loop. Episode ini fokus pada lexer dan parser — dua tahapan pertama pipeline kompilasi.

#Definisi Mini Language

Grammar mini language

program     ::= definition | expression | external
definition  ::= 'def' identifier '(' args ')' expression
external    ::= 'extern' identifier '(' args ')'
args        ::= identifier (',' identifier)*
expression  ::= primary (binop primary)*
primary     ::= number | identifier | '(' expression ')'
              | 'if' expression 'then' expression 'else' expression
              | 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
binop       ::= '+' | '-' | '*' | '/' | '<' | '>'

Contoh program yang valid:

plaintext

def fib(x)
  if x < 3 then 1 else fib(x-1) + fib(x-2)
 
for i = 1, 10, 1 in putd(fib(i))

#Lexer: Tokenisasi

Lexer mengonsumsi source code string dan menghasilkan aliran token:

Token.h

enum Token {
    tok_eof = -1,
    tok_def = -2,
    tok_extern = -3,
    tok_identifier = -4,
    tok_number = -5,
    tok_if = -6,
    tok_then = -7,
    tok_else = -8,
    tok_for = -9,
    tok_in = -10,
};
 
struct TokenData {
    int kind;
    std::string identifierStr;
    double numVal;
};
 
class Lexer {
    std::string buffer;
    size_t pos;
public:
    Lexer(const std::string &src) : buffer(src), pos(0) {}
    TokenData nextToken() {
        TokenData tok;
        // Skip whitespace
        while (pos < buffer.size() && isspace(buffer[pos])) ++pos;
        if (pos >= buffer.size()) { tok.kind = tok_eof; return tok; }
 
        char c = buffer[pos++];
        if (isalpha(c)) {
            std::string id(1, c);
            while (pos < buffer.size() && isalnum(buffer[pos]))
                id += buffer[pos++];
            tok.identifierStr = id;
            if (id == "def") tok.kind = tok_def;
            else if (id == "extern") tok.kind = tok_extern;
            else if (id == "if") tok.kind = tok_if;
            else if (id == "then") tok.kind = tok_then;
            else if (id == "else") tok.kind = tok_else;
            else if (id == "for") tok.kind = tok_for;
            else if (id == "in") tok.kind = tok_in;
            else tok.kind = tok_identifier;
        } else if (isdigit(c) || c == '.') {
            std::string num(1, c);
            while (pos < buffer.size() && (isdigit(buffer[pos]) || buffer[pos] == '.'))
                num += buffer[pos++];
            tok.numVal = std::stod(num);
            tok.kind = tok_number;
        } else {
            tok.kind = c;
        }
        return tok;
    }
};

#Parser: Recursive Descent

Parser mengonsumsi aliran token dan membangun AST (Abstract Syntax Tree):

AST.h

struct ExprAST {
    virtual ~ExprAST() = default;
    virtual Value *codegen() = nullptr;
};
 
struct NumberExprAST : ExprAST {
    double val;
    NumberExprAST(double v) : val(v) {}
};
 
struct VariableExprAST : ExprAST {
    std::string name;
    VariableExprAST(const std::string &n) : name(n) {}
};
 
struct BinaryExprAST : ExprAST {
    char op;
    std::unique_ptr<ExprAST> LHS, RHS;
    BinaryExprAST(char o, std::unique_ptr<ExprAST> L,
                  std::unique_ptr<ExprAST> R)
        : op(o), LHS(std::move(L)), RHS(std::move(R)) {}
};
 
struct CallExprAST : ExprAST {
    std::string callee;
    std::vector<std::unique_ptr<ExprAST>> args;
    CallExprAST(const std::string &c,
                std::vector<std::unique_ptr<ExprAST>> a)
        : callee(c), args(std::move(a)) {}
};
 
struct PrototypeAST {
    std::string name;
    std::vector<std::string> args;
};
 
struct FunctionAST {
    std::unique_ptr<PrototypeAST> proto;
    std::unique_ptr<ExprAST> body;
};

Parser recursive descent membaca token satu per satu dan memanggil dirinya sendiri untuk sub-expressions:

Parser inti

std::unique_ptr<ExprAST> parseExpression() {
    auto LHS = parsePrimary();
    return parseBinOpRHS(0, std::move(LHS));
}
 
std::unique_ptr<ExprAST> parsePrimary() {
    switch (currentToken.kind) {
        case tok_number:
            return std::make_unique<NumberExprAST>(currentToken.numVal);
        case tok_identifier:
            return std::make_unique<VariableExprAST>(currentToken.identifierStr);
        case '(': return parseParen();
        case tok_if: return parseIf();
        case tok_for: return parseFor();
        default: return nullptr;
    }
}

#Praktik: REPL

Bangun REPL (Read-Eval-Print Loop) yang mencetak AST dari input:

REPL loop

void mainLoop() {
    Lexer lexer("");
    Parser parser(lexer);
    while (true) {
        std::cout << ">> ";
        std::string line;
        std::getline(std::cin, line);
        if (line.empty()) continue;
        lexer.reset(line);
        auto ast = parser.parseTopLevel();
        if (ast) ast->print();
    }
}

Contoh REPL

>> def f(x) x * 2
FunctionAST(PrototypeAST(f, [x]), BinaryExprAST(*, VariableExprAST(x), NumberExprAST(2)))
>> f(21)
42

Note

REPL ini belum menghasilkan kode LLVM — ia hanya membangun dan mencetak AST. Codegen dari AST ke IR akan kita lakukan di episode 11. Pemisahan parser dari codegen adalah desain bersih yang memudahkan testing dan maintainability.

#Penutup

Inti yang harus dibawa pulang:

Lexer mengonsumsi string dan menghasilkan aliran token: keywords, identifiers, numbers, operators.
Parser recursive descent mengonsumsi token dan membangun AST secara hierarkis.
AST terdiri dari: NumberExpr, VariableExpr, BinaryExpr, CallExpr, IfExpr, ForExpr.
REPL memungkinkan interaksi langsung: ketik ekspresi, lihat AST.

Di episode 11 selanjutnya kita akan melanjutkan ke AST Codegen ke IR dengan IRBuilder — visitor pattern AST → IR, konversi tipe dinamis, error handling, dan REPL pertama yang menghasilkan kode 42 dari input def f(x) x*2; f(21). Sampai jumpa di episode 11!