Bottom Up Evaluation of S Attribute

An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values.
The evaluation 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:

Synthesized attributes - The value of a synthesized attribute is computed from the values of attributes at the children of that node in the parse tree.
Inherited attributes - The value of a inherited attribute is computed from the values of attributes at the siblings and parent of that node.

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.
Syntax-directed definitions with only synthesized attributes are called S-attributes. This is commonly used in LR parsers.
Only synthesized attributes appear in the syntax-directed definition in the following table for constructing the syntax tree for an expression.

Synthesized Attributes on the Parser Stack

A translator for an S-attributed definition can often be implemented with the help of an LR parser generator.
From an S-attributed definition, the parser generator can construct a translator that evaluates attributes as it parses the input.
A bottom-up parser uses a stack to hold information about subtrees that have been parsed. We can use extra fields in the parser stack to hold the values of synthesized attributes.
We put the values of the synthesized attributes of the grammar symbols into a parallel stack

When an entry of the parser stack holds a grammar symbol X the corresponding entry in the parallel stack will hold the synthesized attributes of the symbol X.

Example :
A -> XYZ
A.a = f(X.x , Y.y , Z.z) -> Synthesized attributes

Parser Stack

PDF