hn-classics/_stories/2009/14434209.md

---
created_at: '2017-05-28T12:55:35.000Z'
title: Growing a Compiler (2009)
url: http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/gem/html/GrowingCompiler.html
author: ingve
points: 234
story_text: 
comment_text: 
num_comments: 16
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1495976135
_tags:
- story
- author_ingve
- story_14434209
objectID: '14434209'
year: 2009

---
[Source](http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/gem/html/GrowingCompiler.html "Permalink to Growing a Compiler")

# Growing a Compiler

# Growing a Compiler

by Bill McKeeman and Lu He

MathWorks and Dartmouth, May 2009

## Contents

* [Abstract][1]
* [Chapters][2]
* [Notes][3]
* [References][4]
* [Signatures][5]

## Abstract

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 accomodate 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. 

## Chapters

1. [Base GEM][6]
    * statement of the problem
    * executable grammars
    * simple examples
2. [Robust GEM][7]
    * pre-entered character classes
    * using nowhite, pretty, invert
3. [GEM with builtin nowhite and chars][8]
    * using multi-character input and output symbols
    * left-associative arithmetic expressions
    * X86 floating point stack
4. [GEM with builtin multichar symbols][9]
    * using Kleene * and + in executable grammars
5. [Running Intel X86 code][10]
    * X86 Assembler
    * calculator
    * atoi
6. [Plenty Phrase Names][11]
    * BNF
    * self
    * pretty

## Notes

The origin of the idea is a undergraduate thesis (UC Santa Cruz, 1978) written by Doug Michels under the supervsion of Bill McKeeman. 

The title is inspired by: Guy Steele's 1998 OOPSLA talk _Growing a Language_. 

Thanks to Steve Johnson for critical advice in the preparation of this presentation.

The default font sizes in Firefox are uncomfortably large for this paper. Try [view][edit][zoom][text only][zoom out][zoom out]. 

## References

* Bill McKeeman [ Compiler and Compiler Course][12]
* Wikipedia [Mealy Machine][13]
* Guy Steele [ Growing a Language][14]. 
* Doug Michels [ A concise extensible metalanguage for translator implementation][15]

## Signatures

* _Bill McKeeman_ , MathWorks Fellow 
* _Lu He_, Computer Science Department, Dartmouth 

An earlier version was presented to the Computer Science Colloquium, Stanford, March 4, 2009

  
Published with MATLAB® 7.7  

[1]: http://www.cs.dartmouth.edu#1
[2]: http://www.cs.dartmouth.edu#2
[3]: http://www.cs.dartmouth.edu#3
[4]: http://www.cs.dartmouth.edu#4
[5]: http://www.cs.dartmouth.edu#5
[6]: http://www.cs.dartmouth.edu/GrowingCompilerCh1.html
[7]: http://www.cs.dartmouth.edu/GrowingCompilerCh2.html
[8]: http://www.cs.dartmouth.edu/GrowingCompilerCh3.html
[9]: http://www.cs.dartmouth.edu/GrowingCompilerCh4.html
[10]: http://www.cs.dartmouth.edu/GrowingCompilerCh5.html
[11]: http://www.cs.dartmouth.edu/GrowingCompilerCh6.html
[12]: http://www.mathworks.com/matlabcentral/fileexchange/20149
[13]: http://en.wikipedia.org/wiki/Mealy_machine
[14]: http://www.brics.dk/~hosc/local/HOSC-12-3-pp221-236.pdf
[15]: http://www.cs.dartmouth.edu/michels1978.pdf