Analizadores sintácticos monádicos

Analizadores sintácticos

Aunque no existe una única representación, aquí definiremos un analizador sintáctico como una función que recibe dos parámetros: la entrada que debe ser analizada y la posición por la que debe seguir analizando la entrada. Utilizaremos el constructor Parser como contenedor de estas funciones.

function Parser(parser) {
    this.parser = parser;
}

El analizador devolverá como resultado un array de objetos formados por dos propiedades:

• value: el valor analizado; es decir, el dato estructurado.
• index: la posición del último carácter analizado.

Es frecuente que los analizadores sintácticos produzcan una lista de resultados en lugar de uno solo permitiendo así que el proceso de análisis sea no determinista: ante una única entrada el analizador podría fallar o devolver una o varias respuestas.

Parser.prototype.run = function(input) {
    var results = this.parser(input, 0);
    if(results.length === 0)
        return null;
    return results[0].value;
}

Cuando ejecutamos el proceso de análisis mediante el método run analizamos la cadena de entrada input desde el principio y devolvemos únicamente el valor del primer resultado obtenido.

Bloques de construcción básicos

La mayoría de analizadores se construyen combinando otros analizadores más simples. La función más elemental para construir analizadores sintácticos es sat. Esta función toma como argumento un predicado y devuelve un analizador que consume el primer carácter de la entrada si este satisface el predicado.

Parser.sat = function(p) {
    return new Parser(function(input, i) {
        var c = input.charAt(i);
        return p(c) ? [{value: c, index: i+1}] : [];
    });
};

Por ejemplo, podemos definir el predicado isDigit para comprobar si un caracter es un dígito y construir un analizador que consume el siguiente caracter de la entrada si es un dígito:

function isDigit(c) {
    return c >= '0' && c <= '9';
}

nodejs> Parser.sat(isDigit).run("123");
'1'
nodejs> Parser.sat(isDigit).run("abc");
null

A partir de sat podemos construir otras funciones básicas como char, que recibe un carácter c y devuelve un analizador que consume el siguiente carácter de la cadena si es c; o next, que consume el siguiente carácter de la cadena, sea cual sea:

Parser.char = function(x) {
    return Parser.sat(c => c == x);
};

Parser.next = Parser.sat(_ => true);

nodejs> Parser.char('a').run("abc");
'a'
nodejs> Parser.char('a').run("bcd");
null
nodejs> Parser.next.run("abc");
'a'
nodejs> Parser.next.run("");
null

Análisis aplicativo

A menudo resulta de utilidad poder transformar el posible valor generado por un analizador. Para ello, la función map recibe una función y devuelve un nuevo analizador que ejecuta el analizador original y aplica la función al valor de cada resultado.

Parser.prototype.map = function(f) {
    var parser = this.parser;
    return new Parser(function(input, i) {
        var results = parser(input, i);
        for(var j = 0; j < results.length; j++)
            results[j].value = f(results[j].value);
        return results;
    });
};

De esta forma, el comportamiento del nuevo analizador es el mismo que el del anterior, pero los valores generados son modificados. Por ejemplo, si un analizador consume un dígito nos podría interesar que el analizador devolviese directamente el número que representa el carácter analizado:

nodejs> Parser.sat(isDigit).map(parseInt).run("123");
1

De forma más general, estamos interesados en aplicar una función a dos o más posibles valores generados por analizadores.

Parser.pure = function(value) {
    return new Parser((_, i) => [{value: value, index: i}]);
};

La función pure recibe un valor y devuelve un analizador que, independientemente de la entrada, siempre analiza ese valor sin consumir nada de la entrada.

Parser.prototype.ap = function(q) {
    var p = this;
    return new Parser(function(input, i) {
        var fs = p.parser(input, i);
        var results = [];
        for(var j = 0; j < fs.length; j++) {
            if(q instanceof Function)
                q = q();
            var xs = q.parser(input, fs[j].index);
            for(var k = 0; k < xs.length; k++)
                results.push({value: fs[j].value(xs[k].value), index: xs[k].index});
        }
        return results;
    });
};

