Combinadores de analizador de Scala

Cuando se requiere un generador de analizadores, algunos analizadores famosos que se nos pasan por la cabeza son: Yacc y Bison para analizadores escritos en C y ANTLR para analizadores escritos en Java, pero están diseñados para ejecutarse en lenguajes de programación específicos. Esto acorta el ámbito de uso de los analizadores. Sin embargo, Scala ofrece una alternativa única y útil. En lugar de usar el lenguaje específico de dominio independiente de un generador de analizadores, se puede usar un lenguaje específico de dominio interno (DSL interno para abreviar). El DSL interno constará de una biblioteca de combinadores de analizadores: funciones y operadores definidos en Scala que servirán como bloques de construcción para los analizadores.

Para comprender este contenido, se deben tener conocimientos básicos de compiladores y comprender lenguajes regulares y libres de contexto.

• Gramática regular
• Gramática libre de contexto

El primer paso siempre es escribir una gramática para el lenguaje que se va a analizar.
Expresión: cada expresión (representada por expr) es un término que puede ir seguido de una secuencia de operadores ‘+’ o ‘-‘ y otros términos.
Término: Un término es un factor, posiblemente seguido por una secuencia de operadores ‘*’ o ‘/’ y otros factores.
Factor: Un factor es un literal numérico o una expresión entre paréntesis.

Ejemplo de analizador de expresiones aritméticas:

expr ::= term {"+" term | "-" term}. 
term ::= factor {"*" factor | "/" factor}. 
factor ::= ?FloatingPointNumber | "(" expr ")".

| denota producciones alternativas
{ … } denota repetición (cero o más veces)

Código de Scala para el ejemplo anterior:

import scala.util.parsing.combinator._
class Arith extends JavaTokenParsers 
{ 
    def expr: Parser[Any] = term~rep("+"~term | "-"~term) 
    def term: Parser[Any] = factor~rep("*"~factor | "/"~factor) 
    def factor: Parser[Any] = floatingPointNumber | "("~expr~")" 
}

Los analizadores de expresiones aritméticas están contenidos en una clase que hereda del rasgo JavaTokenParsers.

Pasos para convertir la gramática libre de contexto en código:

1. Cada producción se convierte en un método, por lo tanto, agregue un prefijo ‘def’.
2. El tipo de resultado de cada método es Parser[Any], por lo que debemos cambiar el símbolo ::= a “: Parser[Any] =”.
3. En la gramática, la composición secuencial estaba implícita, pero en el programa se expresa mediante un operador explícito: ~. Entonces necesitamos insertar un ‘~’ entre cada dos símbolos consecutivos de una producción.
4. La repetición se expresa rep(…) en lugar de {…}.
5. Se omite el punto (.) al final de cada producción, sin embargo, también se pueden usar punto y coma (;).

¡Prueba si tu analizador funciona o no con el siguiente código!

object ParseExpr extends Arith 
{ 
    def main(args: Array[String]) 
    { 
        println("input : "+ args(0)) 
        println(parseAll(expr, args(0))) 
    } 
}

El objeto ParseExpr define un método principal que analiza el primer argumento de la línea de comandos que se le pasa. El análisis se realiza mediante la expresión: parseAll(expr, input)

Podemos ejecutar el analizador aritmético con el siguiente comando:

$ scala ParseExpr "4 * (5 + 7)" 
input: 4 * (5 + 7) 
[1.12] parsed: ((4~List((*~(((~((5~List())~List((+ ~(7~List())))))~)))))~List())

La salida nos dice que el analizador analizó con éxito la string de entrada hasta la posición [1.12]. Eso significa que se analizó la primera línea y la duodécima columna o podemos decir que se analizó toda la string de entrada.

También podríamos verificar si el analizador funciona para una entrada incorrecta y da un error o no.
Ejemplo:

$ scala ParseExpr "2 * (3 + 7))" 
input: 2 * (3 + 7)) 
[1.12] failure: `-' expected but `)' found
2 * (3 + 7))            ˆ 

El analizador expr analizó todo excepto el paréntesis de cierre final que no forma parte de la expresión aritmética. El método ‘parseAll’ luego emitió un mensaje de error, diciendo que esperaba un operador en el punto del paréntesis de cierre.