Parser Combinators: Parsing simple bytecode

Anteriormente, http://miguelinlas3.blogspot.com/2011/03/parser-combinators-un-poco-de-teoria.html, introducíamos de manera somera el concepto de parser combinators y parte de la teoría relacionada con los mismos. Durante esta entrada vamos a construir un sencillo parser que nos permita analizar un conjunto mínimo de instrucciones de la máquina virtual java (simplemente permitiremos la definición de funciones y la capacidad de ejecución de las mismas).

No analizaremos en detalle el funcionamiento de la máquina virtual java ni el conjunto de instrucciones  de la misma (podríamos llevarnos algo más que unos cuantos posts :) ) dado que el objetivo principal de esta entrada es profundizar en el concepto de parser combinators y presentar un ejemplo de uso real de los mismos. Pongámonos manos a la obra.

El código fuente que nos servirá como conductor de la entrada será el de la función factorial mostrado a continuación:

static int fact(int);

Code:

Stack=2, Locals=3, Args_size=1

0: iconst_1

1: istore_1

2: iconst_1

3: istore_2

4: iload_2

5: iload_0

6: if_icmpgt 19

9: iload_1

10: iload_2

11: imul

12: istore_1

13: iinc 2, 1

16: goto 4

19: iload_1

20: ireturn

Podréis objener el código desensamblado como el mostrado anteriormente mediante el comando javap -v Class donde Class represente un archivo bytecode.

El proceso de parsing se lleva a cabo mediante el uso de parser combinators (no perdamos de vista el objetivo de nuestra entrada ;) ) y presenta las siguientes características

1. Para cada una de las diferentes tipos de instrucciones soportadas definimos un parser combinator que es el encargado de parsear este tipo de instrucciones.
2. Cada uno de los parsers anteriores sabe cómo generar un objeto del tipo correspondiente. Se utiliza una jerarquía de tipos en la que cada una de las instrucciones bytecode soportadas está representada mediante una clase Scala.
3. El parser global construye un AST (en este caso es un simple lista de objetos) y un conjunto de infraestructura adicional con el objetivo de implementar un intérprete que ejecute la secuencia de instrucciones obtenida (fuera del ámbito de esta entrada podéis echarle un vistazo al código fuente)

¿Cómo actúan nuestros diferentes parsers? Analicemos por ejemplo el componente encargado de parsear las instrucciones ISTORE

lazy val beginInstructionFragment: Parser[Int] = integer <~ ":" ^^ { _.toInt}

lazy val iStoreBytecode: Parser[List[BytecodeInstruction]] = beginInstructionFragment ~> "istore_" ~ integer ^^ {

    case name ~ value => new IStoreInstruction(name,value)  :: List()

  }

El parser beginInstructionFragment es el encargado de parsear la primera parte de la instrucción, la que corresponde al lugar que ocupa la instrucción en el array de instrucciones. 

El segundo parser hace uso del primero y además sabe cómo parsear el texto restante de manera adecuada. En este caso nuestro este analizador es capaz de parsear las instrucciones istore_N donde N representa un número entero positivo cualquiera y devolver un objeto (dentro de una lista) de tipo IStoreInstruction en el que se incluyen el nombre de la instrucción y el entero correspondiente.

Como seguramente a muchos de los lectores de este post el fragmento de código anterior les suene un poco raro intentaremos analizar las diferentes opciones de combinaciones de parsers disponibles:

• Si escribimos un parser en el que utilizamos una cadena, como por ejemplo "istore", el resultado es la propia cadena.
• Podemos utilizar expresiones regulares, como por ejemplo, "[A-Z]".r . En este caso el resultado también sería la propia cadena
• Si utilizamos el símbolo ~ (composición secuencial) el resultado del proceso de parseo será la combinación de ambos resultados. Por tanto, si A devuelve "X" y B devuelve "true", el resultado de A~B sería  ~("X","true") (el tipo de este resultado sería una case class de tipo ~ . Adicionalmente podemos hacer uso de los operadores <~ y ~> los cuales mantienen los valores a la izquierda y a la derecha respectivamente.
• Otro elemento de combinación de parsers sería | . En este caso el valor de retorno sería el de aquel parser que pudiera parsear la entrada con éxito.
• rep(P) o rep(P,separator) retornan una lista de las múltiples ejecuciones de P.
• opt(P) retorna una instancia de tipo Option.

Adicionalmente a la combinación de los parsers, necesitaremos un mecanismo que nos permita reescribir la salida de los mismos, en nuestro caso para instanciar los objetos de tipo necesario y configurar nuestro AST. Para ello tendremos que hacer uso del operador de transformación ^^.

Una definición formar del operador anterior sería: Dado un parser P y una funcion f cualesquiera, una expresión del tipo P^^f implica que para cada resultado R de P el resultado de la expresión global es f(R) 

En el ejemplo que estamos tratando nuestra función es un simple pattern matching que transforma la case class retornada por nuestra combinación de parsers en un objeto de tipo IStoreInstruction.

No me ha resultado sencillo ponerlo por escrito y tampoco estoy seguro de que me haya explicado con la mayor claridad posible. Si estáis interesados os recomiendo que clonéis el repositorio alojado en GitHub

git://github.com/migue/parser-combinators.git

Hasta pronto!

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

Introducción a Scala

El siguiente documento es un pequeño resumen (introductorio) sobre el lenguaje de programación Scala y alguno de sus beneficios. No es nada nuevo que no podáis encontrar en los libros de referencia :) pero a lo mejor a alguien le sirve para dar sus primeros pasos en este genial lenguaje de programación. 

Espero que os guste: