However, this simpler grammar would also
allow a rightmost approach, with the following result:
( X * 3 + 4 ) expression
/ | \
/ | \
X * (3 + 4) expression operator expression
| \
X Identifier \
(3 + 4) expression operator expression
/ \
/ | \
/ | \
/ | \
3 number + 4 number
The meaning of the second parsing is very different from the first, because in the rightmost parsing the
addition occurs before the multiplication. That is not the customary hierarchy of operations, and the second
parse tree will, in general, produce a different value for the expression than the first.
Because the simpler grammar can produce two different and valid parse trees for the same expression, the
grammar is ambiguous. Programming language grammars must be unambiguous.
Look again at the first grammar, the more complex example, and notice how the grammar enforces a hierarchy
of operations; multiplication and division occur before addition or subtraction. Correct grammars place higher
???precedence??? operations lower in the cascade of productions.
Another key to a correctly specified grammar is the ???associativity??? of language elements. Does a mathematical
operator associate left to right, or right to left? This makes a difference with expressions like (9 - 4 - 2).
Pages:
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181