Subject: Re: simple lisp interpreter
From: rpw3@rpw3.org (Rob Warnock)
Date: Fri, 07 Sep 2007 19:10:49 -0500
Newsgroups: comp.lang.lisp
Message-ID: <woWdnQFxgKEUdXzbnZ2dnUVZ_s2tnZ2d@speakeasy.net>
George Neuner  <gneuner2/@comcast.net> wrote:
+---------------
| I think we're talking at crossed purposes and we should probably stop...
...
| One thing I would like to say though before we stop: the original
| poster asked a theoretical question ... whether Lisp (he did not
| specify CL) was LL(1).  The answer to that is "no" regardless of
| whether readtable processing is considered - some of the basic (I want
| to avoid the word "standard") language forms are not LL(1).
...
| Also, I was not discussing CL in particular but rather sexpr based
| languages which resemble Lisp in notation.
+---------------

As you note, it is possible even in non-CL sexpr-based languages
that some of the basic forms might not be LL(1). E.g., consider a
hypothetical dialect of Scheme which adopted John Foderaro's IF*[1]:

    (if* <predicate>	; [I don't know where the THENRET fits in.]
      then <form>...
      elseif <form>...
      elseif <form>...
      else <form>...)

I don't think this is LL(1), yet a simple recursive-descent parser
can handle it easily.

On the other hand, is there anything in Standard Scheme
[either IEEE or R4RS, take your pick (I'm not sure about
whether R5RS macros break this or not)] that isn't LL(1)?
Or at least LL(n) for *small* "n"?


-Rob

[1] http://www.franz.com/~jkf/ifstar.txt

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607