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.