|
An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler. The attributes are divided into two groups: synthesized attributes and inherited attributes. The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes. In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down and across it. For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax definition. Attribute grammars can also be used to translate the syntax tree directly into code for some specific machine, or into some intermediate language. One strength of attribute grammars is that they can transport information from anywhere in the abstract syntax tree to anywhere else, in a controlled and formal way.
Example 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) ] Synthesized attributes Let G=<V_n,V_t,P,S> be an Attribute grammar, where - V_n is the set of non terminal symbols
- V_t is the set of terminal symbols
- P is the set of productions
- S is the distinguished symbol, that is the start symbol
A.a is a synthesized attribute if, - A \rightarrow \alpha \in P
- \alpha = \alpha_1 \ldots \alpha_n, \forall_{i, 1 \leq i \leq n}: \alpha_i \in (V_n \cup V_t)
- \{\alpha_{j1}, \ldots ,\alpha_{jm}\} \subseteq \{\alpha_1, \ldots ,\alpha_n\}
- A.a = f(\alpha_{j1}.a_1, \ldots ,\alpha_{jm}.a_m)
Inherited attributes 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. | Production rule | Semantic rule | | S T L | L.in:=T.type | | T int | T.type:=integer | | T float | T.type:=float | | T char | T.type:=char | | T double | T.type:=double | | L L1, id | L1.in=L.in enter_type(id.entry, L.in) | | L id | enter_type(id.entry, L.in) | Special types of attribute grammars See also External links - 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 as the implementation used in the examples.)
- Attribute grammar in relation to Haskell and functional programming.
- Semantics of context-free languages, by Don Knuth, is the original paper introducing attributed grammars.
- D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), LNCS, vol. 461, 1 12. Some informal, historical information.
- Jukka Paakki: Attribute grammar paradigms a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196 255.
de:Attributgrammatik fr:Grammaire attribu e nl:Attributengrammatica ja: pt:Gram tica de atributos
|
Encyclopedia
top
