Chapter 8: LR(k) Crammars ~ 271
Recall the definition of an ambiguous grammar. A grammar G is
ambiguous if there exists W E L(G) which has two derivation trees. The next
theorem gives the relation between LR(k) grammars and unambiguous
grammars.
Property 1 Every LR(k) grammar G is unambIguouS.
Proof We have to show that for any x E Ii\ there exists a unique right-most
derivation. Suppose \ve have two rightmost derivations for x, namely
s ~ aAw ~ a[3w = x
R
R
S ~ ajt/w/ ~ a'b'w' = x
R
R
(8.l)
(8.2)
As a[3w = a'[3'w', from the definition it follows that a = a', A = A' and
[3 = [3'. As a[3w = a'[3'w', we get w = w', and so aAw = a'A'w'. Hence the
last step in the derivations (8.l) and (8.2) is the same. Repeating the arguments
for the other sentential forms derived in the course of (8.1) and (8.2), we can
show that (8.l) is the same as (8.2). Therefore, G is unambiguous. I
We have seen that the detenninistic and the nondeterministic finite
automata behave in the same way in so far as acceptability of languages is
concerned. The same is the case with Turing machines. But the behaviour of
deterministic and nondeterministic pushdown automata is different. In
Chapter 7 we have proved "that any pushdown automaton accepts a contextfree language and for any context-free language L, we can construct a
pushdown automaton accepting L. The following property gives the relation
between LR(k) grammars and pushdown automata.
Property 2 If G is an LR(k) grammar. there exists a deterministic pushdown
automaton A accepting L(G).
Property 3 If A is a deterministic pushdown automaton A, there exists an
LR(l) grammar G such that L(G) =N(A).
Property 4 If G is an LR(k) grammar, where k > L then there exists an
equivalent grammar G! which is LR(l). In so far as languages are concerned,
it is enough to study the languages generated by LR(O) grammars and LR(l)
grammars.
Defmition 8.2 A context-free language is said to be deterministic if it is
accepted by a detenmnistic pushdO\vn automaton.
Property 5 The class of deterministic languages is a proper subclass of the
class of context-free languages.
The class of deterministic languages can be denoted by
Property 6 ot'dctl is closed under complementation but not under union and
intersection.
The following definition is useful in characterizing the languages accepted
by an LR(O) grammar.
Recall the definition of an ambiguous grammar. A grammar G is
ambiguous if there exists W E L(G) which has two derivation trees. The next
theorem gives the relation between LR(k) grammars and unambiguous
grammars.
Property 1 Every LR(k) grammar G is unambIguouS.
Proof We have to show that for any x E Ii\ there exists a unique right-most
derivation. Suppose \ve have two rightmost derivations for x, namely
s ~ aAw ~ a[3w = x
R
R
S ~ ajt/w/ ~ a'b'w' = x
R
R
(8.l)
(8.2)
As a[3w = a'[3'w', from the definition it follows that a = a', A = A' and
[3 = [3'. As a[3w = a'[3'w', we get w = w', and so aAw = a'A'w'. Hence the
last step in the derivations (8.l) and (8.2) is the same. Repeating the arguments
for the other sentential forms derived in the course of (8.1) and (8.2), we can
show that (8.l) is the same as (8.2). Therefore, G is unambiguous. I
We have seen that the detenninistic and the nondeterministic finite
automata behave in the same way in so far as acceptability of languages is
concerned. The same is the case with Turing machines. But the behaviour of
deterministic and nondeterministic pushdown automata is different. In
Chapter 7 we have proved "that any pushdown automaton accepts a contextfree language and for any context-free language L, we can construct a
pushdown automaton accepting L. The following property gives the relation
between LR(k) grammars and pushdown automata.
Property 2 If G is an LR(k) grammar. there exists a deterministic pushdown
automaton A accepting L(G).
Property 3 If A is a deterministic pushdown automaton A, there exists an
LR(l) grammar G such that L(G) =N(A).
Property 4 If G is an LR(k) grammar, where k > L then there exists an
equivalent grammar G! which is LR(l). In so far as languages are concerned,
it is enough to study the languages generated by LR(O) grammars and LR(l)
grammars.
Defmition 8.2 A context-free language is said to be deterministic if it is
accepted by a detenmnistic pushdO\vn automaton.
Property 5 The class of deterministic languages is a proper subclass of the
class of context-free languages.
The class of deterministic languages can be denoted by
Property 6 ot'dctl is closed under complementation but not under union and
intersection.
The following definition is useful in characterizing the languages accepted
by an LR(O) grammar.