Java Reference
In-Depth Information
The row of entries for state 3 is derived from item set s
3
. Because there are no
transitions on a non-terminal from item set s
3
, no entries are indicated for state 3 in
the Goto table.
All other entries in rows 0, 1, 2, and 3 are left blank to indicate an error. The derivations
of the entries in rows 4 to 21 in the Goto table (see Figure 3.7) are left as an exercise.
Conflicts in the Action Table
There are two different kinds of conflicts possible for an entry in the Action table:
1. The first is the shift-reduce conflict, which can occur when there are items of the forms
[Y ::= ,
a
] and
[Y ::=
a
,
b
]
The first item suggests a reduce if the next unscanned token is an
a
; the second
suggests a shift of the
a
onto the stack.
Although such conflicts may occur for unambiguous grammars, a common cause is
ambiguous constructs such as
S ::=
if(
E
)
S
S ::=
if(
E
)
S
else
S
As we saw in Section 3.2.3, language designers will not give up such ambiguous con-
structs for the sake of parser writers. Most parser generators that are based on LR
grammars permit one to supply an extra disambiguating rule. For example, the rule
in this case would be to favor a shift of the
else
over a reduce of the \
if(
E
)
S" to
an S.
2. The second kind of conflict that we can have is the reduce-reduce conflict. This can
happen when we have a state containing two items of the form
[X ::= ,
a
] and
[Y ::= ,
a
]
Here, the parser cannot distinguish which production rule to apply in the reduction.
Of course, we will never have a shift-shift conflict, because of the definition of goto for
terminals. Usually, a certain amount of tinkering with the grammar is sucient for removing
bona fide conflicts in the Action table for most programming languages.
3.4.3 LALR(1) Parsing
Merging LR(1) States
An LR(1) parsing table for a typical programming language such as Java can have thousands
of states, and so thousands of rows. One could argue that, given the inexpensive memory
nowadays, this is not a problem. On the other hand, smaller programs and data make for
Search WWH ::
Custom Search