Compilers - Am I writing one?

Levi Pearson levi at cold.org
Sun Jun 29 22:14:08 MDT 2008


"Daniel C." <dcrookston at gmail.com> writes:
> Lisp actually ;-)  There's Zebu, which is similar to a yak both in
> animal and programming terms.

Lisp is surprisingly weak in parsing tools, mainly because once you
invest in Lisp, using anything other than s-expressions seems rather
counterproductive. :)

>> You might want to write a recursive descent parser.
>
> My primary goal is to make Raskal as simple as possible, so using a
> tool that requires obfuscation in the language isn't really where I
> want to go.

Well, it might not be very bad if you don't have many left-recursive
rules in your grammar.  Have you written out a grammar in BNF for
Raskal yet?

> More resources would be good.  I've got a copy of the Dragon Book
> (purple type, one each) on order and I'm reading various online
> tutorials (like this one:
> http://lambda.uta.edu/cse5317/notes/node1.html and the Wikipedia pages
> for CFGs, DFAs, etc.) but they're not as good as it seems like they
> could be.  Mostly I find myself grasping at context - what problem is
> this specific thing designed to solve?, etc.  I suspect the Dragon
> Book will answer these questions for me.

The Dragon Book is a pretty comprehensive source for classical parsing
and compiling techniques, but it's not really a gentle introduction.
Expect to put some serious concentration into reading it.

For compiling with Common Lisp, Norvig's Paradigms of Artificial
Intelligence Programming is also an excellent source, though primarily
for parts after the parsing phase.

Here's a free book from a DIKU course: http://www.diku.dk/~torbenm/Basics/

Here's a rather heavy-duty book just on parsing, which goes into great
detail about how yacc and friends work:
http://www.cs.vu.nl/~dick/PTAPG.html

Here's a book by Wirth (designer of Pascal, Modula, Oberon) that
covers (and includes the full source code for) a compiler for the
Oberon language: http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf

As for context... well, the thing about automata theory is that it's
rather abstract, so it's useful for all sorts of things.  Finite state
machines are used for all sorts of hardware and software designs for
system control.  Any program can be reduced to a turing machine, which
is a class of automata.  Protocols are often described as automata.
And, of course, regular expression engines and more general parsers
are often built on automata.

                --Levi



More information about the PLUG mailing list