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.
This joint meeting of the Boston Chapter of the IEEE Computer Society and GBC/ACM.
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.
