Attribute grammar
From Free net encyclopedia
Attribute grammar is a formal way to define attributes for the productions of a grammar, associating this attributes to values. The evaluation of the attributes 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, called synthesised attributes and inherited attributes. The synthesised attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are, as the name says, inherited from parent nodes.
In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes are used to pass semantic information down the parse tree. 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.
Attribute grammars can also be used to translate the syntax tree directly into code for some specific machine, or into some intermediate language.
The 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.
Types of attribute grammars
External links
- Why Attribute Grammars Matter, The Monad Reader, Issue 4, July 5th 2005
- Semantics of context-free grammars, 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), 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.