Una gramática de cláusula definida ( DCG ) es una forma de expresar 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 a partir del cual se desarrolló originalmente Prolog. 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 que utilizan 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 cierto árbol de análisis sintáctico pueden considerarse teoremas que se derivan de estos axiomas. [1] Esto tiene la ventaja de hacer que el reconocimiento y el análisis sintáctico de expresiones en un lenguaje se convierta en una cuestión general de probar declaraciones, como declaraciones en un lenguaje de programación lógica.
Historia
La historia de los DCG está estrechamente relacionada con la historia de Prolog, y la historia de Prolog gira en torno a varios investigadores de Marsella, Francia y 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 idioma fue un gran sistema de procesamiento del 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 de idiomas llamado Q-systems que se usaba 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 arquitectos tempranos de Prolog, acuñaron el término "gramática de cláusula definida" y crearon la notación para DCG que se usa 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 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". Prólogo". [4]
Pereira, Warren y otros pioneros de Prolog escribieron más tarde sobre varios otros aspectos de los DCG. Pereira y Warren escribieron un artículo llamado "Análisis como deducción", describiendo cosas tales como cómo se usa el procedimiento de prueba de Deducción de Earley para el análisis. [5] Pereira también colaboró con Stuart M. Shieber en un libro llamado "Prólogo y análisis del lenguaje natural", que pretendía ser una introducción general a la lingüística computacional utilizando la programación lógica. [6]
Ejemplo
Un ejemplo básico de DCG ayuda a ilustrar qué son y cómo se ven.
oración -> sustantivo_frase , verbo_frase . sustantivo_frase -> det , sustantivo . verbo_frase -> verbo , sustantivo_frase . 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 lenguaje generado por esta gramática en un intérprete de Prolog escribiendo sentence(X,[])
. De manera similar, se puede probar si una oración es válida en el idioma escribiendo algo como sentence([the,bat,eats,the,bat],[])
.
Traducción a cláusulas definidas
La notación DCG es simplemente azúcar sintáctica para las cláusulas definidas normales en Prolog. Por ejemplo, el ejemplo anterior podría traducirse a lo siguiente:
oración ( A , Z ) : - frase_nombre ( A , B ), frase_verbo ( B , Z ). sustantivo_frase ( A , Z ) : - det ( A , B ), sustantivo ( B , Z ). verbo_frase ( A , Z ) : - verbo ( A , B ), sustantivo_frase ( B , Z ). det ([ el | X ], X ). det ([ a | X ], X ). sustantivo ([ cat | X ], X ). sustantivo ([ murciélago | X ], X ). verbo ([ come | X ], X ).
Listas de diferencias
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 más grande incluye 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 X
, y por lo tanto representado con el par ([H|X],X)
, por ejemplo.
Decir que P
es la diferencia entre A
y B
es lo mismo que decir que append(P,B,A)
vale. 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 lista (prefijos), en las circunstancias en que se pueden usar, porque la concatenación de (A,B)
y (B,Z)
es justa (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
Gramáticas sin contexto
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 ; 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 -> una ( 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 , representando estructuralmente n [ cita requerida ]
Representando características
Varias características lingüísticas también se pueden representar de manera bastante concisa con DCG al proporcionar argumentos adicionales a los functores. [9] Por ejemplo, considere el siguiente conjunto de reglas DCG:
oración -> pronombre ( sujeto ), verbo_frase . verbo_frase -> verbo , pronombre ( objeto ). pronombre ( sujeto ) -> [ él ]. pronombre ( sujeto ) -> [ ella ]. pronombre ( objeto ) -> [ él ]. pronombre ( objeto ) -> [ ella ]. verbo -> [me gusta ].
Esta gramática permite oraciones como "le gusta" y "le gusta", pero no "a ella le gusta" y "le gusta".
Analizando con DCGs
El principal uso práctico de un DCG es analizar oraciones de la gramática dada, es decir, construir un árbol de análisis sintáctico. Esto se puede hacer proporcionando "argumentos adicionales" a los functores en el DCG, como en las siguientes reglas:
oración ( s ( NP , VP )) -> frase_nombre ( NP ), frase_verbo ( VP ). sustantivo_frase ( np ( D , N )) -> det ( D ), sustantivo ( N ). VERB_PHRASE ( vp ( V , NP )) -> verbo ( V ), noun_phrase ( 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 , [ the , bat , eats , a , cat ], []). Parse_tree = s ( np ( d ( el ), n ( murciélago )), vp ( v ( come ), np ( d ( a ), n ( gato )))) ? ;
Otros usos
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 I / O debe estar representado por un par de io.state
argumentos. La notación DCG se puede usar para hacer que el uso de E / S sea más conveniente, [10] aunque generalmente se prefiere la notación de variables de estado. [ cita requerida ] La notación DCG también se usa para analizar y cosas similares en Mercury como en Prolog.
Extensiones
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). [11] Este formalismo estaba destinado en parte a facilitar 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 extendió los DCG para permitir múltiples acumuladores. [12] [13]
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. [14]
Otra extensión, llamada gramáticas de traducción de cláusulas definidas (DCTG) fue descrita en 1984. [15] La notación DCTG es muy similar a la notación DCG; la principal diferencia es que se usa en ::=
lugar de -->
en las reglas. Fue diseñado para manejar los atributos gramaticales de manera conveniente. [16] La traducción de DCTG en cláusulas Prolog normales es como la de DCG, pero se agregan 3 argumentos en lugar de 2.
Ver también
Notas
- ^ Johnson, M. (1994). "Dos formas de formalizar gramáticas". Lingüística y Filosofía . 17 (3): 221–240. doi : 10.1007 / BF00985036 .
- ^ Kowalski, RA "Los primeros años de la programación lógica" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Colmerauer, A. (1978). "Gramáticas de metamorfosis". Comunicación en lenguaje natural con computadoras . Apuntes de conferencias en Ciencias de la Computación. 63 : 133–189. doi : 10.1007 / BFb0031371 . ISBN 3-540-08911-X.
- ^ Pereira, F .; D. Warren (1980). "Gramáticas de cláusulas definidas para el análisis del lenguaje" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Pereira, FCN; DHD Warren (1983). "Análisis como deducción" (PDF) . Actas de la 21ª reunión anual de la Asociación de Lingüística Computacional . Asociación de Lingüística Computacional Morristown, Nueva Jersey, EE. UU. págs. 137-144.
- ^ Pereira, FCN; SM Shieber (2002). Prólogo y análisis de lenguaje natural . Publicación de microtomos. ISBN 9780971977709.
- ^ Fleck, Arthur. "Traducción gramatical de cláusula definida" . Consultado el 16 de abril de 2009 .
- ^ Fisher, JR "Tutorial de Prolog - 7.1" . Consultado el 17 de mayo de 2016 .
- ^ "Los DCG nos dan una notación natural para las características" . Consultado el 21 de abril de 2009 .
- ^ "Guía de transición del prólogo a mercurio: entrada / salida" . Consultado el 26 de marzo de 2015 .
- ^ Pereira, F. (1981). "Gramáticas de extraposición" (PDF) . Lingüística computacional . 7 (4): 243-256.
- ^ Van Roy, Peter (1990). "Notación DCG extendida: una herramienta para la programación aplicativa en Prolog" . Informe técnico UCB . 90 (583).
- ^ El código fuente está disponible en [1] .
- ^ Shimazu, H .; Y. Takashima (1995). "Gramática de cláusula definida multimodal" (PDF) . Sistemas y computadoras en Japón . 26 (3): 93-102. doi : 10.1002 / scj.4690260309 .
- ^ Abramson, H. (1984). "Gramáticas de traducción de cláusulas definidas". Cite journal requiere
|journal=
( ayuda ) - ^ Sperberg-McQueen, CM "Una breve introducción a las gramáticas de cláusulas definidas y las gramáticas de traducción de cláusulas definidas" . Consultado el 21 de abril de 2009 .
enlaces externos
- PNL con Prolog
- Gramáticas libres de contexto y DCG
- Gramáticas de cláusulas definidas: ya no solo para analizar
- Gramáticas de cláusulas definidas para el análisis del lenguaje