Грамматики типа 1

Грамматики типа 0

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

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

r = η ψ

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

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

Грамматики типа 1

Грамматики типа 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