Java Reference
In-Depth Information
procedure
C
ompute
L
ookahead
()
/
Reserved for the LALR(
k
) computation given in Section 6.5.2
/
end
procedure
T
ry
R
ule
I
n
S
tate
(
s
,
r
)
if
LHS(
r
)
→
RHS(
r
)
•∈
s
then
foreach
X∈
(
Σ∪
N
)
do call
A
ssert
E
ntry
(
s
,X,
reduce r)
end
Figure 6.14: LR(0) version of T
ry
R
ule
I
n
S
tate
.
State
num plus
$
Start
E
0
accept
2
1
3
1
2
1
5
2
reduce 3
3
4
4
reduce 1
5
2
1
6
6
reduce 2
Figure 6.15: LR(0) parse table for the grammar in Figure 6.2.
Sometimes LR construction is not successful, even for simple languages and
grammars. In the following sections we consider table-construction methods
that are more powerful than LR(0), thereby accommodating a much larger
class of grammars. This section examines why
conflicts
arise during LR table
construction and develops approaches for understanding and resolving such
conflicts.
The generic LR parser shown in Figure 6.3 is
deterministic
.Givenaparse
state and an input symbol, the parse table can specify exactly one action to
be performed by the parser—shift, reduce, accept, or error. In Chapter 3 we
tolerated nondeterminism in the scanner specification because we knew of
an e
cient algorithm for transforming a nondeterministic DFA into a deter-
ministic DFA. Unfortunately, no such algorithm is possible for stack-based
parsing engines. Some CFGss cannot be parsed deterministically.
In such
