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

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add wikitechy.com to your ad blocking whitelist or disable your adblocking software.

×