正式な文法

形式文法は、形式言語のアルファベットのどの文字列が言語の構文に従って有効であるかを記述します。文法は文字列の意味や、どのようなコンテキストでも文字列を使用して何ができるかを記述するものではなく、文字列の形式のみを記述します。形式文法は、形式言語におけるそのような文字列の 生成規則のセットとして定義されます。

形式言語理論は、形式文法と言語を研究する学問であり、応用数学の一分野です。その応用分野は、理論計算機科学、理論言語学、形式意味論、数理論理学、その他の分野に見られます。

形式文法は、文字列を書き換えるための一連の規則と、書き換えを開始する「開始記号」です。したがって、文法は通常、言語ジェネレーターと考えられています。ただし、文法は「認識子」の基礎として使用されることもあります。認識子とは、特定の文字列がその言語に属しているか、文法的に間違っているかを判断するコンピューティング機能です。このような認識子を説明するために、形式言語理論では、オートマトン理論と呼ばれる別の形式を使用します。オートマトン理論の興味深い結果の 1 つは、特定の形式言語に対して認識子を設計できないことです。^[1] 構文解析は、発話 (自然言語の文字列) を一連の記号に分解し、各記号を言語の文法に照らして分析することによって認識するプロセスです。ほとんどの言語では、発話の意味は構文に従って構造化されており、これは構成意味論と呼ばれる手法です。結果として、言語で発話の意味を記述するための最初のステップは、それを部分ごとに分解し、分析された形式（コンピューターサイエンスでは構文解析ツリー、生成文法では深層構造として知られています）を確認することです。

文法は主に、文字列を変換するための書き換え規則である生成規則のセットから構成されます。各規則は、特定の文字列 (その左側) を別の文字列 (その右側) に置き換えることを指定します。規則は、その左側を含む各文字列に適用でき、その左側の出現箇所が右側に置き換えられた文字列を生成します。

これらの規則によって完全に定義される半Thueシステムとは異なり、文法ではさらに、非終端記号と終端記号の2種類の記号を区別します。各左側には、少なくとも1つの非終端記号が含まれている必要があります。また、開始記号と呼ばれる特別な非終端記号も区別します。

文法によって生成される言語は、単一の開始記号からなる文字列から、その規則を可能な限り（場合によっては繰り返して）適用することによって生成できる、非終端記号を含まないすべての文字列の集合として定義されます。同じ単一の文字列を生成する方法が本質的に複数ある場合、その文法はあいまいであると言われます。

次の例では、終端記号はaとb、開始記号はSです。

次のような生成規則があるとします。

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

次にSから始めて、それに適用するルールを選択できます。ルール 1 を選択すると、文字列aSbが得られます。次にルール 1 をもう一度選択すると、S がaSbに置き換えられ、文字列aaSbbが得られます。ここでルール 2 を選択すると、S がbaに置き換えられ、文字列aababbが得られ、完了です。この一連の選択は、記号を使用して、より簡潔に記述できます。 ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$

文法の言語は無限集合 であり、 は回繰り返されます（特に、 は生成規則 1 が適用された回数を表します）。この文法は文脈自由（単一の非終端記号のみが左側に現れる）であり、明確です。 ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$${\displaystyle a^{k}}$${\displaystyle a}$${\displaystyle k}$${\displaystyle n}$

代わりに、ルールが次のようになっているとします。

1.${\displaystyle S\rightarrow a}$

2.${\displaystyle S\rightarrow SS}$

3.${\displaystyle aSa\rightarrow b}$

この文法は、規則 3 により文脈自由ではなく、規則 2 を使用して s のシーケンスを生成する方法が複数あるため、あいまいです。 ${\displaystyle S}$

しかし、これが生成する言語は、単におよび/またはからなるすべての空でない文字列の集合です。これは簡単にわかります。から を生成するには、ルール 2 を 2 回使用して を生成し、次にルール 1 を 2 回、ルール 3 を 1 回使用して を生成します。つまり、任意の空でない のシーケンスを生成し、それらをそれぞれまたはに好きなように置き換えることができます。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle S}$${\displaystyle SSS}$${\displaystyle b}$${\displaystyle S}$${\displaystyle a}$${\displaystyle b}$

同じ言語は、文脈に依存しない、曖昧でない文法によっても生成できる。例えば、規則のある正規文法などである。

1.${\displaystyle S\rightarrow aS}$

2.${\displaystyle S\rightarrow bS}$

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

1950年代にノーム・チョムスキーが最初に提案した生成文法の古典的な形式化では、 ^{[2] [3]}文法Gは次の要素から構成されます。

