{"history":[],"article":{"id":"9d0d4e65-e655-4450-8b06-63512bf31453","title":"Adaptive grammar","slug":"adaptive-grammar","content":":::summary\n:::\n\n# \nAn **adaptive grammar** is a [formal grammar](https://bliptext.com/articles/formal-grammar) that explicitly provides mechanisms within the [formalism](https://bliptext.com/articles/formal-system) to allow its own [production rules](https://bliptext.com/articles/production-rule-formal-languages) to be manipulated.\n\n# Overview\nJohn N. Shutt defines adaptive grammar as a grammatical formalism that allows rule sets (aka sets of production rules) to be explicitly manipulated within a grammar.\nTypes of manipulation include rule addition, deletion, and modification.\n\n## Early history\nThe first description of grammar adaptivity (though not under that name) in the literature is generally taken to be in a paper by Alfonso Caracciolo di Forino published in 1963.\nThe next generally accepted reference to an adaptive formalism (extensible context-free grammars) came from Wegbreit in 1970 in the study of [extensible programming](https://bliptext.com/articles/extensible-programming) languages, followed by the dynamic syntax of Hanford and Jones in 1973.\n\n## Collaborative efforts\nUntil fairly recently, much of the research into the [formal](https://bliptext.com/articles/formal-system) properties of adaptive grammars was uncoordinated between researchers, only first being summarized by Henning Christiansen in 1990 in response to a paper in ACM [SIGPLAN](https://bliptext.com/articles/sigplan) Notices by Boris Burshteyn.\nThe Department of Engineering at the [University of São Paulo](https://bliptext.com/articles/university-of-s-o-paulo) has its [Adaptive Languages and Techniques Laboratory](https://bliptext.com/articles/undefined), specifically focusing on research and practice in adaptive technologies and theory.\nThe LTA also maintains a page naming researchers in the field.\n\n## Terminology and taxonomy\nWhile early efforts made reference to dynamic syntax and extensible, modifiable, dynamic, and adaptable grammars, more recent usage has tended towards the use of the term adaptive (or some variant such as adaptativa, depending on the publication language of the literature).\nIwai refers to her formalism as adaptive grammars, but this specific use of simply adaptive grammars is not typically currently used in the literature without name qualification.\nMoreover, no standardization or categorization efforts have been undertaken between various researchers, although several have made efforts in this direction.\n\n### The Shutt classification (and extensions)\nShutt categorizes adaptive grammar models into two main categories:\nJackson refines Shutt's taxonomy, referring to changes over time as [global](https://bliptext.com/articles/global-variable) and changes over space as [local](https://bliptext.com/articles/local-variable), and adding a hybrid time-space category:\n\n# Adaptive formalisms in the literature\nAdaptive formalisms may be divided into two main categories: full grammar formalisms (adaptive grammars), and adaptive machines, upon which some grammar formalisms have been based.\n\n## Adaptive grammar formalisms\nThe following is a list (by no means complete) of grammar formalisms that, by Shutt's definition above, are considered to be (or have been classified by their own inventors as being) adaptive grammars.\nThey are listed in their historical order of first mention in the literature.\n\n### Extensible context-free grammars (Wegbreit)\nDescribed in Wegbreit's doctoral dissertation in 1970, an extensible [context-free grammar](https://bliptext.com/articles/context-free-grammar) consists of a [context-free grammar](https://bliptext.com/articles/context-free-grammar) whose rule set is modified according to instructions output by a [finite state transducer](https://bliptext.com/articles/finite-state-transducer) when reading the terminal prefix during a leftmost derivation.\nThus, the rule set varies over position in the generated string, but this variation ignores the hierarchical structure of the syntax tree.\nExtensible context-free grammars were classified by Shutt as imperative.\n\n### Christiansen grammars (Christiansen)\nFirst introduced in 1985 as Generative Grammars and later more elaborated upon, Christiansen grammars (apparently dubbed so by Shutt, possibly due to conflict with Chomsky generative grammars) are an adaptive extension of [attribute grammars](https://bliptext.com/articles/attribute-grammar).\nChristiansen grammars were classified by Shutt as declarative.\nThe redoubling language is demonstrated as follows:\n →

\nwhere w-rule =\n → w\n → \n> → <ε>\n → a\n\n### Bottom-up modifiable grammars, top-down modifiable grammars, and USSA (Burshteyn)\nFirst introduced in May 1990 and later expanded upon in December 1990, modifiable grammars explicitly provide a mechanism for the addition and deletion of rules during a parse.\nIn response to the ACM SIGPLAN Notices responses, Burshteyn later modified his formalism and introduced his adaptive Universal Syntax and Semantics Analyzer (USSA) in 1992.\nThese formalisms were classified by Shutt as imperative.\n\n### Recursive adaptive grammars (Shutt)\nIntroduced in 1993, Recursive Adaptive Grammars (RAGs) were an attempt to introduce a [Turing powerful](https://bliptext.com/articles/turing-completeness) formalism that maintained much of the elegance of [context-free grammars](https://bliptext.com/articles/context-free-grammar).\nShutt self-classifies RAGs as being a declarative formalism.\n\n### Dynamic grammars (Boullier)\nBoullier's dynamic grammars, introduced in 1994, appear to be the first adaptive grammar family of grammars to rigorously introduce the notion of a time continuum of a parse as part of the notation of the grammar formalism itself.\nDynamic grammars are a sequence of grammars, with each grammar Gi differing in some way from other grammars in the sequence, over time.\nBoullier's main paper on dynamic grammars also defines a dynamic parser, the machine that effects a parse against these grammars, and shows examples of how his formalism can handle such things as [type checking](https://bliptext.com/articles/type-checking), [extensible languages](https://bliptext.com/articles/extensible-programming-language), [polymorphism](https://bliptext.com/articles/polymorphism-computer-science), and other constructs typically considered to be in the semantic domain of programming language translation.\n\n### Adaptive grammars (Iwai)\nThe work of Iwai in 2000 takes the adaptive automata of Neto further by applying adaptive automata to [context-sensitive grammars](https://bliptext.com/articles/context-sensitive-grammar).\nIwai's adaptive grammars (note the qualifier by name) allow for three operations during a parse: ?\nquery (similar in some respects to a [syntactic predicate](https://bliptext.com/articles/syntactic-predicate), but tied to inspection of rules from which modifications are chosen), + addition, and - deletion (which it shares with its predecessor adaptive automata).\n\n### §-calculus (Jackson)\nIntroduced in 2000 and most fully discussed in 2006, the §-Calculus (§ here pronounced meta-ess) allows for the explicit addition, deletion, and modification of productions within a grammar, as well as providing for [syntactic predicates](https://bliptext.com/articles/syntactic-predicate).\nThis formalism is self-classified by its creator as both imperative and adaptive, or, more specifically, as a time-space adaptive grammar formalism, and was further classified by others as being an [analytic](https://bliptext.com/articles/analytic-grammar) formalism.\nThe redoubling language is demonstrated as follows:\ngrammar ww {\nS ::= #phi(A.X<-\"\") R; R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R; };\n(Note on notation: In the above example, the #phi(...) statements identify the points in the production R that modify the grammar explicitly. #phi(A.X<-A.X C) represents a global modification (over time) and the #phi(N<=A.X) statement identifies a local modification (over space). The #phi(A.X<-\"\") statement in the S production effectively declares a global production called A.X by placing the [empty string](https://bliptext.com/articles/empty-string) into that production before its reference by R.)\n\n### Adaptive devices (Neto & Pistori)\nFirst described by Neto in 2001, adaptive devices were later enhanced and expanded upon by Pistori in 2003.\n\n### Adapser (Carmi)\nIn 2002, Adam Carmi introduced an [LALR(1)](https://bliptext.com/articles/lalr-parser)-based adaptive grammar formalism known as Adapser.\nSpecifics of the formalism do not appear to have been released.\n\n### Adaptive CFGs with appearance checking (Bravo)\nIn 2004, César Bravo introduced the notion of merging the concept of appearance checking with adaptive context-free grammars, a restricted form of Iwai's adaptive grammars, showing these new grammars, called Adaptive CFGs with Appearance Checking to be [Turing powerful](https://bliptext.com/articles/turing-complete).\n\n## Adaptive machine formalisms\nThe formalisms listed below, while not grammar formalisms, either serve as the basis of full grammar formalisms, or are included here because they are adaptive in nature.\nThey are listed in their historical order of first mention in the literature.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T08:36:26.348Z","updated_at":"2025-01-26T08:36:26.348Z","search_vector":"'adapt':1 'grammar':2","search_content":" \n \n\n# \nAn **adaptive grammar** is a [formal grammar](https://bliptext.com/articles/formal-grammar) that explicitly provides mechanisms within the [formalism](https://bliptext.com/articles/formal-system) to allow its own [production rules](https://bliptext.com/articles/production-rule-formal-languages) to be manipulated.\n\n# Overview\nJohn N. Shutt defines adaptive grammar as a grammatical formalism that allows rule sets (aka sets of production rules) to be explicitly manipulated within a grammar.\nTypes of manipulation include rule addition, deletion, and modification.\n\n## Early history\nThe first description of grammar adaptivity (though not under that name) in the literature is generally taken to be in a paper by Alfonso Caracciolo di Forino published in 1963.\nThe next generally accepted reference to an adaptive formalism (extensible context-free grammars) came from Wegbreit in 1970 in the study of [extensible programming](https://bliptext.com/articles/extensible-programming) languages, followed by the dynamic syntax of Hanford and Jones in 1973.\n\n## Collaborative efforts\nUntil fairly recently, much of the research into the [formal](https://bliptext.com/articles/formal-system) properties of adaptive grammars was uncoordinated between researchers, only first being summarized by Henning Christiansen in 1990 in response to a paper in ACM [SIGPLAN](https://bliptext.com/articles/sigplan) Notices by Boris Burshteyn.\nThe Department of Engineering at the [University of São Paulo](https://bliptext.com/articles/university-of-s-o-paulo) has its [Adaptive Languages and Techniques Laboratory](https://bliptext.com/articles/undefined), specifically focusing on research and practice in adaptive technologies and theory.\nThe LTA also maintains a page naming researchers in the field.\n\n## Terminology and taxonomy\nWhile early efforts made reference to dynamic syntax and extensible, modifiable, dynamic, and adaptable grammars, more recent usage has tended towards the use of the term adaptive (or some variant such as adaptativa, depending on the publication language of the literature).\nIwai refers to her formalism as adaptive grammars, but this specific use of simply adaptive grammars is not typically currently used in the literature without name qualification.\nMoreover, no standardization or categorization efforts have been undertaken between various researchers, although several have made efforts in this direction.\n\n### The Shutt classification (and extensions)\nShutt categorizes adaptive grammar models into two main categories:\nJackson refines Shutt's taxonomy, referring to changes over time as [global](https://bliptext.com/articles/global-variable) and changes over space as [local](https://bliptext.com/articles/local-variable), and adding a hybrid time-space category:\n\n# Adaptive formalisms in the literature\nAdaptive formalisms may be divided into two main categories: full grammar formalisms (adaptive grammars), and adaptive machines, upon which some grammar formalisms have been based.\n\n## Adaptive grammar formalisms\nThe following is a list (by no means complete) of grammar formalisms that, by Shutt's definition above, are considered to be (or have been classified by their own inventors as being) adaptive grammars.\nThey are listed in their historical order of first mention in the literature.\n\n### Extensible context-free grammars (Wegbreit)\nDescribed in Wegbreit's doctoral dissertation in 1970, an extensible [context-free grammar](https://bliptext.com/articles/context-free-grammar) consists of a [context-free grammar](https://bliptext.com/articles/context-free-grammar) whose rule set is modified according to instructions output by a [finite state transducer](https://bliptext.com/articles/finite-state-transducer) when reading the terminal prefix during a leftmost derivation.\nThus, the rule set varies over position in the generated string, but this variation ignores the hierarchical structure of the syntax tree.\nExtensible context-free grammars were classified by Shutt as imperative.\n\n### Christiansen grammars (Christiansen)\nFirst introduced in 1985 as Generative Grammars and later more elaborated upon, Christiansen grammars (apparently dubbed so by Shutt, possibly due to conflict with Chomsky generative grammars) are an adaptive extension of [attribute grammars](https://bliptext.com/articles/attribute-grammar).\nChristiansen grammars were classified by Shutt as declarative.\nThe redoubling language is demonstrated as follows:\n → \nwhere w-rule =\n → w\n → \n > → \n → a\n\n### Bottom-up modifiable grammars, top-down modifiable grammars, and USSA (Burshteyn)\nFirst introduced in May 1990 and later expanded upon in December 1990, modifiable grammars explicitly provide a mechanism for the addition and deletion of rules during a parse.\nIn response to the ACM SIGPLAN Notices responses, Burshteyn later modified his formalism and introduced his adaptive Universal Syntax and Semantics Analyzer (USSA) in 1992.\nThese formalisms were classified by Shutt as imperative.\n\n### Recursive adaptive grammars (Shutt)\nIntroduced in 1993, Recursive Adaptive Grammars (RAGs) were an attempt to introduce a [Turing powerful](https://bliptext.com/articles/turing-completeness) formalism that maintained much of the elegance of [context-free grammars](https://bliptext.com/articles/context-free-grammar).\nShutt self-classifies RAGs as being a declarative formalism.\n\n### Dynamic grammars (Boullier)\nBoullier's dynamic grammars, introduced in 1994, appear to be the first adaptive grammar family of grammars to rigorously introduce the notion of a time continuum of a parse as part of the notation of the grammar formalism itself.\nDynamic grammars are a sequence of grammars, with each grammar Gi differing in some way from other grammars in the sequence, over time.\nBoullier's main paper on dynamic grammars also defines a dynamic parser, the machine that effects a parse against these grammars, and shows examples of how his formalism can handle such things as [type checking](https://bliptext.com/articles/type-checking), [extensible languages](https://bliptext.com/articles/extensible-programming-language), [polymorphism](https://bliptext.com/articles/polymorphism-computer-science), and other constructs typically considered to be in the semantic domain of programming language translation.\n\n### Adaptive grammars (Iwai)\nThe work of Iwai in 2000 takes the adaptive automata of Neto further by applying adaptive automata to [context-sensitive grammars](https://bliptext.com/articles/context-sensitive-grammar).\nIwai's adaptive grammars (note the qualifier by name) allow for three operations during a parse: ?\nquery (similar in some respects to a [syntactic predicate](https://bliptext.com/articles/syntactic-predicate), but tied to inspection of rules from which modifications are chosen), + addition, and - deletion (which it shares with its predecessor adaptive automata).\n\n### §-calculus (Jackson)\nIntroduced in 2000 and most fully discussed in 2006, the §-Calculus (§ here pronounced meta-ess) allows for the explicit addition, deletion, and modification of productions within a grammar, as well as providing for [syntactic predicates](https://bliptext.com/articles/syntactic-predicate).\nThis formalism is self-classified by its creator as both imperative and adaptive, or, more specifically, as a time-space adaptive grammar formalism, and was further classified by others as being an [analytic](https://bliptext.com/articles/analytic-grammar) formalism.\nThe redoubling language is demonstrated as follows:\ngrammar ww {\nS ::= #phi(A.X<-\"\") R; R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R; };\n(Note on notation: In the above example, the #phi(...) statements identify the points in the production R that modify the grammar explicitly. #phi(A.X<-A.X C) represents a global modification (over time) and the #phi(N<=A.X) statement identifies a local modification (over space). The #phi(A.X<-\"\") statement in the S production effectively declares a global production called A.X by placing the [empty string](https://bliptext.com/articles/empty-string) into that production before its reference by R.)\n\n### Adaptive devices (Neto & Pistori)\nFirst described by Neto in 2001, adaptive devices were later enhanced and expanded upon by Pistori in 2003.\n\n### Adapser (Carmi)\nIn 2002, Adam Carmi introduced an [LALR(1)](https://bliptext.com/articles/lalr-parser)-based adaptive grammar formalism known as Adapser.\nSpecifics of the formalism do not appear to have been released.\n\n### Adaptive CFGs with appearance checking (Bravo)\nIn 2004, César Bravo introduced the notion of merging the concept of appearance checking with adaptive context-free grammars, a restricted form of Iwai's adaptive grammars, showing these new grammars, called Adaptive CFGs with Appearance Checking to be [Turing powerful](https://bliptext.com/articles/turing-complete).\n\n## Adaptive machine formalisms\nThe formalisms listed below, while not grammar formalisms, either serve as the basis of full grammar formalisms, or are included here because they are adaptive in nature.\nThey are listed in their historical order of first mention in the literature.","revisionCount":0},"hasMore":false,"nextCursor":null}

History