Gramática de Wiingaarden

La gramática van Wiingaarden (también vB-grammar o B-grammar ) es una gramática de dos niveles que proporciona una forma de definir gramáticas potencialmente infinitas a través de un número finito de reglas. El formalismo fue inventado por Adrian van Wiingaarden para definir algunas de las restricciones sintácticas que antes debían formularse en los lenguajes naturales, a pesar de su naturaleza fundamentalmente sintáctica. Aplicaciones típicas son el manejo de género y número en lenguajes naturales y la correcta formulación de identificadores en lenguajes de programación.

El método fue utilizado y desarrollado en la definición del lenguaje de programación ALGOL 68 . Este es un ejemplo de una clase más amplia de gramáticas de afijos.

Resumen

Una gramática B consta de un número finito de metarreglas que se utilizan para derivar reglas de inferencia (potencialmente infinitas) a partir de un número finito de hiperreglas. La definición de metarreglas se limita a una gramática libre de contexto. Las hiperreglas limitan los contextos permitidos a un nivel superior. En esencia, la sustitución consistente utilizada en el proceso de inferencia es equivalente al proceso de unificación, por ejemplo, del lenguaje Prolog, como señaló Alan Colmeroe.

Ejemplos de ALGOL 68

Antes del lenguaje ALGOL 68 , ALGOL 60 se formalizaba a través de formularios Backus-Naur libres de contexto. El advenimiento de nuevas gramáticas de dos niveles sensibles al contexto presentó una dificultad para algunos lectores del "Informe final" sobre ALGOL 68 en 1968. Posteriormente, el informe final fue editado por Weingaarden y sus colegas y publicado como "Informe editado" sobre ALGOL 68 en 1973.

ALGOL 68 en el informe de 1968 § 2.1

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

ALGOL 68 en 1973 informe editado § 2.2.1, § 10.1.1

programa: fuerte vacío 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: token de inicio de ESTILO, nuevos preludios de CAPA1, token paralelo, nuevo PACK de tareas LAYER1, Ficha final de ESTILO. b) Preludios NEST1: preludio estándar 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 NEST1 con DECSETY1 : serie fuerte vacía NEST1 con DECSETY1, siga con el token; donde (DECSETY1) es (VACÍO), VACÍO. d) Tareas NEST1: lista de tareas del sistema NEST1, y también token, Lista de PACK de tareas de usuario de NEST1. e) Tarea del sistema NEST1: fuerte unidad NEST1 vacía. f) Tarea de usuario de NEST1: preludio particular de NEST2 con DECS, PAQUETE de programa particular de NEST2, siga el token, nido2 postludio particular, donde (NEST2) es (NEST1 new DECS STOP). g) programa particular NEST2: NEST2 nueva definición de etiqueta unida a LABETY3 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: vacío fuerte Serie NEST2 con STOP.

Historia

Las gramáticas B se basan en la idea de complementar los símbolos no terminales de las gramáticas COP con atributos (o afijos ) que transmiten información entre los nodos del árbol de análisis y se utilizan para restringir la sintaxis y especificar la semántica. Esta idea era bien conocida en ese momento, en particular Donald Knuth visitó el comité de desarrollo de ALGOL 68 durante el desarrollo de su propia versión. [1] Una característica interesante de las gramáticas B es su relación estricta con los atributos de cadena dados por una gramática CF, 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 y se les puede aplicar cualquier operación.

Después de ser presentado en el informe Algol 68, las gramáticas B se consideraron demasiado poderosas y sin restricciones para un uso práctico. En parte influenciado por cómo se aplicaron, el informe editado de Algol 68 contenía una gramática mucho más legible, mientras mantenía el formalismo adecuado de la gramática B.

En ese momento, quedó claro que las gramáticas B eran demasiado poderosas. Son Turing-completos, lo que hace que sea imposible analizarlos en absoluto: el problema de verificar si una gramática B dada puede generar una cadena dada es algorítmicamente irresoluble. Su uso debe estar severamente restringido para su uso en análisis o traducción automatizados. Se han desarrollado versiones limitadas y modificadas de gramáticas B para resolver este problema, en particular

Aplicaciones diferentes a ALGOL 68

Anthony Fisher escribió un analizador para una gran clase de gramáticas B [1] Archivado el 14 de diciembre de 2007 en Wayback Machine .

Dick Grune ha creado un programa en C que genera todo tipo de reglas de inferencia para una gramática de dos niveles [2] .

Las aplicaciones de las gramáticas de afijos extendidos mencionadas anteriormente pueden considerarse aplicaciones de las gramáticas B, ya que las gramáticas PA están bastante cerca de ellas.

También se han propuesto gramáticas B para describir acciones humanas complejas en ergonomía.

Enlaces

  1. [DE Knuth: La génesis de las gramáticas de atributos Archivado el 15 de julio de 2010 en Wayback Machine . Actas de la conferencia internacional sobre gramáticas de atributos y sus aplicaciones (1990), 1-12.]