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.
|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.
A -> XYZ
A.a = f(X.x , Y.y , Z.z) -> Synthesized attributes