Java Reference
In-Depth Information
are all sentential forms. Clearly, any sentential form consisting solely of terminal symbols
is a sentence in the language.
An alternative representation of a derivation is the parse tree, a tree that illustrates the
derivation and the structure of an input string (at the leaves) from a start symbol (at the
root). For example, Figure 3.2 shows the parse tree for
id+id*id
.
FIGURE 3.2 A parse tree for
id+id*id
.
Consider the j-- grammar in Appendix B. In this grammar, compilationUnit is the start
symbol; from it one may derive syntactically legal j-- programs. Not every syntactically
legal j-- program is in fact a bona fide j-- program. For example, the grammar permits such
fragments as
5*true;
The j-- grammar in fact describes a superset of the programs in the j-- language. To
restrict this superset to the set of legal j-- programs, we need additional rules, such as
type rules requiring, for example, that the operands to
*
must be numbers. Type rules are
enforced during semantic analysis.
3.2.3 Ambiguous Grammars and Unambiguous Grammars
Given a grammar G, if there exists a sentence s in L(G) for which there are more than one
left-most derivations in G (or equivalently, either more than one right-most derivations, or
more than one parse tree for s in G), we say that the sentence s is ambiguous. Moreover,
if a grammar G describes at least one ambiguous sentence, the grammar G is ambiguous
(grammar). If there is no such sentence, that is, if every sentence is derivable by a unique
left-most (or right-most) derivation (or has a unique parse tree), we say the grammar is
unambiguous.
Example. Consider the grammar
E ::= E
+
E j E
*
E j
(
E
)
j
id
(3.11)
and, consider the sentence
id+id*id
. One left-most derivation for this sentence is
E
)
E
+
E
)
id+
E
)
id+
E
*
E
)
id+id*
E
)
id+id*id
Search WWH ::
Custom Search