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

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