Compiler Design and Construction - Old Questions

8.  What do you mean by S-attributed definition and how they are evaluated? Explain with example.

A syntax directed definition that uses synthesized attributes exclusively is said to be an S-attributed definition. A parse tree for S-attributed definition can always be annotated by evaluating the semantic rules for attributes at each node in bottom up manner. The evaluation of s-attributed definition is based on the Depth first Traversal (DFT) of the annotated tree.

Example for S-attributed definitions:

Let us consider the Grammar for arithmetic expressions:

Attributes in S-attributed definitions are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes.

Consider input string: 5+3*4 return

Depth first Traversal (DFT) of annotated graph: