Una gramática de afijos es un formalismo gramatical de dos niveles que se utiliza para describir la sintaxis de idiomas, principalmente 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 la 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 , Quartet 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 cuerda se publicó en 1968, como Mathematical Center Report 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 de los no terminales (los afijos ) se utilizan como argumentos. Si el mismo afijo aparece varias veces en una regla, su valor debe coincidir , es decir, debe ser el mismo en todas partes. En algunos tipos de gramática de afijos, son posibles relaciones más complejas entre valores de afijos.
Podemos describir un fragmento extremadamente simple de 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 gran variedad de oraciones en inglés; por lo que éste es un enfoque prometedor para describir la sintaxis del inglés.
Sin embargo, la gramática dada también describe oraciones como
Estas oraciones están equivocadas: en inglés, sujeto y verbo tienen un número gramatical , que debe coincidir.
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 en su lugar debería leerse
Esto también se puede incorporar utilizando afijos, si los medios para describir las relaciones entre diferentes valores de afijos son lo suficientemente potentes. Como se señaló anteriormente, estos medios dependen del tipo de gramática de afijos elegido.
En el tipo más simple de gramática de afijos, los afijos sólo pueden tomar valores de un dominio finito, y los valores de los afijos sólo 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 las reglas. Los rangos de valores permitidos para los afijos se pueden describir con reglas gramaticales libres de 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 . Estos 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 afijos sólo pueden manipularse con concatenación de cadenas, este formalismo es completo de Turing ; por lo tanto, incluso las preguntas más básicas sobre el lenguaje descrito por una gramática arbitraria de 2VW son indecidibles en general.
Las gramáticas de afijos 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 código escrito en algún lenguaje de programación. Se han utilizado dos enfoques básicos: