Entender el diseño de compiladores para escribir mejor código

Introducción accesible a los fundamentos de los compiladores: lexing, parsing, ASTs y generación de código, con ejemplos que mejoran tu forma de programar.

Publicado el 25 de octubre de 2022Actualizado el 9 de septiembre de 20265 min de lectura

compilers ast parsing typescript programming-languages tooling

No necesitas construir un compilador de producción para beneficiarte de entender cómo funcionan los compiladores. Los conceptos de los compiladores aparecen por todas partes en la ingeniería de software: las reglas de ESLint recorren árboles de sintaxis abstracta, Babel transforma código manipulando ASTs, los motores de plantillas analizan y generan HTML, y los constructores de consultas construyen SQL a partir de cadenas de métodos.

Entender el pipeline de compilación — lexing, parsing, transformación y generación de código — te da el modelo mental para construir linters personalizados, generadores de código, DSLs (lenguajes específicos de dominio) y analizadores de configuración. Esta guía construye un pequeño evaluador de expresiones para hacer estos conceptos más concretos.

Etapa 1: Lexing (Tokenización)

El lexer convierte el texto fuente sin procesar en un flujo de tokens. Cada token tiene un tipo y un valor. Los espacios en blanco y los comentarios se descartan. El lexer no entiende la estructura — solo identifica los átomos.

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

Etapa 2: Parsing (Construcción del AST)

El parser toma el flujo de tokens y construye un Árbol de Sintaxis Abstracta (AST) — una estructura de árbol que representa las relaciones jerárquicas entre operaciones. La precedencia de operadores (la multiplicación antes que la suma) y el agrupamiento entre paréntesis quedan capturados en la estructura del árbol.

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

Etapa 3: Transformación del AST

Con un AST, puedes analizar y transformar código sin manipular cadenas de texto. Así es como funcionan ESLint, Prettier y Babel — analizan el código para obtener un AST, lo recorren, y reportan problemas o producen un árbol modificado.

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)

Etapa 4: Generación de Código

La generación de código recorre el AST y produce una salida — JavaScript, SQL, HTML o cualquier formato de destino.

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

Aplicaciones en el Mundo Real

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

Conclusiones Clave

Los compiladores siguen un pipeline: lex → parse → transform → generate — entender cada etapa te ayuda a construir herramientas, escribir linters personalizados y crear DSLs
Los lexers convierten texto en tokens, los parsers convierten tokens en árboles — el AST es la estructura de datos central; todo el análisis y la transformación ocurren sobre el árbol, no sobre cadenas de texto
El patrón visitor es la forma en que las herramientas recorren los ASTs — las reglas de ESLint, los plugins de Babel y los formateadores de código usan visitors para recorrer y modificar árboles de sintaxis
Nunca manipules el código como cadenas de texto — la manipulación de cadenas es frágil y propensa a inyecciones; la generación de código basada en AST es estructurada, segura y componible
Los parsers de descenso recursivo manejan la precedencia de operadores de forma natural — cada nivel de precedencia es una función que llama al siguiente nivel, construyendo el árbol con el anidamiento correcto