Una gramática adaptativa es una gramática formal que proporciona explícitamente mecanismos dentro del formalismo para permitir que se manipulen sus propias reglas de producción .
John N. Shutt define la gramática adaptativa como un formalismo gramatical que permite manipular explícitamente conjuntos de reglas (también conocidos como conjuntos de reglas de producción) dentro de una gramática. Los tipos de manipulación incluyen la adición, eliminación y modificación de reglas. [1]
La primera descripción de la adaptabilidad gramatical (aunque no bajo ese nombre) en la literatura generalmente [2] [3] [4] se considera que aparece en un artículo de Alfonso Caracciolo di Forino publicado en 1963. [5] La siguiente referencia generalmente aceptada a un formalismo adaptativo ( gramáticas extensibles libres de contexto ) provino de Wegbreit en 1970 [6] en el estudio de lenguajes de programación extensibles , seguido por la sintaxis dinámica de Hanford y Jones en 1973. [7]
Hasta hace relativamente poco, gran parte de la investigación sobre las propiedades formales de las gramáticas adaptativas no estaba coordinada entre investigadores; solo Henning Christiansen la resumió por primera vez en 1990 [2] en respuesta a un artículo de Boris Burshteyn en ACM SIGPLAN Notices . [8] El Departamento de Ingeniería de la Universidad de São Paulo tiene su Laboratorio de Lenguajes y Técnicas Adaptativas, que se centra específicamente en la investigación y la práctica en tecnologías y teorías adaptativas. El LTA también mantiene una página que nombra a los investigadores en el campo. [9]
Aunque los primeros esfuerzos hacían referencia a la sintaxis dinámica [7] y a las gramáticas extensibles [6] , modificables [10] , dinámicas [ 11] y adaptables [2] [12] , el uso más reciente ha tendido hacia el uso del término adaptativo (o alguna variante como adaptativa [13] [14] dependiendo del idioma de publicación de la literatura). [3] Iwai se refiere a su formalismo como gramáticas adaptativas [ 13] , pero este uso específico de gramáticas simplemente adaptativas no se utiliza normalmente en la actualidad en la literatura sin calificación de nombre. Además, no se han realizado esfuerzos de estandarización o categorización entre varios investigadores, aunque varios han hecho esfuerzos en esta dirección. [3] [4]
Shutt clasifica los modelos de gramática adaptativa en dos categorías principales: [3] [15]
Jackson refina la taxonomía de Shutt, refiriéndose a los cambios en el tiempo como globales y a los cambios en el espacio como locales , y añadiendo una categoría híbrida de tiempo-espacio : [4]
Los formalismos adaptativos pueden dividirse en dos categorías principales: formalismos gramaticales completos (gramáticas adaptativas) y máquinas adaptativas, en las que se han basado algunos formalismos gramaticales.
La siguiente es una lista (de ninguna manera completa) de formalismos gramaticales que, según la definición de Shutt, se consideran (o han sido clasificados por sus propios inventores como) gramáticas adaptativas. Se enumeran en el orden histórico de su primera mención en la literatura.
Descrita en la tesis doctoral de Wegbreit en 1970, [6] una gramática extensible libre de contexto consiste en una gramática libre de contexto cuyo conjunto de reglas se modifica de acuerdo con las instrucciones emitidas por un transductor de estados finitos al leer el prefijo terminal durante una derivación más a la izquierda. Por lo tanto, el conjunto de reglas varía según la posición en la cadena generada, pero esta variación ignora la estructura jerárquica del árbol sintáctico. Shutt clasificó las gramáticas extensibles libres de contexto como imperativas . [3]
Introducidas por primera vez en 1985 como gramáticas generativas [16] y luego más elaboradas, [17] las gramáticas de Christiansen (aparentemente llamadas así por Shutt, posiblemente debido a un conflicto con las gramáticas generativas de Chomsky) son una extensión adaptativa de las gramáticas de atributos . Shutt clasificó las gramáticas de Christiansen como declarativas . [3]
El lenguaje redoblante se demuestra de la siguiente manera: [17]
<programa↓ G > → <dcl↓ G ↑ w > <cuerpo↓{ regla-w }>donde w-regla =<cuerpo↓ G '> → w
<dcl↓ G ↑ ch • w > → <char↓ G ↑ ch > <dcl↓ G ↑ w ><dcl↓G↑<>> → <ε><char↓G↑a> → a
Introducidas por primera vez en mayo de 1990 [8] y ampliadas posteriormente en diciembre de 1990 [10] , las gramáticas modificables proporcionan explícitamente un mecanismo para la adición y eliminación de reglas durante un análisis. En respuesta a las respuestas de los avisos de ACM SIGPLAN , Burshteyn modificó posteriormente su formalismo e introdujo su Analizador Universal de Sintaxis y Semántica (USSA) adaptativo en 1992. [18] Shutt clasificó estos formalismos como imperativos . [3]
Introducidas en 1993, las gramáticas adaptativas recursivas (RAG) fueron un intento de introducir un formalismo de Turing poderoso que mantuviera gran parte de la elegancia de las gramáticas libres de contexto . [3] Shutt se autoclasifica a las RAG como un formalismo declarativo .
Las gramáticas dinámicas de Boullier , introducidas en 1994, [11] parecen ser la primera familia de gramáticas adaptativas que introduce rigurosamente la noción de un continuo temporal de un análisis sintáctico como parte de la notación del formalismo gramatical en sí. [4] Las gramáticas dinámicas son una secuencia de gramáticas, en la que cada gramática G i difiere de alguna manera de otras gramáticas en la secuencia, a lo largo del tiempo. El artículo principal de Boullier sobre gramáticas dinámicas también define un analizador sintáctico dinámico, la máquina que efectúa un análisis sintáctico contra estas gramáticas, y muestra ejemplos de cómo su formalismo puede manejar cuestiones como la comprobación de tipos , los lenguajes extensibles , el polimorfismo y otras construcciones que normalmente se consideran parte del dominio semántico de la traducción de lenguajes de programación.
El trabajo de Iwai en 2000 [13] lleva los autómatas adaptativos de Neto [19] más allá al aplicarlos a las gramáticas sensibles al contexto . Las gramáticas adaptativas de Iwai (nótese el calificador por su nombre) permiten tres operaciones durante un análisis: ? consulta (similar en algunos aspectos a un predicado sintáctico , pero vinculada a la inspección de reglas de las que se eligen modificaciones), + adición y - eliminación (que comparte con sus autómatas adaptativos predecesores).
Introducido en 2000 [20] y discutido más completamente en 2006, [4] el §-Cálculo (§ aquí pronunciado meta-ess ) permite la adición, eliminación y modificación explícita de producciones dentro de una gramática, así como también proporciona predicados sintácticos . Este formalismo es autoclasificado por su creador como imperativo y adaptativo , o, más específicamente, como un formalismo gramatical adaptativo espacio-temporal , y fue clasificado además por otros como un formalismo analítico . [14] [21]
El lenguaje redoblante se demuestra de la siguiente manera:
gramática ww { S::= #phi(AX<-"") R; R ::= $C('[ab]') #phi(AX<-AX C) #phi(N<=AX) N | R;};(Nota sobre la notación: En el ejemplo anterior, las #phi(...)declaraciones identifican los puntos en la producción R que modifican la gramática explícitamente. #phi(A.X<-A.X C)representa una modificación global (en el tiempo) y la #phi(N<=A.X)declaración identifica una modificación local#phi(A.X<-"") (en el espacio). La declaración en la producción S declara efectivamente una producción global llamada AX al colocar la cadena vacía en esa producción antes de su referencia por R ).
Descritos por primera vez por Neto en 2001, [22] los dispositivos adaptativos fueron mejorados y ampliados posteriormente por Pistori en 2003. [23]
En 2002, [24] Adam Carmi introdujo un formalismo gramatical adaptativo basado en LALR(1) conocido como Adapser . No parece que se hayan publicado detalles específicos del formalismo.
En 2004, [14] César Bravo introdujo la noción de fusionar el concepto de verificación de apariencia [25] con gramáticas adaptativas libres de contexto , una forma restringida de las gramáticas adaptativas de Iwai, [13] mostrando que estas nuevas gramáticas, llamadas CFG adaptativas con verificación de apariencia, son potentes en términos de Turing .
Los formalismos que se enumeran a continuación, si bien no son formalismos gramaticales, sirven como base de formalismos gramaticales completos o se incluyen aquí porque son de naturaleza adaptativa. Se enumeran en el orden histórico de su primera mención en la literatura.