Gramática de atributos

Tipo de gramática formal

Una gramática de atributos es una forma formal de complementar una gramática formal con el 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 en el árbol de sintaxis abstracta a cualquier otro lugar, de una manera controlada y formal. ^[1]

Cada función semántica se ocupa de los atributos de los símbolos que aparecen solo en una regla de producción: tanto los parámetros de la función semántica como su resultado son atributos de los símbolos de una regla en 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 denomina sintetizado ; de lo contrario, se denomina 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 puede utilizarse para describir toda la tarea que se realizará además del análisis sintáctico de una manera sencilla; en sistemas complicados, por ejemplo, al construir una herramienta de traducción de lenguajes, como un compilador, puede utilizarse para validar comprobaciones semánticas asociadas con una gramática, que representan las reglas de un lenguaje que no se imparten explícitamente en la definición de sintaxis. También puede utilizarse por analizadores sintácticos o compiladores para traducir el árbol sintáctico directamente en código para alguna máquina específica, o en 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] el autor de IMP .

Ejemplo

La siguiente es una gramática simple libre de contexto que puede describir un lenguaje compuesto de 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 atributos 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 los valores de los hijos deben calcularse primero, este es un ejemplo de propagación de abajo hacia arriba. ^[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 de inicio

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}$(ie 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 no terminal o 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 del padre o de los hermanos. Los atributos heredados son convenientes para expresar la dependencia de una construcción del lenguaje de programación en el contexto en el que aparece. Por ejemplo, podemos utilizar 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 del padre o de los 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. Del mismo modo, 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 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 utiliza solo atributos sintetizados , pero no atributos heredados.

Véase también

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

Referencias

1. Knuth 1968, pág. 134.
2. Knuth 1968, pág. 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, pág. 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 2020-05-19 . Consultado el 2018-03-23 ​​.{{cite journal}}: CS1 maint: bot: estado de URL original desconocido ( enlace ),

Enlaces externos

• Por qué son importantes las gramáticas de atributos, 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 manera compositiva . Hace referencia al sistema de gramática de atributos de la Universidad de Utrecht Archivado el 5 de junio de 2013 en Wayback Machine (véase 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 la programación funcional .
• Jukka Paakki: Paradigmas de gramática de atributos: una metodología de alto nivel para la implementación de lenguajes. ACM Computing Surveys 27 :2 (junio de 1995), 196–255.
• Ox es un sistema de compilación de gramática de atributos que amplía las especificaciones 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 Lex y Yacc ordinarias que construyen y decoran un árbol de análisis de atributos . Ox funciona 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 de GitHub). (Consulte el repositorio SourceForge).
• Silver es un lenguaje y sistema de especificación de gramática de atributos extensible de la Universidad de Minnesota. (Consulte también el repositorio de GitHub).