compiler-compilers

[dr.mt...@gmail.com]

In between  domestic chores and financial paperwork,  I'm looking at the history of compiler-compilers and finding out just how old they are.  In fact the first was Meta II

in 1963!  Meta II was written in Meta I.   I got into this area through Gyorgy Lajos who made it into his Ph.D.    He developed a compiler-compiler called MetaLisp and I used the architecture for Shen-YACC.   But unlike Gyorgy I didn't see this as a general way of writing all programs.

Re Shen-YACC you can write some cuties like

(defcc <len>
  {(list A) ==> number}
   _ <len> := (+ 1 <len>);
   <e> := 0;)
   
(defcc <rev>
  {(list A) ==> (list A)}
  X <rev> := (append <rev> [X]);
  <e>;)
         
(defcc <last>
  {(list A) ==> A}
  _ <last> := <last>;
  X := X;)  

viz.

(179+) (compile (fn <rev>) [1 2 3])
[3 2 1] : (list number)

(180+) (compile (fn <last>) [a b c])
c : symbol

(181+) (compile (fn <len>) [a b c d])
4 : number

But these encodings are slower than the equivalent Shen versions and the procedure doesn't really fit functions of an arity > 1.   Shen-YACC works best on compilers which is of course what it was meant for.

It's an old field and so I started reading Aho and Ullman which was the 70s classic on compiler writing and it seems dated today.  I think because a lot of effort went into making parsing fast and the languages used were procedural.  It's a bit like a travel guide that begins 'Before setting off, make sure your horse is well rested and fed'.   The issues that, IMO, they struggled with were a product of low level languages and very very slow machines.

I think if you wrote a book on compiler design based on Shen-YACC it would be a very different book than these old classics.   Just to begin, the division of compilation into lexing and parsing is not as rigid.  In you look at the sources for Shen you see that the lexing and parsing are seamless.

M.