Pratt Parsers: Una Solución Eficiente para el Análisis de Expresiones

El análisis de expresiones es uno de los desafíos más complejos en la construcción de un compilador o intérprete, especialmente cuando se manejan reglas de sintaxis con diferentes niveles de precedencia de operadores. Los enfoques tradicionales, como el análisis descendente recursivo, suelen requerir la implementación de múltiples funciones específicas para cada nivel de precedencia, lo que genera código extenso y difícil de mantener.

Sin embargo, existe una alternativa menos conocida pero altamente eficiente: el análisis de expresiones mediante Pratt Parsers, también conocido como análisis de precedencia de operadores de arriba hacia abajo. Introducido por Vaughan Pratt en los años 70, este método permite una forma más intuitiva y estructurada de analizar expresiones, eliminando muchas de las complicaciones de los enfoques tradicionales.

En este artículo exploraremos cómo funciona un Pratt Parser, por qué es una alternativa superior a otros métodos y cómo implementarlo paso a paso.

El Problema del Análisis de Expresiones Tradicional

Los lenguajes de programación suelen contar con operadores infijos (+, *, /), prefijos (-a, !b) y posfijos (a!). Esto complica el análisis, ya que se requiere manejar correctamente la precedencia de operadores (por ejemplo, la multiplicación tiene mayor prioridad que la suma) y la asociatividad (muchos operadores binarios se procesan de izquierda a derecha).

Consideremos la siguiente expresión:

a + b * c - d / e

Un analizador sintáctico descendente recursivo tendría que definir múltiples funciones para manejar cada nivel de precedencia:

• parseMultiplicacion()
• parseSuma()
• parseExpresionUnaria()

Este enfoque genera código difícil de leer y modificar, ya que las reglas gramaticales quedan dispersas entre muchas funciones.

La Solución con Pratt Parsing

Concepto Clave: Procesamiento Dinámico de la Precedencia de Operadores

En lugar de definir funciones separadas para cada operador, Pratt Parsing trata la precedencia de operadores de forma dinámica, utilizando un único método central de análisis.

El Pratt Parser:

1. Define comportamientos de análisis en una tabla, en lugar de funciones rígidas.
2. Procesa operadores conforme aparecen, determinando su precedencia en tiempo real.
3. Maneja operadores prefijos, infijos y posfijos de manera unificada.

El resultado es un código más modular, extensible y fácil de mantener.

Implementación de un Pratt Parser

1. Tokenización del Código

Antes de analizar una expresión, necesitamos dividir el código en tokens. Un token representa una unidad mínima de código y tiene:

• Tipo (por ejemplo, NUMERO, MAS, MENOS, PARENTESIS_IZQ)
• Valor (por ejemplo, 42, +, -)

Ejemplo de tokenización de 3 + 5 * (2 - 1):

[
  {"tipo": "NUMERO", "valor": "3"},
  {"tipo": "MAS", "valor": "+"},
  {"tipo": "NUMERO", "valor": "5"},
  {"tipo": "MULTIPLICAR", "valor": "*"},
  {"tipo": "PARENTESIS_IZQ", "valor": "("},
  {"tipo": "NUMERO", "valor": "2"},
  {"tipo": "MENOS", "valor": "-"},
  {"tipo": "NUMERO", "valor": "1"},
  {"tipo": "PARENTESIS_DER", "valor": ")"}
]

2. Estructura del Analizador

Un Pratt Parser se compone de dos elementos principales:

1. Prefix Parselets – Procesan expresiones que comienzan con un token (como números o operadores unarios).
2. Infix Parselets – Procesan expresiones con operadores binarios (+, *).

Definiendo la Estructura Base

abstract class Expresion {}

Gestión de Tokens

class Analizador {
    private final List<Token> tokens;
    private int posicion = 0;

    public Analizador(List<Token> tokens) {
        this.tokens = tokens;
    }

    private Token verSiguiente() {
        return posicion < tokens.size() ? tokens.get(posicion) : null;
    }

    private Token consumir() {
        return tokens.get(posicion++);
    }
}

3. Implementación de Prefix e Infix Parselets

Un Prefix Parselet maneja expresiones como 3, x, o -a:

interface PrefijoParselet {
    Expresion parse(Analizador analizador, Token token);
}

class NumeroParselet implements PrefijoParselet {
    public Expresion parse(Analizador analizador, Token token) {
        return new ExpresionNumero(Integer.parseInt(token.getValor()));
    }
}

Un Infix Parselet maneja operadores binarios (+, -, *):

interface InfijoParselet {
    Expresion parse(Analizador analizador, Expresion izquierda, Token token);
    int getPrecedencia();
}

class OperadorBinarioParselet implements InfijoParselet {
    private final int precedencia;

    public OperadorBinarioParselet(int precedencia) {
        this.precedencia = precedencia;
    }

    public Expresion parse(Analizador analizador, Expresion izquierda, Token token) {
        Expresion derecha = analizador.parseExpresion(precedencia);
        return new ExpresionBinaria(izquierda, token, derecha);
    }

    public int getPrecedencia() {
        return precedencia;
    }
}

4. Implementación del Algoritmo Central

class Analizador {
    private final Map<TipoToken, PrefijoParselet> prefijos = new HashMap<>();
    private final Map<TipoToken, InfijoParselet> infijos = new HashMap<>();

    public Expresion parseExpresion(int precedencia) {
        Token token = consumir();
        PrefijoParselet prefijo = prefijos.get(token.getTipo());

        if (prefijo == null) {
            throw new ParseException("Token inesperado: " + token);
        }

        Expresion izquierda = prefijo.parse(this, token);

        while (precedencia < getPrecedencia()) {
            token = consumir();
            InfijoParselet infijo = infijos.get(token.getTipo());
            izquierda = infijo.parse(this, izquierda, token);
        }

        return izquierda;
    }

    private int getPrecedencia() {
        InfijoParselet parser = infijos.get(verSiguiente().getTipo());
        return (parser != null) ? parser.getPrecedencia() : 0;
    }

    public void registrar(TipoToken tipo, PrefijoParselet prefijo) {
        prefijos.put(tipo, prefijo);
    }

    public void registrar(TipoToken tipo, InfijoParselet infijo) {
        infijos.put(tipo, infijo);
    }
}

5. Definiendo Precedencia de Operadores

class Precedencia {
    public static final int BAJA = 1;
    public static final int SUMA = 2;       
    public static final int PRODUCTO = 3;   
    public static final int PREFIJO = 4;    
}

Registramos los operadores con su precedencia:

analizador.registrar(TipoToken.NUMERO, new NumeroParselet());
analizador.registrar(TipoToken.MAS, new OperadorBinarioParselet(Precedencia.SUMA));
analizador.registrar(TipoToken.MENOS, new OperadorBinarioParselet(Precedencia.SUMA));
analizador.registrar(TipoToken.MULTIPLICAR, new OperadorBinarioParselet(Precedencia.PRODUCTO));
analizador.registrar(TipoToken.DIVIDIR, new OperadorBinarioParselet(Precedencia.PRODUCTO));

Conclusión

El Pratt Parser es una alternativa eficiente al análisis descendente recursivo, permitiendo un código más modular, flexible y mantenible. Es una herramienta esencial para intérpretes, compiladores y lenguajes de dominio específico, facilitando el análisis de expresiones complejas con facilidad.

Fuente: journal.stuffwithstuff.com