В теории формальных языков выделяются 4 типа грамматик, которым соответствуют 4 типа языков. Эти грамматики выделяются путем наложения усиливающихся ограничений на правила грамматики

Грамматики типа 0, которые называют грамматиками общего вида, не имеют никаких ограничений на правила порождения. Эти грамматики порождают естественные языки.

Любое правило

r = η ψ

может быть построено с использованием произвольных цепочек η , ψ (V_т V_А)*. Например,

<T><W> <W><T> или x<A>b<C><D> x<H><D>

Грамматики типа 1, которые называют также контекстно-зависимыми грамматиками, не допускают использования любых правил. Правила вывода в таких грамматиках должны иметь вид:

χ₁<A>χ₂ χ₁ ω χ₂,

где χ₁, χ₂ - цепочки, возможно пустые, из множества (V_т V_А)*, символ <А> V_А и цепочка ω (V_т V_А)*. Цепочки χ₁ и χ₂ остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно-зависимой.

Грамматики типа 1 значительно удобнее на практике, чем грамматики типа 0, поскольку в левой части правила заменяется всегда один нетерминальный символ, который можно связать с некоторым синтаксическим понятием, в то время как в грамматике типа 0 можно заменять сразу несколько символов, в том числе и терминальных.

Например, грамматика:

Г_{1. 4}:

V_т = {a, b, c, d}, V_А = {<I>, <A>, <B>}

R = { <I> aA<I>,

A<I> AA<I>,

AAA A<B>A,

A b,

b<B>A bcdA,

b<I> ba }

является контекстно-зависимой, поскольку второе и шестое правила имеют непустой левый контекст, а третье и пятое правила содержат оба контекста. Вывод в такой грамматике может иметь вид:

<I> a<A><I> a<A><A><I> ab<A><I> abb<I> abba

Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками (КС-грамматики или Б-грамматики).

Правила вывода таких грамматик имеют вид:

<A> α,

где <A> V_А и α (V_т V_А)*.

Очевидно, что эти правила получаются из правил грамматики типа 1 при условии χ₁ = χ₂ = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования.

Примером КС-грамматики может служить следующая:

Г_{1. 5}:

V_т = {a, b}, V_А = {<I>},

R = { <I> a<I>a,

<I> b<I>b,

<I> aa,

<I> bb}

Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки β V_т* и зеркального отображения этой цепочки β'.

L( Г₅ ) = { bb' | b V_т⁺},

где V_т⁺ - это множество V_т* без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:

<I> a<I>a ab<I>ba aba<I>aba ababbaba

Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:

<A> a или <A> a<B> или <A> <B>a,

где a V_т, <A>, <B> V_А, причем грамматика может иметь только правила вида <A> a<B> - правосторонние правила, либо только вида <A> <B>a - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г_{1. 6} и левосторонняя грамматика Г_{1. 7}.

Г_{1. 6}

V_т = {a, b}, V_А = {<I>, <A>},

R = { <I> a<I>,

<I> a<A>,

<A> b<A>,

<A> b<Z>,

<Z> $ }

Г_{1. 7}

V_т = {a, b}, V_А = {<I>, <A>},

R = { <I> <A>b,

<A> <A>b,

<A> <Z>a,

<Z> <Z>a,

<Z> $ }

Эти грамматики являются эквивалентными и порождают язык

L(Г₇) = {a...ab...b | n,m > 0}

Между множествами языков различных типов существует отношение включения:

{ L _{типа 3} } { L _{типа 2} } { L _{типа 1} } { L _{типа 0} }

Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.