Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #661

Does someone have a reference to the statement that almost all practical languages are LL?

Show all headers | View raw

Chris F Clark wrote:
> I'm writing up a small whitepaper(*) where I want to discuss LL and
> LR grammars. In it I want to sidestep the issue of the fact that
> there are LL grammars that are not LR

These would be hard to find.  You probably mean LL grammars which are
not LALR.

> and vice-versa. Thus, I simply want to quote the conventional wisdom,
> i.e. that nearly any (artificial) language in use has an LL grammar.
> However, I'd like to reference someone else who has made that
> statement, so that it simply isn't a bald assertion without proof in
> my paper. It's instead a reference to a bald assertion without proof
> in someone else's paper (or web page or interview or whatever) ;-)

Terence Parr's papers should provide this kind of argument.

> With lesser importance, I wouldn't mind a reference to a proof that
> all deterministic context free languages have an LR(1) grammar.

This was already proven in Knuth's original paper on LR parsing, _On the
Translation of Languages from Left to Right_, Information and Control
8:607--639 (1965), Section V.

--
Regards,

   Sylvain

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

Does someone have a reference to the statement that almost all practical langauges are LL? Chris F Clark <cfc@shell01.TheWorld.com> - 2012-05-30 13:27 -0400
  Does someone have a reference to the statement that almost all practical languages are LL? Sylvain Schmitz <Sylvain.Schmitz@lsv.ens-cachan.fr> - 2012-05-30 23:17 +0200

csiph-web