simple lisp interpreter

Hey, lisp's wizz !
I just read the definition of LL parser, and have to write the lisp
interpreter. Is LL(1) parser enought for lisp language ?

Thomas wrote:

> I just read the definition of LL parser, and have to write the lisp
> interpreter. Is LL(1) parser enought for lisp language ?

Not if you include readtables...

On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <arabel9@o2.pl> wrote:

>I just read the definition of LL parser, and have to write the lisp
>interpreter. Is LL(1) parser enought for lisp language ?

IIRC from Scheme, you need at least LL(2) to handle the optional parts
of forms like IF and LET et al. Whether that is sufficient I don't
know offhand.

As an open question to Matthias or whoever, I don't really see how
readtable handling would materially affect the parser's LL complexity.
Macro character parsing itself is LL(1) and it would be subsumed by
the greater complexity of parsing the forms. What is the extra
complexity?

George
--
for email reply remove "/" from address

George Neuner wrote:

> As an open question to Matthias or whoever, I don't really see how
> readtable handling would materially affect the parser's LL complexity.
> Macro character parsing itself is LL(1) and it would be subsumed by
> the greater complexity of parsing the forms. What is the extra
> complexity?

Can you construct (theoretically) an LL(n) grammar that can produce any
Common Lisp program?

Matthias Buelow <mkb@incubus.de> writes:

> George Neuner wrote:
>
> > As an open question to Matthias or whoever, I don't really see how
> > readtable handling would materially affect the parser's LL complexity.
> > Macro character parsing itself is LL(1) and it would be subsumed by
> > the greater complexity of parsing the forms. What is the extra
> > complexity?
>
> Can you construct (theoretically) an LL(n) grammar that can produce any
> Common Lisp program?

I'm pretty sure you trivially can, but probably because you aren't
asking the question you think you are asking.

Common Lisp is defined in terms of structure, not in terms of text.
So any strange syntax you have trouble with can almost surely be
compensated for by some other syntax that yields the same object.
The notion of a grammar generating programs involves a type/category
error.

Programs are objects, not syntaxes. The reader yields objects, not
programs. There is an extra level of indirection in there. As a
result, there are probably many syntaxes that lead to the same object
and generating all the possible objects that are programs does not
require generating all the possible textual syntaxes that would, if
read, yield objects that are valid programs.

(Importantly, too, there are valid programs that print the same but
mean different things because their object identity is different.)

Regardless, though, I'm curious: what is someone planning to _do_ with
this information? Why is the question being asked?

Kent M Pitman wrote:

> Programs are objects, not syntaxes. The reader yields objects, not
> programs. There is an extra level of indirection in there. As a
> result, there are probably many syntaxes that lead to the same object
> and generating all the possible objects that are programs does not
> require generating all the possible textual syntaxes that would, if
> read, yield objects that are valid programs.

Yes but the OP was asking whether the "Lisp language" can be parsed by
an LL parser, by which I understand that he means in textual source-code
form, otherwise it wouldn't make much sense.
In the case of Common Lisp, parsing Lisp source code with an LL(k)
parser is not possible, since read macro dispatches make parsing the
language Turing-complete, which cannot be decided by a parser that can
handle only (a subset of) context-free languages.

> Regardless, though, I'm curious: what is someone planning to _do_ with
> this information? Why is the question being asked?

I guess it's a parser generator exercise, since basic Lisp (without
extensible syntax) is relatively easy to write a grammar for.

George Neuner <gneuner2/@comcast.net> writes:

> On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <arabel9@o2.pl> wrote:
>
> As an open question to Matthias or whoever, I don't really see how
> readtable handling would materially affect the parser's LL complexity.
> Macro character parsing itself is LL(1) and it would be subsumed by
> the greater complexity of parsing the forms. What is the extra
> complexity?

Well, I'm pretty sure I have, in the past, made a readtable that
redefines every single character to be the same readmacro (one that
trampolines to another parser, for example, to implement a readmacro
that implements a FORTRAN parser... though it could have been any kind
of parser once the readmacro got control. That's how CGOL worked to
add infix syntax to MACLISP). Since I could then trampoline to a
parser of any nature whatsoever, that means that once a readmacro is
in play, you can really make no statements about the parser's nature.

It is for this reason that I generally don't refer to Lisp's reader as
a parser, and even when I do use the parse metaphor, I try not to
refer to a notion of a grammar as what drives it. I feel like it just
sets people on the path to ask a bunch of questions the answers to
which will mostly mislead them into a wrong model of what's going on.

George Neuner wrote:

> What is the extra complexity?

For example, a macro dispatch function for the character #\[ that reads
words of the form wWw, where W is the reverse of w, in square brackets
in the input stream, and produces an error for words (within square
brackets) that are not of that form.
That is, for example, [abbaab] is valid, but [ababab] produces an error.
This language is not context free (which can be shown by applying the
Pumping Lemma for context-free languages) and hence it can't be handled
by a parser for (a subset of) context-free languages, such as an
LL/LR-parser.

On 05 Sep 2007 20:53:13 -0400, Kent M Pitman <pitman@nhplace.com>
wrote:

>George Neuner <gneuner2/@comcast.net> writes:
>
>> On Wed, 5 Sep 2007 00:04:04 +0200, "Thomas" <arabel9@o2.pl> wrote:
>>
>> As an open question to Matthias or whoever, I don't really see how
>> readtable handling would materially affect the parser's LL complexity.
>> Macro character parsing itself is LL(1) and it would be subsumed by
>> the greater complexity of parsing the forms. What is the extra
>> complexity?
>
>Well, I'm pretty sure I have, in the past, made a readtable that
>redefines every single character to be the same readmacro (one that
>trampolines to another parser, for example, to implement a readmacro
>that implements a FORTRAN parser... though it could have been any kind
>of parser once the readmacro got control. That's how CGOL worked to
>add infix syntax to MACLISP). Since I could then trampoline to a
>parser of any nature whatsoever, that means that once a readmacro is
>in play, you can really make no statements about the parser's nature.

Ok, that makes sense. I was only thinking about Lisp syntax and what
extra was necessary for dispatching. I forgot that the handler might
do anything once it got control.

>It is for this reason that I generally don't refer to Lisp's reader as
>a parser, and even when I do use the parse metaphor, I try not to
>refer to a notion of a grammar as what drives it. I feel like it just
>sets people on the path to ask a bunch of questions the answers to
>which will mostly mislead them into a wrong model of what's going on.

Also sensible.

George
--
for email reply remove "/" from address

On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <mkb@incubus.de>
wrote:

>George Neuner wrote:
>
>> As an open question to Matthias or whoever, I don't really see how
>> readtable handling would materially affect the parser's LL complexity.
>> Macro character parsing itself is LL(1) and it would be subsumed by
>> the greater complexity of parsing the forms. What is the extra
>> complexity?
>
>Can you construct (theoretically) an LL(n) grammar that can produce any
>Common Lisp program?

In general ... no.

Kent pointed out (and I guess you were alluding to) that readtable
macros might do absolutely anything - including parsing a completely
different language - and so it is very hard to reason about the
grammar complexity of a Lisp program.

If you confine the problem to Lisp syntax then the answer is yes.

From experience, I know Scheme grammar is mostly LL(1) with just a
couple of forms that require more look ahead - LL(2) or LL(3), nothing
drastically hard. A grammar for Lisp should be of the same order
complexity - Lisp's additional keywords, expanded parameter lists, and
multiple name spaces don't materially affect the grammar complexity
.... the parser complexity, but not the grammar.

George
--
for email reply remove "/" from address