Java Reference
In-Depth Information
State 0
Goto
State 1
Goto
State 2
Goto
[ Start→•S $
, $ ]
1
[ Start→S •
$,$ ]
13
[ S →lp •Mrp, $ ]
10
[ S
→•
lp M rp , $ ]
2
[ S →lp •Urb, $ ]
9
[ S
→•
lb M rb , $ ]
3
[ M
→•
expr
, rp ]
6
[ S
→•
lp U rb , $ ]
2
[ U
→•
expr
, rb ]
6
[ S
→•
lb U rp , $ ]
3
State 3
Goto
State 4
Goto
State 5
Goto
[ S
→
lb
•
Mrb, $ ]
5
[ S
→
lb U
•
rp , $ ]
8
[ S
→
lb M
•
rb , $ ]
7
[ S
→
lb
•
Urp, $ ]
4
[ M
→•
expr
, rb ]
14
[ U
→•
expr
, rp ]
14
State 6
Goto
State 7
Goto
State 8
Goto
[ M
→
expr
•
, rp ]
[ S
→
lb M rb
•
, $ ]
[ S
→
lb U rp
•
, $ ]
[ U
→
expr
•
, rb ]
State 9
Goto
State 10
Goto
State 11
Goto
[ S→lp U • rb , $ ]
12
[ S→lp M • rp , $ ]
11
[ S→lp M rp •
, $ ]
State 12
Goto
State 13
Goto
State 14
Goto
[ S
→
lp U rb
•
, $ ]
[ Start
→
S $
•
, $ ]
[ M
→
expr
•
, rb ]
[ U
→
expr
•
, rp ]
Figure 6.40: LR(1) construction.
in response to reduce
/
reduce conflicts that arise in LALR(
k
)constructions.
Summary
This concludes our study of bottom-up parsers. We have investigated a num-
ber of LR table-building methods, from LR(0) to LR(1). The intermediate
methods—SLR(1) and LALR(1)—are the most practical. In particular, LALR(1)
provides excellent conflict resolution and generates very compact tables. Tools
based on LALR(1) grammars are available for most languages. Such tools are
indispensable for language modification and extension. Changes can be pro-
totyped using an LALR(1) grammar for the language's syntax. When conflicts
occur, the methods discussed in Section 6.4 help identify why the proposed
modification may not work.
Because of their e
ciency and power, LALR(1) grammars are available
for most modern programming languages. Indeed, the syntax of modern
programming languages is commonly designedwith LALR(1) parsing inmind.
