Adaptive grammar
Encyclopedia
An adaptive grammar is a formal grammar
that explicitly provides mechanisms within the formalism
to allow its own production rules to be manipulated.
Types of manipulation include rule addition, deletion, and modification.
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
Notices by Boris Burshteyn. The Department of Engineering at the University of São Paulo
has its Adaptive Languages and Techniques Laboratory, specifically focusing on research and practice in adaptive technologies and theory. The LTA also maintains a page naming researchers in the field.
Jackson refines Shutt's taxonomy, referring to changes over time as global
and changes over space as local
, and adding a hybrid time-space category:
whose rule set is modified according to instructions output by a finite state transducer
when reading the terminal prefix during a leftmost derivation. Thus, the rule set varies over position in the generated string, but this variation ignores the hierarchical structure of the syntax tree. Extensible context-free grammars were classified by Shutt as imperative.
s. Christiansen grammars were classified by Shutt as declarative.
The redoubling language
is demonstrated as follows:
G> → G↑w> w-rule}>
where w-rule =
G’> → w
G↑ch•w> → G↑ch> G↑w>
> → <ε>
→ a
formalism that maintained much of the elegance of context-free grammars. Shutt self-classifies RAGs as being a declarative formalism.
grammars. Iwai's adaptive grammars (note the qualifier by name) allow for three operations during a parse: ? query (similar in some respects to a syntactic predicate
, but tied to inspection of rules from which modifications are chosen), + addition, and - deletion (which it shares with its predecessor adaptive automata).
s. This 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 formalism.
The redoubling language
is demonstrated as follows:
grammar ww {
S ::= #phi(A.X<-"") R;
R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R;
};
(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
into that production before its reference by R.)
-based adaptive grammar formalism known as Adapser. Specifics of the formalism do not appear to have been released.
Self-Modifying Finite State Automata (Shutt & Rubinstein)
Adaptive Automata (Neto)
Post-Secondary Level Courses Covering Adaptive Grammar
List of Researchers in Adaptive Grammars
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
that explicitly provides mechanisms within the formalism
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
to allow its own production rules to be manipulated.
Overview
John N. Shutt defines adaptive grammars as follows:- ADAPTIVE GRAMMAR MODEL: A grammatical formalism that allows rule sets (aka sets of production rules) to be explicitly manipulated within a grammar.
Types of manipulation include rule addition, deletion, and modification.
Early history
The 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. The next generally accepted reference to an adaptive formalism (extensible context-free grammars) came from Wegbreit in 1970 in the study of extensible programming languages, followed by the dynamic syntax of Hanford and Jones in 1973.Collaborative efforts
Until fairly recently, much of the research into the formalFormal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
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
SIGPLAN
SIGPLAN is the Association for Computing Machinery's Special Interest Group on programming languages.- Conferences :* Principles of Programming Languages * Programming Language Design and Implementation...
Notices by Boris Burshteyn. The Department of Engineering at the University of São Paulo
University of São Paulo
Universidade de São Paulo is a public university in the Brazilian state of São Paulo. It is the largest Brazilian university and one of the country's most prestigious...
has its Adaptive Languages and Techniques Laboratory, specifically focusing on research and practice in adaptive technologies and theory. The LTA also maintains a page naming researchers in the field.
Terminology and taxonomy
While 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). Iwai 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. Moreover, no standardization or categorization efforts have been undertaken between various researchers, although several have made efforts in this direction.The Shutt classification (and extensions)
Shutt categorizes adaptive grammar models into two main categories:- ImperativeImperative programmingIn computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
adaptive grammars vary their rules based on a global stateState (computer science)In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
changing over the time of the generationGenerative grammarIn theoretical linguistics, generative grammar refers to a particular approach to the study of syntax. A generative grammar of a language attempts to give a set of rules that will correctly predict which combinations of words will form grammatical sentences...
of a languageFormal languageA formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. - DeclarativeDeclarative programmingIn computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
adaptive grammars vary their rules only over the space of the generation of a language (i.e., position in the syntax tree of the generated string).
Jackson refines Shutt's taxonomy, referring to changes over time as global
Global variable
In computer programming, a global variable is a variable that is accessible in every scope . Interaction mechanisms with global variables are called global environment mechanisms...
and changes over space as local
Local variable
In computer science, a local variable is a variable that is given local scope. Such a variable is accessible only from the function or block in which it is declared. In programming languages with only two levels of visibility, local variables are contrasted with global variables...
, and adding a hybrid time-space category:
- Time-space adaptive grammars (hybrids) vary their rules over either the time or the space (or both) of the generation of a language (and local and global operations are explicitly differentiated by the notation for such changes).
Adaptive formalisms in the literature
Adaptive formalisms may be divided into two main categories: full grammar formalisms (adaptive grammars), and adaptive machines, upon which some grammar formalisms have been based.Adaptive grammar formalisms
The 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. They are listed in their historical order of first mention in the literature.Extensible Context-Free Grammars (Wegbreit)
Described in Wegbreit's doctoral dissertation in 1970, an extensible context-free grammar consists of a context-free grammarContext-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
whose rule set is modified according to instructions output by a finite state transducer
Finite state transducer
A finite state transducer is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton , which has a single tape.-Overview:...
when reading the terminal prefix during a leftmost derivation. Thus, the rule set varies over position in the generated string, but this variation ignores the hierarchical structure of the syntax tree. Extensible context-free grammars were classified by Shutt as imperative.
Christiansen Grammars (Christiansen)
First introduced in 1985 as Generative Grammars and later more elaborated upon, Christiansen grammars are an adaptive extension of attribute grammarAttribute grammar
An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler....
s. Christiansen grammars were classified by Shutt as declarative.
The redoubling language
is demonstrated as follows:where w-rule =
Bottom-Up Modifiable Grammars, Top-Down Modifiable Grammars, and USSA (Burshteyn)
First 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. In response to the ACM SIGPLAN Notices responses, Burshteyn later modified his formalism and introduced his adaptive Universal Syntax and Semantics Analyzer (USSA) in 1992. These formalisms were classified by Shutt as imperative.Recursive Adaptive Grammars (Shutt)
Introduced in 1993, Recursive Adaptive Grammars (RAGs) were an attempt to introduce a Turing powerfulTuring completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
formalism that maintained much of the elegance of context-free grammars. Shutt self-classifies RAGs as being a declarative formalism.
Dynamic Grammars (Boullier)
Boullier'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. Dynamic grammars are a sequence of grammars, with each grammar Gi differing in some way from other grammars in the sequence, over time. Boullier'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, extensible languages, polymorphism, and other constructs typically considered to be in the semantic domain of programming language translation.Adaptive Grammars (Iwai)
The work of Iwai in 2000 takes the adaptive automata of Neto further by applying adaptive automata to context-sensitiveContext-sensitive
Context-sensitive is an adjective meaning "depending on context" or "depending on circumstances". It may refer to:* Context-sensitive grammar* Context-sensitive language* Context-sensitive help* Context sensitive user interface in computing...
grammars. Iwai's adaptive grammars (note the qualifier by name) allow for three operations during a parse: ? query (similar in some respects to a syntactic predicate
Syntactic predicate
A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of dramatically improving the recognition strength of an LL...
, but tied to inspection of rules from which modifications are chosen), + addition, and - deletion (which it shares with its predecessor adaptive automata).
§-Calculus (Jackson)
Introduced 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 predicateSyntactic predicate
A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of dramatically improving the recognition strength of an LL...
s. This 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 formalism.
The redoubling language
is demonstrated as follows:grammar ww {
S ::= #phi(A.X<-"") R;
R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R;
};
(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
Empty string
In computer science and formal language theory, the empty string is the unique string of length zero. It is denoted with λ or sometimes Λ or ε....
into that production before its reference by R.)
Adaptive Devices (Neto & Pistori)
First described by Neto in 2001, adaptive devices were later enhanced and expanded upon by Pistori in 2003.Adapser (Carmi)
In 2002, Adam Carmi introduced an LALR(1)LALR parser
In computer science, an LALR parser is a type of LR parser based on a finite-state-automata concept. The data structure used by an LALR parser is a pushdown automaton...
-based adaptive grammar formalism known as Adapser. Specifics of the formalism do not appear to have been released.
Adaptive CFGs with Appearance Checking (Bravo)
In 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.Adaptive machine formalisms
The 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. They are listed in their historical order of first mention in the literature.Self-Modifying Finite State Automata (Shutt & Rubinstein)
- Introduced in 1994 by Shutt and Rubinstein, Self-Modifying Finite State Automata (SMFAs) are shown to be, in a restricted form, Turing powerful.
Adaptive Automata (Neto)
- In 1994, Neto introduced the machine he called a structured pushdown automaton, the core of adaptive automata theory as pursued by Iwai, Pistori, Bravo and others. This formalism allows for the operations of inspection (similar to syntactic predicateSyntactic predicateA syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of dramatically improving the recognition strength of an LL...
s, as noted above relating to Iwai's adaptive grammars), addition, and deletion of rules.
External links
Scholarly Conferences Specifically Covering Adaptive Aspects of Formal Languages- ICANNGA 2005 - 7th International Conference on Adaptive & Natural Computing Algorithms (Coimbra, Portugal, 23–25 March 2005)
- Adaptive Technology in AI (Presentations in various formalisms mentioned in this article.)
Post-Secondary Level Courses Covering Adaptive Grammar
- Fundamentos e Aplicações da Tecnologia Adaptativa (Escola Politécnica - University of São PauloUniversity of São PauloUniversidade de São Paulo is a public university in the Brazilian state of São Paulo. It is the largest Brazilian university and one of the country's most prestigious...
)
List of Researchers in Adaptive Grammars
- http://www.pcs.usp.br/~lta/f_pesquisadores.htm (Maintained by LTA)