An attribute grammar is a formal way to define attributes

Attribute (computing)

In computing, an attribute is a specification that defines a property of an object, element, or file. It may also refer to or set the specific value for a given instance of such....

 for the productions of a formal grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree

Abstract syntax tree

In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...

, when the language is processed by some parser or compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

.

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

Intermediate language

In computer science, an intermediate language is the language of an abstract machine designed to aid in the analysis of computer programs. The term comes from their use in compilers, where a compiler first translates the source code of a program into a form more suitable for code-improving...

.

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

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

 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

S-attributed grammar

S-Attributed Grammars are a class of attribute grammars characterized by having no inherited attributes, but only synthesized attributes. Inherited attributes, which must be passed down from parent nodes to children nodes of the abstract syntax tree during the semantic analysis of the parsing...

.

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 be an Attribute grammar, where

• is the set of non terminal symbols
• is the set of terminal symbols
• is the set of productions
• is the distinguished symbol, that is the start symbol

is a synthesized attribute if,

• 
• 
• 
• 

Inherited Attributes

An Inherited Attribute at a node in parse tree is defined using the attibute 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

• S-attributed grammar
  S-attributed grammar
  S-Attributed Grammars are a class of attribute grammars characterized by having no inherited attributes, but only synthesized attributes. Inherited attributes, which must be passed down from parent nodes to children nodes of the abstract syntax tree during the semantic analysis of the parsing...
  
   : a simple type of attribute grammar, using only synthesized attributes, but no inherited attributes.
• L-attributed grammar
  L-attributed grammar
  L-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated in one left-to-right traversal of the abstract syntax tree. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in top-down parsing.Many programming...
  
   : inherited attributes can be evaluated in top-down parsing
  Top-down parsing
  Top-down parsing is a type of parsing strategy where in one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar...
  
  .
• LR-attributed grammar
  LR-attributed grammar
  LR-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated on LR parsing. As a result, attribute evaluation in LR-attributed grammars can be incorporated conveniently in bottom-up parsing. zyacc is based on LR-attributed grammars...
  
   : an L-attributed grammar whose inherited attributes can also be evaluated in bottom-up parsing
  Bottom-up parsing
  Bottom-up parsing is a strategy for analyzing unknown information that attempts to identify the most fundamental units first, and then to infer higher-order structures from them...
  
  .
• ECLR-attributed grammar
  ECLR-attributed grammar
  ECLR-attributed grammars are a special type of attribute grammars. They are a variant of LR-attributed grammars where an equivalence relation on inherited attributes is used to optimize attribute evaluation. EC stands for equivalence class. Rie is based on ECLR-attributed grammars...
  
   : equivalent classes can also be used to optimize the evaluation of inherited attributes.

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
  Aspect-oriented programming
  In computing, aspect-oriented programming is a programming paradigm which aims to increase modularity by allowing the separation of cross-cutting concerns...
  
   to functional programming
  Functional programming
  In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
  
   by helping writing catamorphism
  Catamorphism
  In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...
  
  s compositionally. It refers to the Utrecht University Attribute Grammar system as the implementation used in the examples.)
• Attribute grammar in relation to Haskell
  Haskell (programming language)
  Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
  
   and functional programming
  Functional programming
  In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
  
  .
• Semantics of context-free languages, by Don Knuth
  Donald Knuth
  Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
  
  , 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.