• Gから形成された文字列とは互いに素な、非終端記号の有限集合N。
• Nと交わらない終端記号の有限集合。${\displaystyle \Sigma }$
• 生成規則の有限集合P、各規則は次の形式をとる

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

ここではクリーネの星型演算子で、 は集合の和集合を表します。つまり、各生成規則は、1 つの記号列を別の記号列にマッピングします。ここで、最初の文字列 (「ヘッド」) には、少なくとも 1 つの非終端記号である任意の数の記号が含まれます。2 番目の文字列 (「本体」) が空の文字列のみで構成される場合、つまり記号がまったく含まれていない場合は、混乱を避けるために特別な表記法 (多くの場合、 、e、または) で表されます。このような規則は消去規則と呼ばれます。^[4]${\displaystyle {*}}$${\displaystyle \cup }$${\displaystyle \Lambda }$${\displaystyle \epsilon }$

• 開始記号であり、文記号とも呼ばれる区別記号です。${\displaystyle S\in N}$

文法はタプル として正式に定義されます。このような形式文法は、文献では書き換えシステムや句構造文法と呼ばれることがよくあります。 ^{[5] [6]}${\displaystyle (N,\Sigma ,P,S)}$

文法の操作は、文字列の関係に基づいて定義できます。

• 文法 が与えられた場合、の文字列の2 項関係(「G は 1 ステップで導出されます」と発音します)は次のように定義されます。 ${\displaystyle G=(N,\Sigma ,P,S)}$${\displaystyle {\underset {G}{\Rightarrow }}}$${\displaystyle (\Sigma \cup N)^{*}}$

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• 関係（Gと発音し、0回以上のステップで導出される）は、反射的推移閉包として定義される。${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$${\displaystyle {\underset {G}{\Rightarrow }}}$
• 1つの文形式は、開始記号から有限個のステップで導出できる の要素です。つまり、文形式は の要素です。非終端記号を含まない文形式（つまり の要素）は文と呼ばれます。^[7]${\displaystyle (\Sigma \cup N)^{*}}$${\displaystyle S}$${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$${\displaystyle \Sigma ^{*}}$
• の言語はと表記され、 によって構築される文の集合として定義されます。${\displaystyle G}$${\displaystyle {\boldsymbol {L}}(G)}$${\displaystyle G}$

文法は実質的には半Thueシステムであり、文字列をまったく同じ方法で書き換えます。唯一の違いは、書き換え規則で書き換える必要がある特定の非終端記号を区別し、指定された開始記号から非終端記号のない文字列への書き換えのみに関心があるという点です。 ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle (N\cup \Sigma ,P)}$${\displaystyle S}$

これらの例では、形式言語はセットビルダー表記法を使用して指定されます。

、が開始記号であり、次の生成規則で構成される 文法を考えます。${\displaystyle G}$${\displaystyle N=\left\{S,B\right\}}$${\displaystyle \Sigma =\left\{a,b,c\right\}}$${\displaystyle S}$${\displaystyle P}$

1.${\displaystyle S\rightarrow aBSc}$

2.${\displaystyle S\rightarrow abc}$

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

この文法は、がn個の連続する の文字列を表す言語を定義します。つまり、言語は、 1 個以上の 、それに続く同じ数の、それに続く同じ数の で構成される文字列のセットです。 ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle a^{n}}$${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

文字列の導出の例をいくつか示します。 ${\displaystyle L(G)}$

(表記上: 「文字列P は生成規則iによって文字列Qを生成する」と表示され、生成される部分はその都度太字で示されます。)${\displaystyle P{\underset {i}{\Rightarrow }}Q}$

ノーム・チョムスキーが1956年に初めて生成文法を形式化したとき、 ^[2]彼はそれを現在チョムスキー階層として知られているタイプに分類しました。これらのタイプの違いは、生成規則が次第に厳格になり、表現できる形式言語が少なくなることです。2つの重要なタイプは、文脈自由文法（タイプ2）と正規文法（タイプ3）です。このような文法で記述できる言語は、それぞれ文脈自由言語と正規言語と呼ばれます。チューリングマシンが受け入れ可能な言語であれば何でも表現できる無制限文法（タイプ0）ほど強力ではありませんが、これら2つの制限付きタイプの文法は、パーサーを効率的に実装できるため、最もよく使用されます。^[8]例えば、すべての正規言語は有限状態機械によって認識することができ、文脈自由文法の有用なサブセットについては、それらの文法が生成する対応する言語を認識するための効率的なLLパーサーとLRパーサーを生成するよく知られたアルゴリズムが存在します。

文脈自由文法とは、各生成規則の左側が 1 つの非終端記号のみで構成される文法です。この制限は重要であり、すべての言語が文脈自由文法で生成できるわけではありません。生成できる言語は文脈自由言語と呼ばれます。

上記で定義した言語は文脈自由言語ではなく、これは文脈自由言語のポンピング補題を使用して厳密に証明できますが、たとえば、言語(少なくとも 1個の に同じ数の が続く)は文脈自由であり、、、開始記号、および次の生成規則 を含む文法で定義できます。${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{2}}$${\displaystyle N=\left\{S\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ab}$

文脈自由言語は、アーリーの認識器などのアルゴリズムによって時間内に認識できる（ビッグオー記法を参照） 。つまり、あらゆる文脈自由言語について、文字列を入力として受け取り、文字列が言語のメンバーであるかどうかを時間内に判断する機械を構築できる。ここで、は文字列の長さである。^[9]決定性文脈自由言語は、線形時間で認識できる文脈自由言語のサブセットである。^[10]この言語セットまたはそのサブセットを対象とするさまざまなアルゴリズムが存在している。 ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3})}$${\displaystyle n}$

