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

Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.

Тип 0. (формальные грамматики с фразовой структурой, неограниченные). Грамматика G = (VT, VN,P, S) называется грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений, кроме тех, которые указаны в определении грамматики. Любое правило α→β может быть построено с использованием произвольных цепочек α, βÎ(V_TÈV_N). Этот тип грамматик самый общий, включающий все грамматики. Однако некоторые грамматики могут принадлежать только к этому типу. Практического применения в силу своей сложности такие грамматики не имеют. Например:

P = TR→HT или abC→xDa.

Тип 1. (контекстно-зависимые, контекстные грамматики, грамматика непосредственно составляющих, НС-грамматика). К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики.

Грамматика G = (VT,VN,P,S) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈V_N.

Грамматика G = (VT,VN,P,S) называется неукорачивающий грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈V_N и |A|<=|γ|.

Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.

Тип 2. (Контекстно-свободной грамматикой, КС-грамматикой, бесконтекстной грамматикой). Грамматика G = (VT,VN,P,S) называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈V_N. То есть грамматика допускает появление в левой части правила только нетерминального символа. КС-грамматики широко применяются для описания синтаксиса компьютерных языков (программирования).

Тип 3. (регулярная, Р-грамматика, линейная. К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные

грамматики могут быть разделены на два эквивалентных класса:

· Грамматика G = (VT, VN, Р, S) называется праволинейной, если ее правила вывода имеют вид A→γB или A→γ, где γ∈V_T*, A, B∈V_N;

· Грамматика G = (VT, VN, Р, S) называется леволинейной, если ее правила вывода имеют вид A→Bγ или A→γ, где γ∈V_T*, A, B∈V_N.

Регулярные грамматики применяются для описания простейших конструкций: идентификаторов, строк, констант, а также языков ассемблера, командных процессоров и др.