(ii)
(iii)
268 ~ Theory of Computer Science
Consider some sentential form af3H' of a context-free grammar G, where
Ct., 13 E (Y\ U L)* and W E I*, Suppose we are interested in finding the
production applied in the last step of the deivation for af3,v, If A -7 13 is a
productiDn, it is likely that A -7 13 is the production applied in the last step,
but we cannot definitely say that this is the case, If it is possible to assert that
11 -7 13 is the production applied in the last step by looking ahead for k
symbols (i.e. k symbols to the right of 13 in af3w), then G is called an LR(k)
grammar, The production A -7 13 is called a handle production and 13 is called
a handle.
We write a ,,; 13 if 13 is delived from a by a right-most delivation. Before
R
giving the rigorous definition of an LR(kJ grammar, let us consider a grammar
for which parsing is possible by looking ahead for one symbol.
EXAMPLE 8.1
Let G be 5 -7 AB, A -7 aAb. A -7 A, B -7 Bb, B -7 b. It is easy to see
that L(G) = {(Fbi! ill> m ~ I}. Some sentential forms of G obtained by
right-most derivati~ns are "4B. ABb
k . a
Ill Ab
i11 bk, a"'b"'+k, where k ~ 1. AB
a;pears as the R.H.S. of 5 -7 AB. So liB may be a handle for AB or ABb
k .
If we apply the handle to AB, we get 5 =f' AB. If we apply the handle to ABbk,
we get 5b
k
==} ABb
k . But Sb
k is not a sentential form. So to decide whether
AB can be a handle, we have to scan the symbol to the right of AE. If it is
A, then AB sen'es as a handle. If the next symbol is b, AB cannot be a handle.
So only by looking ahead for one symbol we are able to decide whether AB
is a handle. Let us consider a
2
b
3 . As we scan from left to right we see that
the handle production A -7 A may be applied. A can serve as a handle only
when it is taken bet\veen the rightmost a and the leftmost b. In this case we
get a
2
Ab
3 => a
2 b
3 , and we are able to decide that A -7 A is a handle
~
R
production only by looking ahead of one symbol (to the right of A). If A is
taken between two a's. we get aAab
3 => a
2 b
3
. But aAab
3 is not a sentential
R
form. Similarly, \ve can see that the correct handle production can be
determined by looking ahead of one symbol for various sentential forms,
A rigorous definition of an LR(k) grammar is now given.
DefInition 8.1 Let G = (V\". L, P, 5) be a context-free grammar in which
5 .;; 5 only when n = O. G is an LR(k) grammar (k ~ 0) if
(i) 5 ,,; aAH' => af3w, \vhere a, f3 E V~, W E P,
R
R
S ;i:
, i.'
I
'f3' I h
I
13'
' I
,* d
. => a Ii H' => a H', were a,
E V"'. W E k;'. an
R
R
the first Iaf3l + k symbols of af3\V and (XI,f3'\v' coincide. Then a =a',
A = A'. f3 = 13'.
Remarks 1. If af3H or a ' f3' \\' I have less than Iaf3l + k symbols. we add
some 'blank symbols'. say S. on the right and compare.