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

Groups > comp.compilers > #659 > unrolled thread

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

Back to article view | Back to comp.compilers

Contents

  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

#659 — Does someone have a reference to the statement that almost all practical langauges are LL?

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 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) ;-)

With lesser importance, I wouldn't mind a reference to a proof that
all deterministic context free langauges have an LR(1) grammar.
However, since I know that is a proven statement, I'm a little less
worried about it.

-Chris

******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [next] | [standalone]

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

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web