270 g Theory ofComputer Science
To get the last step of a
2
Ab", we scan a
2
Ab" from left to right aAb is a
possible handle. We are able to decide that this is the right handle without
looking ahead and so we get
aAbb
2 =? a
2
Ab
4
R
Once again using the handle aAb, we obtain
Ab
2 =? aAbb
2
R
To get the last step of the rightmost derivation of Ab
2
, we scan Ab
2 • A possible
handle production is B -'7 b. We also note that this handle production can be
applied to the first b we encounter, but not to the last b. So, we get
ABb =? Ab
2 .
R
For ABb. a possible a-handle is Bb. Hence, we get AB =? ABb. Finally,
R
we obtain S =? AB. Thus we have the following derivations:
R
a
2
Ab
4 =? a
2 Ab
4
by looking ahead of one symbol
R
aAbb
2 =? a
2
Ab
4
R
Ab
2 =? ClAbb
2
R
ABb =? Ab
2
R
AB =? ABb
R
by not looking ahead of any symbol
by not looking ahead of any symbol
by not looking ahead of any symbol
by not looking ahead of any symbol
by looking ahead of one symbol
S =?AB
R
The derivation tree for a
2 b
4 is as shown in Fig. 8.1.
s
a
a
A
b
b
I
b ab
Fig. 8.1 Derivation tree for a
2 b
4
8.2 PROPERTIES OF LR(k) GRAMMARS
In this section we give some important properties of LR(k) grammars which
are useful for parsing and other applications.