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!