Gramática adaptativa - Adaptive grammar

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.

Historia temprana

La primera descripción de la adaptabilidad gramatical (aunque no bajo ese nombre) en la literatura se considera generalmente en un artículo de Alfonso Caracciolo di Forino publicado en 1963. La siguiente referencia generalmente aceptada a un formalismo adaptativo ( gramáticas extensibles libres de contexto ) vino de Wegbreit en 1970 en el estudio de lenguajes de programación extensibles , seguido de la sintaxis dinámica de Hanford y Jones en 1973.

Esfuerzos colaborativos

Hasta hace relativamente poco, gran parte de la investigación sobre las propiedades formales de las gramáticas adaptativas no estaba coordinada entre los investigadores, y solo Henning Christiansen la resumió por primera vez en 1990 en respuesta a un artículo en ACM SIGPLAN Notices de Boris Burshteyn. 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.

Terminología y taxonomía

Mientras que los primeros esfuerzos hicieron referencia a la sintaxis dinámico y extensible , modificable , dinámico , y adaptables gramáticas, el uso más reciente ha tendido hacia el uso del término adaptativo (o alguna variante como adaptativa , en función del idioma publicación de la literatura). Iwai se refiere a su formalismo como gramáticas adaptativas , 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.

La clasificación de Shutt (y extensiones)

Shutt categoriza los modelos de gramática adaptativa en dos categorías principales:

  • Las gramáticas adaptativas imperativas varían sus reglas en función de un estado global que cambia 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 :

  • 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, 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 .

Gramáticas de Christiansen (Christiansen)

Introducidas por primera vez en 1985 como gramáticas generativas y más tarde más elaboradas, 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 .

El lenguaje de duplicación se demuestra de la siguiente manera: 

<program↓G>       →   <dcl↓G↑w> <body↓{w-rule}>

where w-rule  =
<body↓G’>         →   w

<dcl↓G↑ch•w>     →   <char↓G↑ch> <dcl↓G↑w>
<dcl↓G↑<>>       →   <ε>
<char↓G↑a>       →   a

Gramáticas modificables ascendentes, gramáticas modificables descendentes y USSA (Burshteyn)

Introducidas por primera vez en mayo de 1990 y luego ampliadas en diciembre de 1990, 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ó posteriormente su formalismo e introdujo su Analizador de sintaxis y semántica universal adaptable (USSA) en 1992. Shutt clasificó estos formalismos como imperativos .

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. Shutt autoclasifica los RAG como un formalismo declarativo .

Gramáticas dinámicas (Boullier)

Las gramáticas dinámicas de Boullier , introducidas en 1994, 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 en sí. 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 lleva los autómatas adaptativos de Neto más allá mediante la aplicación de autómatas adaptativos a gramáticas sensibles al contexto . Las gramáticas adaptativas de Iwai (tenga en cuenta 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 y más ampliamente discutido en 2006, el §-Cálculo (§ aquí se pronuncia 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 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 .

El lenguaje de duplicación se demuestra de la siguiente manera: 

grammar ww {
 S ::= #phi(A.X<-"") R;
 R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) 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 adaptativos (Neto y Pistori)

Descrito por primera vez por Neto en 2001, los dispositivos adaptativos fueron mejorados y ampliados por Pistori en 2003.

Adapser (Carmi)

En 2002, 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.

CFG adaptables con verificación de apariencia (Bravo)

En 2004, César Bravo introdujo la noción de fusionar el concepto de verificación de apariencia con gramáticas adaptativas libres de contexto , una forma restringida de las gramáticas adaptativas de Iwai, mostrando que estas nuevas gramáticas, llamadas CFG adaptativas con verificación de apariencia, son poderosas de Turing .

Formalismos de máquinas adaptables

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)
Introducidos en 1994 por Shutt y Rubinstein, se ha demostrado que los autómatas de estado finito automodificables (SMFA) son, en una forma restringida, poderosos de Turing .
Autómatas adaptativos (Neto)
En 1994, 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 según la perseguían Iwai, Pistori, Bravo 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

Referencias