Compiler Frontend

Compiler frontend

Contract

Inputs

1. Language description (required): the token set, the grammar or a set of example programs, and the operators with their precedence and associativity.
2. Implementation language (required): C or Rust. C samples below use the LLVM C API in llvm-c/; in Rust use the inkwell or llvm-sys crates.
3. Requested stages (required): any subset of lexer, parser, symbol table, type checker, IR emitter.
4. Test inputs (required): at least one valid program per stage and one program with an error the stage must report.

Procedure

1. Fix the pipeline: source to lexer (tokens) to parser (AST) to type checker to IR generator to LLVM IR. Write down which stages this task delivers. Done when: the delivered stages and their input and output types are listed.

2. Write the lexer as a hand-written state machine. Tokens carry a kind, a pointer into the source, a length, and any literal value. Skip whitespace, then dispatch on the first character: digits build an integer, letters build an identifier, single characters map to punctuation.

   typedef enum { TOK_EOF, TOK_INT, TOK_IDENT, TOK_PLUS, TOK_MINUS,
                  TOK_LPAREN, TOK_RPAREN, TOK_SEMI, TOK_EQ, TOK_RETURN } TokenKind;
   
   typedef struct { TokenKind kind; const char *start; int length; int64_t int_val; } Token;
   typedef struct { const char *src; int pos; int line; } Lexer;
   
   Token lexer_next(Lexer *l) {
       while (l->src[l->pos] == ' ' || l->src[l->pos] == '\n') l->pos++;
       const char *start = &l->src[l->pos];
       if (isdigit((unsigned char)l->src[l->pos])) {
           int64_t val = 0;
           while (isdigit((unsigned char)l->src[l->pos]))
               val = val * 10 + (l->src[l->pos++] - '0');
           return (Token){ TOK_INT, start, (int)(&l->src[l->pos] - start), val };
       }
       if (isalpha((unsigned char)l->src[l->pos])) {
           while (isalnum((unsigned char)l->src[l->pos])) l->pos++;
           return (Token){ TOK_IDENT, start, (int)(&l->src[l->pos] - start), 0 };
       }
       switch (l->src[l->pos++]) {
           case '+': return (Token){ TOK_PLUS, start, 1, 0 };
           case '(': return (Token){ TOK_LPAREN, start, 1, 0 };
           case ')': return (Token){ TOK_RPAREN, start, 1, 0 };
           case ';': return (Token){ TOK_SEMI, start, 1, 0 };
           default:  return (Token){ TOK_EOF, start, 0, 0 };
       }
   }
   

   A generated lexer is the alternative when the token set is large: flex lexer.l && gcc -o lexer lex.yy.c -lfl. With flex, order rules so the longest match wins and keywords precede the identifier rule. Done when: every test input produces the expected token stream, including the EOF token.

3. Parse expressions with a Pratt parser. Each infix operator has a left and a right binding power; a higher power binds tighter, and right associativity is a right power one below the left. The loop consumes operators while their left power is at least the minimum.

   typedef enum { AST_INT, AST_BINOP, AST_VAR } AstKind;
   typedef struct AstNode {
       AstKind kind;
       union {
           int64_t int_val;
           struct { int op; struct AstNode *lhs, *rhs; } binop;
           char *name;
       };
   } AstNode;
   
   enum { BP_NONE = 0, BP_SUM = 10, BP_PRODUCT = 20 };
   
   AstNode *parse_expression(Parser *p, int min_bp) {
       AstNode *left = parse_prefix(p);
       for (;;) {
           int lbp, rbp;
           if (!infix_binding_power(p->cur.kind, &lbp, &rbp) || lbp < min_bp) break;
           int op = p->cur.kind;
           advance(p);
           AstNode *right = parse_expression(p, rbp);
           left = make_binop(op, left, right);
       }
       return left;
   }
   

   Capture the operator before advance; reading p->cur.kind after the recursive call returns the wrong token. Done when: a table of expressions with expected trees passes, including mixed precedence and associativity cases.

4. Parse statements with recursive descent, one function per nonterminal. Every branch must consume at least one token or return; a branch that neither advances nor returns is the cause of an infinite loop.

   AstNode *parse_statement(Parser *p) {
       if (p->cur.kind == TOK_IDENT && peek(p) == TOK_EQ) {
           char *name = take_ident(p);
           advance(p);
           AstNode *expr = parse_expression(p, BP_NONE);
           expect(p, TOK_SEMI);
           return make_assign(name, expr);
       }
       if (match(p, TOK_RETURN)) {
           AstNode *expr = parse_expression(p, BP_NONE);
           expect(p, TOK_SEMI);
           return make_return(expr);
       }
       return parse_expression_statement(p);
   }
   

   Done when: every statement form in the test inputs parses and every branch is audited for token progress.

