|
You have seen that tokens can have attributes that provide additional information. Often, the attribute of a token is the lexeme that was read.
Nonterminals can also have attributes.
To be more precise, an occurrence of a nonterminal on the right-hand side of a production can have an attribute. But it is easier to discuss the attribute of a nonterminal, meaning of a particular occurrence.
If nonterminal N has an attribute then each node of a parse tree that is labeled by N has such an attribute attached to it.
To illustrate, let's use or simple expression grammar. Each n token has an integer attribute that is defined by the lexer.
Let's make each node that is labeled by a nonterminal have an attribute that is the value of the expression in that node's subtree.
Here is a parse tree for (15 + 3) * 2. The attribute of each node is written beside the node.
E(36)
|
T(36)
/|\
/ | \
/ | \
/ | \
/ | \
T(18) * F(2)
| |
F(18) n(2)
/|\
/ | \
/ | \
/ | \
( E(18) )
/|\
/ | \
/ | \
E(15) + T(3)
| |
T(15) F(3)
| |
F(15) n(3)
|
n(15)
Although the attribute of a nonterminal can be whatever you want it to be, it is often an abstract syntax tree.
For example, here is a parse tree of (15+3)*2 where the attribute of each internal node is an abstract syntax tree.
E(t5)
|
T(t5)
/|\
/ | \
/ | \
/ | \
/ | \
T(t3) * F(t4)
| |
F(t3) n(2)
/|\
/ | \
/ | \
/ | \
( E(t3) )
/|\
/ | \
/ | \
E(t1) + T(t2)
| |
T(t1) F(t2)
| |
F(t1) n(3)
|
n(15)
Abstract syntax trees t1, t2, … are all in the following diagram.
t1→ *
/ \
t3→ + 2 ← t4
/ \
t1→ 15 3 ←t2
|