Gramática de Van Wijngaarden

En informática , una gramática de Van Wijngaarden (también vW-grammar o W-grammar ^[1] ) es una gramática de dos niveles que proporciona una técnica para definir gramáticas libres de contexto potencialmente infinitas en un número finito de reglas. El formalismo fue inventado por Adriaan van Wijngaarden ^[2] para definir rigurosamente algunas restricciones sintácticas que previamente debían ser formuladas en lenguaje natural , a pesar de su contenido esencialmente sintáctico.

Las aplicaciones típicas son el tratamiento del género y el número en la sintaxis del lenguaje natural y la claridad de los identificadores en los lenguajes de programación . Por ejemplo, "hay una persona" y "hay dos personas" son ambos gramaticalmente correctos, pero "hay una persona" es incorrecto por razones sensibles al contexto que podría representar una gramática W.

La técnica fue utilizada y desarrollada en la definición del lenguaje de programación ALGOL 68 . Es un ejemplo de la clase más amplia de gramáticas de afijos .

Visión general

Una gramática W consiste en un conjunto finito de meta- reglas, que se utilizan para derivar (posiblemente infinitas) reglas de producción a partir de un conjunto finito de hiper- reglas. Las meta-reglas están restringidas a aquellas definidas por una gramática libre de contexto . Las hiperreglas restringen los contextos admisibles en el nivel superior. Esencialmente, la sustitución consistente utilizada en el proceso de derivación es equivalente a la unificación , como en Prolog , como señaló Alain Colmerauer ^{[ ¿dónde? ]} .

Por ejemplo, la asignación x:=1 solo es válida si la variable x puede contener un número entero. Por lo tanto, la sintaxis libre de contexto variable := valueestá incompleta. En una gramática de dos niveles, esto podría especificarse de manera sensible al contexto como REF TYPE variable := TYPE value. Entonces ref integer variable := integer valuepodría ser una regla de producción pero ref Boolean variable := integer valueno es una regla de producción posible. Esto también significa que la asignación con tipos incompatibles se convierte en un error de sintaxis que puede detectarse en tiempo de compilación. Similar,

STYLE begin token, new LAYER1 preludios, token paralelo, nuevo PAQUETE de tareas LAYER1, Token de finalización de ESTILO

permite begin ... endy { ... }pero no begin ... }.

Ejemplos de ALGOL 68

Antes de ALGOL 68, el lenguaje ALGOL 60 se formalizó utilizando la forma Backus-Naur sin contexto . La aparición de una nueva gramática de dos niveles sensible al contexto presentó un desafío para algunos lectores del "Informe final" de ALGOL 68 de 1968 . Posteriormente, Wijngaarden y sus colegas revisaron el informe final y lo publicaron como "Informe revisado" de ALGOL 68 de 1973.

La gramática de ALGOL 68 se define oficialmente en la gramática de Van Wijngaarden de dos niveles, pero se ha realizado un subconjunto en la forma Backus – Naur de un nivel , compare:

• Gramática de Van Wijngaarden; ^[3]
• Forma Backus – Naur / Yacc ^[4]

ALGOL 68 como en el Informe final de 1968 §2.1

a) programa: símbolo abierto, preludio estándar, opción de preludio de biblioteca, programa en particular, salir, opción de postludio de biblioteca, postludio estándar, símbolo de cierre.
b) preludio estándar: secuencia de preludio de declaración.
c) preludio de la biblioteca: secuencia del preludio de la declaración.
d) programa particular: opción de secuencia de etiquetas, cláusula nula CERRADA fuerte.
e) salir: siga el símbolo, letra e letra x letra i letra t, símbolo de etiqueta.
f) postludio de la biblioteca: interludio de la declaración.
g) postludio estándar: tren de cláusula nula fuerte

ALGOL 68 como en el Informe Revisado de 1973 §2.2.1, §10.1.1

programa: vacío fuerte nueva cláusula cerrada

A) EXTERNO :: estándar; Biblioteca ; sistema ; especial.
B) STOP: etiqueta letra s letra t letra o letra p.

a) texto del programa: STYLE begin token, new LAYER1 preludios, token paralelo, nuevo PAQUETE de tareas LAYER1, Token de finalización de ESTILO.
b) Preludios de NEST1: preludio estándar de NEST1 con DECS1, Preludio de la biblioteca NEST1 con DECSETY2, Preludio del sistema NEST1 con DECSETY3, donde (NEST1) es (nuevo VACÍO nuevo DECS1 DECSETY2 DECSETY3).
c) Preludio EXTERNO de NEST1 con DECSETY1: serie NEST1 fuerte vacío con DECSETY1, vaya token; donde (DECSETY1) es (VACÍO), VACÍO.
d) Tareas de NEST1: lista de tareas del sistema NEST1 y también token, Lista de PAQUETES de tareas de usuario de NEST1.
e) Tarea del sistema NEST1: unidad NEST1 de vacío fuerte.
f) Tarea de usuario de NEST1: preludio particular de NEST2 con DECS, PAQUETE de programa particular de NEST2, vaya token, Postludio particular de NEST2, donde (NEST2) es (NEST1 new DECS STOP).
g) Programa particular de NEST2: NEST2 nueva definición de etiqueta unida a LABSETY3 de LABSETY3, fuerte vacío NEST2 nuevo LABSETY3 Cláusula ADJUNTA.
h) Definición de etiqueta unida a NEST de LABSETY: donde (LABSETY) es (VACÍO), VACÍO; donde (LABSETY) es (LAB1 LABSETY1), Definición de etiqueta NEST de LAB1, NEST se unió a la definición de etiqueta de $ LABSETY1.
i) Postludio particular de NEST2: Serie NEST2 de vacío fuerte con STOP.