La función ap ejecuta secuencialmente dos analizadores y aplica la función generada por el primer analizador al valor generado por el segundo analizador. Nótese que la entrada que lee el segundo analizador es la cadena restante que deja por analizar el primero. De esta forma, si queremos aplicar varios argumentos a una función sólo tenemos que encadenar llamadas a la función ap.

Por ejemplo, supongamos que queremos sumar el resultado de dos analizadores que consumen un dígito de la cadena de entrada:

nodejs> var digit = Parser.sat(isDigit).map(parseInt);
undefined
nodejs> Parser.pure(x => y => x + y).ap(digit).ap(digit).run("12");
3

Es importante observar que cuando la función devuelta por el primer analizador tiene más en parámetro, la función debe estar currificada; es decir, debe tomar los argumento de uno en uno e ir devolviendo funciones hasta que tenga todos los parámetros y pueda computar el resultado.

Además, también son muy útiles los métodos que nos permiten aplicar secuencialmente dos analizadores descartando el primer o segundo valor analizado: right y left, respectivamente. Estas funciones se construyen de forma inmediata a partir de ap.

Parser.prototype.right = function(q) {
    return Parser.pure(_ => y => y).ap(this).ap(q);
};

Parser.prototype.left = function(q) {
    return Parser.pure(x => _ => x).ap(this).ap(q);
};

Por ejemplo, la función pair recibe dos analizadores sintácticos, uno que analiza un dato x y otro que analiza un dato y, y devuelve un analizador que consume una tupla (x,y).

function pair(px, py) {
    return Parser.pure(x => y => [x,y])
        .ap(Parser.char('(').right(px))
        .ap(Parser.char(',').right(py))
        .left(Parser.char(')'));
}

nodejs> pair(digit, digit).run("(1,2)");
[1, 2]
nodejs> pair(digit, Parser.next).run("(1,a)");
[1, 'a']

Fallos y alternativas

Como indicamos al principio del artículo, nuestro proceso de análisis es no determinista, lo que siginifica que es posible fallar a la hora de analizar una entrada. Por ello, es conveniente introducir un combinador para manejar fallos y alternativas de forma que sea posible lanzar un analizador y, si este no tiene éxito, ejecutar otro en su defecto.

Parser.prototype.or = function(q) {
    var p = this;
    return new Parser(function(input, i) {
        var results = p.parser(input, i);
        if(results.length !== 0)
            return results;
        if(q instanceof Function)
            q = q();
        return q.parser(input, i);
    });
};

nodejs> Parser.char('a').or(Parser.char('b')).run("abc")
'a'
nodejs> Parser.char('a').or(Parser.char('b')).run("bac")
'b'
nodejs> Parser.char('a').or(Parser.char('b')).run("cab")
null

A partir de este combinador podemos construir otras dos funciones realmente útiles para el análisis sintáctico:

• many aplica un analizador cero o más veces.
• some aplica un analizador una o más veces.

Parser.prototype.many = function() {
    return Parser.pure(x => xs => [x, ...xs])
        .ap(this)
        .ap(() => this.some());
};

Parser.prototype.some = function() {
    return this.many().or(Parser.pure([]));
};

La diferencia entre many y some es que many permite analizar una cadena vacía, mientras que some tiene que tener éxito al menos una vez.

Por ejemplo, un número natural es una secuencia no nula de dígitos. Podemos utilizar el combinador some para consumir uno o más dígitos numéricos de la entrada, y transformar la cadena resultante a un entero.

var natural = Parser.sat(isDigit)
    .many()
    .map(xs => parseInt(xs.join('')));

nodejs> natural.run("123foo");
123
nodejs> natural.run("foo");
null

La interfaz de funtor aplicativo es lo suficientemente expresiva para analizar gramáticas libres de contexto. Una gramática libre de contexto es una gramática formal en la que cada regla de producción es de la forma A → α, donde A es un símbolo no terminal y α es una cadena de símbolos terminales y no terminales.^[1]

