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 relacionado con el concepto de gramáticas de atributos / gramáticas de afijos . Los DCG suelen estar asociados con Prolog, pero lenguajes similares como Mercury también incluyen DCG. Se llaman gramáticas de cláusulas definidas 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 utilizando cláusulas definidas se consideran DCG. Sin embargo, todas las capacidades o propiedades de los DCG serán las mismas para cualquier gramática que se represente con cláusulas definidas esencialmente 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 determinado á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 prueba de declaraciones, como 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 en Marsella, Francia como en 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 este lenguaje fue un gran sistema de procesamiento de lenguaje natural. Fernando Pereira y David Warren de la Universidad de Edimburgo también participaron en el desarrollo inicial de Prolog.
Colmerauer había trabajado anteriormente 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 Marseille Prolog. 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 de los primeros arquitectos de Prolog, acuñaron el término "gramática de cláusulas definidas" y crearon la notación para DCG que se utiliza en Prolog hoy. Le dieron crédito por la idea a Colmerauer y Kowalski, y señalan que los 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 los 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". Prólogo". [4]
Pereira, Warren y otros pioneros de Prolog escribieron más tarde sobre otros aspectos de los DCG. Pereira y Warren escribieron un artículo llamado "Análisis como deducción", que describe cosas como cómo se utiliza el procedimiento de prueba de deducción Earley para el análisis. [5] Pereira también colaboró con Stuart M. Shieber en un libro llamado "Prolog and Natural Language Analysis", que pretendía ser una introducción general a la lingüística computacional utilizando 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 frases 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 idioma 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 idioma escribiendo algo como sentence([the,bat,eats,the,bat],[]).
La notación DCG es simplemente azúcar sintáctico para cláusulas definidas normales en Prolog. Por ejemplo, el ejemplo anterior podría traducirse a lo siguiente:
oración ( A , Z ) : - frase_sustantiva ( A , B ), frase_verbo ( B , Z ). frase_nombre ( A , Z ) : - det ( A , B ), sustantivo ( B , Z ). frase_verbo ( A , Z ) : - verbo ( A , B ), frase_sustantiva ( B , Z ). det ([ el | X ], X ). det ([ a | X ], X ). sustantivo ([ gato | X ], X ). sustantivo ([ murciélago | X ], X ). verbo ([ come | X ], X ).Los argumentos de cada functor, 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 más grande, incluido el más pequeño). Usando la notación de Prolog para listas, un prefijo de lista singleton P = [H]puede verse como la diferencia entre [H|X]y y X, por lo tanto, representarse con el par ([H|X],X), por ejemplo.
Decir que Pes la 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 diferencias de listas (prefijos), en las circunstancias en que se pueden usar, porque la concatenación de (A,B)y (B,Z)es solo (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 sobre los functores, como en el ejemplo anterior, solo pueden expresar gramáticas libres de contexto ; sólo 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 ( norte ), b ( norte ), c ( norte ). un ( 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 necesaria ]
También se pueden representar varias características lingüísticas de manera bastante concisa con DCG proporcionando argumentos adicionales a los functores. [9] Por ejemplo, considere el siguiente conjunto de reglas DCG:
oración --> pronombre ( sujeto ), frase_verbo . frase_verbo --> verbo , pronombre ( objeto ). pronombre ( sujeto ) --> [ él ]. pronombre ( sujeto ) --> [ ella ]. pronombre ( objeto ) --> [ él ]. pronombre ( objeto ) --> [ ella ]. verbo --> [ me gusta ].Esta gramática permite oraciones como "a él le gusta" y "a él le gusta", pero no "a ella le gusta él" y "a él le gusta".
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 functores 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 que obtenga un árbol de análisis de cualquier oración determinada:
| ?- oración ( Parse_tree , [ el , murciélago , come , un , gato ], []). Parse_tree = s ( np ( d ( el ), n ( murciélago )), vp ( v ( come ), np ( d ( a ), 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 del análisis de aplicaciones. En el lenguaje de programación declarativamente puro, Mercury I/O debe representarse mediante un par de io.stateargumentos. La notación DCG se puede utilizar para hacer más conveniente el uso de E/S, [10] aunque generalmente se prefiere la notación de variables de estado. [11]
La notación DCG también se usa para analizar y cosas similares en Mercury como en Prolog.
Desde que Pereira y Warren introdujeron los DCG, 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 hacer más fácil la expresión de ciertos fenómenos gramaticales, como la extraposición a 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]
Investigadores de NEC Corporation realizaron otra extensión, más reciente, llamada Gramáticas de cláusulas definidas multimodales (MM-DCG) en 1995. Sus extensiones estaban destinadas a 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áticas de traducción de cláusulas definidas (DCTG), 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 ideado para manejar atributos gramaticales de manera conveniente. [17] La traducción de los DCTG a cláusulas Prolog normales es como la de los DCG, pero se añaden 3 argumentos en lugar de 2.
