Understanding Compiler Design for Better Code

A developer-friendly introduction to compiler fundamentals: lexing, parsing, ASTs and code generation, with examples that make you a better programmer.

Published on October 25, 2022Updated on September 9, 20264 min read

compilers ast parsing typescript programming-languages tooling

You do not need to build a production compiler to benefit from understanding how compilers work. Compiler concepts show up everywhere in software engineering: ESLint rules walk abstract syntax trees, Babel transforms code by manipulating ASTs, template engines parse and generate HTML, and query builders construct SQL from method chains.

Understanding the compilation pipeline — lexing, parsing, transformation, and code generation — gives you the mental model to build custom linters, code generators, DSLs (domain-specific languages), and configuration parsers. This guide builds a small expression evaluator to make the concepts concrete.

Stage 1: Lexing (Tokenization)

The lexer converts raw source text into a stream of tokens. Each token has a type and a value. Whitespace and comments are discarded. The lexer does not understand structure — it just identifies the atoms.

tstypescript

type TokenType =
  | "NUMBER"
  | "PLUS"
  | "MINUS"
  | "MULTIPLY"
  | "DIVIDE"
  | "LPAREN"
  | "RPAREN"
  | "IDENTIFIER"
  | "EOF";
 
interface Token {
  type: TokenType;
  value: string;
  position: number;
}
 
class Lexer {
  private pos = 0;
  private tokens: Token[] = [];
 
  constructor(private source: string) {}
 
  tokenize(): Token[] {
    while (this.pos < this.source.length) {
      const char = this.source[this.pos];
 
      if (/\s/.test(char)) {
        this.pos++;
        continue;
      }
 
      if (/\d/.test(char)) {
        this.readNumber();
        continue;
      }
 
      if (/[a-zA-Z_]/.test(char)) {
        this.readIdentifier();
        continue;
      }
 
      const singleCharTokens: Record<string, TokenType> = {
        "+": "PLUS",
        "-": "MINUS",
        "*": "MULTIPLY",
        "/": "DIVIDE",
        "(": "LPAREN",
        ")": "RPAREN",
      };
 
      const tokenType = singleCharTokens[char];
      if (tokenType) {
        this.tokens.push({
          type: tokenType,
          value: char,
          position: this.pos,
        });
        this.pos++;
        continue;
      }
 
      throw new Error(
        `Unexpected character '${char}' at position ${this.pos}`
      );
    }
 
    this.tokens.push({ type: "EOF", value: "", position: this.pos });
    return this.tokens;
  }
 
  private readNumber(): void {
    const start = this.pos;
    while (this.pos < this.source.length && /[\d.]/.test(this.source[this.pos])) {
      this.pos++;
    }
    this.tokens.push({
      type: "NUMBER",
      value: this.source.slice(start, this.pos),
      position: start,
    });
  }
 
  private readIdentifier(): void {
    const start = this.pos;
    while (
      this.pos < this.source.length &&
      /[a-zA-Z0-9_]/.test(this.source[this.pos])
    ) {
      this.pos++;
    }
    this.tokens.push({
      type: "IDENTIFIER",
      value: this.source.slice(start, this.pos),
      position: start,
    });
  }
}
 
// "3 + 4 * (2 - 1)" → [NUMBER:3, PLUS, NUMBER:4, MULTIPLY, LPAREN, ...]

Stage 2: Parsing (Building the AST)

The parser takes the token stream and builds an Abstract Syntax Tree (AST) — a tree structure that represents the hierarchical relationships between operations. Operator precedence (multiplication before addition) and parenthetical grouping are captured in the tree structure.

tstypescript

type ASTNode =
  | { type: "NumberLiteral"; value: number }
  | { type: "Identifier"; name: string }
  | {
      type: "BinaryExpression";
      operator: string;
      left: ASTNode;
      right: ASTNode;
    }
  | {
      type: "UnaryExpression";
      operator: string;
      operand: ASTNode;
    };
 
class Parser {
  private pos = 0;
 
  constructor(private tokens: Token[]) {}
 
  parse(): ASTNode {
    const node = this.parseExpression();
    if (this.current().type !== "EOF") {
      throw new Error(
        `Unexpected token: ${this.current().value}`
      );
    }
    return node;
  }
 
  // Recursive descent parser with operator precedence
  // expression → term ((PLUS | MINUS) term)*
  private parseExpression(): ASTNode {
    let left = this.parseTerm();
 
    while (
      this.current().type === "PLUS" ||
      this.current().type === "MINUS"
    ) {
      const operator = this.consume().value;
      const right = this.parseTerm();
      left = { type: "BinaryExpression", operator, left, right };
    }
 
    return left;
  }
 
  // term → factor ((MULTIPLY | DIVIDE) factor)*
  private parseTerm(): ASTNode {
    let left = this.parseFactor();
 
    while (
      this.current().type === "MULTIPLY" ||
      this.current().type === "DIVIDE"
    ) {
      const operator = this.consume().value;
      const right = this.parseFactor();
      left = { type: "BinaryExpression", operator, left, right };
    }
 
    return left;
  }
 
  // factor → NUMBER | IDENTIFIER | LPAREN expression RPAREN | MINUS factor
  private parseFactor(): ASTNode {
    const token = this.current();
 
    if (token.type === "NUMBER") {
      this.consume();
      return { type: "NumberLiteral", value: parseFloat(token.value) };
    }
 
    if (token.type === "IDENTIFIER") {
      this.consume();
      return { type: "Identifier", name: token.value };
    }
 
    if (token.type === "LPAREN") {
      this.consume(); // eat (
      const node = this.parseExpression();
      this.expect("RPAREN"); // eat )
      return node;
    }
 
    if (token.type === "MINUS") {
      this.consume();
      return {
        type: "UnaryExpression",
        operator: "-",
        operand: this.parseFactor(),
      };
    }
 
    throw new Error(`Unexpected token: ${token.value} at ${token.position}`);
  }
 
