再帰文法

コンピュータサイエンスでは、文法が再帰的な生成規則を含む場合、非公式に再帰文法と呼ばれます。再帰的な生成規則とは、これらの規則に従って非終​​端記号を展開すると、最終的に同じ非終端記号を再び含む文字列が得られることを意味します。そうでない場合は、非再帰文法と呼ばれます。^{[ 1 ]}

例えば、文脈自由言語の文法は、非終端記号Aが存在し、その記号 A を生成規則に通してA を(最も左の記号として)含む文字列を生成できる場合、左再帰的である。 ^{[ 2 ] [ 3 ]}チョムスキー階層 のすべてのタイプの文法は再帰的であり、無限の単語セットの生成を可能にするのは再帰である。^{[ 1 ]}

非再帰文法は有限言語しか生成できず、また、各有限言語は非再帰文法によって生成できる。^{[ 1 ]} 例えば、直線文法は単語を1つだけ生成する。

不要な規則を含まない再帰的な文脈自由文法は、必然的に無限言語を生成する。この性質は、文脈自由文法が有限言語を生成するか無限言語を生成するかを効率的にテストできるアルゴリズムの基礎となる。^{[ 4 ]}