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