Una gramática de cláusula definida ( DCG ) es una forma de expresar la gramática, ya sea para lenguajes naturales o formales , en un lenguaje de programación lógica como Prolog . Está estrechamente relacionada con el concepto de gramáticas de atributos / gramáticas de afijos . Las DCG suelen asociarse con Prolog, pero lenguajes similares como Mercury también incluyen DCG. Se denominan gramáticas de cláusula definida porque representan una gramática como un conjunto de cláusulas definidas en lógica de primer orden .
El término DCG se refiere al tipo específico de expresión en Prolog y otros lenguajes similares; no todas las formas de expresar gramáticas mediante cláusulas definidas se consideran DCG. Sin embargo, todas las capacidades o propiedades de las DCG serán las mismas para cualquier gramática que se represente con cláusulas definidas de la misma manera que en Prolog.
Las cláusulas definidas de un DCG pueden considerarse un conjunto de axiomas donde la validez de una oración y el hecho de que tenga un cierto árbol de análisis pueden considerarse teoremas que se derivan de estos axiomas. [1] Esto tiene la ventaja de hacer que el reconocimiento y análisis de expresiones en un lenguaje se convierta en una cuestión general de probar declaraciones, como las declaraciones en un lenguaje de programación lógica.
La historia de los DCG está estrechamente ligada a la historia de Prolog, y la historia de Prolog gira en torno a varios investigadores tanto de Marsella, Francia, como de Edimburgo, Escocia. Según Robert Kowalski , uno de los primeros desarrolladores de Prolog, el primer sistema Prolog fue desarrollado en 1972 por Alain Colmerauer y Phillipe Roussel. [2] El primer programa escrito en el lenguaje fue un gran sistema de procesamiento de lenguaje natural. Fernando Pereira y David Warren de la Universidad de Edimburgo también estuvieron involucrados en el desarrollo inicial de Prolog.
Colmerauer había trabajado previamente en un sistema de procesamiento del lenguaje llamado Q-systems que se utilizaba para traducir entre inglés y francés. [3] En 1978, Colmerauer escribió un artículo sobre una forma de representar gramáticas llamadas gramáticas de metamorfosis que formaban parte de la primera versión de Prolog llamada Prolog de Marsella. En este artículo, dio una descripción formal de las gramáticas de metamorfosis y algunos ejemplos de programas que las utilizan.
Fernando Pereira y David Warren, otros dos arquitectos tempranos de Prolog, acuñaron el término "gramática de cláusulas definidas" y crearon la notación para las DCG que se utiliza en Prolog hoy en día. Ellos dieron crédito por la idea a Colmerauer y Kowalski, y señalan que las DCG son un caso especial de las gramáticas de metamorfosis de Colmerauer. Introdujeron la idea en un artículo llamado "Gramáticas de cláusulas definidas para el análisis del lenguaje", donde describen las DCG como un "formalismo... en el que las gramáticas son cláusulas expresadas de lógica de predicados de primer orden" que "constituyen programas efectivos del lenguaje de programación Prolog". [4]
Pereira, Warren y otros pioneros de Prolog escribieron posteriormente sobre otros aspectos de los DCG. Pereira y Warren escribieron un artículo titulado "El análisis sintáctico como deducción", en el que describían aspectos como el uso del procedimiento de prueba de deducción de Earley para el análisis sintáctico. [5] Pereira también colaboró con Stuart M. Shieber en un libro titulado "Prolog and Natural Language Analysis", que pretendía ser una introducción general a la lingüística computacional mediante programación lógica. [6]
Un ejemplo básico de DCG ayuda a ilustrar qué son y cómo se ven.
oración --> frase_sustantiva , frase_verbo . frase_sustantiva --> det , sustantivo . frase_verbo --> verbo , frase_sustantiva . det --> [ el ]. det --> [ a ]. sustantivo --> [ gato ]. sustantivo --> [ murciélago ]. verbo --> [ come ].Esto genera oraciones como "el gato se come al murciélago", "un murciélago se come al gato". Se pueden generar todas las expresiones válidas en el lenguaje generado por esta gramática en un intérprete de Prolog escribiendo sentence(X,[]). De manera similar, se puede comprobar si una oración es válida en el lenguaje escribiendo algo como sentence([the,bat,eats,the,bat],[]).
La notación DCG es simplemente una sintaxis simplificada para las cláusulas definidas normales en Prolog. Por ejemplo, el ejemplo anterior podría traducirse de la siguiente manera:
oración ( A , Z ) :- sintagma nominal ( A , B ), sintagma verbal ( B , Z ). sintagma nominal ( A , Z ) :- det ( A , B ), sustantivo ( B , Z ). sintagma verbal ( A , Z ) :- verbo ( A , B ), sintagma nominal ( B , Z ). det ([ el | X ], X ). det ([ un | X ], X ). sustantivo ( [ gato | X ] , X ). sustantivo ([ murciélago | X ], X ). verbo ([ come | X ], X ). Los argumentos de cada funtor, como (A,B)y , (B,Z)son listas de diferencias ; las listas de diferencias son una forma de representar un prefijo de una lista como la diferencia entre sus dos sufijos (el mayor incluye al menor). Si se utiliza la notación de Prolog para listas, un prefijo de lista singleton P = [H]puede verse como la diferencia entre [H|X]y X, y por lo tanto representarse con el par ([H|X],X), por ejemplo.
Decir que Pla diferencia entre Ay Bes lo mismo que decir que append(P,B,A)se cumple. O en el caso del ejemplo anterior, append([H],X,[H|X]).
Las listas de diferencias se utilizan para representar listas con DCG por razones de eficiencia. Es mucho más eficiente concatenar las diferencias de listas (prefijos), en las circunstancias en que se pueden utilizar, porque la concatenación de (A,B)y (B,Z)es simplemente (A,Z). [7]
De hecho, append(P,B,A), append(Q,Z,B)implica append(P,Q,S), append(S,Z,A). Esto es lo mismo que decir que la concatenación de listas es asociativa :
A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A
En Prolog puro , las reglas DCG normales sin argumentos adicionales en los funtores, como el ejemplo anterior, solo pueden expresar gramáticas independientes del contexto ; solo hay un argumento en el lado izquierdo de la producción . Sin embargo, las gramáticas sensibles al contexto también se pueden expresar con DCG, proporcionando argumentos adicionales, como en el siguiente ejemplo:
s --> a ( N ), b ( N ), c ( N ). a ( 0 ) --> []. a ( M ) --> [ a ], a ( N ), { M es N + 1 }. b ( 0 ) --> []. b ( M ) --> [ b ], b ( N ), { M es N + 1 }. c ( 0 ) --> []. c ( M ) --> [ c ], c ( N ), { M es N + 1 }.Este conjunto de reglas DCG describe la gramática que genera el lenguaje que consta de cadenas de la forma . [8]
s --> símbolos ( Sem , a ), símbolos ( Sem , b ), símbolos ( Sem , c ). símbolos ( fin , _ ) --> []. símbolos ( s ( Sem ), S ) --> [ S ], símbolos ( Sem , S ).Este conjunto de reglas DCG describe la gramática que genera el lenguaje que consta de cadenas de la forma , al representar estructuralmente n [ cita requerida ]
Varias características lingüísticas también se pueden representar de manera bastante concisa con DCG proporcionando argumentos adicionales a los funtores. [9] Por ejemplo, considere el siguiente conjunto de reglas DCG:
oración --> pronombre ( sujeto ), frase_verbal . frase_verbal --> verbo , pronombre ( objeto ). pronombre ( sujeto ) --> [ él ]. pronombre ( sujeto ) --> [ ella ]. pronombre ( objeto ) --> [ él ]. pronombre ( objeto ) --> [ ella ]. verbo --> [ le gusta ]. Esta gramática permite oraciones como "a él le gusta ella" y "a él le gusta él", pero no "a ella le gusta él" y "a él le gusta él".
El principal uso práctico de un DCG es analizar oraciones de la gramática dada, es decir, construir un árbol de análisis. Esto se puede hacer proporcionando "argumentos adicionales" a los funtores en el DCG, como en las siguientes reglas:
oración ( s ( NP , VP )) --> frase_sustantiva ( NP ), frase_verbo ( VP ). frase_nombre ( np ( D , N )) --> det ( D ), sustantivo ( N ). frase_verbo ( vp ( V , NP )) --> verbo ( V ), frase_sustantiva ( NP ). det ( d ( el )) --> [ el ]. det ( d ( a )) --> [ a ]. sustantivo ( n ( murciélago )) --> [ murciélago ]. sustantivo ( n ( gato )) --> [ gato ]. verbo ( v ( come )) --> [ come ].Ahora se puede consultar al intérprete para obtener un árbol de análisis de cualquier oración dada:
| ?- oración ( Parse_tree , [ el , murciélago , come , un , gato ], []). Parse_tree = s ( np ( d ( el ), n ( murciélago )), vp ( v ( come ), np ( d ( un ), n ( gato )))) ? ;Los DCG pueden servir como un azúcar sintáctico conveniente para ocultar ciertos parámetros en el código en otros lugares además de las aplicaciones de análisis. En el lenguaje de programación declarativamente puro Mercury, la E/S debe representarse mediante un par de io.stateargumentos. La notación DCG se puede utilizar para que el uso de la E/S sea más conveniente, [10] aunque normalmente se prefiere la notación de variable de estado. [11]
La notación DCG también se utiliza para el análisis y cosas similares en Mercury como en Prolog.
Desde que Pereira y Warren introdujeron las gramáticas de extraposición, se han propuesto varias extensiones. El propio Pereira propuso una extensión llamada gramáticas de extraposición (XG). [12] Este formalismo tenía como objetivo, en parte, facilitar la expresión de ciertos fenómenos gramaticales, como la extraposición por la izquierda. Pereira afirma: "La diferencia entre las reglas XG y las reglas DCG es que el lado izquierdo de una regla XG puede contener varios símbolos". Esto facilita la expresión de reglas para gramáticas sensibles al contexto.
Peter Van Roy amplió los DCG para permitir múltiples acumuladores. [13] [14]
Otra extensión más reciente fue realizada por investigadores de NEC Corporation llamada Gramáticas de Cláusulas Definidas Multimodales (MM-DCGs) en 1995. Sus extensiones tenían como objetivo permitir el reconocimiento y análisis de expresiones que incluyen partes no textuales, como imágenes. [15]
Harvey Abramson describió otra extensión, llamada gramática de traducción de cláusulas definidas (DCTG, por sus siglas en inglés) en 1984. [16] La notación DCTG es muy similar a la notación DCG; la principal diferencia es que se utiliza ::=en lugar de -->en las reglas. Fue ideada para manejar atributos gramaticales de manera conveniente. [17] La traducción de DCTG en cláusulas Prolog normales es como la de DCG, pero se agregan 3 argumentos en lugar de 2.
