Bottom Up Evaluation of S Attribute




Bottom Up Evaluation of S Attributed

  • 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.
S.no Production Semantic rule
1. E -> E1 + T E.node = new Node ('+', E1.node, T.node)
2 E -> E1 - T E.node = new Node ('-', E1.node, T.node)
3 E -> T E.node = T.node
4 T -> (E) T.node = E.node
5 T -> id T.node = new Leaf (id, id.entry)
6 T -> num T.node = new Leaf (num, num.val)

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

Parser Stack



Related Searches to Bottom Up Evaluation of S Attribute