24 Oct 91 09:05:29 GMT

Related articles |
---|

[6 earlier articles] |

Re: LR(n) parsers mareb@levels.unisa.edu.au (1991-10-15) |

Re: LR(n) parsers nickh@harlqn.co.uk (Nick Haines) (1991-10-16) |

Re: LR(n) parsers mtxinu!angular!jas@uunet.uu.net (1991-10-18) |

Re: LR(n) parsers rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1991-10-19) |

Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-19) |

Re: LR(n) parsers drw@riesz.mit.edu (1991-10-22) |

Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-24) |

Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24) |

Re: LR(n) parsers ge@sci.kun.nl (1991-10-25) |

Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-25) |

Re: LR(n) parsers markh@csd4.csd.uwm.edu (1991-11-06) |

Newsgroups: | comp.compilers |

From: | Thomas Schoebel <schoebel@bs5.informatik.uni-stuttgart.de> |

Keywords: | parse, LR(1), theory |

Organization: | IfI, Univ. Stuttgart, W Germany |

References: | 91-10-036 91-10-088 |

Date: | 24 Oct 91 09:05:29 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.