Chapter 8: LR(k) Grammars l;! 269
2. It is easy to see how we can get the derivation tree for a given
terminal string. For getting the derivation tree. we want to get the derivation
"in the reverse order", Suppose a sentential form af3,\' is encountered. We can
get a right-most derivation of f3H' in the fol1mving \vay: If A --+ 13 is a
production. then we have to decide whether A --+ 13 is used in the last step of
a right-most derivative of af3\\', On seeing k symbols beyond 13 in af3w, we
are able to decide that A --+ 13 is the required production in the first step, For,
if a'f3'H.' is another sentential foml satisfying condition (iii), then we can
apply A' --+ 13' in the last step of a light-most derivation of a'{3'w
l
,
But by
definition it follows that A = AI, 13 = 13
1 and a = a
l
• So A --+ f3 is the only
possible production we can apply and we are able to decide this after 'seeing'
the k symbols beyond 13, We repeat the process until we get S.
3. If G is an LR(k) grammar, it is an LR(k
l
)
grammar for aU k' > k.
EXAMPLE 8.2
Let G be the grammar 5 --+ all., A --+ Abb Ib, Show that G is an LR(O)
grammar,
Solution
It is easv to see that anv element in UG) is of the fonn ab~iI+l. The sentential
forms of G. are aA. aAb~iI, ab
2n +!. Let us find out the last production applied
in the derivation of ab~n+!. As aA, Ab!?, b are the possible right-hand sides
of productions, only A --+ b can be the last production: we are able to decide
this without looking at any symbol to the right of b, Similarly. the last
productions for aAb c " and aA are A --+ Abb and 5 --+ (lA, respectively. (We
are able to say that A --+ Abb is the last production for any sentential form
aAb
2n for all n ;:::: 1.) Thus, G is an LR(O) grammar.
EXAMPLE 8.3
Consider the grammar G given in Example 8.1. Show that G is an LR(l)
grammar. but not an LR(O) grammar. Also. find the delivation tree for a~b4.
Solution
In Example 8.1 we have shown that for sentential forms of G we can determine
the last step of a right-most derivation by looking ahead of one symbol. So G
is LR(l), We have also seen that 5 --+ AB is a handle production for the
sentential form AB, but not for ABbA, In other words, the handle production
cannot be detennined without looking ahead. So G is not LR(O).
To get the derivation tree for a
C
b
4 we scan a~b'+ from left to right. After
scanning a. we look ahead. If the next symbol is a. we continue to scan. If
the next symbol is b. we decide that A --+ A is the required handle production.
Thus the last step of the right-most derivation of a~b4 is
a~Ab4 => a~/\.b4
R
2. It is easy to see how we can get the derivation tree for a given
terminal string. For getting the derivation tree. we want to get the derivation
"in the reverse order", Suppose a sentential form af3,\' is encountered. We can
get a right-most derivation of f3H' in the fol1mving \vay: If A --+ 13 is a
production. then we have to decide whether A --+ 13 is used in the last step of
a right-most derivative of af3\\', On seeing k symbols beyond 13 in af3w, we
are able to decide that A --+ 13 is the required production in the first step, For,
if a'f3'H.' is another sentential foml satisfying condition (iii), then we can
apply A' --+ 13' in the last step of a light-most derivation of a'{3'w
l
,
But by
definition it follows that A = AI, 13 = 13
1 and a = a
l
• So A --+ f3 is the only
possible production we can apply and we are able to decide this after 'seeing'
the k symbols beyond 13, We repeat the process until we get S.
3. If G is an LR(k) grammar, it is an LR(k
l
)
grammar for aU k' > k.
EXAMPLE 8.2
Let G be the grammar 5 --+ all., A --+ Abb Ib, Show that G is an LR(O)
grammar,
Solution
It is easv to see that anv element in UG) is of the fonn ab~iI+l. The sentential
forms of G. are aA. aAb~iI, ab
2n +!. Let us find out the last production applied
in the derivation of ab~n+!. As aA, Ab!?, b are the possible right-hand sides
of productions, only A --+ b can be the last production: we are able to decide
this without looking at any symbol to the right of b, Similarly. the last
productions for aAb c " and aA are A --+ Abb and 5 --+ (lA, respectively. (We
are able to say that A --+ Abb is the last production for any sentential form
aAb
2n for all n ;:::: 1.) Thus, G is an LR(O) grammar.
EXAMPLE 8.3
Consider the grammar G given in Example 8.1. Show that G is an LR(l)
grammar. but not an LR(O) grammar. Also. find the delivation tree for a~b4.
Solution
In Example 8.1 we have shown that for sentential forms of G we can determine
the last step of a right-most derivation by looking ahead of one symbol. So G
is LR(l), We have also seen that 5 --+ AB is a handle production for the
sentential form AB, but not for ABbA, In other words, the handle production
cannot be detennined without looking ahead. So G is not LR(O).
To get the derivation tree for a
C
b
4 we scan a~b'+ from left to right. After
scanning a. we look ahead. If the next symbol is a. we continue to scan. If
the next symbol is b. we decide that A --+ A is the required handle production.
Thus the last step of the right-most derivation of a~b4 is
a~Ab4 => a~/\.b4
R