Una gramática de atributos es una forma formal de definir atributos para las producciones de una gramática formal , asociando estos atributos con valores. La evaluación ocurre en los nodos del árbol de sintaxis abstracta , cuando el lenguaje es procesado por algún analizador o compilador .
Los atributos se dividen en dos grupos: atributos sintetizados y atributos heredados . Los atributos sintetizados son el resultado de las reglas de evaluación de atributos y también pueden usar los valores de los atributos heredados. Los atributos heredados se transmiten desde los nodos principales.
En algunos enfoques, los atributos sintetizados se utilizan para pasar información semántica por el árbol de análisis, mientras que los atributos heredados ayudan a transmitir la información semántica a través de él. Por ejemplo, al construir una herramienta de traducción de idiomas, como un compilador, se puede usar para asignar valores semánticos a construcciones de sintaxis. Además, es posible validar comprobaciones semánticas asociadas con una gramática, que representan las reglas de un lenguaje no impartidas explícitamente por la definición de sintaxis.
Las gramáticas de atributos también se pueden usar para traducir el árbol de sintaxis directamente en código para alguna máquina específica, o en algún lenguaje intermedio .
Uno de los puntos fuertes de las gramáticas de atributos es que pueden transportar información desde cualquier lugar del árbol de sintaxis abstracta a cualquier otro lugar, de forma controlada y formal. [ cita requerida ]
Historia
Las gramáticas de atributos fueron inventadas por Donald Knuth y Peter Wegner . [1] Si bien a Donald Knuth se le atribuye el concepto general, Peter Wegner inventó los atributos heredados durante una conversación con Knuth. Algunas ideas embrionarias se remontan [1] al trabajo de Edgar T. "Ned" Irons, [2] el autor de IMP .
Ejemplo
La siguiente es una gramática simple sin contexto que puede describir un lenguaje compuesto por multiplicaciones y sumas de números enteros.
Expr → Expr + Término Expr → Término Término → Término * Factor Término → Factor Factor → "(" Expr ")" Factor → entero
La siguiente gramática de atributos se puede utilizar para calcular el resultado de una expresión escrita en la gramática. Tenga en cuenta que esta gramática sólo utiliza valores sintetizados, y por lo tanto es una gramática S-atribuido .
Expr 1 → Expr 2 + Término [ Expr 1 .valor = Expr 2 .valor + Término .valor] Expr → Término [ Expr .valor = Término .valor] Término 1 → Término 2 * Factor [ Término 1 .valor = Término 2 . valor * Factor .valor] Término → Factor [ Término .valor = Factor .valor] Factor → "(" Expr ")" [ Factor .value = Expr .valor] Factor → entero [ Factor .value = strToInt ( entero .str) ]
Atributos sintetizados
Un atributo sintetizado se calcula a partir de los valores de los atributos de los hijos. Dado que los valores de los hijos deben calcularse primero, este es un ejemplo de propagación ascendente. Para definir formalmente un atributo sintetizado, dejemos ser una gramática formal, donde
- es el conjunto de símbolos no terminales
- es el conjunto de símbolos terminales
- es el conjunto de producciones
- es el símbolo distinguido o de inicio
Luego, dada una cadena de símbolos no terminales y un nombre de atributo , es un atributo sintetizado si se cumplen las tres condiciones:
- (es decir es una de las reglas de la gramática)
- (es decir, cada símbolo en el cuerpo de la regla es no terminal o terminal)
- , dónde (es decir, el valor del atributo es una función aplicado a algunos valores de los símbolos en el cuerpo de la regla)
Atributos heredados
Un atributo heredado en un nodo en el árbol de análisis se define utilizando los valores de atributo en el padre o los hermanos. Los atributos heredados son convenientes para expresar la dependencia de una construcción de lenguaje de programación del contexto en el que aparece. Por ejemplo, podemos usar un atributo heredado para realizar un seguimiento de si un identificador aparece en el lado izquierdo o derecho de una asignación para decidir si se necesita la dirección o el valor del identificador. A diferencia de los atributos sintetizados, los atributos heredados pueden tomar valores de los padres y / o hermanos. Como en la siguiente producción,
- S → ABC
donde A puede obtener valores de S, B y C. B puede tomar valores de S, A y C. Asimismo, C puede tomar valores de S, A y B.
Tipos especiales de gramáticas de atributos
- Gramática atribuida a L : los atributos heredados se pueden evaluar en un recorrido de izquierda a derecha del árbol de sintaxis abstracta
- Gramática atribuida a LR : una gramática atribuida a L cuyos atributos heredados también se pueden evaluar en el análisis de abajo hacia arriba .
- Gramática atribuida a ECLR : un subconjunto de gramáticas atribuidas a LR donde se pueden usar clases de equivalencia para optimizar la evaluación de atributos heredados.
- Gramática con atributos S : un tipo simple de gramática de atributos, que usa solo atributos sintetizados , pero no atributos heredados.
Ver también
Referencias
- ^ a b D. E. Knuth: La génesis de las gramáticas de atributos . Actas de la conferencia internacional sobre gramáticas de atributos y sus aplicaciones (1990), LNCS, vol. 461 , 1–12.
- ^ http://zzcad.com/ned.htm
enlaces externos
- ¿Por qué Atributo gramáticas Materia , El lector Mónada, Número 4, 5 de julio de 2005. narra (este artículo sobre cómo el formalismo de las gramáticas de atributos trae la programación orientada a aspectos de la programación funcional , ayudando a escribir catamorphisms compositivamente . Se refiere a la Atributo Universidad de Utrecht Gramática system (ver también Lrc: A Purely Functional, Higher-Order Attribute Grammar based System ) como la implementación utilizada en los ejemplos).
- Gramática de atributos en relación con Haskell y programación funcional .
- Semántica de lenguajes libres de contexto , de Don Knuth , es el artículo original que presenta gramáticas atribuidas
- Jukka Paakki: paradigmas de gramática de atributos : una metodología de alto nivel en la implementación del lenguaje . Encuestas de computación de ACM 27 : 2 (junio de 1995), 196-255.