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