正規文法では、左側は単一の非終端記号のみですが、右側も制限されます。右側は、空の文字列、単一の終端記号、または単一の終端記号とそれに続く非終端記号のいずれかになりますが、それ以外は何も起こりません。(より広い定義が使用される場合もあります。つまり、より長い終端記号の文字列や、他に何もない単一の非終端記号を許可することで、同じ言語クラスを定義しながら、 言語の表記を容易にすることができます。)

上記で定義した言語は正規ではありませんが、(少なくとも1 個の後に少なくとも 1 個の が続き、数字は異なる場合があります)言語は、、開始記号、および次の生成規則を含む文法によって定義できるため正規です。 ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{3}}$${\displaystyle N=\left\{S,A,B\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

正規文法によって生成されるすべての言語は、有限状態マシンによって時間内に認識できます。 実際には、正規文法は正規表現を使用して表現されるのが一般的ですが、実際に使用される正規表現の形式によっては、正規言語を厳密に生成せず、それらの偏差のために線形の認識パフォーマンスを示しません。 ${\displaystyle O(n)}$

チョムスキーの形式文法の階層構造は、言語学者とコンピュータ科学者の両方によって、表現力を高めるため、または分析や構文解析を容易にするために、多くの拡張やバリエーションが開発されてきました。開発された文法の形式には、次のようなものがあります。

• 木結合文法は、書き換え規則が文字列だけでなく構文木にも作用できるようにすることで、従来の生成文法の表現力を高めます。 ^[11]
• 接辞文法^[12]と属性文法^{[13] [14]}は、意味属性と操作で書き換え規則を拡張することを可能にし、文法表現力の向上と実用的な言語翻訳ツールの構築の両方に役立ちます。

再帰文法は、再帰的な生成規則を含む文法です。たとえば、文脈自由言語の文法は、非終端記号Aが存在し、生成規則に渡してAを左端の記号とする文字列を生成できる場合、左再帰的です。 ^[15]再帰文法の例としては、2つのカンマで区切られた文内の節が挙げられます。^[16]チョムスキー階層のすべてのタイプの文法は再帰的です。

構文解析アルゴリズムに関する文献は膨大にありますが、これらのアルゴリズムのほとんどは、解析対象の言語が最初に生成形式文法によって記述され、この生成文法を実用的なパーサーに変換することを目標としていると想定しています。厳密に言えば、生成文法は言語を解析するために使用されるアルゴリズムとはまったく対応しておらず、さまざまなアルゴリズムには、整形式と見なされる生成規則の形式に対するさまざまな制限があります。

別のアプローチとしては、まず言語を解析文法に基づいて形式化することです。これは、言語のパーサーの構造と意味論に、より直接的に対応します。解析文法の形式化の例には、次のものがあります。

• トップダウン構文解析言語（TDPL）：トップダウン構文解析器の動作を研究するために1970年代初頭に開発された、非常にミニマリスト的な解析文法形式。^[17]
• リンク文法：言語学のために設計された分析文法の一種で、単語のペアの位置関係を調べることで統語構造を導き出します。^{[18] [19]}
• 構文解析式文法（PEG）：プログラミング言語とコンパイラの作成者の実用的な表現力のニーズに合わせて設計されたTDPLの最近の一般化。^[20]