Java Reference
In-Depth Information
1 Stmt
→
if Expr then StmtList V
1
2 V
1
→
endif
3
|
else StmtList endif
4 StmtList
→
StmtList
; Stmt
5
|
Stmt
6 Expr
→
var V
2
7 V
2
→
+Expr
8
| λ
Figure 5.14: Factored version of the grammar in Figure 5.12.
procedure
E
liminate
L
eft
R
ecursion
()
foreach
A
∈
N
do
if
∃
r
∈
ProductionsFor
(A)
|
RHS
(
r
)
=
A
α
then
X
←
new
NonTerminal()
Y
←
new
NonTerminal()
foreach
p
∈
ProductionsFor
(A)
do
if
p
=
r
then
Productions
←
Productions
∪{
A
→
XY
}
else
Productions
←
Productions
∪{
X
→
RHS
(
p
)
}
Productions
←
Productions
∪{
Y
→α
Y
,
Y
→λ}
end
Figure 5.15: Eliminating left recursion.
Aproductionis
left recursive
if its LHS symbol is also the first symbol of its
RHS. In Figure 5.14, the production StmtList
StmtList ; Stmt is left-recursive.
This definition extends to nonterminals: a nonterminal is left-recursive if it is
the LHS symbol of a left-recursive production.
Grammars with left-recursive productions can never be LL(1). To see this,
assume that some lookahead symbol t predicts the application of the left-
recursive production A
→
. With recursive-descent parsing, the application
of this production will cause procedure A to be invoked repeatedly without
advancing the input. With the state of the parse unchanged, this behavior will
continue indefinitely. Similarly, with table-driven parsing, application of this
production will repeatedly push A
→
A
β
β
on the stack without advancing the input.
