Attribute Grammars
Attributes in grammar symbols form a fundamental concept in compiler design, especially in semantic analysis. Attributes provide a way to associate information with each grammar symbol. This information is used to store properties of language constructs like the datatype, number of digits in a number, the value of a constant, etc. When the parser recognizes a language construct represented by a grammar symbol, it uses the attribute values to build other attributes or the abstract syntax tree. These attributes may be used later in the symbol table.
During analysis, the parser computes the values of the attributes. This is called syntax-directed evaluation and provides a simple form of semantics. Syntax-directed translates a sequence of input symbols (such as a source program) into an output sequence (such as object code) by means of a syntax-directed translator (often integrated with the parsing process). This method is based on the grammar and its added semantic rules, linking the grammar productions with actions to be performed when these productions are used during parsing. The semantic rules can access and manipulate the attributes of grammar symbols.
The attributes are usually divided into two groups, according with their dependencies on the parse tree:
- Synthesized Attributes: These attributes are calculated from attribute values of the child nodes. Their value depends only on the values in the children of their node. For example, in a grammar representing arithmetic expressions, the value of an expression could be a synthesized attribute computed from the values of its sub-expressions.
- Inherited Attributes: These attributes get their values from the parent node and/or from their siblings. Their value depends on the nodes' parent and/or siblings in the parse tree. For example, in a language where variables must be declared before use, an attribute of a variable-use node could be inherited from an ancestor node where the variable was declared.
Attribute Types and Parser Actions
Depending on the type of parser (frequently, top-down or bottom-up), and the type of attribute, attribute computation may occur in specific ways for each grammar type:
- S-Attributed Grammars: In these grammars, attribute values are only synthesized; that is, they depend only on the attribute values of their children. This makes S-attributed grammars simpler and often easier to manage. S-attributed grammars are well-suited to "bottom-up" or "rightmost" parsing methods, like LR parsing, where nodes corresponding to the right-hand side of a production are created before the node for the left-hand side.
- L-Attributed Grammars: These grammars allow attributes to be inherited as well as synthesized, but with a restriction: an attribute can only inherit from the left, meaning that inherited attributes are dependent on either the attributes of the parent node, or the attributes of siblings to the left (i.e., previously processed siblings). This restriction makes L-attributed grammars suitable for "left-to-right" parsing methods. Both top-down (like LL parsing) and bottom-up parsers (with some restrictions) can handle L-attributed grammars.
Exercises