形式文法
(カッコ内の番号は適用した生成規則の番号であり、変換された部分がボールド体で示されている。)
以上のようにこの言語は、 { a n b n c n | n > 0 } {\displaystyle \left\{a^{n}b^{n}c^{n}|n>0\right\}} という形式を表している( a n {\displaystyle a^{n}} は n 個の a {\displaystyle a} が並んだ文字列を意味する)。従って、この言語は正数個の 'a' を含み、その後に同じ個数の 'b' とさらに同じ個数の 'c' を並べた全ての文字列から構成される。
生成的形式文法はリンデンマイヤーシステム(Lシステム)と等価であるが、相違点もある。Lシステムでは「終端記号」と「非終端記号」を区別しないし、規則を適用する順序に制限がある。また、Lシステムは永遠に規則を適用し続けることができ、無限の文字列を生成する。一般に各文字列は空間内のある点に対応付けることができ、Lシステムの出力は空間内の点の集合の極限を定義しているとも言える。
1956年にノーム・チョムスキーが初めて生成文法を定式化したとき、彼はそれを4つのタイプに分類した。これをチョムスキー階層と言う。これらのタイプの差異は、生成規則の制限の強さであり、表現できる形式言語の多様さである。重要なふたつのタイプとして「文脈自由文法」と「正規文法」がある。これらの文法で生成される言語はそれぞれ「文脈自由言語」と「正規言語」と呼ばれる。制限のない文法よりも非力ではあるが、これらの言語は有限オートマトンで受容(認識)することができ、構文解析が簡単であるために、これらの文法はよく使われる。たとえば文脈自由文法については効率的なLL法やLR法の構文解析器を生成するアルゴリズムが知られている。
形式文法についてのチョムスキーの本来の階層に対して言語学者や情報工学者が独自の拡張や派生を試みてきた。その目的は表現力を強化するか構文解析をやりやすくするためである。もちろん、これら二つの目的は方向性が異なる。表現力が強化された形式文法は自動化されたツールによる構文解析は困難となる。最近開発された文法には以下のようなものがある。
木接合文法は、文字列だけでなく構文木も操作することによって規則を書き換えて、従来の文法で生成されるよりも表現力豊かな言語を生成する。
接辞文法と属性文法は、意味属性と意味に関する操作を加えて生成規則を書き換えられるようにした。これにより表現力を増加させると共に、実用的な言語変換ツールを構築するのにも有効である。