Parseando en Scala (2): Metasintaxis y AST

Demás está decir que, antes de pretender parsear un lenguaje determinado, tenemos que conocer su sintaxis. Y si la conocemos, debemos ser capaces de expresarla formalmente con una metasintaxis, como podría ser BNF o EBNF. Vamos a poner unos ejemplos del tipo de cosas que podemos definir, y los ilustramos con ejemplos de PL/SQL, nuestro lenguaje a parsear.

símbolos	:= (asignación)
palabras clave	PROCEDURE
sucesión de elementos	IF (seguido de) condición (seguido de) THEN ...
elementos alternativos	En una asignación, del lado derecho de := puede haber un identificador o un literal
repetición de elementos (0 a n)	En la sección de declaración de variables puede no haber ninguna, una, o varias
repetición de elementos (1 a n)	En la sección EXCEPTION debe haber al menos un catch (con la forma WHEN excepción THEN ...)

Con este metalenguaje podemos definir el lenguaje completo. Por si no queda claro, cuando decimos "elemento" podemos estar hablando de definiciones de cualquier nivel en la entrada de texto, desde un carácter "A" hasta un bloque de código BEGIN / END. Es decir, en alguna parte definimos en qué consiste un bloque de código y le ponemos un nombre. Luego podemos definir que un PROCEDURE contiene, además de parámetros opcionales, declaración de variables, etc., un bloque de código. Y como las definiciones pueden ser recursivas, también podremos definir que dentro de un bloque de código puede haber bloques de código. ¿Se va entendiendo lo de "combinators"?

Como decía en el post anterior, los parser combinators en Scala son un ejemplo de DSL (domain specific language), ya que "se sienten" como un BNF, o digamos que se presta a una traducción directa desde un BNF. Si no contamos previamente con el BNF del lenguaje que queremos parsear, como para hacer esa traducción, podemos directamente expresar el lenguaje con los parser combinators. Eso es lo que hice yo en este caso, con la salvedad de que no necesitaba parsearlo en profundidad, sino que para mis fines bastaba con capturar la estructura lógica. Esto simplificó la tarea: no necesito interpretar el contenido de una sentencia simple, para reconocerla me basta con que haya una sucesión de caracteres comunes terminados en punto y coma. No importa si hay una asignación, una llamada a un procedimiento, un query, etc.; las sentencias simples las muestro en mi diagrama tal como vienen.

Nuestro cuasi-BNF en Scala no es una mera declaración sino que es a la vez el código que parsea. Lo que tenemos que agregarle es qué hacer con las estructuras que va reconociendo. El que pensó en renderizar la salida, que se retire por favor. Dijimos que vamos a separar las responsabilidades como corresponde.

Con ustedes, el AST

El objetivo inmediato de parsear debe ser obtener el abstract syntax tree, es decir, una representación de la estructura parseada. Una vez que conseguimos esto, nos olvidamos del texto de entrada y las reglas del lenguaje. Piensen en los compiladores de .NET: la plataforma soporta varios lenguajes, y para cada uno hace falta un parseador diferente. Sin embargo todos conducen a lo mismo, el MSIL, una representación del programa que no mantiene dependencia con el lenguaje de origen. Es un AST. Luego desde el AST generamos la salida deseada. Si nos da el cuero podemos generar byte code ejecutable.

El AST consistirá en un grafo de objetos de un modelo que debemos definir, según la estructura que necesitamos capturar. Ese modelo se define como una serie de clases "nodo". A medida que el cuasi-BNF parsea y detecta estructuras en el texto, indicaremos también qué nodos instanciar en cada caso.

Se está poniendo bueno, sigue en la próxima.