miércoles, 25 de febrero de 2009

Parseando en Scala (4): Combinator Parsing en acción

Leemos en el scaladoc del trait Parsers:
(...) El término "parser combinator" se refiere al hecho de que estos parsers son construidos a partir de parsers primitivos y operadores de composición, como secuenciación, alternación, opcionalidad, repetición, etc. Un parser primitivo es un parser que acepta o rechaza una porción de la entrada, en base a cierto criterio. (...)
En la segunda parte de esta serie mencionábamos estas posibilidades de "composición" al definir la sintaxis: que algo se pueda repetir, que algo sea opcional, etc. EBNF utiliza determinados símbolos para esos operadores de composición. Este es un ejemplo de Wikipedia donde se define la sintaxis para escribir un número en un lenguaje hipotético.


number = [ "-" ] , digit , { digit } ;


Esta definición se lee así:
  • Opcionalmente se comienza con un guión (signo menos). Los corchetes indican opcionalidad.
  • Se sigue con un dígito. La coma indica sucesión de elementos.
  • Se sigue con 0 a n dígitos. Las llaves indican repetición arbitraria.
Esto asume que en alguna otra parte se definió lo que es un "digit" de la misma manera que aquí se define lo que es un "number".

En Scala se traduciría más o menos a algo así:

def number: Parser[Number] = opt("-") ~ digit ~ rep(digit) // luego completamos lo que falta

Este sencillo ejemplo ilustra cómo se traduce en forma bastante directa desde la notación EBNF.
  • Opcionalidad: método opt()
  • Sucesión: símbolo ~ (que en realidad es un método)
  • Repetición arbitraria: método rep()
Con una vuelta de tuerca más: el método rep1() es similar a rep() pero requiriendo que exista como mínimo una ocurrencia (1 a n). La misma definición se puede simplificar a:

def number: Parser[Number] = opt("-") ~ rep1(digit) // ...

El tipo de retorno es Parser[X] donde X es una clase del modelo. En este caso supongamos que se definió la clase Number como parte del modelo.

También vamos a usar el símbolo | para indicar alternativas. Si contempláramos también el signo + para escribir un número positivo, haríamos así:

def number: Parser[Number] = opt("-" | "+") ~ rep1(digit) // ...

Como se puede ver, combinamos los operadores según nuestra necesidad: opcionalmente habrá un signo, y el signo puede ser - o +.

Estamos listos para parsear PL/SQL. Como primer ejemplo veamos la definición del LOOP:

def loop: Parser[Loop] = "loop" ~ rep1(code) ~ ("end" ~ "loop" ~ ";") // ...

Desde luego, esto requiere la definición de code retornando un Parser[Code], y así con todas las dependencias.
Todo lo que sea whitespace no es necesario especificarlo: entre elementos puede haber cualquier cantidad de espacios, tabs o line feeds. Observar que como fin del loop usamos ("end" ~ "loop" ~ ";"), porque si usáramos "end loop;" estaríamos reconociéndolo solamente si se escribe exactamente así.

Sigamos con este ejemplo. Esta definición, así como está, no retorna un Parser[Loop]: vamos a completarla. Tenemos que agregar una función (una closure para mayor comodidad) que levante esos elementos parseados y genere un objeto del modelo, en este caso Loop. Pero antes, tenemos que usar variantes del operador ~. Las variantes ~> y <~ son equivalentes a ~ en tanto que indican secuencia de elementos, la diferencia está en que "señalan" el elemento que nos interesa recuperar a fines de construir un nodo del AST, lo que implica que la parte no señalada será ignorada. Para armar el nodo Loop, lo único que necesito de esa definición es la colección de objetos Code. Entonces "señalemos" lo que realmente importa:


def loop: Parser[Loop] = "loop" ~> rep1(code) <~ ("end" ~ "loop" ~ ";") // esto arroja un List[Code]

Ahora sí: rep1(code) produce un List[Code], y eso es lo que la closure tomará como entrada. La closure en cuestión es sencillísima:

{ c:List[Code] => Loop("loop", c) }

(Uso el string "loop" para indicar que no es un FOR ni un WHILE, este es un detalle de mi implementación que no tiene mucha importancia).
Terminamos juntando la definición de la sintaxis y la closure de generación del nodo con el simpático operador ^^.

def loop: Parser[Loop] = "loop" ~> rep1(code) <~ ("end" ~ "loop" ~ ";") ^^ { c => Loop("loop", c) }

Voilà! Y simplificamos la closure dejando que el compilador infiera el tipo del argumento. Todo esto es type-safe, el compilador chilla si nos equivocamos con los tipos.
Insisto, nada de esto es magia, estamos usando una librería estándar. Estos operadores raros son métodos de la clase Parser. Y si bien a primera vista el código parece un jeroglífico, es sólo cuestión de aprender el API como un "sublenguaje": todo cobra sentido, y de hecho parsear termina siendo una pavada. Cada elemento se define con una parte declarativa (equivalente a un EBNF), el operador ^^, y una closure que toma lo necesario de esa declaración para crear un nodo del AST.

Para parsear los FOR y WHILE utilizo una definición unificada porque son muy similares, y también genero un nodo Loop:

def forWhileLoop: Parser[Loop] = ("while" | "for") ~ (regularStr <~ "loop") ~ (rep1(code) <~ ("end" ~ "loop" ~ ";")) ^^ { (t:String, h:String, c:List[Code]) => Loop(t + " " + h, c) }

Esta declaración produce tres cosas relevantes, tomadas como parámetro por la closure: un String que será "while" o "for", un String con la condición o secuencia del FOR, y la correspondiente List[Code].

En la próxima entrega muestro el contexto donde se define todo esto y vamos cerrando lo que es parseo, para más adelante empezar a explotar el AST.

No hay comentarios:

Publicar un comentario