# Difference between revisions of "Attribute Grammar"

Line 3: | Line 3: | ||

- S is a distinguished symbol of N; | - S is a distinguished symbol of N; | ||

- P is a finite non-empty set pairs (L,R) such that L and R are in (N U T)*; | - P is a finite non-empty set pairs (L,R) such that L and R are in (N U T)*; | ||

− | - A is the union of the inherited and | + | - A is the union of the inherited and synthesized attributes of a non-terminal X in (N U T)* (if X in N then A(ttributes) (X) = S(inthesized)A(ttributes) U I(nherited)A(ttributes) and the intersection of this two sets is empty; if X in T then A(X) = SA(X) and A(S) = SA(S)); |

- R = U R(p) is a set of evaluation rules, | - R = U R(p) is a set of evaluation rules, | ||

- CC = U CC(p) is a set of contextual conditions | - CC = U CC(p) is a set of contextual conditions |

## Revision as of 19:21, 15 December 2012

An attribute grammar is an ordered eighttuple AG = (T, N, S, P, A, R, CC, TR) , where:
- N and T are finite alphabets;
- S is a distinguished symbol of N;
- P is a finite non-empty set pairs (L,R) such that L and R are in (N U T)*;
- A is the union of the inherited and synthesized attributes of a non-terminal X in (N U T)* (if X in N then A(ttributes) (X) = S(inthesized)A(ttributes) U I(nherited)A(ttributes) and the intersection of this two sets is empty; if X in T then A(X) = SA(X) and A(S) = SA(S));
- R = U R(p) is a set of evaluation rules,
- CC = U CC(p) is a set of contextual conditions
- and TR is a set of translation rules.

An attribute grammar is a formalism to specify the syntax and semantics of a language; it defines the information that will need to be in the abstract syntax tree to successfully perform semantic analysis and code generation. This information is stored as attributes of the nodes of the abstract syntax tree.

The attributes (see also: Attributes) are divided into two groups, called synthesized attributes and inherited attributes.

- The
**synthesized attributes**of a symbol X0, at the root of a tree, store the values that result from attribute evaluation rules using the values of the synthesized attributes of its children nodes (Y1 to Yn) and its own inherited attributes. - The
**inherited attributes**of a symbol Yi, i=1..n, at the leaves of a tree, store the values that result from attribute evaluation rules using the values of the synthesized attributes of its sibling nodes and inherited attributes of its parent node (the root of that tree).

Basically, synthesized attributes are used to pass semantic information up the parse tree (from leaves to the root), while inherited attributes are used to pass semantic information down the parse tree (propagating values from the root to the leaves). The first is information extracted (directly or after some computation) from the present substring, of the source text, under analysis and processing; the second corresponds to information, available from the context (substrings before or after), that should be taken into consideration for processing the present substring of the source text.