Implementaciones

yo-yo ^[5] analizador para gramáticas de van Wijngaarden con gramáticas de ejemplo para expresiones , eva , sal y Pascal (el estándar actual ISO 7185 para Pascal usa la forma extendida Backus-Naur ).

Historia

Las gramáticas W se basan en la idea de proporcionar a los símbolos no terminales de las gramáticas libres de contexto atributos (o afijos ) que pasan información entre los nodos del árbol de análisis sintáctico , que se utilizan para restringir la sintaxis y especificar la semántica. Esta idea era bien conocida en ese momento; Por ejemplo, Donald Knuth visitó el comité de diseño de ALGOL 68 mientras desarrollaba su propia versión, las gramáticas de atributos . ^[6] Muy peculiar de las gramáticas W era su tratamiento estricto de los atributos como cadenas, definidas por una gramática libre de contexto, en la que la concatenación es la única operación posible; en las gramáticas de atributos, los atributos pueden ser de cualquier tipo de datos y se les puede aplicar cualquier tipo de operación.

Después de su introducción en el informe Algol 68, las gramáticas W fueron ampliamente consideradas como demasiado poderosas y sin restricciones para ser prácticas. ^{[ cita requerida ]} Esto fue en parte una consecuencia de la forma en que se habían aplicado; el informe revisado de Algol 68 contenía una gramática mucho más legible, sin modificar el formalismo de la gramática W en sí.

Mientras tanto, quedó claro que las gramáticas W, cuando se usan en su generalidad completa, son de hecho demasiado poderosas para propósitos prácticos como servir como entrada para un generador de analizador sintáctico . Describen con precisión todos los lenguajes enumerables de forma recursiva , ^{[7] lo} que hace imposible el análisis sintáctico en general: es un problema indecidible decidir si una cadena dada puede ser generada por una gramática W dada. Su uso debe verse seriamente restringido cuando se usa para análisis o traducción automáticos. Se desarrollaron variantes restringidas y modificadas de las gramáticas W para abordar esto, p. Ej.

• Gramáticas de afijo extendidas (EAG), aplicadas para describir las gramáticas del lenguaje natural como inglés y español)
• Q-systems , también aplicado al procesamiento del lenguaje natural
• la serie de lenguajes CDL , aplicada como lenguajes de construcción de compiladores para lenguajes de programación

Aplicaciones fuera de ALGOL 68

Anthony Fisher ha escrito un analizador sintáctico para una gran clase de gramáticas W. ^[5]

Dick Grune creó un programa en C que generaría todas las producciones posibles de una gramática de 2 niveles. ^[8]

Las aplicaciones de las EAG mencionadas anteriormente pueden considerarse efectivamente como aplicaciones de las gramáticas W, ya que las EAG están muy cerca de las gramáticas W.

También se han propuesto las W-gramáticas para la descripción de acciones humanas complejas en ergonomía . ^{[ cita requerida ]}

• Una descripción de la gramática W para Ada ^[9] - "La descripción de la gramática W de Ada sigue siendo útil para los científicos informáticos que necesitan más que una simple comprensión de la sintaxis y una descripción rudimentaria de la semántica"

Ver también

• Adjuntar gramática
• Gramática de afijo extendido
• Gramática de atributos

Referencias

1. Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Gramáticas para lenguajes de programación . Elsevier. ISBN 978-0-444-00199-3.
2. van Wijngaarden, Adriaan (1965), MR 76: Diseño ortogonal y descripción de un lenguaje formal (PDF) , Amsterdam, Países Bajos : CWI .
3. Kleine, "Algol 68", Historial de idiomas (PDF) (informe adjunto), DE : FH Jena .
4. "Sintaxis", Algol 68 , FR : Univ Poitiers.
5. Fisher, Anthony, "yo-yo", Software , Reino Unido : York.
6. Knuth, Donald E (1990), "La génesis de las gramáticas de atributos" ( Plain TeX , gZiped ) , Actas de la conferencia internacional sobre gramáticas de atributos y sus aplicaciones , Springer Verlag : 1–12 .
7. Sintzoff, M. (1967). "Existencia de una sintaxis de van Wijngaarden para cada conjunto recursivamente enumerable". Annales de la Société scientifique de Bruxelles . 81 : 115-118.
8. Grune, Dick, un generador de oraciones de dos niveles , NL : VU.
9. ADA177802: Una descripción de W-Grammar para Ada , EE. UU .: DTIC.

enlaces externos

• "Uso en Algol68", Informática , Trapos para libros.
• Pemberton, Steven , VW (introducción al tutorial), NL: CWI.