適応型文法

適応型文法は、形式主義の中に明示的にメカニズムを提供し、独自の生成規則を操作 できるようにする形式文法です。

ジョン・N・シャットは、適応型文法を、文法内でルールセット（生成ルールのセットとも呼ばれる）を明示的に操作できる文法形式であると定義しています。操作の種類には、ルールの追加、削除、変更が含まれます。^[1]

文献における文法適応性の最初の記述（ただし、その名前ではない）は、一般的に^{[2] [3] [4]} 1963年に発表されたアルフォンソ・カラッチョロ・ディ・フォリーノの論文にあるとみなされている。 ^[5]次に一般的に受け入れられている適応形式（拡張可能な文脈自由文法）への言及は、1970年にウェグブライトが拡張可能なプログラミング言語の研究で^[6]述べ、その後、 1973年にハンフォードとジョーンズが動的構文について述べた。 ^[7]

ごく最近まで、適応型文法の形式的特性に関する研究の多くは研究者間で調整されておらず、1990年にボリス・ブルシュテインがACM SIGPLAN Noticesに発表した論文に対する回答としてヘニング・クリスチャンセンが初めてまとめた^[2]。^[8]サンパウロ大学工学部には適応型言語・技術研究所があり、適応型技術と理論の研究と実践に特化している。LTAもこの分野の研究者の名前を掲載したページを運営している^{[9] 。}

初期の研究では、動的構文[ ^7]や拡張可能^[6] 、変更可能^[10] 、動的^[11]、適応可能^{[2] [12]}な文法が言及されていたが、最近では適応型（または文献の出版言語によっては、適応型^{[13] [14]}などの変形）という用語が使われる傾向にある。 ^{[3]岩井は彼女の形式論を}適応型文法と呼んでいるが^[13]、単に適応型文法というこの特定の用法は、現在、文献では名称修飾語なしでは一般的に使用されていない。さらに、標準化や分類の取り組みは、いくつかの研究者によってこの方向への取り組みは行われているものの、様々な研究者の間で行われていない。^{[3] [4]}

シャットは適応型文法モデルを2つの主要なカテゴリーに分類している。^{[3] [15]}

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

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

• 時空間適応型文法(ハイブリッド)は、言語の生成の時間または空間(あるいはその両方) に応じて規則を変化させます (ローカル操作とグローバル操作は、このような変更の表記によって明示的に区別されます)。

適応形式主義は、完全な文法形式主義 (適応文法) と、いくつかの文法形式主義の基礎となっている適応マシンという 2 つの主なカテゴリに分けられます。

以下は、上記の Shutt の定義により適応型文法であると考えられる (または発明者自身によって適応型文法として分類されている) 文法形式の一覧です (決して完全ではありません)。これらは、文献で最初に言及された歴史的な順序で一覧されています。

1970年のウェグブライト博士論文^[6]で説明されているように、拡張可能な文脈自由文法は、左端導出中に終端接頭辞を読み取る際に有限状態変換器によって出力される指示に従ってルールセットが変更される文脈自由文法で構成されています。したがって、ルールセットは生成された文字列内の位置に応じて変化しますが、この変化は構文木の階層構造を無視します。拡張可能な文脈自由文法は、シャットによって命令型に分類されました。^[3]

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

二重化言語は次のように実証される。^[17]${\displaystyle L=\{ww|w{\mbox{ is a letter}}\}}$

<プログラム↓ G > → <dcl↓ G ↑ w > <本文↓{ w-rule }>

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

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

1990年5月に初めて導入され^[8]、後に1990年12月に拡張された^[10] 変更可能な文法は、構文解析中に規則を追加および削除するメカニズムを明示的に提供します。ACM SIGPLAN Noticesの回答に応えて、Burshteynは後に形式論を修正し、1992年に適応型Universal Syntax and Semantics Analyzer（USSA）を導入しました^{[18]。これらの形式論はShuttによって}命令型に分類されました。^[3]

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

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

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]の制限された形式である}適応型文脈自由文法を融合するという概念を導入し、外観検査付き適応型CFGと呼ばれるこれらの新しい文法がチューリング強力であることを示しました。

以下に挙げる形式主義は文法形式主義ではありませんが、完全な文法形式主義の基礎となるか、または本質的に適応的であるためここに含められています。これらは、文献で最初に言及された歴史的な順序でリストされています。

自己修正有限状態オートマトン (Shutt & Rubinstein)

1994年にシャットとルビンスタイン^[26]によって導入された自己修正有限状態オートマトン（SMFA）は、制限された形式ではチューリング強力であることが示されている。

適応オートマトン (Neto)

^1994年[19]にNetoは構造化プッシュダウンオートマトンと呼ばれる機械を発表した。これは岩井^[13]、 Pistori ^[23] 、 Bravo ^{[14]らが追求した適応型オートマトン理論の中核をなすものである。この形式主義は、}検査（上で述べた岩井の適応型文法に関する統語論述語に類似）、追加、およびルールの削除の操作を可能にする。

• 適応アルゴリズム
• 人工文法学習
• 文法誘導
• カテゴリ:拡張構文プログラミング言語