|
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
|