Java Reference
In-Depth Information
1 Stmt
→
if Expr then StmtList endif
2
|
if Expr then StmtList else StmtList endif
3 StmtList
→
StmtList
; Stmt
4
|
Stmt
5 Expr
→
var + Expr
6
|
var
Figure 5.12: A grammar with common prefixes.
procedure
F
actor
()
foreach
A
∈
N
do
α←
LongestCommonPre f ix
(
ProductionsFor
(A))
while
|α|>
0
do
V
←
new
NonTerminal()
Productions
←
Productions
∪{
A
→α
V
}
foreach
p
∈
ProductionsFor
(
A
)
|
RHS
(
p
)
=αβ
p
do
13
Productions
←
Productions
−{
p
}
Productions
←
Productions
∪{
V
→β
p
}
α←
LongestCommonPre f ix
(
ProductionsFor
(A))
end
Figure 5.13: Factoring common prefixes.
In this category of conflicts, two productions for the same nonterminal share a
common prefix
if the productions' RHSs begin with the same string of gram-
mar symbols. For the grammar shown in Figure 5.12, both Stmt productions
are predicted by the if token. Even if we allow greater lookahead, the else that
distinguishes the two productions can lie arbitrarily far ahead in the input:
Expr and StmtList can each generate a terminal string larger than any constant
k
. The grammar in Figure 5.12 is therefore not LL(
k
)forany
k
.
Prediction conflicts caused by common prefixes can be remedied by the
simple factoring transformation shown in Figure 5.13. At Marker
13
in this
algorithm, a production is identified whose RHS shares a common prefix
α
with other productions. The remainder of the RHS is denoted
β
p
for production
p
. With the common prefix factored and placed into a new production for A,
each production sharing
is stripped of this common prefix. Applying the
algorithm in Figure 5.13 to the grammar in Figure 5.12 produces the grammar
in Figure 5.14.
α
