miércoles, marzo 30, 2011

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))

2 comentarios:

Migue dijo...

Hola tocayo y casi colega (estoy a falta del proyecto para terminar la carrera).
He estado ojeando tu blog y me parecen muy interesantes los temas que propones. Este último sobre los Parsers, por ejemplo, creo que puede ser muy útil, y está, en cierto modo, relacionado con mi pregunta.
Resulta que mi proyecto consiste en desarrollar un IDE para un lenguaje de mi elección. En un principio creí que tenía que inventar un lenguaje y desarrollar también el compilador (de ahí la relación con este tema), pero no, puedo utilizar el lenguaje que quiera. El lenguaje que he elegido es Java, ya que debe ser del que se disponga de más documentación.
A este respecto, quería hacerte unas preguntas:

(1) ¿Sabes dónde encontrar documentación (en español, el inglés lo dejo para cuando entregue el proyecto) sobre las últimas tendencias en desarrollo de IDEs?

(2) ¿Y sobre cómo emprezar desde el principio el desarrollo del IDE?

(3) El proyecto lo voy a desarrollar en Java y, en principio, iba a utilizar Eclipse, que es el que conozco, pero parece que encuentro más información sobre este tema en desarrollos realizados con Netbeans, que no lo he utilizado nunca. Teniendo esto en cuenta, ¿cual me aconsejas que utilice?

Te agradecerá mucho tu ayuda, ya que ahora mismo estoy bastante perdido.

Saludos.

migue dijo...

Hola Migue,

En primero lugar perdona por el retraso en responder pero esta última temporada he estado a 1000 por hora.

Y también muchas gracias por pasarte por el blog y comentar.

A ver si nos logramos entender :)

(1) Muchos de los equipos que desarrollan IDEs para lenguajes que se ejecutan sobre la máquina virtual Java (Scala, Groovy, JRuby, etc) intentan aprovechar la estructura existente con el objetivo de minimizar el esfuerzo de la construcción de un nuevo IDE. En el caso de Eclipse existe una tecnología llamada JDT Weaving service que permite "adherirse" a los puntos de extensión expuestos por el JDT. Es un poco avanzado pero es bastante potente (puedes encontrar un mini-ejemplo aquí http://miguelinlas3.blogspot.com/2009/11/jdt-weaving-service.html).

(2) ¿Por donde empezar? Pues es una tarea complicada. En un primer lugar tendrás que seleccionar el lenguaje para el cuál quieres construir el IDE. Si me permites un consejo, escoge un lenguaje con tipado estático, te facilitará mucho las cosas.

(3) Una vez tengas claro el lenguaje para el cual vas a desarrollar el IDE tendrás que ver donde te encaja mejor y con que tecnlogías te sientes más cómodo. Tanto Eclipse, como Netbeans y también IntelliJ tienen la infraestructura necesaria para la construcción de nuevos IDEs. Yo tengo mucha experiencia con Eclipse y desconozco los otros dos así que mi opinión no creo que sea demasiado objetiva :).

En mi caso, hace un tiempo, desarrollé un IDE basado en Eclipse para el lenguaje de programación R. Este proyecto está basado en unos proyectos de Eclipse llamados DLTK (son una especie de frameworks para la construcción de IDEs de lenguajes de scripting) que están muy bien.

Si buscas el proyecto R-Eclipse en Google Code encontrarás todo el código fuente del proyecto.

Si necesitas alguna cosa más en la que pueda ayudarte no dudes en preguntarme (mejor al email miguelinlas3@gmail.com)

Un saludo y ánimo!

Migue