Классификация языков по Хомскому

Н. Хомский предложил подразделять формальные грамматики, как и порождаемые ими языки на четыре типа.

Тип 0 - формальная грамматика, на правила которой не накладывается никаких ограничений. Для исследования они интереса не представляют – поскольку режим «делай, что хочешь» для математики и для практики редко представляют интерес.

Тип 1. К этому типу относятся грамматики, правила которых имеют вид:

vaw::= vbw, где

v, w Î V^* - произвольные цепочки символов, возможно пустые;

a Î V_N - нетерминальный символ;

b Î V^*\{e} [ иногда b Î V^* ].

[ b Î V^* ].

Эти грамматики еще называют контекстно-зависимыми или КЗ-грамматиками.

Здесь строка a заменяется на строку b в рамках какого-то контекста. Часто используется на практике подмножество таких грамматик, называемое грамматиками непосредственных составляющих:

vAw::= vaw, где v,w, aÎV^*, AÎV_N

При этом часто рассматриваются неукорачивающиеся грамматики (что обеспечивается непустой цепочкой b).

Тип 2. К этому типу относятся грамматики, правила которых имеют вид:

a::= b

a Î V_N - нетерминальный символ;

b Î V^*\{e}:

Здесь также представляют наибольший интерес грамматики непосредственных составляющих.

Такие грамматики называются контекстно-свободными грамматиками или КС-грамматиками.

Языки программирования большей частью описываются грамматиками этого типа.

Тип 3. К этому типу относятся грамматики, правила которых имеют один из двух видов:

æ A:= Bcö

è A:= b ø

где A, B, C ÎV_N; b,c Î V_T;

Это так называемый леворекурсивный вариант. В качестве альтернативы возможен и праворекурсивный вариант:

æ A:= сBö

è A:= b ø

Такие грамматики называют регулярными или автоматными грамматиками. Лексический анализ в компиляторе обычно наиболее целесообразно описывать с помощью этих грамматик.