Gramática de atributos

Una gramática de atributos es una forma formal de complementar una gramática formal con procesamiento de información semántica. La información semántica se almacena en atributos asociados con símbolos terminales y no terminales de la gramática. Los valores de los atributos son el resultado de reglas de evaluación de atributos asociadas con producciones de la gramática. Los atributos permiten la transferencia de información desde cualquier lugar del árbol de sintaxis abstracta a cualquier otro lugar, de forma controlada y formal. ^[1]

Cada función semántica trata con atributos de símbolos que ocurren sólo en una regla de producción: tanto los parámetros de la función semántica como su resultado son atributos de símbolos de una regla particular. Cuando una función semántica define el valor de un atributo del símbolo en el lado izquierdo de la regla, el atributo se llama sintetizado ; de lo contrario se llama heredado . ^[2] Por lo tanto, los atributos sintetizados sirven para pasar información semántica hacia arriba en el árbol de análisis, mientras que los atributos heredados permiten que los valores se pasen desde los nodos principales hacia abajo y a través del árbol de sintaxis.

En aplicaciones simples, como la evaluación de expresiones aritméticas, la gramática de atributos se puede utilizar para describir toda la tarea a realizar además del análisis sintáctico de manera sencilla; en sistemas complicados, por ejemplo, al construir una herramienta de traducción de idiomas, como un compilador, se puede utilizar para validar comprobaciones semánticas asociadas con una gramática, que representa las reglas de un idioma que no se imparten explícitamente en la definición de sintaxis. También puede ser utilizado por analizadores o compiladores para traducir el árbol de sintaxis directamente a código para alguna máquina específica o a algún lenguaje intermedio .

Historia

Las gramáticas de atributos fueron inventadas por Donald Knuth y Peter Wegner . ^[3] 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 ^[3] al trabajo de Edgar T. "Ned" Irons, ^[4] autor de IMP .

Ejemplo

La siguiente es una gramática simple y libre de contexto que puede describir un lenguaje compuesto por multiplicación y suma 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 solo utiliza valores sintetizados y, por lo tanto, es una gramática con atributo S.

 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 .valor = Expr .valor ] Factor → entero [ Factor .valor = strToInt( entero .str) ]

Atributos sintetizados

Un atributo sintetizado se calcula a partir de los valores de los atributos de los hijos. Dado que primero se deben calcular los valores de los hijos, este es un ejemplo de propagación ascendente. ^[5] Para definir formalmente un atributo sintetizado, sea una gramática formal, donde ${\displaystyle G=\langle V_{n},V_{t},P,S\rangle }$

• ${\displaystyle V_{n}}$es el conjunto de símbolos no terminales
• ${\displaystyle V_{t}}$es el conjunto de símbolos terminales
• ${\displaystyle P}$es el conjunto de producciones
• ${\displaystyle S}$es el símbolo distinguido o inicial

Entonces, dada una cadena de símbolos no terminales y un nombre de atributo , es un atributo sintetizado si se cumplen estas tres condiciones: ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle A.a}$

• ${\displaystyle A\rightarrow \alpha \in P}$(es decir, es una de las reglas de la gramática) ${\displaystyle A\rightarrow \alpha }$
• ${\displaystyle \alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})}$(es decir, cada símbolo en el cuerpo de la regla es terminal o no terminal)
• ${\displaystyle A.a=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})}$, donde (es decir, el valor del atributo es una función aplicada a algunos valores de los símbolos en el cuerpo de la regla) ${\displaystyle \{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}}$ ${\displaystyle f}$

Atributos heredados

Un atributo heredado en un nodo del á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 → A B C

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 con atributos L : los atributos heredados se pueden evaluar en un recorrido de izquierda a derecha del árbol de sintaxis abstracta
• Gramática con atributos LR : una gramática con atributos L cuyos atributos heredados también se pueden evaluar en un análisis ascendente .
• Gramática con atributos ECLR : un subconjunto de gramáticas con atributos LR donde se pueden utilizar 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 utiliza solo atributos sintetizados , pero no atributos heredados.

Ver también

• Gramática de afijos
• Gramática de Van Wijngaarden
• Traducción dirigida por la sintaxis

Referencias

1. Knuth 1968, pag. 134.
2. Knuth 1968, pag. 132.
3. DE 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.
4. "Principal".
5. Knuth 1968, pag. 130.

• Artículo original que presenta gramáticas atribuidas: Knuth, Donald E. (1968). "Semántica de lenguajes libres de contexto" (PDF) . Teoría de Sistemas Matemáticos . 2 (2): 127–145. doi :10.1007/BF01692511. S2CID  5182310. Archivado desde el original el 19 de mayo de 2020 . Consultado el 23 de marzo de 2018 .{{cite journal}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace ),

enlaces externos

• Why Attribute Grammars Matter, The Monad Reader, número 4, 5 de julio de 2005. (Este artículo narra cómo el formalismo de las gramáticas de atributos lleva la programación orientada a aspectos a la programación funcional al ayudar a escribir catamorfismos de composición . Se refiere a la gramática de atributos de la Universidad de Utrecht. Archivado el 5 de junio de 2013 en el sistema Wayback Machine (consulte también Lrc: un sistema puramente funcional y basado en gramática de atributos de orden superior) como la implementación utilizada en los ejemplos).
• Gramática de atributos en relación con Haskell y la programación funcional .
• Jukka Paakki: Paradigmas gramaticales de atributos: una metodología de alto nivel en la implementación del lenguaje. ACM Computing Surveys 27 :2 (junio de 1995), 196–255.
• Ox es un sistema de compilación de gramática de atributos que aumenta las especificaciones de Lex y Yacc con definiciones de atributos sintetizados y heredados escritos en una combinación de sintaxis Ox y C / C++ . A partir de estas especificaciones, Ox genera especificaciones ordinarias de Lex y Yacc que construyen y decoran un árbol de análisis de atributos . Ox trabaja con las versiones Lex y Yacc distribuidas en los sistemas operativos Unix y Solaris , Flex , RE/flex , Bison , BYacc , BtYacc y MSTA (en el repositorio DINO GitHub). (Consulte el repositorio de SourceForge).
• Silver es un lenguaje y sistema de especificación gramática de atributos extensibles de la Universidad de Minnesota. (Consulte también el repositorio de GitHub).