チョムスキー階層
形式文法の構成要素は、「終端記号」(Terminal Symbols)の有限集合(形式言語の単語で使われる文字)、「非終端記号」(Nonterminal Symbols)の有限集合、「生成規則」(Production Rules)の有限集合(各生成規則は右側と左側に記号列で構成される単語を含む)、「開始記号」(Start Symbol)から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規則を適用していくことによって終端記号のみから構成される単語を生成する。そのような単語全体の集合が形式言語である。
非終端記号は大文字、終端記号は小文字で表すことが多く、開始記号は S {\displaystyle S} で示される。例えば、終端記号 { a , b } {\displaystyle \{a,b\}} と非終端記号 { S , A , B } {\displaystyle \{S,A,B\}} から構成される文法の生成規則が以下のようなものであるとする。
S → A B S {\displaystyle S\rightarrow ABS}
S → ε {\displaystyle S\rightarrow \epsilon } (ここで ε {\displaystyle \epsilon } は空の文字列)
α {\displaystyle \alpha } と β {\displaystyle \beta } は空の文字列の場合もあるが、 γ {\displaystyle \gamma } は空でない文字列でなければならない。 S {\displaystyle S} が生成規則の右側に現れない場合、 S → ε {\displaystyle S\rightarrow \epsilon } という規則が存在しても良い。この文法によって記述される言語は線形拘束オートマトンで認識できる。
タイプ-2 文法(文脈自由文法)は文脈自由言語を生成する。この文法は A → γ {\displaystyle A\rightarrow \gamma } という形式の生成規則を持ち、 A {\displaystyle A} は非終端記号、 γ {\displaystyle \gamma } は終端記号と非終端記号から構成される文字列である。この文法で生成される言語群は非決定性プッシュダウン・オートマトンが認識できる言語である。多くのプログラミング言語の文法は、ほぼ文脈自由文法である。
タイプ-3 文法(正規文法)は正規言語を生成する。この文法の生成規則は左側には必ずひとつの非終端記号があり、右側には必ずひとつの終端記号とひとつかゼロ個の非終端記号がある(順番はひとつの文法内では決められている。