Summaries of Adaptive Grammar Models

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

Up: Adaptive grammars

I've grouped the imperative and declarative models separately, and ordered them more-or-less chronologically within each group.

Most of these models are discussed at length in my Master's thesis.

Offline sources:  [Chri 90], [Shut 93].


ECFGs - 1970
DTTs - 1984
Modifiable Grammars - 1990

Dynamic Syntax - 1973
Christiansen Grammars - 1985
RAGs - 1993

Imperative models

ECFGs (Extensible Context-Free Grammars) - 1970

Developed by Ben Wegbreit at Harvard University in the late 1960s, as part of an extensible programming language called EL1.  A finite state transducer scans the input string in parallel with the parser, and outputs instructions telling the parser to add or delete rules.

Wegbreit was unable to determine whether all ECFLs are context-sensitive.

See:  Wikipedia article "ECL programming language".

Offline sources:  [Wegb 70].

DTTs (Dynamic Template Translators) - 1984

Developed by K. P. Mason at the University of Adelaide in the early 1980s.

A DTT is essentially a two-level grammar, in which rule-set modification instructions are part of the rules instantiated from rule schemata.  Modification instructions are applied by the derivation relation.

Without the adaptivity mechanism, DTTs would be van Wijngaarden grammars using a different terminology; and van Wijngaarden grammars are Turing-powerful.  In fact, when Mason proved that DTTs are Turing-powerful, he didn't use the adaptivity at all.

Offline sources:  [Maso 84], [Maso 87].

Modifiable Grammars - 1990

Developed by Boris Burshteyn around 1990, as a theoretical foundation for a programming language description language called USSA.  Actually, the USSA meta-language seems to have more in common with Christiansen's grammar model than with Burshteyn's.  However, USSA is not summarized here, as it is properly not a mathematical model at all.

A Modifiable Grammar consists of a CFG and a Turing transducer.  Given a partial derivation as input, the Turing transducer outputs a list of rules to be added, and another to be deleted.  Following the directions of this transducer, the parser modifies the rule set before each derivation step.

Since the purpose of the rule-set modifications is to guide the decisions made by the parser, the transducer must be designed with precise knowledge of the order in which the parser will make those decisions.  To allow for this, Burshteyn actually defines two grammar models, called TDMGs and BUMGs (Top-Down Modifiable Grammars and Bottom-Up Modifiable Grammars; I suspect that Burshteyn generally doesn't pronounce acronyms.)

As you might expect of a grammar with an embedded Turing Machine, Modifiable Grammars are Turing-Powerful.

Offline sources:  [Burs 90], [Robe 91], [Burs 92].

Declarative models

Dynamic Syntax - 1973

Suggested by K. V. Hanford and C. B. Jones in 1973.

In his Survey Of Adaptable Grammars [Chri 90], Christiansen aptly characterizes Dynamic Syntax:

Hanford and Jones (1973) have suggested a concept of dynamic syntax which is a monstrous device based on the -calculus. . . . Unfortunately the approach is not given a proper formalization or accompanied with an appropriate notation.

Offline sources:  [Hanf 73].

Christiansen Grammars - 1985

Developed by Henning Christiansen at Roskilde University in the mid-1980s.

A Christiansen grammar is essentially an EAG in which every nonterminal has a specially designated grammar attribute whose value is a set of grammar rules.  Each nonterminal is expanded, during derivation, via a rule taken from the value of its grammar attribute.  Rule sets are explicitly manipulated in the semantic equations for the grammar attributes (thus satisfying my definition of an adaptive grammar); and adaptations follow the block structure of the parse tree, since all rule-set values are localized to particular nodes of the tree.

Since Christiansen grammars add adaptivity to attribute grammars, and attribute grammars are already Turing-powerful, naturally Christiansen grammars are Turing-powerful.

Although he originally based his model on Watt and Madsen's EAGs, Christiansen reformulated the model around DCGs (Definite Clause Grammars) around 1990 and has clearly preferred the latter ever since.

A superficial idiosyncrasy of the earlier, EAG-based adaptive grammars is that Christiansen called them generative grammars, thus overloading the standard meaning of that term.  (Chomsky grammars use a generative, or transformational, approach to linguistics in preference to the historically orthodox descriptive approach.)  The later, DCG-based adaptive grammars present no such difficulty, as he has called them Generative Clause Grammars, GCGs.  I have chosen to use the term Christiansen Grammars to refer to his adaptive grammar model in both of its formulations.

Offline sources:  The original paper is [Chri 85]; a more developed treatment of the model is [Chri 88a].  The DCG-based formulation is described in [Chri 90], and carried further in the direction of logic meta-programming by [Chri 92a, Chri 92b].

RAGs (Recursive Adaptive Grammars) - 1993

Developed by me here at WPI in the early 1990s.  The subject of my Master's thesis.  If the following short description isn't enough for you, there's a more detailed explanation, HTMLized from my thesis (with a couple dozen small inlined images), on a separate page.

A RAG does not have separate value domains for terminals, nonterminals, and attributes.  Instead, each RAG has a single domain called an answer algebra, whose values (answers) are all capable of acting as syntax, metasyntax, or semantics depending on how they are used.  (See What is a grammar?.)

RAG unbound rules are similar to EAG rule forms, but in place of attributed nonterminals, an unbound rule has ordered pairs of polynomials.  The first component of each pair plays a metasyntactic role, and the second, semantic.  Answers are syntax when they occur outside of the ordered pairs.

Each answer has an associated set of unbound rules; these determine an associated set of possible bound rules, formed by substituting values for the variables in each unbound rule (using the answer itself as the metasyntax value on the left side of the rule).  The derivation relation can use bound rules to expand ordered pairs of answers.

In addition to the operators defined by the answer algebra, polynomials in an unbound rule can also use a special binary operator called the query operator.  The query operator treats its first operand as metasyntax and its second as syntax, and "returns" a semantic value.  Actually, the reduction of a query (i.e. polynomial using the query operator) to an answer is accomplished by the derivation relation, using a potentially unbounded number of steps.  In effect, the query operator allows an RAG parser to invoke itself recursively as part of a derivation step; hence the word "recursive" in the name of the model.

RAGs have both structured conditionals (through selection of bound rules during derivation) and recursion (through application of the query operator). So, naturally, RAGs are Turing-powerful.

Offline sources:  [Shut 93].

See: My Master's thesis

Up: Adaptive grammars