Can a Tiny Compiler-Compiler Grow Into Something Useful?

Abstract

Context-free grammars are extended to accomodate output. A grammar executing machine 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. In this manner, one can start from a small beginning and bootstrap towards a conventional compiler.

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, opening the possibility of indefinite extension.

This development stops well short of even a simple conventional compiler but that is not because of any known limitations to the approach.

This comes from the two MathWorks file exchange entries:

http://www.mathworks.com/matlabcentral/fileexchange/23255

http://www.mathworks.com/matlabcentral/fileexchange/24026

bio:
Bill McKeeman is adjunct faculty at the Computer Science Department of Dartmouth College. He recently retired as a Fellow at the MathWorks and was previously a Senior Consulting Engineer at Digital. He taught at Harvard, the Wang Institute, UC Santa Cruz, Stanford and the US Naval Academy. His interests are in programming, programming languages, and compilers.