IEEE Computer Society and GBC/ACM

7:00 PM, Thursday, October 15, 2009

MIT Room E51-315

Growing a Compiler

Bill McKeeman, MathWorks and Dartmouth

Self-compiling compilers are common. The question is: How far can one go, bootstrapping a (very) small compiler-compiler into more capable compilers? Context-free grammars are extended to accommodate output. A grammar executing machine (GEM) is introduced which accepts an input text and a grammar, and outputs another text. Both the input text and the output text can also be grammars, permitting the production of ever more powerful grammars. GEM itself can be extended to build-in the capabilities of the previous grammars. The rules of the game require that changing GEM does not add to its original capability -- it merely makes the implementation more robust or faster. The grammars and the machine have some simple symmetries that lead to actions such as backtracking and decompiling. It is also possible to directly execute bit-strings in the Intel x86 hardware. Bill McKeeman photo

Bill got one of the first computer science PhDs from Stanford University (1966) and proceeded to teach there, at the University of Toronto and then the University of California Santa Cruz (where he became department head) for the next 13 years. He then spent 2 years at Xerox PARC before returning to teach at the Wang Institute (where he was chair of the faculty from 1981-84) and Harvard. He spent 1988-99 doing research and developing compilers at the Digital Equipment Corp (later Compaq). Bill has been at the MathWorks since 1999, where he is part of the Compiler Group and a MathWorks Fellow. He also teaches part time as an Adjunct Professor at Dartmouth.

Bill is the co-author (with JJ Horning and DB Wortman) of the classic text "A Compiler Generator" (Prentice-Hall, 1970), some chapters of a course book on compiler construction in the Springer Verlag lecture note series, and dozens of technical papers and patents.

This joint meeting of the Boston Chapter of the IEEE Computer Society and GBC/ACM will be held in MIT Room E51-315.  E51 is the Tang Center on the corner of Wadsworth and Amherst Sts and Memorial Dr.; it's mostly used by the Sloan School. You can see it on this map of the MIT campus. Room 315 is on the 3rd floor.

We have 2 email lists we use to send out talk announcements. Both are self-administered. You can access the forms for these at the following web addresses: and

We also have 2 websites with information about upcoming talks: and

For more information contact Peter Mager (p.mager AT

Updated: Aug 30, 2009.