Una gramática de afijos es un formalismo gramatical de dos niveles utilizado para describir la sintaxis de los lenguajes, principalmente los lenguajes informáticos , utilizando un enfoque basado en cómo se describe típicamente el lenguaje natural. [1]
El formalismo fue inventado en 1962 por Lambert Meertens mientras desarrollaba una gramática para generar oraciones en inglés. [2] Meertens también aplicó gramáticas de afijos a la descripción y composición de música, y obtuvo un premio especial del jurado en el Congreso de la Federación Internacional para el Procesamiento de la Información (IFIP) de 1968 en Edimburgo por su cuarteto de cuerdas generado por computadora , Cuarteto No. 1 en do mayor para 2 violines, viola y violonchelo, basado en la primera gramática de afijos no libre de contexto . [3] [4] El cuarteto de cuerdas se publicó en 1968, como Informe del Centro Matemático MR 96. [ 5]
Las reglas gramaticales de una gramática de afijos son las de una gramática libre de contexto , excepto que ciertas partes en los no terminales (los afijos ) se usan como argumentos. Si el mismo afijo aparece varias veces en una regla, su valor debe concordar , es decir, debe ser el mismo en todas partes. En algunos tipos de gramática de afijos, son posibles relaciones más complejas entre los valores de los afijos.
Podemos describir un fragmento extremadamente simple del inglés de la siguiente manera:
Esta gramática libre de contexto describe oraciones simples como
Con más sustantivos y verbos, y más reglas para introducir otras partes del discurso, se puede describir una amplia gama de oraciones en inglés, por lo que este es un enfoque prometedor para describir la sintaxis del inglés.
Sin embargo, la gramática dada también describe oraciones como
Estas oraciones son incorrectas: en inglés, el sujeto y el verbo tienen un número gramatical , que debe concordar.
Una gramática de afijos puede expresar esto directamente:
Esta gramática sólo describe oraciones correctas en inglés, aunque se podría argumentar que
Sigue siendo incorrecto y debería leerse en su lugar
Esto también se puede incorporar mediante afijos, si los medios para describir las relaciones entre los diferentes valores de afijos son lo suficientemente potentes. Como se señaló anteriormente, estos medios dependen del tipo de gramática de afijos elegida.
En el tipo más simple de gramática de afijos, los afijos solo pueden tomar valores de un dominio finito y los valores de los afijos solo pueden relacionarse mediante concordancia, como en el ejemplo. Aplicados de esta manera, los afijos aumentan la compacidad de las gramáticas, pero no añaden poder expresivo.
Otro enfoque es permitir que los afijos tomen cadenas arbitrarias como valores y permitir que se utilicen concatenaciones de afijos en reglas. Los rangos de valores permitidos para los afijos se pueden describir con reglas gramaticales independientes del contexto. Esto produce el formalismo de las gramáticas de dos niveles , también conocidas como gramáticas de Van Wijngaarden o gramáticas 2VW . Estas se han utilizado con éxito para describir lenguajes complicados, en particular, la sintaxis del lenguaje de programación Algol 68. Sin embargo, resulta que, aunque los valores de los afijos solo se pueden manipular con concatenación de cadenas, este formalismo es Turing completo ; por lo tanto, incluso las preguntas más básicas sobre el lenguaje descrito por una gramática 2VW arbitraria son indecidibles en general.
Las gramáticas afijas extendidas , desarrolladas en la década de 1980, son una versión más restringida de la misma idea. Se aplicaron principalmente para describir la gramática del lenguaje natural, por ejemplo, el inglés.
Otra posibilidad es permitir que los valores de los afijos se calculen mediante un código escrito en algún lenguaje de programación. Se han utilizado dos enfoques básicos: