Java Reference
In-Depth Information
cases, perhaps there is another grammar that generates the same language
and for which a deterministic parser can be constructed. There are
context-
free languages
(CFLs) that provably cannot be parsed using the (deterministic)
LR method (see Exercise 11). However, programming languages are typically
designed to be parsed deterministically.
Aparsetable
conflict
arises when the table-construction method cannot
decide betweenmultiple alternatives for some table-cell entry. We then say that
the associated state (row of the parse table) is
inadequate
for that method. An
inadequate state for a weaker table-construction algorithm can sometimes be
resolved by a stronger algorithm. For example, the grammar of Figure 6.4 is not
LR(0) since a mix of shift and reduce actions can be seen in State 0. However,
the table-construction algorithms introduced in Section 6.5.1 resolve the LR(0)
conflicts for this grammar.
If we consider the possibilities for multiple table-cell entries, only the
following two cases are troublesome for LR(
k
)parsing:
•
shift
reduce conflicts
exist in a state when table construction cannot use
the next
k
tokens to decidewhether to shift the next input token or call for
a reduction. The bookmark symbol must occur before a terminal symbol
t in one of the state's items, so that a shift of t could be appropriate. The
bookmark symbol must also occur at the end of some other item, so that
a reduction in this state is also possible.
/
•
reduce
reduce conflicts
exist when table construction cannot use the
next
k
tokens to distinguish between multiple reductions that could be
applied in the inadequate state. Of course, a state with such a conflict
must have at least two reducible items.
/
Other combinations of actions in a table cell do not make sense. For example,
it cannot be the case that some terminal t could be shifted but also cause an
error. Additionally, there cannot be a shift
shift error: if a state admits the
shifting of terminal symbols t and u, then the target state for the two shifts is
di
/
erent, and there is no conflict. Exercise 13 considers the impossibility of a
shift
ff
reduce conflict on a nonterminal symbol.
Although the table-construction methods we discuss in the following sec-
tions vary in power, each is capable of reporting conflicts that render a state
inadequate. Conflicts arise for one of the following reasons:
/
•
The grammar is
ambiguous
. No (deterministic) table-constructionmeth-
od can resolve conflicts that arise due to ambiguity. Ambiguous grammars
are considered in Section 6.4.1, but here we summarize some approaches
for addressing the ambiguity.
If a grammar is ambiguous, then some input string has at least two
distinct parse trees. The following must then be considered:
