チョムスキー標準形

新しい開始記号S0と新しいルール_{を導入する}

S ₀ → S、

ここで、Sは前の開始記号です。これは文法によって生成される言語を変更するものではなく、S _0はどの規則の右辺にも出現しません。

各ルールをなくすために

A → X ₁ ... a ... X _n

終端記号a が右辺の唯一の記号ではない場合、そのような終端記号ごとに新しい非終端記号N _aと新しい規則を導入する。

Na _→ a。​

すべてのルールを変える

A → X ₁ ... a ... X _n

に

A → X ₁ ... N _a ... X _n。

右辺に複数の終端記号が出現する場合は、それぞれを対応する非終端記号に同時に置き換える。これにより、文法が生成する言語は変更されない。^{[ 4 ]： 92}

各ルールを置き換える

A → X ₁ X ₂ ... X _n

2つ以上の非終端記号X ₁ ,..., X _nを持つ規則

A → X ₁ A ₁、

A ₁ → X ₂ A ₂、

...、

A _{n -2} → X _{n -1} X _n、

ここで、A _iは新しい非終端記号である。繰り返しになるが、これは文法が生成する言語を変更するものではない。^{[ 4 ]： 93}

εルールは、次の形式のルールです。

A → ε、

ここで、 Aは文法の開始記号で_あるS0ではない。

この形式の規則をすべて排除するには、まずεを導出するすべての非終端記号の集合を決定します。HopcroftとUllman（1979）は、このような非終端記号をnullableと呼び、次のように計算します。

• 規則A → ε が存在する場合、Aは空集合である。
• ルールA → X ₁ ... X _nが存在し、すべてのX _iが null 許容である場合、Aも null 許容です。

各ルールを置き換えることで中間文法を取得する

A → X ₁ ... X _n

一部null許容X _iを省略した全てのバージョンによる。この文法において、左辺が開始記号でない限り、各ε規則を削除することにより、変換された文法が得られる。^{[ 4 ]： 90}

例えば、開始記号S ₀の次の文法では、

S ₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

非終端記号AおよびBは空文字可能だが、CもS ₀も空文字可能ではない。したがって、次の中間文法が得られる。^{[注 3 ]}

S ₀ → A b B | A b B | A b B | A b B | C  

B → AA | A A | A A | A ε A | A C | A C  

C → b | c

A → a | ε

この文法では、すべてのε規則が「呼び出し箇所にインライン化」されています。 ^{[注4 ]} したがって、次のステップではそれらを削除することができ、次の文法が得られます。

S ₀ → AbB | Ab | bB | b  | C 

B → AA | A  | AC | C 

C → b | c

A → a

この文法は、元の文法例と同じ言語を生成します。 { ab、aba、abaa、abab、abac、abb、abc、b、ba、baa、bab、bac、bb、bc、c } ですが、ε 規則はありません。

単位ルールは、次の形式のルールです。

A → B、

ここで、A、Bは非終端記号です。それを削除するには、各ルールについて

B → X ₁ ... X _n、

ここで、 X ₁ ... X _nは非終端記号と終端記号の文字列であり、ルールを追加します。

A → X ₁ ... X _n

これは既に削除された（または削除されつつある）単位規則でない限り、結果として得られる文法で非終端記号Bをスキップすることは、 B が非終端記号Aの単位閉包のメンバーであるため可能である。^{[ 9 ]}

上記の変換を適用する順序を選択する際には、一部の変換が他の変換によって得られた結果を損なう可能性があることを考慮する必要があります。たとえば、STARTをUNITの後に実行すると、ユニットルールが再導入されます。表には、許容される順序が示されています。

さらに、文法サイズの最悪の場合の膨張^{[注5 ]}は変換順序に依存します。| G |を元の文法Gのサイズを表すとすると、最悪の場合のサイズ膨張は、使用される変換アルゴリズムに応じて、 | G | ²から22 ^{|G|の範囲になる可能性があります。 [ 8 ] : 7}文法サイズの膨張は、DELとBINの順序に依存します。DELが最初に行われる場合は指数関数的になる可能性がありますが、それ以外の場合は線形です。UNITは、文法のサイズの二次膨張を引き起こす可能性があります。^{[ 8 ] : 5} START、TERM、BIN、DEL、UNITおよびSTART、BIN、DEL、UNIT、TERMの順序は、最小の（つまり二次の）膨張につながります。

チョムスキー標準形を定義する別の方法^{[ 4 ]： 92 [ 10 ]は次のとおりです。}

形式文法がチョムスキー縮約形であるとは、その生成規則がすべて次の形式である場合をいう。

${\displaystyle A\rightarrow \,BC}$または

${\displaystyle A\rightarrow \,a}$、

どこ${\displaystyle A}$、${\displaystyle B}$そして${\displaystyle C}$は非終端記号であり、${\displaystyle a}$は終端記号です。この定義を使用する場合、${\displaystyle B}$または${\displaystyle C}$は開始記号である可能性があります。空文字列を生成しない文脈自由文法のみが、チョムスキー縮約形に変換できます。

ドナルド・E・クヌースは、バックアス・ナウア記法（BNF）という用語を提案した手紙の中で、 BNFの「すべての定義がそのような形式を持つ構文は『フロイド標準形』であると言える」と示唆した。

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \mid \langle C\rangle } または

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \langle C\rangle } または

${\displaystyle \langle A\rangle$ ::=\,a} 、

どこ${\displaystyle \langle A\rangle }$、${\displaystyle \langle B\rangle }$そして${\displaystyle \langle C\rangle }$は非終端記号であり、${\displaystyle a}$は終端記号である。なぜなら、ロバート・W・フロイドは1961年に、任意のBNF構文を上記の構文に変換できることを発見したからである。 ^{[ 11 ]} しかし彼はこの用語を取り下げた。「疑いなく多くの人々が独自にこの単純な事実を自分の研究で使用しており、この点はフロイドのメモの主な考察とは付随的なものにすぎないからである。」^{[ 12 ]}フロイドのメモはチョムスキーの1959年の原著論文を引用しているが、クヌースの手紙は引用していない。