Stanford EE Computer Systems Colloquium

4:15PM, Wednesday, Mar 04, 2009
HP Auditorium, Gates Computer Science Building B01

Executable Grammars
Seeking the minimal extendable self-compiling compiler.

Bill McKeeman
MathWorks and Dartmouth College
About the talk:

My goal is the smallest extendable self-compiling compiler.

The context-free grammar <VN,VT,Π,G> is extended to include two terminal vocabularies and multiple goals: <VN,VI,VO,Π,VG>. The extension (called an i-o grammar) is convenient for expressing closely related languages, finite automata, and some simple translation tasks.

Each concrete grammar is expressed in a programming-language like notation. Such a grammar can be directly executed with a back-tracking Grammar Executing Machine (about 200 lines of C). As it happens, the concrete grammar is symmetrical (right-to-left and left-to-right) so that backtracking is accomplished by executing the grammar in reverse.

One capability of the concrete grammars is self-description and generated extensions. Examples include scanning, pretty printing, and inversion.

This material is one lecture in my online MATLAB-based compiler course.

Since this talk was presented, a new version of the talk has become available.


Reference materials for this talk can be found HERE.

About the speaker:

I am presently a Fellow at the MathWorks and adjunct faculty at the Computer Science Department of Dartmouth College. I was previously at Digital, Harvard, the Wang Institute, Xerox Research, UC Santa Cruz, Stanford and the US Naval Academy. My interests are in programming, programming languages, and compilers.

Contact information: