適応型文法

Shuttは適応型文法モデルを2つの主要なカテゴリに分類しています。^{[ 3 ] [ 15 ]}

• 命令型適応文法は、言語生成の過程で変化するグローバルな状態に基づいて規則を変化させる。
• 宣言型適応文法は、言語生成の空間（つまり、生成された文字列の構文木における位置）においてのみ規則を変化させる

ジャクソンはシャットの分類法を改良し、時間経過に伴う変化をグローバル、空間経過に伴う変化をローカルと呼び、ハイブリッドな時間と空間のカテゴリーを追加している。^{[ 4 ]}

• 時間空間適応型文法（ハイブリッド）は、言語生成の時間または空間（あるいはその両方）にわたって規則を変化させます（そして、局所的操作と全体的操作は、そのような変化を表す表記法によって明示的に区別されます）。

1970 年の Wegbreit の博士論文^{[ 6 ]}で説明されている拡張可能な文脈自由文法は、左端導出中に終端接頭辞を読み取る際に有限状態トランスデューサによって出力される指示に従ってルールセットが変更される文脈自由文法から構成されます。したがって、ルールセットは生成された文字列内の位置によって変化しますが、この変化は構文木の階層構造を無視します。拡張可能な文脈自由文法は Shutt によって命令文法に分類されました。^{[ 3 ]}

1985年に生成文法^{[ 16 ]}として初めて導入され、後にさらに詳細化された^{[ 17 ]}クリスチャンセン文法（おそらくチョムスキー生成文法との衝突のため、シャットによってそう名付けられた）は、属性文法の適応的拡張である。クリスチャンセン文法はシャットによって宣言文法に分類された^{[ 3 ]}。

二重言語${\displaystyle L=\{ww|w{\mbox{は文字です}}\}}$以下のように実証されています。^{[ 17 ]}

<program↓ G > → <dcl↓ G ↑ w > <body↓{ w-rule }>

ここでw ルール = <body↓ G '> → w

<dcl↓ G ↑ ch • w > → <char↓ G ↑ ch > <dcl↓ G ↑ w > <dcl↓G↑<>> → <ε> <char↓G↑a> → a

1990 年 5 月に初めて導入され^{[ 8 ]}、その後 1990 年 12 月に拡張された^{[ 10 ]}修正可能な文法は、構文解析中に規則を追加および削除するメカニズムを明示的に提供します。ACM SIGPLAN Notices の応答に応じて、Burshteyn は後に自身の形式体系を修正し、1992 年に適応型ユニバーサル構文および意味解析器(USSA)を導入しました。 ^{[ 18 ]}これらの形式体系は Shutt によって命令型に分類されました。^{[ 3 ]}

1993年に導入された再帰適応文法（RAG）は、文脈自由文法の優雅さの多くを維持しつつ、チューリング級に強力な形式体系を導入しようとする試みでした。^{[ 3 ]} ShuttはRAGを宣言的形式体系として自ら分類しています。

1994 年に導入されたBoullier の動的文法^{[ 11 ]}は、構文解析の時間連続体の概念を文法形式体系自体の表記の一部として厳密に導入した最初の適応文法ファミリーであると思われる。^{[ 4 ]}動的文法は文法のシーケンスであり、各文法G _iは時間の経過とともにシーケンス内の他の文法と何らかの点で異なっている。動的文法に関する Boullier の主要論文では、これらの文法に対して構文解析を実行する機械である動的パーサーも定義されており、彼の形式体系が、型チェック、拡張可能な言語、多相性、および通常プログラミング言語翻訳の意味領域にあると考えられるその他の構成要素をどのように処理できるかの例が示されている。

2000年の岩井の研究^{[ 13 ]}は、適応型オートマトンを文脈依存文法に適用することで、Neto ^{[ 19 ]}の適応型オートマトンをさらに発展させたものである。岩井の適応型文法（名前の修飾語に注意）は、構文解析中に3つの操作を可能にする。 ?クエリ（構文述語といくつかの点で似ているが、変更が選択される規則の検査に結びついている）、+追加、および-削除（これは前身の適応型オートマトンと共有されている）。 

2000年に導入され^{[ 20 ]}、2006年に最も詳細に議論された^{[ 4 ]} §計算（§はメタエスと発音される）は、文法内の生成規則の明示的な追加、削除、変更を可能にするだけでなく、構文述語も提供する。この形式体系は、作成者自身によって命令的かつ適応的、より具体的には時空間適応文法形式体系として分類されており、さらに他の研究者によって分析形式体系として分類されている^{[ 14 ] [ 21 ]}。

二重言語${\displaystyle L=\{ww|w\in \{a,b\}^{+}\}}$以下のように実証されます。

文法 ww { S ::= #phi(AX<-"") R; R ::= $C('[ab]') #phi(AX<-AX C) #phi(N<=AX) N | R; };

（表記に関する注記：上記の例では、#phi(...)文は生成規則Rの中で文法を明示的に変更する箇所を示しています。は時間的なグローバルな#phi(A.X<-A.X C)変更を表し、 は空間的なローカルな変更を表します。生成規則S内の は、Rによる参照の前に空文字列を配置することで、AXというグローバルな生成規則を実質的に宣言しています。）#phi(N<=A.X)#phi(A.X<-"")

2001年にNetoによって初めて記述された適応型デバイス^{[ 22 ]}は、その後2003年にPistoriによって改良および拡張された^{[ 23 ]。}

2002年に^{[ 24 ]}アダム・カーミは、Adapserとして知られるLALR(1)ベースの適応文法形式を導入した。形式の詳細については公開されていないようだ。

2004年、^{[ 14 ]}セザール・ブラボーは、外観チェックの概念^{[ 25 ]}と適応的文脈自由文法（岩井の適応文法^{[ 13 ]}の制限された形式）を融合するという概念を導入し、外観チェック付き適応的文脈自由文法と呼ばれるこれらの新しい文法がチューリング強力であることを示した。