Prolog DCG: gramáticas de clausula definida

Hoy, 14 de enero, es el WORLD LOGIC DAY. Para celebrarlo, una entrada que tenía ya escrita sobre nuestro lenguaje de programación lógico preferido: Prolog.

Una de las caracterśiticas más potentes de Prolog es su potencia para la manipulación simbólica. Uno de los primeros usos que se le dio fue la definición de gramáticas a través de cláusulas. Estas definiciones constan de una sintaxis especial, aunque no es más que azúcar sintáctico sobre el lenguaje basado en predicados y términos de siempre. Aquí veremos la potencia de estas gramáticas dentro de Prolog y los usos que se les puede llegar a dar, desde simplemente validar "listas" a construir compiladores de lenguajes de programación.

Pero vamos a ir poco a poco desgranando todo esto.

Gramáticas

En esencia un DCG es simple: es un conjunto de reglas que describen un tipo concreto de lista. Estas "reglas" en ciencias de la computación tienen un nombre especial: gramáticas. Las gramáticas nos permiten generar lenguajes, entendiendo lenguajes como cualquier conjunto de símbolos, uno detrás de otro (o sea, el español, Python o una imagen digital). Las gramáticas se dividen en varias categorías, según los lenguajes que son capaces de generar. Esta diferenciación viene de Noam Chomsky, que a parte de filósofo y activista, se le considera el padre de las gramáticas.

Las gramáticas regulares son las que generan lenguajes regulares. Los lenguajes regulares son aquellos que podemos analizar mediante expresiones regulares. Las expresiones regulares o Regex no dejan de ser una manera de definir gramáticas regulares. Los DCG de Prolog nos permiten llegar a las gramáticas dependientes de contexto, el último paso antes de llegar a las recursivamente enumerables que son prácticamente intratables. Sin embargo, para no complicarlo mucho, vamos a hacer los ejemplos de este post con gramáticas independientes de contexto. Otros programas capaces de llegar a este punto son el famoso programa de Unix Yacc (en GNU es Bison) y el famoso ANTLR. Además, prácticamente todos los lenguajes de programación están definidos por gramáticas independientes de contexto.

Una gramática muy simple sería por ejemplo, podría definir un lenguaje que es una cadena de x. Mientras el "código" sea una sucesión de x, es parte del lenguaje, pero cualquier otra cosa es un error. Conceptualmente lo podríamos definir así, siendo S una variable y x un término:

S -> .
S -> xS

Donde . significa "nada" o "cadena vacía". La gramática se define de forma recursiva. Dado una cadena de entrada S, se puede descomponer según la primera regla en cadena vacía o en un caracter x más S otra vez. Pongamos un ejemplo:

xx forma parte del lenguaje porque S = xx, podemos descomponerlo según la segunda regla en x(S=x). Hemos aceptado de este modo el primer caracter y nos sigue quedando una parte por analizar. Como ha aparecido una S nueva, volvemos a aplicar la segunda regla y obtenemos xx(S=). No hemos acabado, nos sigue quedando una S, pero al aplicar la primera regla ya nos quedamos sin variables y la gramática ha aceptado la cadena. Por tanto xx forma parte del lenguaje.

Esto se puede complicar mucho, he aquí una gramática algo más compleja:

Frase -> SujetoVerbo
Sujeto -> DeterminanteNombre
Determinante -> el
Nombre -> gato
Nombre -> perro
Verbo -> ladra
Verbo -> maulla

No es difícil comprobar que frases como "elgatoladra" o "elperromaulla" son válidas, pero "lavacaladra" no.

Vuelta a Prolog

Volvamos a Prolog con nuestro lenguaje X. La gramática la podemos expresar con las DCG de esta forma:

program --> [].
program --> [x], program.

Podemos usar el predicado phrase para comprobar si una cadena pertenece al lenguaje X:

Así xxxx forma parte del lenguaje y xxyx no forma parte. Prolog tiene la característica, de que si sobre algo no puede esclarecer si es cierto o falso, buscará la forma de satisfacer las condiciones. Podemos usar esto para ir generando todos los lenguajes posibles.

Parseando programas

Podemos usar las capacidades de Prolog para añadir variables que nos permitan realizar un parseo y obtener así una estructura de árbol del documento.

Para este ejemplo, primero vamos a definir un lenguaje de calculadora, que permita de momento solamente sumar.

program --> expr, oper, expr.
expr --> ['('], expr, oper, expr, [')'].
expr --> [N], {number(N)}.
oper --> [+].

La sintaxis con llaves nos permite llamar a predicados auxiliares para construir una variable. Esta gramática admite expresiones de este tipo: 45 + ((70+45)+56).

Ahora para parsear, añadimos variables a las DCG para ir guardando un árbol AST.

program(node(O, E1, E2)) --> expr(E1), oper(O), expr(E2).
expr(node(O, E1, E2)) --> ['('], expr(E1), oper(O), expr(E2), [')'].
expr(node(number, N)) --> [N], {number(N)}.
oper(+) --> [+].

Y vemos el resultado de parsear diferentes expresiones

Y ahora realizar un compilador/intérprete para este lenguaje es trivial.

program(node(O, E1, E2)) --> expr(E1), oper(O), expr(E2).
expr(node(O, E1, E2)) --> ['('], expr(E1), oper(O), expr(E2), [')'].
expr(node(number, N)) --> [N], {number(N)}.
oper(+) --> [+].

execute(node(number, Out), Out).
execute(node(+, E1, E2), Out) :-
    execute(E1, OutE1),
    execute(E2, OutE2),
    Out is OutE1 + OutE2.

execute(Program) :-
    phrase(program(Tree), Program),
    execute(Tree, Out),
    format(Out).

¡Y funciona correctamente!

Añadir el resto de operaciones (resta, multiplicación, división) queda en manos del lector. Por supuesto, para ejecutar los programas todavía tenemos que pasar una cadena de elementos, que en terminología de lenguajes se llaman tokens, pero eso se podría hacer con otra gramática DCG o de otra forma dependiendo del lenguaje (en el mundo Unix clásico se suele hacer con Lex, cuya versión en Linux suele ser Flex).

Como conclusión, hemos visto que la manipulación de símbolos de Prolog es potente y nos permite describir de forma corta y elegante, así como realizar un parseado de forma sencilla también.