Compiler-Design verstehen, um besseren Code zu schreiben

Entwicklerfreundliche Einführung in Compiler-Grundlagen: Lexing, Parsing, ASTs und Codegenerierung, mit Beispielen für besseren eigenen Code.

Veröffentlicht am 25. Oktober 2022Aktualisiert am 9. September 20265 Min. Lesezeit

compilers ast parsing typescript programming-languages tooling

Du musst keinen produktionsreifen Compiler bauen, um von einem Verständnis der Funktionsweise von Compilern zu profitieren. Compiler-Konzepte tauchen überall in der Softwareentwicklung auf: ESLint-Regeln durchlaufen abstrakte Syntaxbäume, Babel transformiert Code, indem es ASTs manipuliert, Template-Engines parsen und erzeugen HTML, und Query-Builder konstruieren SQL aus Methodenketten.

Wenn du die Compiler-Pipeline — Lexing, Parsing, Transformation und Codegenerierung — verstehst, hast du das mentale Modell, um eigene Linter, Codegeneratoren, DSLs (domänenspezifische Sprachen) und Konfigurationsparser zu bauen. Dieser Leitfaden baut einen kleinen Evaluator für Ausdrücke, um die Konzepte greifbar zu machen.

Stufe 1: Lexing (Tokenisierung)

Der Lexer wandelt rohen Quelltext in einen Strom von Tokens um. Jedes Token hat einen Typ und einen Wert. Leerzeichen und Kommentare werden verworfen. Der Lexer versteht keine Struktur — er identifiziert nur die Atome.

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, ...]

Stufe 2: Parsing (Aufbau des AST)

Der Parser nimmt den Token-Strom entgegen und baut einen abstrakten Syntaxbaum (AST) — eine Baumstruktur, die die hierarchischen Beziehungen zwischen Operationen abbildet. Operatorpriorität (Multiplikation vor Addition) und Klammerung werden in der Baumstruktur erfasst.

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

Stufe 3: AST-Transformation

Mit einem AST kannst du Code analysieren und transformieren, ohne Strings zu manipulieren. So arbeiten ESLint, Prettier und Babel — sie parsen Code zu einem AST, durchlaufen ihn und melden entweder Probleme oder erzeugen einen veränderten Baum.

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)

Stufe 4: Codegenerierung

Die Codegenerierung durchläuft den AST und erzeugt eine Ausgabe — JavaScript, SQL, HTML oder ein beliebiges Zielformat.

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

Anwendungen aus der Praxis

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

Die wichtigsten Erkenntnisse

Compiler folgen einer Pipeline: lex → parse → transform → generate — das Verständnis jeder Stufe hilft dir, Tools zu bauen, eigene Linter zu schreiben und DSLs zu erstellen
Lexer wandeln Text in Tokens um, Parser wandeln Tokens in Bäume um — der AST ist die zentrale Datenstruktur; jede Analyse und Transformation findet auf dem Baum statt, nicht auf Strings
Das Visitor-Pattern ist die Art, wie Tools ASTs durchlaufen — ESLint-Regeln, Babel-Plugins und Code-Formatter nutzen alle Visitors, um Syntaxbäume zu durchlaufen und zu verändern
Manipuliere Code niemals als String — String-Manipulation ist fragil und anfällig für Injections; AST-basierte Codegenerierung ist strukturiert, sicher und komponierbar
Rekursive Abstiegsparser handhaben Operatorpriorität auf natürliche Weise — jede Prioritätsstufe ist eine Funktion, die die nächste Stufe aufruft und so den Baum mit korrekter Verschachtelung aufbaut

Compiler-Design verstehen, um besseren Code zu schreiben

Stufe 1: Lexing (Tokenisierung)

Stufe 2: Parsing (Aufbau des AST)

Stufe 3: AST-Transformation

Stufe 4: Codegenerierung

Anwendungen aus der Praxis

Die wichtigsten Erkenntnisse

Ähnliche Beiträge

Ein eigenes ESLint-Plugin entwickeln

Schluss mit any: unknown in TypeScript sicher eingrenzen

Cancellation-Patterns in TypeScript: AbortController gezähmt