Una gramática de afijos es una especie de gramática formal ; se utiliza 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]
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.
Ejemplo
Podemos describir un fragmento extremadamente simple de inglés de la siguiente manera:
- Oración → Predicado sujeto
- Asunto → Sustantivo
- Predicado → Objeto de verbo
- Objeto → Sustantivo
- Sustantivo → John
- Sustantivo → María
- Sustantivo → niños
- Sustantivo → padres
- Verbo → me gusta
- Verbo → me gusta
- Verbo → ayuda
- Verbo → ayuda
Esta gramática libre de contexto describe oraciones simples como
- A John le gustan los niños
- María ayuda a Juan
- los niños ayudan a los padres
- padres como John
Con más sustantivos y verbos, y más reglas para introducir otras partes del habla, se puede describir una gran variedad 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
- A John le gustan los niños
- los niños ayudan a los padres
Estas oraciones son incorrectas: en inglés, el sujeto y el verbo tienen un número gramatical que debe coincidir.
Una gramática de afijos puede expresar esto directamente:
- Oración → Sujeto + número Predicado + número
- Asunto + número → Sustantivo + número
- Predicado + número → Verbo + número Objeto
- Objeto → Sustantivo + número
- Sustantivo + singular → John
- Sustantivo + singular → María
- Sustantivo + plural → niños
- Sustantivo + plural → padres
- Verbo + singular → me gusta
- Verbo + plural → me gusta
- Verbo + singular → ayuda
- Verbo + plural → ayuda
Esta gramática solo describe oraciones correctas en inglés, aunque se podría argumentar que
- A John le gusta John
sigue siendo incorrecto y en su lugar debería leer
- John se gusta a sí mismo
Esto también puede incorporarse mediante 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 afijo elegido.
Tipos
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 afijos solo pueden relacionarse mediante un acuerdo, 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 usen 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 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 solo pueden manipularse con la 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 de afijo 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:
- En las gramáticas de atributos , los afijos (llamados atributos) pueden tomar valores de dominios arbitrarios (por ejemplo, números enteros o reales, estructuras de datos complejas) y se pueden especificar funciones arbitrarias, escritas en un idioma de elección, para describir cómo se derivan los valores de afijos en las reglas. de cada uno.
- En CDL (el lenguaje de descripción del compilador ) y su sucesor CDL2 , desarrollado en la década de 1970, los fragmentos de código fuente (generalmente en lenguaje ensamblador ) se pueden usar en reglas en lugar de los lados derechos normales, lo que permite primitivas para el escaneo de entrada y cálculos de valores de afijos. para ser expresado directamente. Diseñado como base para la construcción práctica de compiladores , este enfoque se utilizó para escribir compiladores y otro software, por ejemplo, un editor de texto .
Referencias
- ^ Koster, Cornelis HA. " Adjuntar gramáticas para lenguajes naturales ". Gramáticas de atributos, aplicaciones y sistemas. Springer, Berlín, Heidelberg, 1991.