<$BlogRSDUrl$>

Pro·Log·[IR]

Programación Lógica y Recuperación de Información

«Algorithm = Logic + Control» Robert Kowalski (1979)

¡Importante! esta página hace uso de estilos recogidos en la especificación CSS2, no soportados por el navegador que está utilizando. Por favor, lea esta recomendación al respecto.

Archivo

Guardado por meses.

Enlaces

Los siguientes listados son una referencia a partir de la cual ampliar la búsqueda de sitios relacionados (i).

Bitácoras en castellano

Bitácoras en inglés

Directorios, metablogs

Programación lógica, Inteligencia Artificial, Recuperación de Información

Usabilidad, Arquitectura de la Información

Listas, foros, wikis

Matemáticas, ciencias

Miscelánea

Búsquedas

Búsqueda simple en varios de los motores más conocidos. Para mayor precisión, entrar en la página correspondiente e ir al apartado de búsqueda avanzada.

Búsqueda con Google
 

Búsqueda con Yahoo!
 

Búsqueda con AlltheWeb

Varios

Esta página traducida:

Traducción al catalán, internostrum; traducción al portugués, universia.

Reciba un aviso de nuevos comentarios (por Bloglet).


Agregue este sitio a su lector de "feeds" (sindicación mediante el sistema Atom).

Sobre este sitio

Espacio dedicado a la programación lógica y la recuperación de información, con una atención especial al lenguaje Prolog y otros lenguajes afines, pertenecientes al paradigma lógico y declarativo. También se tratará de hablar de estos temas desde la perspectiva de la Biblioteconomía y la Documentación.

En esta página

6.3.06

DCG: notación de reglas gramaticales en Prolog

La notación de reglas gramaticales DCG (Definite Clause Grammar, en castellano gramática de cláusulas definidas) es una variante o extensión sintáctica de la sintaxis ordinaria del lenguaje Prolog, cuyo objeto es implementar gramáticas formales de forma abreviada, y en consecuencia simplificar y hacer más legibles los analizadores sintácticos escritos en este lenguaje, ya que permite manejar información (entiéndase por ésta "variables") implícita. Su expresión es una notación abreviada de la sintaxis del lenguaje Prolog, recogida por la práctica totalidad de los parsers e intérpretes actuales para este lenguaje, que la transforman automáticamente y de forma interna en cláusulas normales. En la notación DCG el operador infijo ":-" es sustituido por el operador del mismo carácter "-->", y se puede establecer, a modo de ejemplo, la siguiente correspondencia entre notaciones, siendo la primera la cláusula Prolog en sintaxis ordinaria, y la segunda la notación DCG equivalente:

oracion(S0,S) :- sintagma_nominal(S0,S1), sintagma_verbal(S1,S).
oracion --> sintagma_nominal, sintagma_verbal.

La anterior cláusula Prolog se expresa en palabras como sigue:

"Existe una oración entre S0 y S si existe un sintagma nominal entre S0 y S1, y existe un sintagma verbal entre S1 y S"

La notación DCG se basa en la utilizada para las gramáticas libres de contexto (context-free grammars o CFGs, N. Chomsky), estructura jerárquica que indica las relaciones de las construcciones del lenguaje, descritas mediante notación BNF (Backus Normal Form ó Backus-Naur form), creada originalmente para definir la estructura sintáctica del lenguaje ALGOL60 (1960, John Backus), y muy utilizada tanto para definir la estructura sintáctica de los lenguajes de programación, como para definir estructuras sintácticas de los lenguajes en general. Por tanto, mediante notación DCG, es posible manejar directamente en lenguaje Prolog gramáticas libres de contexto. Las gramáticas libres de contexto vienen a ser una simplificación de la gramática ordinaria, que, por ejemplo, y referida al idioma castellano, podría adoptar la siguiente expresión en notación DCG:

oracion --> sintagma_nominal, sintagma_verbal.

sintagma_nominal --> determinante, nombre.

sintagma_verbal --> verbo, sintagma_nominal.
sintagma_verbal --> verbo.

determinante --> [el].
determinante --> [la].

nombre --> [hombre].
nombre --> [manzana].

verbo --> [come].
verbo --> [canta].

Que el sistema Prolog (en este caso SWI-Prolog) traduce automáticamente al siguiente conjunto de cláusulas:

oracion(A,B):- sintagma_nominal(A,C),
               sintagma_verbal(C,B).

sintagma_nominal(A,B):- determinante(A,C),
                        nombre(C,B).

sintagma_verbal(A,B):- verbo(A,C),
                       sintagma_nominal(C,B).
sintagma_verbal(A,B):- verbo(A,B).

determinante([el|A],A).
determinante([la|A],A).

nombre([hombre|A],A).
nombre([manzana|A],A).

verbo([come|A],A).
verbo([canta|A],A).

Como es fácilmente deducible, el programa basado en esta pequeña y muy limitada gramática, solo aceptará como oraciones gramaticalmente correctas "el hombre come la manzana", "el hombre canta", y combinaciones similares, incluso por ejemplo frases a todas luces gramaticalmente incorrectas como "la manzana canta", "la hombre come", etc., devolviéndonos una lista vacía, pero no aceptará por ejemplo "el hombre baila" (el verbo "baila" no se halla dentro de la base de hechos o conocimiento del programa). Se entiende por tanto que una gramática completa, que abarque todas las posibles estructuras, relaciones y combinaciones de las partes constitutivas de una lengua, requiere un programa muy complejo y difícil de implementar. En el ejemplo expuesto, se pueden obtener todas las oraciones aceptadas como gramaticalmente correctas por la gramática del programa, lanzando en el intérprete el siguiente objetivo:

?- oracion(X,[]).

Por su parte, un ejemplo muy sencillo de gramática para el idioma inglés, escrita mediante notación DCG, adopta la siguiente expresión:

sentence --> noun_phrase, verb_phrase.

noun_phrase --> noun.
noun_phrase --> determiner, noun, rel_clause.

verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.

rel_clause --> [].
rel_clause --> [that], verb_phrase.

determiner --> [the].
determiner --> [a].

noun --> [john].
noun --> [annie].
noun --> [man].
noun --> [men].
noun --> [woman].
noun --> [women].
...

verb --> [like].
verb --> [likes].
...

En la notación DCG se suprimen dos parámetros, una lista de entrada, y una lista de salida. La primera puede estar representada, por ejemplo, por la oración [el,perro,muerde] y la segunda por una lista vacía [] que es el resultado de comprobar la estructura sintáctica de dicha oración en función del parser utilizado. Adicionalmente, es posible agregar variables a las gramáticas representadas mediante notación DCG, por ejemplo para especificar el género y el número.

Como se ha dicho anteriormente, la notación DCG permite añadir argumentos adicionales, y también incorporar objetivos Prolog en el cuerpo de las reglas, estos últimos encerrados entre llaves {}. Los argumentos adicionales nos permitirían por ejemplo introducir las reglas gramaticales correctas en función de las convenciones adoptadas por la lengua objeto de representación, y así evitar incorrecciones en la concordancia género / número, etc. También, mediante notación DCG también es posible construir programas capaces de representar árboles de análisis de una oración (que representan las categorías gramaticales implicadas en la descomposición de sus partes), y árboles sintácticos (parse trees) que de una forma gráfica muestran la estructura en forma de árbol descendente de determinada construcción gramatical. Como explicamos en la anterior anotación, los analizadores sintácticos o parsers se encargan de la construcción de árboles de análisis de las oraciones de una lengua, capaces de representar la estructura sintagmática de las mismas. Siguiendo con el ejemplo de la sencilla gramática en castellano, expuesto más arriba, la representación gráfica del árbol de análisis de la oración "el hombre come la manzana" presenta el siguiente aspecto, haciendo uso para ello de este programa:

?- draw(o(sn(d(el),n(hombre)),sv(v(come),sn(d(la),n(manzana))))).

                       o
                       |
        +--------------------+
        sn                   sv
        |                    |
   +-------+        +------------+
   d       n        v            sn
   |       |        |            |
   |       |        |      +--------+
   |       |        |      d        n
   |       |        |      |        |
   |       |        |      |        |
   el    hombre    come    la    manzana

Donde "o" = oración, "sn" = Sintagma Nominal, "d" = Determinante, "n" = Nombre, "sv" = Sintagma Verbal, y "v" = Verbo. Hay que advertir que este programa no realiza el árbol de análisis propiamente dicho, que es:

o(sn(d(el),n(hombre)),sv(v(come),sn(d(la),n(manzana))))

Simplemente lleva a cabo su representación gráfica en forma de diagrama de caracteres ASCII. El código fuente del programa en cuestión, que originalmente se llama draw.swi, ha sido copiado a un editor de texto plano, y salvado con la extensión ".pl" para poder ser ejecutado por el intérprete SWI-Prolog, aunque otra opción es asociar los archivos con extensión ".swi" con el ejecutable de dicho intérprete. Su autor es Bertram Ludäscher, de la "University of California Davis".

Los ejemplos de notación DCG y Prolog en castellano se han tomado del capítulo 9, "Uso de reglas gramaticales en Prolog", apartado 9.1, "El problema del análisis sintáctico", de la obra de W.F. Clocksin y C.S. Mellish "Programación en Prolog" (2ª ed.; Barcelona: Gustavo Gili, 1993; ISBN: 84-252-1339-8), traducción del original en inglés "Programming in Prolog", a la que me remito para obtener una explicación detallada sobre reglas gramaticales, análisis sintáctico, y notación DCG en Prolog, habida cuenta de que los autores reseñados hacen una exposición clara y perfectamente comprensible sobre el particular, perfectamente asequible para las personas no excesivamente versadas en este lenguaje.

Por su parte el ejemplo de gramática en inglés se ha obtenido del capítulo 17, "Languague Processing with Grammar Rules", de la obra "Prolog - Programming for Artificial Intelligence" (Ivan Bratko, 2ª ed.; Addison-Wesley, 1990; ISBN: 0-201-41606-9). Se trata de un libro muy recomendable, de nivel más avanzado y completo que el de Clocksin y Mellish, claramente más introductorio, y como su propio nombre indica cubre por un lado las generalidades del lenguaje Prolog, y por otro lado su aplicación a las principales técnicas del campo de la IA (búsqueda y clasificación, sistemas expertos y representación del conocimiento, PLN, Machine Learning, etc.).

Por último, mencionar otro ejemplo de utilización práctica de la notación DCG y el lenguaje de programación lógica Prolog, la librería Html-write [1] [2] [3] del intérprete y entorno de desarrollo SWI-Prolog, que traslada términos Prolog en HTML, generando salidas en este último lenguaje, para lo cual hace uso precisamente de estructuras escritas en notación DCG.

Más información (PLN y DCGs en Prolog):

Específicamente sobre DCG:

CFGs y BNF:

Forman parte del mismo conjunto de lecturas de clase:

[7] comentarios | # | lista |


Pro·Log·[IR],

Publicación: Blogger | Estadísticas: eXTReMe Tracking

Se recomienda ver este sitio con Mozilla 1+, Firefox 0.8+ ó Netscape 7+. Si no queda más remedio, con IE 6+. Si lo desea, comunique cualquier problema al respecto. También será bien recibida cualquier sugerencia sobre el contenido. La fuente de letra preferente es Georgia. Se prohibe la utilización del diseño de la página salvo autorización expresa del autor. Los contenidos escritos son de uso libre, siempre que se cite la fuente.