Imperative Adaptive Grammars

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.

An imperative adaptive grammar model is a grammar model in which the explicit manipulation of rule sets is accomplished by imperative means (as opposed to declarative; see What is an adaptive grammar? ).  That is, the rule set is varied over time during parsing:  the set of rules available to expand a given instance of a nonterminal depends necessarily on when it is expanded (not just on where that instance occurs in the syntax tree).

Because of this time-dependence, imperative adaptive grammars generally have a global internal state, typically just the set of production rules.  Consequently, they have configurations, in the same sense that an automaton has configurations.  The derivation relation of an imperative adaptive grammar often bears a striking resemblance to the computation relation of an automaton.  See What is a grammar?.

Here is a list of some imperative adaptive grammar models I know about.  I've written HTML summaries of the ones I understand, and most of them are discussed at greater length in my Master's thesis.  (Some other, more recent models are mentioned in the Wikipedia article "Adaptive grammar".)

A characteristic of the entire family of imperative adaptive grammars is that each grammar is inherently dependent on the parsing algorithm used.  The consequences of a rule-set modification instruction depend on what decisions will be made by the parser, and in what order.  (This effect is illustrated particularly well by Burshteyn's model.)

Next: Declarative adaptive grammars
Prev: What is an adaptive grammar?
Up: Adaptive Grammars