For example, we can parse the following expression according to the grammar:
X * 3 + 4
We can, by rule 1, replace the original expression with another expression (X * 3), an add_op (+), and
a term (4). By rule 2 the single-token term (4) can be replaced by a factor, which can, by rule 3 be replaced
by a number (4), which is a terminal for us.
It remains for us to parse the expression (X * 3). At this point, by rule 1 the only legal substitution for
(X * 3) is a term. By rule 2 the term (X * 3) can be replaced by another term (X), a mult_op (*), and
a factor (3). Again, rule 3 says the factor (3) can be replaced by a number (3), which is a terminal.
By rule 2 the term (X) can be replaced by a factor (X), which by rule 3 can be replaced by an identifier
(X), which we said was a terminal for us.
CHAP. 4] SOFTWARE 61
Such decomposition of a more complex expression into its terminals according to the rules of the grammar
is called a derivation. The result of a successful derivation is a parse tree or syntax tree. Here is the parse tree
for the derivation we just completed:
( X * 3 + 4 ) expression
/ | \
/ | \
(X * 3) + 4 expression add_op term
/ | \ 4 factor
/ | \ 4 number
/ | \
/ | \
X * 3 term mult_op factor
X factor 3 number
X identifier
To compute the meaning of the expression, the parse tree can be traversed from the bottom up, computing
the multiplication first and then performing the addition.
Pages:
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178