Una gramática adaptativa es una gramática formal que proporciona explícitamente mecanismos dentro del formalismo para permitir la manipulación de sus propias reglas de producción .
Descripción general
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]
Historia temprana
La primera descripción de la adaptabilidad gramatical (aunque no bajo ese nombre) en la literatura se considera generalmente [2] [3] [4] 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 ) vino de Wegbreit en 1970 [6] en el estudio de lenguajes de programación extensibles , seguido de la sintaxis dinámica de Hanford y Jones en 1973. [7]
Esfuerzos colaborativos
Hasta hace relativamente poco tiempo, gran parte de la investigación sobre las propiedades formales de las gramáticas adaptativas no estaba coordinada entre los investigadores, y sólo Henning Christiansen la resumió por primera vez en 1990 [2] en respuesta a un artículo en ACM SIGPLAN Notices de Boris Burshteyn. [8] El Departamento de Ingeniería de la Universidad de São Paulo tiene su Laboratorio de Idiomas y Técnicas Adaptativas , específicamente enfocado en la investigación y práctica en tecnologías y teoría adaptativas. La LTA también mantiene una página para nombrar a los investigadores en el campo. [9]
Terminología y taxonomía
Si bien los primeros esfuerzos hacían referencia a la sintaxis dinámica [7] y extensible , [6] modificable , [10] dinámica , [11] y adaptable [2] [12] gramáticas, 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 usa normalmente 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 realizado esfuerzos en esta dirección. [3] [4]
La clasificación de Shutt (y extensiones)
Shutt clasifica los modelos de gramática adaptativa en dos categorías principales: [3] [15]
- Las gramáticas adaptativas imperativas varían sus reglas en función de un estado global quecambia durante el tiempo de generación de un idioma .
- Las gramáticas adaptativas declarativas varían sus reglas solo en el espacio de la generación de un lenguaje (es decir, la posición en el árbol de sintaxis de la cadena generada).
Jackson refina la taxonomía de Shutt, refiriéndose a los cambios en el tiempo como globales y los cambios en el espacio como locales , y agrega una categoría híbrida de tiempo-espacio : [4]
- Las gramáticas adaptativas espacio-temporales ( híbridos ) varían sus reglas en el tiempo o en el espacio (o ambos) de la generación de un lenguaje (y las operaciones locales y globales se diferencian explícitamente por la notación de tales cambios).
Formalismos adaptativos en la literatura
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.
Formalismos gramaticales adaptativos
La siguiente es una lista (de ninguna manera completa) de formalismos gramaticales que, según la definición de Shutt anterior, se consideran (o han sido clasificados por sus propios inventores como) gramáticas adaptativas. Se enumeran en su orden histórico de primera mención en la literatura.
Gramáticas extensibles sin contexto (Wegbreit)
Descrita en la tesis doctoral de Wegbreit en 1970, [6] una gramática libre de contexto extensible consiste en una gramática libre de contexto cuyo conjunto de reglas se modifica de acuerdo con las instrucciones producidas por un transductor de estado finito 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 de sintaxis. Shutt clasificó las gramáticas extensibles sin contexto como imperativas . [3]
Gramáticas de Christiansen (Christiansen)
Introducidas por primera vez en 1985 como Gramáticas generativas [16] y más tarde 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 redoblado se demuestra de la siguiente manera: [17]
G > → G ↑ w > w-rule }>
donde w-rule =G '> → w
G ↑ canal • w > → ácter>G ↑ canal > G ↑ w > > → <ε> → a ácter>
Gramáticas modificables ascendentes, gramáticas modificables descendentes y USSA (Burshteyn)
Introducidas por primera vez en mayo de 1990 [8] y luego ampliadas 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 ACM SIGPLAN Notices , Burshteyn modificó más tarde su formalismo e introdujo su Analizador de sintaxis y semántica universal adaptable (USSA) en 1992. [18] Estos formalismos fueron clasificados por Shutt como imperativos . [3]
Gramáticas adaptativas recursivas (Shutt)
Introducidas en 1993, las Gramáticas Adaptativas Recursivas (RAG) fueron un intento de introducir un formalismo poderoso de Turing que mantuvo gran parte de la elegancia de las gramáticas libres de contexto. [3] Shutt autoclasifica los RAG como un formalismo declarativo .
Gramáticas dinámicas (Boullier)
Las gramáticas dinámicas de Boullier , introducidas en 1994, [11] parecen ser la primera familia de gramáticas adaptativas en introducir rigurosamente la noción de un continuo de tiempo de un análisis sintáctico como parte de la notación del formalismo gramatical mismo. [4] Las gramáticas dinámicas son una secuencia de gramáticas, y 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 cosas como verificación de tipos , lenguajes extensibles , polimorfismo y otras construcciones que normalmente se consideran en el dominio semántico de la traducción de lenguajes de programación.
Gramáticas adaptativas (Iwai)
El trabajo de Iwai en 2000 [13] lleva los autómatas adaptativos de Neto [19] más allá mediante la aplicación de autómatas adaptativos a gramáticas sensibles al contexto . Las gramáticas adaptativas de Iwai (observe el calificador por nombre) permiten tres operaciones durante un análisis:? consulta (similar en algunos aspectos a un predicado sintáctico , pero vinculado a la inspección de las reglas de las que se eligen las modificaciones), + adición y - eliminación (que comparte con su predecesor autómata adaptativo).
§-cálculo (Jackson)
Introducido en 2000 [20] y más ampliamente discutido en 2006, [4] el §-Calculus (§ aquí pronunciado meta-ess ) permite la adición, supresión y modificación explícita de producciones dentro de una gramática, así como proporcionar sintáctica predicados . Este formalismo es auto-clasificado por su creador como imperativo y adaptativo , o, más específicamente, como un formalismo gramatical adaptativo espacio-temporal , y otros lo clasificaron además como un formalismo analítico . [14] [21]
El lenguaje redoblado 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 (en el espacio). La #phi(A.X<-"")
declaración en la S La producción declara efectivamente una producción global llamada AX colocando la cadena vacía en esa producción antes de su referencia por R. )
Dispositivos adaptables (Neto y Pistori)
Descrito por primera vez por Neto en 2001, [22] los dispositivos adaptativos fueron posteriormente mejorados y ampliados por Pistori en 2003. [23]
Adapser (Carmi)
En 2002, [24] Adam Carmi introdujo un formalismo gramatical adaptativo basado en LALR (1) conocido como Adapser . No parece que se hayan dado a conocer detalles específicos del formalismo.
CFG adaptables con verificación de apariencia (Bravo)
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 estas nuevas gramáticas, llamadas CFG adaptativas con verificación de apariencia ser Turing poderoso .
Formalismos adaptativos de la máquina
Los formalismos que se enumeran a continuación, aunque no son formalismos gramaticales, sirven como base de formalismos gramaticales completos o se incluyen aquí porque son de naturaleza adaptativa. Se enumeran en su orden histórico de primera mención en la literatura.
- Autómatas de estado finito auto modificables (Shutt & Rubinstein)
- Introducido en 1994 por Shutt y Rubinstein, [26] Los Autómatas de Estado Finito Auto Modificantes (SMFA) se muestran, en una forma restringida, poderosos de Turing .
- Autómatas adaptativos (Neto)
- En 1994, [19] Neto introdujo la máquina que llamó un autómata de empuje estructurado , el núcleo de la teoría de los autómatas adaptativos como lo perseguían Iwai, [13] Pistori, [23] Bravo [14] y otros. Este formalismo permite las operaciones de inspección (similares a los predicados sintácticos , como se señaló anteriormente en relación con las gramáticas adaptativas de Iwai), la adición y eliminación de reglas.
Ver también
- Algoritmo adaptativo
- Aprendizaje de gramática artificial
- Inducción gramatical
- Categoría: lenguajes de programación de sintaxis extensible
Referencias
- ^ Shutt, John N. "¿Qué es una gramática adaptativa?" . Consultado el 6 de febrero de 2019 .
- ^ a b c Christiansen, Henning, "Una encuesta de gramáticas adaptables " , Avisos de ACM SIGPLAN , vol. 25 No. 11, págs. 35-44, noviembre de 1990.
- ^ a b c d e f g h Shutt, John N., Gramáticas adaptables recursivas , Tesis de maestría, Instituto Politécnico de Worcester, 1993. (Revisión enmendada del 16 de diciembre de 2003).
- ↑ a b c d e Jackson, Quinn Tyler, Adapting to Babel: Adaptivity and Context-Sensitivity in Parsing , Ibis Publications, Plymouth, Massachusetts, marzo de 2006.
- ^ Caracciolo di Forino, Alfonso, " Algunas observaciones sobre la sintaxis de los lenguajes de programación simbólicos ", Comunicaciones de la ACM , vol. 6, núm. 8., págs. 456-460, agosto de 1963.
- ^ a b c Wegbreit, Ben, Estudios en lenguajes de programación extensibles , ESD-TR-70-297, Universidad de Harvard, Cambridge, Massachusetts, mayo de 1970. En forma de libro, Garland Publishing, Inc., Nueva York, 1980.
- ^ a b Hanford, KV & Jones, CB, " Sintaxis dinámica: un concepto para la definición de la sintaxis de los lenguajes de programación ", Revisión anual en Programación automática 7 , Pergamon Press, Oxford, págs. 115-142, 1973.
- ^ a b Burshteyn, Boris. " Sobre la modificación de la gramática formal en el momento del análisis ", Avisos ACM SIGPLAN , vol. 25 No. 5, págs. 117-123, mayo de 1990.
- ^ http://www.pcs.usp.br/~lta/union/index.php?cp=4&categoria=28 [ enlace muerto ]
- ^ a b Burshteyn, Boris, " Generación y reconocimiento de lenguajes formales mediante gramáticas modificables " , Avisos ACM SIGPLAN , vol. 25 No. 12, págs. 45-53, diciembre de 1990.
- ^ a b Boullier, Pierre, " Gramáticas dinámicas y análisis semántico ", Informe de investigación de INRIA No. 2322, agosto de 1994.
- ^ John Shutt originalmente llamó a sus Gramáticas adaptativas recursivas por el nombreGramáticas adaptables recursivas, y señala su cambio a adaptativas en esta URL: Tesis de MS de John Shutt .
- ^ a b c d e Iwai, Margarete Keiko, Um formalismo gramatical adaptativo para linguagens dependientes de contexto , Tesis doctoral, Departamento de Ingeniería, Universidad de São Paulo, Brasil, enero de 2000.
- ^ a b c d Bravo, César, Grámmaticas Livres de Contexto Adaptativas com verificação de aparência , Tesis doctoral, Departamento de Ingeniería Eléctrica, Universidad de São Paulo, enero de 2004.
- ^ Shutt, John N., página web "Imperative Adaptive Grammars" fechada el 28 de marzo de 2001, en la URL: http://web.cs.wpi.edu/~jshutt/adapt/imperative.html
- ^ Christiansen, Henning, "Sintaxis, semántica y estrategias de implementación para lenguajes de programación con potentes mecanismos de abstracción", Actas de la 18ª Conferencia Internacional de Hawaii sobre Ciencias de Sistemas , vol. 2, págs. 57-66, 1985.
- ^ a b Christiansen, Henning, " La sintaxis y la semántica de los lenguajes extensibles ", Datalogiske skrifter 14 , Universidad de Roskilde, 1988.
- ^ Burshteyn, Boris, " USSA - Analizador de sintaxis y semántica universal ", Avisos de ACM SIGPLAN , vol. 27 No. 1, págs. 42-60, enero de 1992.
- ^ a b Neto, João Jose, "Autómatas adaptativos para lenguajes sensibles al contexto" , Avisos ACM SIGPLAN , vol. 29 No. 9, págs. 115-124, septiembre de 1994.
- ^ Jackson, Quinn Tyler, " Predicados adaptativos en el análisis del lenguaje natural ", perfección , vol. 1 No. 4, abril de 2000.
- ^ Okhotin, Alexander, Gramáticas booleanas: poder expresivo y algoritmos , tesis doctoral, Escuela de Computación, Universidad de Queens, Kingston, Ontario, agosto de 2004.
- ^ Neto, João Jose, " Dispositivos adaptados basados en reglas: Formulación general y estudio de caso [ enlace muerto permanente ] ", BW Watson, D. Wood (Eds.): Implementación y aplicación de Automata 6th International Conference , CIAA 2001 , Lecture Notes en Ciencias de la Computación , Vol. 2494, Pretoria, Sudáfrica, Springer-Verlag, págs. 234–250, 23–25 de julio de 2001.
- ^ a b Pistori, Hemerson, Tecnologia Adaptativa em Engenharia de Computação: Estado da Arte e Aplicações , Tesis doctoral, Departamento de Ingeniería Eléctrica, Universidad de São Paulo, 2003.
- ^ Carmi, Adam, " Adapser: An LALR (1) Adaptive Parser [ enlace muerto permanente ] ", el taller israelí sobre lenguajes de programación y entornos de desarrollo, Haifa, Israel, 1 de julio de 2002.
- ^ Salomaa, Arto, Lenguajes formales , Prensa académica, 1973.
- ^ Shutt, John & Rubinstein, Roy, " Autómatas finitos auto-modificables ", en B. Pehrson y I. Simon, editores, Tecnología y fundamentos: procesamiento de información '94 vol. I: Actas del 13 ° Congreso Mundial de Computación de la IFIP , Ámsterdam: Holanda Septentrional, págs. 493-498, 1994.