  private current(): Token {
    return this.tokens[this.pos];
  }
 
  private consume(): Token {
    return this.tokens[this.pos++];
  }
 
  private expect(type: TokenType): Token {
    const token = this.consume();
    if (token.type !== type) {
      throw new Error(`Expected ${type}, got ${token.type}`);
    }
    return token;
  }
}

Stage 3: AST Transformation

With an AST, you can analyze and transform code without manipulating strings. This is how ESLint, Prettier, and Babel work — they parse code into an AST, walk it, and either report problems or produce a modified tree.

tstypescript

// Visitor pattern for walking ASTs
type Visitor = {
  [K in ASTNode["type"]]?: (
    node: Extract<ASTNode, { type: K }>
  ) => ASTNode | void;
};
 
function walkAndTransform(node: ASTNode, visitor: Visitor): ASTNode {
  const handler = visitor[node.type] as
    | ((n: ASTNode) => ASTNode | void)
    | undefined;
  const transformed = handler ? handler(node) ?? node : node;
 
  // Recurse into children
  if (transformed.type === "BinaryExpression") {
    return {
      ...transformed,
      left: walkAndTransform(transformed.left, visitor),
      right: walkAndTransform(transformed.right, visitor),
    };
  }
 
  if (transformed.type === "UnaryExpression") {
    return {
      ...transformed,
      operand: walkAndTransform(transformed.operand, visitor),
    };
  }
 
  return transformed;
}
 
// Example: constant folding (evaluate compile-time expressions)
const constantFolder: Visitor = {
  BinaryExpression(node) {
    if (
      node.left.type === "NumberLiteral" &&
      node.right.type === "NumberLiteral"
    ) {
      const ops: Record<string, (a: number, b: number) => number> = {
        "+": (a, b) => a + b,
        "-": (a, b) => a - b,
        "*": (a, b) => a * b,
        "/": (a, b) => a / b,
      };
      const fn = ops[node.operator];
      if (fn) {
        return {
          type: "NumberLiteral",
          value: fn(node.left.value, node.right.value),
        };
      }
    }
  },
};
 
// "3 + 4 * 2" → NumberLiteral(11)

Stage 4: Code Generation

Code generation walks the AST and produces output — JavaScript, SQL, HTML, or any target format.

tstypescript

// ❌ String concatenation for code generation
function generateBad(expr: string): string {
  return `console.log(${expr})`;
}
// Fragile, no structure, injection-prone
 
// ✅ AST-based code generation
function generateJS(node: ASTNode): string {
  switch (node.type) {
    case "NumberLiteral":
      return node.value.toString();
    case "Identifier":
      return node.name;
    case "BinaryExpression":
      return `(${generateJS(node.left)} ${node.operator} ${generateJS(node.right)})`;
    case "UnaryExpression":
      return `(${node.operator}${generateJS(node.operand)})`;
  }
}
 
// Generate SQL WHERE clauses from filter AST
interface FilterNode {
  type: "comparison" | "and" | "or";
  field?: string;
  operator?: string;
  value?: string | number;
  left?: FilterNode;
  right?: FilterNode;
}
 
function generateSQL(
  filter: FilterNode,
  params: unknown[]
): string {
  switch (filter.type) {
    case "comparison": {
      params.push(filter.value);
      return `${filter.field} ${filter.operator} $${params.length}`;
    }
    case "and":
      return `(${generateSQL(filter.left!, params)} AND ${generateSQL(filter.right!, params)})`;
    case "or":
      return `(${generateSQL(filter.left!, params)} OR ${generateSQL(filter.right!, params)})`;
  }
}
 
// Parameterized — no SQL injection possible

Real-World Applications

tstypescript

// Where compiler concepts appear in daily work:
 
const compilerConceptsInPractice = {
  eslintRules:
    "ESLint parses JS/TS into AST (using Espree/TypeScript parser), " +
    "your custom rules are visitors that walk the tree",
  templateEngines:
    "Handlebars, EJS, and JSX are DSLs with their own lexers " +
    "and parsers that output render functions",
  queryBuilders:
    "Prisma, Knex, and TypeORM build SQL ASTs from method chains " +
    "and generate parameterized queries",
  configParsers:
    "YAML, TOML, and JSON parsers all follow the lexer → parser → " +
    "AST pipeline to produce structured data",
  codegen:
    "OpenAPI code generators parse API specs into ASTs and generate " +
    "client/server code from templates",
  linters:
    "Custom linting rules for your team's conventions are AST " +
    "visitors that flag specific patterns",
};

Key Takeaways

Compilers follow a pipeline: lex → parse → transform → generate — understanding each stage helps you build tooling, write custom linters, and create DSLs
Lexers convert text to tokens, parsers convert tokens to trees — the AST is the central data structure; all analysis and transformation happens on the tree, not on strings
The visitor pattern is how tools walk ASTs — ESLint rules, Babel plugins, and code formatters all use visitors to traverse and modify syntax trees
Never manipulate code as strings — string manipulation is fragile and prone to injection; AST-based code generation is structured, safe, and composable
Recursive descent parsers handle operator precedence naturally — each precedence level is a function that calls the next level, building the tree with correct nesting

Understanding Compiler Design for Better Code

Stage 1: Lexing (Tokenization)

Stage 2: Parsing (Building the AST)

Stage 3: AST Transformation

Stage 4: Code Generation

Real-World Applications

Key Takeaways

Related Posts

Building a Custom ESLint Plugin

Stop Reaching for any: Narrowing unknown in TypeScript

Cancellation Patterns in TypeScript: Taming AbortController