終端記号と非終端記号
以下、単に「集合」とあるものは全て有限集合である。この理論では文法は一般に、記号列を別の記号列に置換できるものとして定義する生成規則の集合によって定義される。これらの生成規則は、文字列の生成やパースに使われる。それぞれの生成規則は、置換される記号列からなる ヘッド (左辺)と、置換する記号列からなる ボディ (右辺)を持つ。規則は、ヘッド → ボディ のような形に書く。例えば、規則 z0 → z1 は、z0 を z1 で置き換えることを表す。
1950年代に ノーム・チョムスキー によって提案された生成文法の古典的な形式では、文法 G は次のように構成される:
非終端記号 の集合 N {\displaystyle N}
終端記号(アルファベット) の集合 Σ {\displaystyle \Sigma }
生成規則 の集合 P {\displaystyle P} 。 P {\displaystyle P} の要素であるそれぞれの規則は次のような形をしている: