Parser Combinators: un poco de teoría

Puede que en algunas ocasiones os hayais tenido que enfrentar con la necesidad de escribir un pequeño lenguaje que realice una tarea muy concreta (profundizaremos en el tema de los DSLs en un post futuro): como, por ejemplo, procesar determinados archivos de configuración de vuestra aplicación o la definición de interfaces de usuario de manera sencilla.

Independientemente de las razones por las que estamos desarrollando este componente, necesitaremos un parser que nos ayude a transformar el lenguaje de entrada en una estructura de datos que nuestro programa pueda comprender y procesar. Algunas de las alternativas que se nos plantean son:

• Escribir nuestro propio parser (conllevaría escribir también el analizador léxico). Si no somos expertos en la materia estaremos enfrentándonos a una tarea relativamente complicada.

• Utilizar herramientas para la generación de parsers como Antlr,Bison o JavaCC entre otras muchas. En este caso la dificultad estriba en la necesidad de aprender a manejar una nueva herramienta/lenguaje e integrarlo en nuestro desarrollo y ecosistema.

Durante esta entrada, y posiblemente la siguiente, vamos a presentar un enfoque alternativo a las dos opciones anteriores. En lugar de utilizar un DSL externo como podría ser el ofrecido por Antlr, vamos a utilizar un DSL interno. Dicho DSL estará formado por parser combinators (funciones y operadores definidos en Scala que servirán como base para la construcción de nuestros futuros parsers).

Siendo originales :), imaginemos que deseamos cosntruir un parser de expresiones aritméticas de números enteros. En primer lugar, definamos la gramática de nuestro lenguaje:

expr  ::= term {"+" term | "-" term}. 

term  ::= factor {"*" factor | "/" factor}.

factor  ::=  integer | "(" expr ")".

El fragmento de código anterior representa una gramática libre de contexto (no vamos a profundizar en este tema porque tendríamos que escribir miles de posts) que modela nuestro lenguaje de expresiones aritméticas de números enteros. ¿Y ahora?

Una vez definida la gramática anterior hemos llevado a cabo la tarea más complicada de todas. Si utilizais los parser combinators ofrecidos por Scala tendremos casi todo el trabajo sucio realizado. A modo de ejemplo:

import scala.util.parsing.combinator._

class IntegerArithmetics extends JavaTokenParsers {

   def expr: Parser[Any] = term~rep("+"~term | "-"~term)

   def term: Parser[Any] = factor~rep("*"~factor | "/"~factor)

   def factor: Parser[Any] = integer | "("~expr~")"

}

Si comparamos el código Scala con la definición en notación EBNF de nuestra gramática observaremos que podríamos inferir nuestro código fuente Scala sin más que realizar una serie de reemplazos en nuestra notación EBNF:

1. Cada regla se convierte en un método por lo que tendremos que prefijarlas con def.
2. El tipo de retorno de cada uno de los métodos anteriores es Parser[Any] (veremos en la siguiente entrada que significa esto) por lo que tendremos que cambiar el símbolo "::=" por ":Parser[Any] ="
3. Insertar el símbolo ~ entre todos los elementos de cada una de las reglas (en la notación EBNF esto es implícito)
4. La repetición se refleja mediante el uso de rep(...) en lugar de {...}
5. El punto al final de cada regla no es necesario (podríamos poner ; si lo deseamos)

Esto no ha sido más que una toma de contacto con el mundo de los parser combinators en Scala. En la siguiente entrada descubriremos cómo realizar construcciones más complejas, formatear la salida de manera que podamos construir las estructuras de datos requeridas para nuestro procesamiento o ejecutar nuestros parsers. 

Para todo ello diseñaremos y construiremos un pequeño parser que nos permita analizar el bytecode de la máquina virtual una vez desemsamblado (para los más inquietos javap -v ClassFile (sin .class))