Java Reference
In-Depth Information
1 Stmt
→
if Expr then StmtList V
1
2 V
1
→
endif
3
|
else StmtList endif
4 StmtList
→
XY
5 X
→
Stmt
6 Y
→
;StmtY
7
| λ
8 Expr
→
var V
2
9 V
2
→
+Expr
10
| λ
Figure 5.16: LL(1) version of the grammar in Figure 5.14.
Consider the following left-recursive rules.
1 A
→
A
α
2
| β
Each time Rule 1 is applied, an
α
is generated. The recursion ends when
Rule 2 prepends a
symbols. Using the regular-expression
notation developed in Chapter 3, the grammar generates
β
to the string of
α
βα
. The algorithm
βα
. However, the
in Figure 5.15 obtains a grammar that also generates
β
is
generated
first
.The
symbols are then generated via right recursion. Applying
this algorithm to the grammar in Figure 5.14 results in the grammar shown in
Figure 5.16. Since X appears as the LHS of only one production, X's unique
RHS can be automatically substituted for all uses of X. This allows Rules 4
and 5 of Figure 5.14 to be replaced with StmtList
α
→
Stmt Y.
The algorithms presented in Figures 5.13 and 5.15 typically succeed in ob-
taining an LL(1) grammar. However, some grammars require greater thought
to obtain an LL(1) version (some of these are included as exercises at the end
of this chapter). All grammars that include the $ (end-of-input) symbol can be
rewritten into a formwhere all right-hand sides begin with a terminal symbol;
this form is called
Greibach normal form
(GNF) (see Exercise 17). Once a
grammar is in GNF, factoring of common prefixes is straightforward. Sur-
prisingly, even this transformation does not guarantee that a grammar will be
LL(1) (see Exercise 18). In fact, as we discuss in the next section, language con-
structs do exist that have no LL(1) grammar. Fortunately, such constructs are
rare in practice and can be handled by modest extensions to the LL(1) parsing
technique.
