Re: A handful of LISP questions

Lieven Marchand <>
Tue, 19 Jun 2007 15:58:47 +0200

          From comp.compilers

Related articles
A handful of LISP questions (tactics) (2007-06-19)
Re: A handful of LISP questions (Gene) (2007-06-19)
Re: A handful of LISP questions (Nils M Holm) (2007-06-19)
Re: A handful of LISP questions (Martin Rodgers) (2007-06-19)
Re: A handful of LISP questions (Lieven Marchand) (2007-06-19)
Re: A handful of LISP questions (Andreas Hinze) (2007-06-19)
Re: A handful of LISP questions (tactics) (2007-06-20)
Re: A handful of LISP questions (Gene) (2007-06-20)
| List of all articles for this month |

From: Lieven Marchand <>
Newsgroups: comp.compilers
Date: Tue, 19 Jun 2007 15:58:47 +0200
Organization: Only under extreme pressure
References: 07-06-033
Keywords: Lisp

tactics <> writes:

> I was wondering from a theoretical standpoint, what kind of grammar is
> a LISP grammar? Obviously, it's a straightforward CFG, but is it
> LL(1)? I took a class in Programming Languages in college, but nothing
> more than how to write a calculator in JavaCC. The web resources for
> LL and LR parsing methods are quiet pathetic too (someone needs to
> clean up their LL algorithm explanation really badly). Can anyone
> point me in the right direction here? What would be a good technique
> to look into for this job?

Traditionally, in Lisp (the modern language is commonly written in
lower case) the parser is called the reader and it is part of the
facilities that are available to the programmer. The Lisp toplevel is
often called the REPL (Read-Eval-Print-Loop).

In Lisp, everything is either an atom or a list. So the Lisp grammar,
to a first approximation, is

sexp:= '(' (atom|sexp)* ')'

where it's the lexers job to recognize the syntax for the various
atoms such as symbols (FOO, COMMON-LISP:LENGTH), numbers (12, -5,
3.14e0), characters (#\a, #\Newline) etc.

It's simple enough not to need LR or even LL.

A complication is the mechanism of read-time macros. For instance, the
QUOTE facility, where you can stop evaluation of an item by quoting
it, like '(this is a literal list) is implemented in Common Lisp by
making ' a read-time macro that expand to the form (QUOTE (THIS IS A
LITERAL LIST)) where QUOTE is a special form that doesn't evaluate its

> My next question is about garbage collection. I have a nice mark and
> sweep algorithm written, but the big issue here is I don't know when
> to actually DO garbage collection. Right now, I just call it at the
> end of my program, but that is hardly useful. Do I just run it
> periodically in a separate thread? Do I set a recurring signal timer?

Generally, you can do garbage collection when an allocation fails or
when your program has used more than a predetermined amount of
memory. In a first try, avoid concurrent garbage collection because it
is fairly difficult to write the rest of your lisp system in such a
way that the garbage collecting thread always sees a consistent state
of the memory.

> In either case, what is the best way to ensure I still have access to
> the current environment?

What do you mean by this?

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.