|
A Synthesized attribute is an attribute of the nonterminal on the left-hand side of a production.
All of the attributes that we have used so far have been synthesized. Synthesized attributes represent information that is being passed up the parse tree.
In general, attribute equations are allowed to define attributes of any of the nonterminals in a production, even those on the right-hand side.
An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute.
Recall that a top-down parser needs a left-factored grammar. Let's look at such a grammar and derive attribute equations for it. The grammar is as follows.
| E | → | T R |
| R | → | ε |
| R | → | + E |
| T | → | F S |
| S | → | ε |
| S | → | * T |
| F | → | n |
| F | → | ( E ) |
Suppose that our goal is to associate an attribute of each E, T and F node that is the value of the expression.
Look at the following parse tree.
E
/ \
/ \
T R
/ \ |
/ \ ε
F S
| / \
3 * T
/ \
F S
| |
5 ε
Each F node gets its value from the n token. But an S node that uses production S → * T needs to get the left-hand operand of * from its left sibling. The information needs to go across the tree.
Here is the tree with attributes shown.
E(val = 8)
/ \
/ \
/ \
/ \
/ \
T(val = 8) R(inh = 8, val = 8)
/ \ |
/ \ ε
/ \
/ \
/ \
F(val = 3) S(inh = 3, val = 8)
| / \
3 * T(val = 5)
/ \
/ \
/ \
/ \
F(val = 5) S(inh = 5, val = 5)
| |
5 ε
Here are attribute equations that accomplish this.
| Production | Semantic rule | ||
|---|---|---|---|
| E → T R |
|
||
| R → ε | R.val = R.inh | ||
| R → + E | R.val = R.inh + E.val | ||
| T → F S |
|
||
| S → ε | S.val = S.inh | ||
| S → * T | S.val = S.inh * T.val | ||
| F → n | F.val = n.val | ||
| F → ( E ) | F.val = E.val |
Attribute equations only have one restriction: They must not be cyclic. You cannot
But that does not prevent an attribute of one node in a parse tree from depending on an attribute of a node that will not be created until later.
(To handle that, the attribute equation solver would need to defer an equation until it could be used.)
Normally, compiler designers avoid really strange attribute equations.
A set of attribute equations is L-attributed if each equation can be processed at the point where it is written. Specifically,
Synthesized attributes are allowed in L-attributed definitions.
Suppose that an attribute equation associated with production A → X1 X2 … Xn defines an attribute of Xi.
The right-hand side of that equation can use:
Inherited attributes in an L-attributed set of equations are easy to handle by recursive descent.
A synthesized attribute is a value returned by a syntactic function.
An inherited attribute is a parameter that is passed to a syntactic function.
That explains why the functions in the recursive-descent example are written the way they are.
A recursive descent parser makes one downward pass over the parse tree and one upward pass. The downward pass makes handling of inherited attributes easy.
But an LR parser only makes one pass up the parse tree. That makes handling inherited attributes tricky.
Recall that you use $1 for the attribute of the first thing on the right-hand side of a production, $2 for the second thing, etc.
You can also look at other attributes that are sitting in the stack. $0 is the attribute of the thing that immediately precedes this production, $−1 is the one before that, etc.
A catch is that Bison does not know the type of $0, $−1, etc. So you must provide it. $<intval>0 is $0, but understood to use the intval field of YYSTYPE.
Be careful with this. It requires that you know what will be on the stack when a particular rule reduces.
|