形式文法（けいしきぶんぽう、"Formal Grammar"）は、形式的に与えられた（形式体系を参照）文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、（有限の）文字群上の有限長の文字列の（通常無限な）集合が、形式的に記述される。形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。以下で「文法の規則（構文規則）の集まり」と呼んでいるのは、具体的には、句構造規則#基本モデルにあるようなものである。また終端記号と非終端記号の記事も参照のこと。生成文法は、ある言語に含まれる文字列を生成するアルゴリズムを定式化するもの、分析的文法は、ある言語に含まれる文字列を構文解析し受理するアルゴリズムを定式化するもの、とも言える。（トップダウン構文解析とボトムアップ構文解析とまぎらわしいが、それらはどちらも分析的である）生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は曖昧であると言う。たとえば、'formula_1' と 'formula_2' から成る文字セットがあり、開始記号 'formula_3' に対して以下の規則を適用するものとする。そこで、"formula_3" から開始して、適用する規則を選んでいくことができる。規則1を選ぶと、開始記号 'formula_3' から 'formula_8' に変換されるので "formula_8" が得られる。再度規則1を選ぶと、'formula_3' が 'formula_8' に変換されるので全体として "formula_12" となる。この過程は最終的に本来の文字セット（つまり 'formula_1' と 'formula_2'）だけから構成される文字列になるまで続けられる。さて、終了させるために規則2を適用すると 'formula_3' が 'formula_16' に変換されるので、最終的に "formula_17" を得る。この過程をまとめると formula_18 となる。この文法による言語はこのような過程で生成される全文字列 formula_19 を含む。生成文法の定式化は1950年代にノーム・チョムスキーによって最初に提案された。文法 "G" は以下の構成要素から成る。一般にこのような形式文法 formula_31 は 4要素 formula_32 で要約される。形式文法 formula_33 の言語は formula_34 と記述され、開始記号 formula_3 に formula_23 の規則を非終端記号が無くなるまで適用して得られる（formula_21 内の文字から構成される）全ての文字列として定義される。"以下の例では、形式言語を集合の内包的記法で記述している。"formula_38, formula_39 の文法 formula_31 について、生成規則 formula_23 が以下の規則から構成される。また、非終端記号 formula_3 は開始記号である。formula_34 における文字列生成の実例は以下のようになる。（カッコ内の番号は適用した生成規則の番号であり、変換された部分がボールド体で示されている。）以上のようにこの言語は、formula_52 という形式を表している（formula_53 は n 個の formula_1 が並んだ文字列を意味する）。従って、この言語は正数個の 'a' を含み、その後に同じ個数の 'b' とさらに同じ個数の 'c' を並べた全ての文字列から構成される。生成的形式文法はリンデンマイヤーシステム（Lシステム）と等価であるが、相違点もある。Lシステムでは「終端記号」と「非終端記号」を区別しないし、規則を適用する順序に制限がある。また、Lシステムは永遠に規則を適用し続けることができ、無限の文字列を生成する。一般に各文字列は空間内のある点に対応付けることができ、Lシステムの出力は空間内の点の集合の極限を定義しているとも言える。1956年にノーム・チョムスキーが初めて生成文法を定式化したとき、彼はそれを４つのタイプに分類した。これをチョムスキー階層と言う。これらのタイプの差異は、生成規則の制限の強さであり、表現できる形式言語の多様さである。重要なふたつのタイプとして「文脈自由文法」と「正規文法」がある。これらの文法で生成される言語はそれぞれ「文脈自由言語」と「正規言語」と呼ばれる。制限のない文法よりも非力ではあるが、これらの言語は有限オートマトンで受容（認識）することができ、構文解析が簡単であるために、これらの文法はよく使われる。たとえば文脈自由文法については効率的なLL法やLR法の構文解析器を生成するアルゴリズムが知られている。文脈自由文法では、生成規則の左側にはひとつの非終端記号だけが置かれる。この制限があるため、文脈自由文法はあらゆる言語を生成できるわけではない。文脈自由文法で表現される言語を「文脈自由言語」と呼ぶ。前述の例で定義された言語は文脈自由言語ではない。これは文脈自由言語の反復補題を使って厳密に証明可能である。formula_55 で表される言語（ひとつ以上の 'a' の後に同じ個数の 'b' が続く）を定義する文法 formula_56 を例として考えよう。formula_56 は formula_58, formula_59 から成り、開始記号 formula_3 と以下の生成規則で定義される。文脈自由言語はアーリー法のようなアルゴリズムを使って formula_63 の時間（ランダウの記号参照）で認識可能である。すなわち、全ての文脈自由言語について、任意の文字列を入力とし、それが特定の言語に含まれるかどうかを formula_63 の時間内に決定する機械を構築できる。ここで、formula_65 は入力文字列長である。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。正規文法でも生成規則の左側はひとつの非終端記号だけが置かれるが、さらに右側も制限が加えられ、ひとつの終端文字か、ひとつの終端文字とひとつの非終端記号から成る文字列のいずれかしか許されない。（広く採用されている定義として、複数の終端文字で構成される文字列か、ひとつの非終端文字のいずれか、という言い方もできる。どちらにしても同じクラスの言語を意味している。）formula_66 で表される言語（ひとつ以上の 'a' の後にひとつ以上の 'b' が続く）を定義する文法 formula_67 を例として考える。formula_67 は formula_69, formula_59 から成り、開始記号 formula_3 と以下の生成規則で定義される。正規文法で生成される言語は、全て有限オートマトンで線形時間内で認識される。実際には正規文法は正規表現で表されるのが一般的だが、正規表現が必ずしも正規文法を表すためだけに使われるとは限らない。以上のふたつの言語を生成した生成規則の違いとは別に、ふたつの言語 formula_55（文脈自由）と formula_79（正規）の高いレベルで見たときの大きな違いは、文脈自由言語では 'a' の個数と 'b' の個数が同じになるということである。つまり、文脈自由言語を理解するオートマトンは正規言語を理解するオートマトンよりも保持すべき情報が多い。正規言語では 'a' や 'b' の個数を数える必要はなく、単にどちらもゼロより多いことだけを確認できればいいのである。詳細については文脈自由言語と正規言語を参照されたい。形式文法についてのチョムスキーの本来の階層に対して言語学者や情報工学者が独自の拡張や派生を試みてきた。その目的は表現力を強化するか構文解析をやりやすくするためである。もちろん、これら二つの目的は方向性が異なる。表現力が強化された形式文法は自動化されたツールによる構文解析は困難となる。最近開発された文法には以下のようなものがある。プログラミング言語処理系の実装のフロントエンドとしてさかんに研究されたため、それに関係する構文解析についての論文は非常に多い。それらでは、解析対象の言語を形式的に定義し、そこから動作可能な構文解析器を生成することが目標である。自然言語についても計算言語学や自然言語処理などで必要であり、研究されている。いくつかの例を示す。

出典:wikipedia