Un ejemplo sencillo de gramática libre de contexto es una gramática para analizar expresiones aritméticas. Por simplicidad, consideraremos que las expresiones aritméticas contienen únicamente números naturales, sumas +, productos * y paréntesis ( y ) para agrupar expresiones, con la precedencia usual de los operadores, pero asociándolos por la derecha.

• <Expr> → <Factor> "+" <Expr> | <Factor>
• <Factor> → <Term> "*" <Factor> | <Term>
• <Term> → "(" <Expr> ")" | <Natural>

donde | es un operador usado para separar múltiples opciones para un mismo no terminal. (De hecho, en este contexto, | se corresponde con la función or).

function rexpr() {
    return Parser.pure(x => y => {return {op: '+', left: x, right: y}})
        .ap(() => rfactor().left(Parser.char('+')))
        .ap(rexpr)
        .or(rfactor);
}

function rfactor() {
    return Parser.pure(x => y => {return {op: '*', left: x, right: y}})
        .ap(() => rterm().left(Parser.char('*')))
        .ap(rfactor)
        .or(rterm);
}

function rterm() {
    return natural.or(
        Parser.char('(')
        .right(rexpr)
        .left(Parser.char(')')));
}

nodejs> rexpr().run("(1+2+3)*4");
{
  op: '*',
  left: { op: '+', left: 1, right: { op: '+', left: 2, right: 3 } },
  right: 4
}

Análisis monádico

No todos los lenguajes pueden ser expresados mediante gramáticas libres de contexto. Para analizar algunas gramáticas es necesario que el segundo analizador tenga la información del valor generado por el primero. La función lazo de un analizador permite extraer el valor generado por un analizador y pasarlo como parámetro a una función que devuelva otro analizador en función del valor consumido anteriormente.

Parser.prototype.then = function(f) {
    var p = this;
    return new Parser(function(input, i) {
        var results = [];
        var xs = p.parser(input, i);
        for(var j = 0; j < xs.length; j++)
            results.push(...f(xs[j].value).parser(input, xs[j].index));
        return results;
    });
};

Ahora podemos reimplementar el analizador de expresiones aritméticas respetando la asociatividad usual de los operadores por la izquierda. La gramática correspodiente es la siguiente:

• <Expr> → <Factor> <Expr'>
• <Expr'> → "+" <Factor> <Expr'> | ε
• <Factor> → <Term> <Expr'>
• <Factor'> → "*" <Term> <Factor'> | ε
• <Term> → <Natural> | "(" <Expr> ")"

donde ε representa la producción nula.

function lexpr() {
    return lfactor().then(lexpr_);
}

function lexpr_(x) {
    return Parser.char('+')
        .right(lfactor)
        .then(y => lexpr_({op: '+', left: x, right: y}))
        .or(Parser.pure(x));
}

function lfactor() {
    return lterm().then(lfactor_);
}

function lfactor_(x) {
    return Parser.char('*')
        .right(lterm)
        .then(y => lfactor_({op: '*', left: x, right: y}))
        .or(Parser.pure(x));
}

function lterm() {
    return natural.or(
        Parser.char('(')
        .right(lexpr)
        .left(Parser.char(')')));
}

nodejs> lexpr().run("(1+2+3)*4");
{
  op: '*',
  left: { op: '+', left: { op: '+', left: 1, right: 2 }, right: 3 },
  right: 4
}

Referencias

• Hutton, G., & Meijer, E. (1998). Monadic parsing in Haskell. Journal of functional programming, 8(4), 437-444.
• Hutton, G. (2016). Monadic parsing. In Programming in Haskell (pp. 177-195). Cambridge: Cambridge University Press.

Notas

1. _{El término «libre de contexto» se refiere al hecho de que el símbolo no terminal A siempre puede ser reemplazado por α sin tener en cuenta el contexto en el que ocurra.}