5. Build the symbol table as a chain of scopes. Lookup walks from the innermost scope to the root; definition writes only into the current scope, so shadowing an outer name is allowed and redefining a name in the same scope is an error.

   typedef struct Symbol { char *name; Type *type; LLVMValueRef llvm_val; struct Symbol *next; } Symbol;
   typedef struct Scope { Symbol *symbols; struct Scope *parent; } Scope;
   
   Symbol *scope_lookup(Scope *s, const char *name) {
       for (Scope *cur = s; cur; cur = cur->parent)
           for (Symbol *sym = cur->symbols; sym; sym = sym->next)
               if (strcmp(sym->name, name) == 0) return sym;
       return NULL;
   }
   
   void scope_define(Scope *s, const char *name, Type *type) {
       Symbol *sym = malloc(sizeof *sym);
       if (!sym) abort();
       sym->name = strdup(name); sym->type = type; sym->llvm_val = NULL;
       sym->next = s->symbols; s->symbols = sym;
   }
   

   Replace the linked list with a hash map when scopes hold more than a few dozen names. Done when: shadowing resolves to the inner name and a same-scope duplicate is rejected.

6. Type-check by walking the AST and returning a type per node. Integers have the integer type; a variable takes its symbol's type or reports "undefined"; a binary operation requires equal operand types.

   Type *check_expr(Scope *s, AstNode *node) {
       switch (node->kind) {
       case AST_INT: return type_int();
       case AST_VAR: {
           Symbol *sym = scope_lookup(s, node->name);
           if (!sym) error("undefined variable %s", node->name);
           return sym->type;
       }
       case AST_BINOP: {
           Type *lt = check_expr(s, node->binop.lhs);
           Type *rt = check_expr(s, node->binop.rhs);
           if (!type_equal(lt, rt)) error("type mismatch in binary op");
           return lt;
       }
       }
       return type_void();
   }
   

   For an ML-style language with inference, assign a type variable to each unknown and unify on constraints (Hindley-Milner); this is a separate stage, not a change to the checker above. Done when: each error test input produces the expected diagnostic and valid inputs pass.

7. Recover from syntax errors with panic mode: on error, advance until a synchronizing token, then resume. Pick the synchronizing set per nonterminal (statement end ;, block end }, statement-start keywords).

   void synchronize(Parser *p) {
       advance(p);
       while (p->cur.kind != TOK_EOF) {
           if (p->prev.kind == TOK_SEMI) return;
           if (p->cur.kind == TOK_RETURN || p->cur.kind == TOK_IDENT) return;
           advance(p);
       }
   }
   

   Error productions for common mistakes and single-token insertion or deletion are the next steps when the frontend serves an editor. Done when: an input with two independent errors reports both, not a cascade from the first.

8. Emit LLVM IR from the typed AST through the C API. Create types from a context, build instructions through a builder, and use the typed load: the untyped LLVMBuildLoad is gone from the current C API (LLVM 23.1.0) and LLVMInt32Type() without a context is deprecated.

   #include <llvm-c/Core.h>
   #include <llvm-c/Analysis.h>
   
   LLVMContextRef ctx; LLVMModuleRef module; LLVMBuilderRef builder;
   
   LLVMValueRef codegen_expr(Scope *s, AstNode *node) {
       switch (node->kind) {
       case AST_INT:
           return LLVMConstInt(LLVMInt32TypeInContext(ctx), (unsigned long long)node->int_val, 1);
       case AST_BINOP: {
           LLVMValueRef l = codegen_expr(s, node->binop.lhs);
           LLVMValueRef r = codegen_expr(s, node->binop.rhs);
           if (node->binop.op == TOK_PLUS) return LLVMBuildAdd(builder, l, r, "add");
           break;
       }
       case AST_VAR: {
           Symbol *sym = scope_lookup(s, node->name);
           return LLVMBuildLoad2(builder, LLVMInt32TypeInContext(ctx), sym->llvm_val, node->name);
       }
       }
       return NULL;
   }
   

   After emitting, dump and verify: LLVMDumpModule(module); and LLVMVerifyModule(module, LLVMReturnStatusAction, &err); where LLVMVerifyModule is declared in llvm-c/Analysis.h. Done when: the verifier returns success on every valid test input.

Failure and recovery

No partial result is claimed complete. If a stage cannot finish, the report states which stages passed their verification and which are blocked.

Output

A frontend delivery containing:

1. Files written: each source file created or edited, per stage.
2. Verification: per stage, the test inputs run and the observed token stream, tree, diagnostic, or verifier result.
3. Open decisions: any grammar ambiguity or type rule the language description left undefined, with the choice made.