My Master's Thesis
NOTE that I have since switched from the term "adaptable",
which I used in my thesis for compatibility with
to the more technically accurate "adaptive".
Recursive Adaptable Grammars
by John N. Shutt
Context-Free Grammars (CFGs) are a simple and intuitively appealing
formalism for the description of programming languages, but lack
the computational power to describe many common language features.
Over the past three decades,
numerous extensions of the CFG model have been developed.
Most of these extensions retain a CFG kernel,
and augment it with a distinct facility with greater computational power.
However, in all the most powerful CFG extensions,
the clarity of the CFG kernel is undermined
by the opacity of the more powerful extending facility.
An intuitively appealing strategy for CFG extension is grammar adaptability,
the principle that declarations in a program effectively modify the
context-free grammar of the programming language. An adaptable grammar
is equipped with some formal means for modifying its own CFG kernel.
Most previous adaptable grammar formalisms have, unfortunately,
failed to realize the potential clarity of this concept. In this thesis,
a representative sample of previous grammar formalisms is surveyed.
Based on insights gleaned from the survey,
a novel adaptable grammar formalism (Recursive Adaptable Grammars, RAGs)
is proposed that attempts to combine Turing-power
with the conceptual elegance and simplicity of CFGs.
I've HTMLized most of chapter 0,
including an extended summary of the whole thesis.
Much of the information from the thesis has been woven into my pages on
The complete thesis is available as:
my other Academic Work.