Java Reference
In-Depth Information
nonterminal is always expanded. This derivation sequence may seem less
intuitive given the English convention of processing information left to right.
However, such derivations are produced by an important class of parsers,
namely the bottom-up parsers discussed in Chapter 6.
As a bottom-up parser discovers the productions that derive a given token
sequence, it traces a rightmost derivation, but the productions are applied in
reverse order
. That is, the last step taken in a rightmost derivation is the first
production applied by the bottom-up parser; the first step involving the start
symbol is the parser's final production. The sequence of productions applied
by a bottom-up parser is called a
rightmost
or
canonical
parse. For derivations
that are rightmost, the notation
⇒
rm
is used. A sentential
form produced via a rightmost derivation is called a
right sentential form
.A
rightmost derivation of the grammar shown in Figure 4.1 is as follows.
⇒
rm
,
⇒
rm
,and
E
⇒
rm
Prefix ( E )
⇒
rm
Prefix ( v Tail )
⇒
rm
Prefix ( v + E )
⇒
rm
Prefix(v+vTail)
⇒
rm
Prefix(v+v)
⇒
rm
f(v+v)
A derivation is often represented by a
parse tree
(sometimes called a
derivation
tree
). A
parse tree
has the following characteristics:
•
It is rooted by the grammar's start symbol S.
•
Each node is either a grammar symbol or
λ
.
•
Its interior nodes are nonterminals. An interior node and its children
represent the application of a production. That is, a node representing
anonterminalA can have o
ff
spring
X
,X
,...,X
m
if, and only if, there
1
2
exists a grammar production A
X
m
.Whenaderiva ionis
complete, each leaf of the corresponding parse tree is either a terminal
symbol or
→X
X
2
...
1
λ
.
Figure 4.2 shows the parse tree for f(v+v)using the grammar fromFigure 4.1.
Parse trees serve nicely to visualize how a string is structured by a grammar.
A leftmost or rightmost derivation is essentially a textual representation of a
parse tree, but the derivation also conveys the order in which the productions
are applied.
A sentential form is derivable from a grammar's start symbol. Hence,
a parse tree must exist for every sentential form. Given a sentential form
