Java Reference
In-Depth Information
1 S
→
Stmt $
2 Stmt
→
if expr then Stmt V
3
|
other
4 V
→
else Stmt
5
| λ
Lookahead
Nonterminal
if
expr
then
else
other
$
S
1
1
Stmt
2
3
V
4,5
5
Figure 5.19: Ambiguous grammar for if-then-else and its LL(1) table.
The ambiguity is resolved by favoring Rule 4 over Rule 5 in
the boxed entry.
Our analysis shows that LL(1) parser generators cannot automatically cre-
ate parsers from grammars that embed the if-then-else construct. This short-
coming can be handled by using grammars that lead to LL(1) conflicts. Such
conflicts are then resolved by hand to obtain the desired e
ect. Factoring the
grammar in Figure 5.17 yields the ambiguous grammar and (correspondingly
nondeterministic) parse table shown in Figure 5.19. As expected, the else
symbol predicts multiple productions as seen in Rules 4 and 5. Since the else
should match the closest then,weresolvetheconflictinfavorofRule4. Fa-
voring Rule 5 would defer consumption of the else. Moreover, the parse table
entry for nonterminal V and terminal else is Rule 4's only legitimate chance to
appear in the parse table. If this rule is absent from the parse table, then the
resulting LL(1) parser could never match
any
else. We therefore insist that rule
V
ff
else Stmt be predicted for Vwhen the lookahead is else.Theparsetableor
recursive-descent code can be modified manually to achieve this e
→
ff
ect. Some
parser generators o
ff
er mechanisms for establishing priorities when conflicts
arise.
We can establish the following useful properties for LL(1) parsers:
•
A correct, leftmost parse is constructed.
This follows from the fact that LL(1) parsers simulate a leftmost deriva-
tion. Moreover, the algorithm in Figure 5.4 finds a CFGs to be LL(1) only
