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

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

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

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

vaw ::= vbw, где

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

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

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

[ b Î V* ].

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

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

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

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

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

a ::= b

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

b Î V*\{e}:

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

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

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

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

æ A := Bcö

è A := b ø

где A, B, C ÎVN; b,c Î VT ;

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

æ A := сBö

è A := b ø

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