Java Reference
In-Depth Information
if the Predict sets of a nonterminal's productions are disjoint. Thus, the
LL(1) parser traces the unique, leftmost derivation of an accepted string.
•
All grammars in the LL(1) class are unambiguous.
If a grammar is ambiguous, then some string has two or more distinct
leftmost derivations. When two such derivations are compared, there
must be a nonterminal A for which at least two di
ff
erent productions
could be applied to obtain the di
erent derivations. In other words, with
a lookahead token of x, a derivation could continue by applying A
ff
→α
or A
). Thus,
thetestatMarker
4
in Figure 5.4 determines that such a grammar is
not LL(1).
→β
. It follows that x
∈
Predict(A
→α
)andx
∈
Predict(A
→β
•
All table-driven LL(1) parsers operate in linear time and space with
respect to the length of the parsed input. (Exercise 14 examines whether
recursive-descent parsers are equally e
cient.)
Consider the number of actions that can be taken by an LL(1) parserwhen
the token x is presented as lookahead. Some number of productions will
be applied before x is either matched or found to be in error.
-
Suppose a grammar is
-free. In this case, no production can be
applied twice without advancing the input. Otherwise, the cycle
involving the same production would continue to be applied indef-
initely. This condition should have been reported as an error when
the LL(1) parser was constructed.
-
If the grammar does include
λ
, then the number of nonterminals
that could pop from the stack because of the application of
λ
-rules
is proportional to the length of the input. Exercise 15 explores this
point in more detail.
λ
Thus, each input token induces a bounded number of parser actions. It
follows that the parser operates in linear time.
The LL(1) parser consumes space for the
lookahead bu
er
and for the
ff
parse stack. The lookahead bu
er is of constant size, but the stack grows
and contracts during parsing. However, themaximumstack used during
any parse is proportional to the length of the parsed input, for either of
the following reasons:
ff
-
The stack grows only when a production is applied of the form
A
. As argued previously, no production could be applied twice
without advancing the input and, correspondingly, decreasing the
stack size. If we regard the number and size of a grammar's pro-
ductions to be bounded by some constant, then each input token
contributes to a constant increase in stack size.
→α
