Java Reference
In-Depth Information
State
a
b
c
d
q
$
Start
S
A
B
C
Q
0
8
8
8
accept
3
2
4
1
5
1
4
11
14
2
8
8
8
8
2
13
3
8
8
2
9
4
8
5
10
10
7
6
6
6
6
7
9
9
8
1
9
4
11
10
10
12
11
3
3
12
5
5
13
7
7
7
7
14
2
Figure 6.5: Parse table for the grammar shown in Figure 6.4.
Of course, the parse table plays a central role in determining the shifts and
reductions that are necessary to recognize a valid string. For example, the rule
C
could be applied at any time, but the parse table calls for this only in
certain states and only when certain tokens are next in the input stream.
→λ
The concept of LR parsing was introduced by Knuth [Knu65], whose famous
series entitled
The Art of Computer Programming
[Knu73a, Knu73b, Knu73c]
began as introductory material for a textbook on compiler construction. As
is the case with LL parsers, LR parsers are parameterized by the number of
lookahead symbols that are consulted to determine the appropriate parser
action. An LR(
k
) parser can peek at the next
k
tokens. This notion of “peeking”
and the term LR(0) are confusing, because even an LR(0) parser must refer to
