RSS
Twitter
Facebook
SDDs
are useful for is construction of syntax trees. A syntax tree is a condensed form
of parse tree.
• Syntax trees are useful for representing
programming language constructs like expressions and statements.
• They help compiler design by decoupling
parsing from translation.
• Each node of a syntax tree represents a
construct; the children of the node represent the meaningful components of the
construct.
• e.g.
a syntax-tree node representing an expression E1 + E2 has label
+
and
two children representing the sub expressions E1 and E2
• Each node is implemented by objects with
suitable number of fields; each object will have an op
field that is the label of the node with additional
fields as follows:
_ If
the node is a leaf, an additional field holds the lexical value for the
leaf
. This is created by function Leaf(op, val)
_ If
the node is an interior node, there are as many fields as the node has
children
in the syntax tree. This is created by function Node(op,
c1, c2,...,ck) .
Example:
The S-attributed definition in figure below constructs syntax trees for a
simple expression grammar involving only the binary operators + and -. As
usual, these operators are at the same precedence level and are jointly left
associative. All nonterminals have one synthesized attribute node,
which represents a node of the syntax tree.
Syntax
tree for a-4+c using the above SDD is shown below.
Steps
in the construction of the syntax tree for a-4+c
If
the rules are evaluated during a post order traversal of the parse tree, or
with reductions during a bottom-up parse, then the sequence of steps shown
below ends with p5 pointing to the root of the constructed syntax tree.
Constructing
Syntax Trees during Top-Down Parsing
With
a grammar designed for top-down parsing, the same syntax trees areconstructed, using
the same sequence of steps, even though the structure of the parse trees
differs significantly from that of syntax trees. The L-attributed definition
below performs the same translation as the S-attributed definition shown
before.
Dependency
Graph for a-4+c with L-Attributed SDD
Structure
of a Type
This
is an example of how inherited attributes can be used to carry information one
part of the parse tree to another. In C, the type int [2][3] can be read as,
"array of 2 arrays of 3 integers." The corresponding type expression
array(2, array(3, integer)) is represented by the tree as shown below.
The
nonterminals B and T have a synthesized attribute t representing a type. The nonterminal
C has two attributes: an inherited attribute b and a synthesized attribute t. The
inherited b attributes pass a basic type down the tree, and the synthesized t
attributes accumulate the result.
An
annotated parse tree for the input string int [2][3]
is shown below. The corresponding type expression is constructed by passing the
type integer from B, down the chain of C's through the inherited attributes b.
The array type is synthesized up the chain of C's through the attributes t.
0 comments