[help-3dldf] Re: Compiler construction projects (fwd)

[Laurence Finston]

---------- Forwarded message ----------
Date: Thu, 2 Jun 2005 12:02:23 +0200
From: Laurence Finston <address@hidden>
To: Roderick Bloem <address@hidden>
Newsgroups: comp.compilers
Subject: Re: Compiler construction projects

On Thu, 2 Jun 2005, Roderick Bloem wrote:

>   In particular, I would be interested in the details of projects to
> build a compiler:  Which source and destionation languages do you use,
> which implementation language for the compiler, and, especially, which
> tools?

> It would be great if you could post your experiences to this newsgroup.

My project is GNU 3DLDF.  It implements an interpreter for a
language based on Donald Knuth's Metafont language, but
extended to three-dimensions.  I've implemented it in C++
using the CWEB package written by Knuth and Silvio Levy.
Currently, its only form of output is MetaPost code, but
this may change in the future.  (MetaPost was written by
John D. Hobby.)  It does not share any code
with Metafont or MetaPost, which were originally written in
Pascal.  It is part of the GNU project of the Free Software
Foundation.

> On the tools especially, I would like to hear experiences of people
> using different tools and better tools, perhaps even tools for building
> attributed grammars.

I use GNU Bison for the parser.  I generate a C parser, but
I've written the rule actions in C++.  I use Flex for
other parts of the project, but not for generating the
scanning function for 3DLDF itself.  Instead, I wrote
'yylex()' by hand.  It uses what I call the "category code"
approach to scanning rather than regular expressions.
It's based on the way TeX and Metafont perform scanning.

I use Emacs for development and have written quite a bit of
Emacs-Lisp code over the years.  I compile with GCC (The GNU
Compiler Collection) and use GDB (the GNU debugger) for
debugging.  I use Texinfo for the manual.  I use
TeX, dvips, ImageMagick, and netpbm for manipulating the
images produced by 3DLDF.  I may be forgetting some tools I
use.

Metafont is a very interesting language and I've learned a
lot by trying to implement a similar language myself.  One
of the most interesting aspects is the hierarchical
structure of expressions, which makes it possible to specify
the precedence of operations implicitly in the parser rules.
For example, instead of a single non-terminal symbol
'point', I have 'point_primary', 'point_secondary',
'point_tertiary', and 'point_expression'.
Multiplication and division take place at the secondary level:

  970 point_secondary: point_primary
  971                | point_secondary times_or_over numeric_primary


Addition at the tertiary level:

  980 point_tertiary: point_secondary
  981               | point_tertiary PLUS point_secondary

Hans Aberg has published an article on his own research on a
similar topic, but I don't have the reference handy.

Now that I've written the parser, my next major project is
to implement surface-hiding using vector methods, rather
than the raster methods used by most rendering packages.
This involves programming routines for finding the
intersections of various geometrical figures.  To my dismay,
I've discovered that intersection theory is a non-trivial
branch of mathematics.  I'm also particularly interested in
polyhedra.

Perhaps the most important aspect of the project has been
the opportunity to gain an insight into a part of Don
Knuth's work.  I would like to write a second parser that
implements a machine-like language for fast loading of
format files, which would lead me further into his work,
his specialty being machine language.

> I can make the assignments (and a solution) available on request.

I don't believe in programming exercises --- I've never done
one.  If any of your students are looking for something to
do, I could keep several of them busy for a long, long time.

I hope you find this information useful --- and thanks for
asking.

Laurence Finston
http://www.gnu.org/software/3dldf/LDF.html