Re: LR(n) parsers

In article 91-10-088 drw@riesz.mit.edu (Dale R. Worley) writes:


> When was this proven? Last I heard was that it wasn't known of LR(k) was
> larger than LR(0).


The difference is whether you are speaking of grammars or of languages.
Of course, you can *deterministically* parse more *grammars* with an
LR(k+1) parser than with an LR(k) one. However, the *language* classes
LR(k) are equal for any k. The resulting one language class is often
called "deterministic context-free languages with prefix property".


> [Maybe he meant 1 rather than 0. -John]


No, it's even the same for k=0. See Hopcroft/Ullman page 256, where it is
shown that any deterministic pushdown automata (DPDA) can be converted to
an LR(0) grammar. Since any LR(k) (k>0) parser is in fact a DPDA, the
*language classes* are equal for any k. In theory, an LR(0) parser would
be sufficient, but in practice the transformations of grammars from LR(k)
(k>0) to LR(0) would be too complicated.


> Also, is it known yet if there are unambiguous CF
> languages that aren't LR?


See my previous posting. An example for an unambiguous language which has
no LR(k) grammar:


  L = { ww^R | w \in (0+1)* } (See Hopcroft/Ullman Exercise 10.5 page 265)


(w^R means the reverse word)


It is easy to construct a non-ambiguous context-free grammar for this
language:


  G = ({S},{0,1},P,S) with productions


      S -> 0S0 | 1S1 | \epsilon


This grammar is even linear, and therefore easily classified as
unambigous. But the language is not *deterministically* context-free and
therefore has no LR(k) grammar.


Intuitively, one can explain this (less formally, not mathematically
correct) as follows:


If you want to build a deterministic automaton for the language, you must
be able to decide when you have reached the middle of the word. Before
the middle, all symbols have to be pushed to stack, and afterwards, the
stack symbols must match the rest of the input. However, it is not
decidable without lookahead when the middle is reached (a classical
shift-reduce conflict); for example take 0^2n as input word and you cannot
decide anything because all input symbols look the same. To decide the
middle point, you would have to use a lookahead of n symbols, but n is no
fixed number. In other words, you would have to use an unbounded
lookahead to decide the point of the middle, and that simply is not LR(k).


-- Thomas
--

Return to the comp.compilers page.
Search the comp.compilers archives again.