Attribute grammar

Attribute grammars were invented by Donald Knuth and Peter Wegner.[3] While Donald Knuth is credited for the overall concept, Peter Wegner invented inherited attributes during a conversation with Knuth. Some embryonic ideas trace back[3] to the work of Edgar T. "Ned" Irons,[4] the author of IMP.

The following is a simple context-free grammar which can describe a language made up of multiplication and addition of integers.

 Expr → Expr + Term
 Expr → Term
 Term → Term * Factor
 Term → Factor
 Factor → "(" Expr ")"
 Factor → integer

The following attribute grammar can be used to calculate the result of an expression written in the grammar. Note that this grammar only uses synthesized values, and is therefore an S-attributed grammar.

 Expr1 → Expr2 + Term [ Expr1.value = Expr2.value + Term.value ]
 Expr → Term [ Expr.value = Term.value ]
 Term1 → Term2 * Factor [ Term1.value = Term2.value * Factor.value ]
 Term → Factor [ Term.value = Factor.value ]
 Factor → "(" Expr ")" [ Factor.value =  Expr.value ]
 Factor → integer [ Factor.value = strToInt(integer.str) ]

A synthesized attribute is computed from the values of attributes of the children. Since the values of the children must be computed first, this is an example of bottom-up propagation.[5] To formally define a synthesized attribute, let ${\displaystyle G=\langle V_{n},V_{t},P,S\rangle }$ be a formal grammar, where

• ${\displaystyle V_{n}}$ is the set of non terminal symbols
• ${\displaystyle V_{t}}$ is the set of terminal symbols
• ${\displaystyle P}$ is the set of productions
• ${\displaystyle S}$ is the distinguished, or start, symbol

Then, given a string of nonterminal symbols ${\displaystyle A}$ and an attribute name ${\displaystyle a}$, ${\displaystyle A.a}$ is a synthesized attribute if all three of these conditions are met:

• ${\displaystyle A\rightarrow \alpha \in P}$ (i.e. ${\displaystyle A\rightarrow \alpha }$ is one of the rules in the grammar)
• ${\displaystyle \alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})}$ (i.e. every symbol in the body of the rule is either nonterminal or terminal)
• ${\displaystyle A.a=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})}$, where ${\displaystyle \{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}}$ (i.e. the value of the attribute is a function ${\displaystyle f}$ applied to some values from the symbols in the body of the rule)

An inherited attribute at a node in parse tree is defined using the attribute values at the parent or siblings. Inherited attributes are convenient for expressing the dependence of a programming language construct on the context in which it appears. For example, we can use an inherited attribute to keep track of whether an identifier appears on the left or the right side of an assignment in order to decide whether the address or the value of the identifier is needed. In contrast to synthesized attributes, inherited attributes can take values from parent and/or siblings. As in the following production,

S → ABC

where A can get values from S, B, and C. B can take values from S, A, and C. Likewise, C can take values from S, A, and B.

• L-attributed grammar: inherited attributes can be evaluated in one left-to-right traversal of the abstract syntax tree
• LR-attributed grammar: an L-attributed grammar whose inherited attributes can also be evaluated in bottom-up parsing.
• ECLR-attributed grammar: a subset of LR-attributed grammars where equivalence classes can be used to optimize the evaluation of inherited attributes.
• S-attributed grammar: a simple type of attribute grammar, using only synthesized attributes, but no inherited attributes

• Affix grammar
• Van Wijngaarden grammar
• Syntax-directed translation

• Original paper introducing attributed grammars: Knuth, Donald E. (1968). "Semantics of context-free languages" (PDF). Mathematical Systems Theory. 2 (2): 127–145. doi:10.1007/BF01692511. S2CID 5182310. Archived from the original on 2020-05-19. Retrieved 2018-03-23.{{cite journal}}: CS1 maint: bot: original URL status unknown (link),

• Why Attribute Grammars Matter, The Monad Reader, Issue 4, July 5, 2005. (This article narrates on how the formalism of attribute grammars brings aspect-oriented programming to functional programming by helping writing catamorphisms compositionally. It refers to the Utrecht University Attribute Grammar system (see also Lrc: A Purely Functional, Higher-Order Attribute Grammar based System) as the implementation used in the examples.)
• Attribute grammar in relation to Haskell and functional programming.
• Jukka Paakki: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196–255.
• Ox is an attribute grammar compiling system that augments Lex and Yacc specifications with definitions of synthesized and inherited attributes written in a combination of Ox and C/C++ syntax. From these specifications, Ox generates ordinary Lex and Yacc specifications that build and decorate an attributed parse tree. Ox works with the Lex and Yacc versions distributed in the Unix and Solaris operating systems, Flex, RE/flex, Bison, BYacc, BtYacc and MSTA (in the DINO GitHub repository). (See the SourceForge repository.)
• Silver is an extensible attribute grammar specification language and system from University of Minnesota. (See also the GitHub repository.)