Java Reference
In-Depth Information
), the syntax
modifications are usually prototyped using the language's grammar. Analysis
performed by the parser generator can reveal problems with the proposed
syntax extensions. By proceeding carefully, a language designer can ensure
that old programs retain their meaning in the extended language.
When language extensions are considered (e.g., C to C
++
In Chapter 5, we learned how to construct top-down (also called LL)parsers
based on
context-free grammars
(CFGs) that had certain properties. The
fundamental concern of an LL parser is which production to choose in ex-
panding a given nonterminal. This choice is based on the parser's current
state and on a peek at the unconsumed portion of the parser's input string.
The derivations and parse trees produced by LL parsers are constructed as
follows: the leftmost nonterminal is expanded at each step, and the parse tree
grows systematically—top-down, from left to right. The LL parser begins with
the tree's root, which is labeled with the grammar's goal symbol. Suppose
that A is the next nonterminal to be expanded, and that the parser chooses
the production A
. In the parse tree, the node corresponding to this A is
supplied with children that are labeled with the symbols in
→γ
.
In this chapter, we study bottom-up (also called LR) parsers, whose oper-
ation can be compared with top-down parsers as follows:
γ
•
Abottom-upparser beginswith the parse tree's leaves andmoves toward
its root. A top-down parser moves the parse tree's root toward its leaves.
•
A bottom-up parser traces a
rightmost
derivation
in reverse
.Atop-down
parser traces a leftmost derivation.
•
A bottom-up parser uses a grammar rule to replace the rule's
right-hand
side
(RHS) with its
left-hand side
(LHS). A top-down parser does the
opposite, replacing a rule's LHS with its RHS.
Figures 4.5 and 4.6 illustrate the di
erences between a top-down and a bottom-
up parse. The style of parsing considered in this chapter is known by the
following names:
ff
•
Bottom-up
, because the parser works its way from the terminal symbols
to the grammar's goal symbol
•
Shift-reduce
, because the twomost prevalent actions taken by the parser
are to
shift
symbols onto the parse stack and to
reduce
a string of such
symbols located at the top-of-stack to one of the grammar's nonterminals
