Java Reference
In-Depth Information
•
Top-down, because the parser begins with the grammar's start symbol
and grows a parse tree from its root to its leaves.
•
Predictive, because the parser must predict at each step in the derivation
which grammar rule is to be applied next.
•
LL(
k
), because these techniques scan the input from left to right (the first
“L” of LL), produce a leftmost derivation (the second “L” of LL), and use
k
symbols of lookahead.
•
Recursive descent, because this kind of parser can be implemented by a
collection of mutually recursive procedures.
In Section 5.2, we identify a subset of CFGss known as the LL(
k
) grammars.
In Sections 5.3 and 5.4, we show how to construct recursive-descent and
table-driven LL parsers from LL(1) grammars—an e
cient subset of the LL(
k
)
grammars. For grammars that are not LL(1), Section 5.5 considers grammar
transformations that can eliminate non-LL(1) properties. Unfortunately, some
languages have no LL(
k
) grammar, as discussed in Section 5.6. Section 5.7
establishes some useful properties of LL grammars and parsers. Parse table
representations are considered in Section 5.8. Because parsers are typically
responsible for discovering syntax errors in programs, Section 5.9 considers
how an LL(
k
) parser might respond to syntactically faulty inputs.
The following is a reprise from Chapter 2 of the process for constructing a
recursive-descent parser
from a CFGs.
•
A
parsing procedure
is associated with each nonterminal A.
•
The procedure associated with A is chargedwith accomplishing one step
of a derivation by choosing and applying one of A's productions.
•
The parser chooses the appropriate production for A by inspecting the
next
k
tokens (terminal symbols) in the input stream. The
Predict set
for production A
→α
is the set of tokens that trigger application of that
production.
•
The Predict set for A
—the
right-hand side
(RHS) of the production. Other CFGs productions may
participate in the computation of a production's Predict set.
→α
is determined primarily by the detail in
α
Generally, the choice of production can be predicated on the next
k
tokens of
input, for some constant
k
chosen before the parser is pressed into service.
