Java Reference
In-Depth Information
1 Start
→
E$
2 E
→
Eplusnum
3
|
E times num
4
|
num
Start
E
E
E
num plus
num times
num
$
Figure 6.20: Expressions with sums and products.
can provide important clues for diagnosing a grammar's inadequacies; un-
derstanding and resolving such conflicts requires human intelligence. Also,
the LR(0) construction forms the basis of the more advanced constructions
considered next.
While LR(0) construction succeeded for the grammar in Figure 6.18, most
grammars require some lookahead during table construction. Sections 6.5.1,
6.5.2, and 6.5.4 consider methods that, while based on the LR(0) construction,
use increasingly sophisticated
lookahead techniques
to resolve conflicts. Sec-
tion 6.5.1 presents the SLR(
k
) construction, which is simple but does not work
as well as the LALR(
k
) construction introduced in Section 6.5.2. The most
powerful technique, LR(
k
), is presented in Section 6.5.4.
The SLR(
k
)(Simple LRwith
k
tokens of lookahead) method attempts to resolve
inadequate states using grammar analysis methods presented in Chapter 4.
To demonstrate the SLR(
k
) construction, we require a grammar that is not
LR(0). We begin by extending the grammar in Figure 6.18 to accommodate
expressions involving sums and products. Figure 6.20 shows such a grammar
along with a parse tree for the string num plus num times num $.Exercise17
