The Concept of Grammar Adaptivity

This page is Copyright John N. Shutt 1996–2001, 2007.  Here's what you're allowed to do with it.
Last modified:  05-Jul-07.

If programming languages aren't context-free, why are we always writing CFGs for them?  (And don't say, "Because it's useful to do so;" that begs the question:  Why is it useful?)

Even though most programming languages aren't context-free as such, they are locally context-free, in the sense that the set of permissible expressions within a small region in a particular program can be described by a context-free grammar.  This idea was first suggested, as far as I know, by Caracciolo in 1963.

Another way of saying this is that the act of programming amounts to the construction of a new programming language:  declarations add to the language, encapsulation subtracts from it.  This view is explicitly recommended, for example, by Henning Christiansen in [Chri 88b], even the title of which is "Programming as language development".  Christiansen observes that this view is not uncommon in the literature of programming methodology (where it is separate from formal grammars); as examples, he cites [Dahl 72, Wino 79].

The notion of programming as language development is carried to a logical extreme by the RAG formalism, in which the only meaning of a syntactic construct is its grammatical effect.  That is, the domain of semantic values is exactly the domain of metasyntactic values; see What is a Grammar?.


The principle that the rule set of a grammar should be allowed to vary is called grammar adaptivity.  There's a more precise definition on another page.  Several formal adaptive grammar models have been proposed, but none of them have been widely accepted.  In fact, some of the researchers seem to have been substantially unaware of previous work in the field.  An important exception is the recent work of Henning Christiansen, whose survey of the subject [Chri 90] provided most of the basic references on which my own work draws.


Next: What is an adaptive grammar?
Up: Adaptive Grammars

See also: The future of the concept