Attribute grammar

An attribute grammar is a context-free grammar is extended to include attributes, rules and conditions for these attributes. Applied the concept is in the compiler to check the compliance of rules that can not be formulated with context-free grammars. These rules are, for example, that each variable must be declared and their data type is used accordingly.

A compiler checks compliance with these rules during semantic analysis. He has only the information available, which are included in the syntax tree of the program. Additional information which may facilitate the semantic analysis, one can integrate as attributes in the syntax tree.

For example, the type of an expression can be annotated as an attribute to the appropriate node in the syntax tree. Through attribute rules and conditions dependencies (also other node in the syntax tree ) can also be specified by other attributes.

The programming of the relevant parts of the compiler is simplified if the productions of the grammar are even provided with appropriate attributes.

Notation

  • Is an attribute associated with a non-terminal production, with.

Definitions

Is an attribute grammar which is defined by the following components:

  • Is a context-free grammar.
  • Is a finite set of attributes, each of which is uniquely associated with a symbol. The individual attribute sets are disjoint, it is so.
  • Is a finite set of Attributionsregeln.
  • Is a finite set of conditions. The condition of production can be regarded as an attribute in the form of the left side, therefore, the attributes are also all of the conditions detected.
  • Is the set of attributes which are defined in the rules of the production.

The attributes of a symbol can be divided into two disjoint classes divide, as there are for all attributes only a calculation rule of the form in:

  • Is the set of synthesized ( derived ) attributes. These are the attributes that are defined in the rules of the production, which is on the left.
  • Is the set of hereditary ( inherited) attributes. These are the attributes that are defined in the rules of the production, which is on the right side.

Circularity

Attribute grammars are circular, if the dependency graph of the attribute variables, which is induced by the functional dependency contains a loop.

This circularity can be tested in exponential time.

A simplified test that allows less grammar, calculates the problem in polynomial time.

Grammar types

S- attribute grammars

S- attribute grammars, attribute grammars are briefly SAG who work only on synthetic attributes. Thus, they can be calculated directly from the Reduce- steps of the parse process of LR ( k) parser. Implemented in yacc.

L- attribute grammars

L- attribute grammars (LAG ) can be evaluated by the abstract syntax tree in a top-down pass from left to right. They can be evaluated for each LL grammar and thus be used for Pascal -like programming languages. These only derived and the following parts of the tree are allowed to access current attributes.

Example:

This facilitates the forward declaration of variables and functions.

LR- attributed grammars

A subclass of L- attribute grammars, precisely those that can be evaluated in a single pass from left to right during LR- parsing. Implementation: zyacc; implemented in yacc by hand using global variables. The advantage of the greater power of the LR parsing compared to the LL- parsing thus manifests itself in mirror image at a disadvantage to the smaller thickness of the LR- attributed grammars with respect to the L- attribute grammars.

ECLR attribute grammars

A variant of the LR- attributed grammars; it uses an equivalence relation, in order to optimize the evaluation attribute. Implementation: rie.

  • Compiler
  • Theory of formal languages
Compiler construction Declaration (computer programming) Disjoint sets LL-Parser
87558
de