1.3. Процесс порождения

Порождающая грамматика позволяет получить (породить) все цепочки символов определяемого ею языка следующим образом.

Порождение всегда начинается с одного из начальных символов грамматики, пусть это будет S₁. Среди всех правил множества P применяется правило, в котором левая часть (слева от стрелки) состоит только из одного символа S₁, и эта левая часть заменяется на правую. Затем среди полученной цепочки символов находится такая ее часть (подцепочка), которая совпадает с левой частью какого-либо из правил множества P, и делается еще одна подстановка и т.д. Процесс заканчивается, если в полученной после всех подстановок цепочке больше не найдется ни одной части, совпадающей с левой частью ни одного из правил множества P.

Если в полученной таким образом цепочке все символы принадлежат алфавиту языка Σ, то считается, что вся порожденная цепочка принадлежит языку L. Если же в этой цепочке присутствует хотя бы один символов алфавита грамматики N, то такая цепочка не может принадлежать языку L. В этом случае говорят, что процесс порождения зашел в тупик. Может случиться, что процесс порождения никак не может остановиться, какие бы правила ни применялись на очередном шаге. Тогда говорят, что процесс порождения зациклил (попал в бесконечный цикл).

Символы алфавита языка Σ имеют еще одно название – терминальные символы (или просто терминалы), потому что получившаяся цепочка, состоящая только из них, прекращает процесс порождения. В свою очередь, символы алфавита грамматики N также имеют другое название – нетерминальные символы (или просто нетерминалы).

1.4. Классификация грамматик по Хомскому

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

Грамматика относится к классу 1, если все порождающие правила имеют вид:

αAβ → αγβ,

где α и β – цепочки из терминальных и (или) нетерминальных символов, одна из них или они обе могут быть пустыми; A – нетерминальный символ, γ – цепочка из терминальных и (или) нетерминальных символов, она не должна быть пустой. Грамматика класса 1 имеет еще одно название – контекстно-зависимая грамматика (или сокращенно КЗ-грамматика), потому что при порождении нетерминал A заменяется цепочкой γ в контексте цепочек α и β. Таким образом, все правила КЗ-грамматики должны быть неукорачивающими.

Грамматика относится к классу 2, если все порождающие правила имеют вид:

A → γ,

где A – нетерминальный символ, γ – цепочка из терминальных и (или) нетерминальных символов. Грамматика класса 2 имеет еще одно название – бесконтекстная или контекстно-свободная грамматика (сокращенно КС-грамматика). В КС-грамматике допускаются правила, правая часть которых состоит из пустой цепочки, т.е. правила, которые являются укорачивающими.

Грамматика относится к классу 3, если все порождающие правила имеют вид:

A → aB или A → a,

где A,B – нетерминальные символы, а – терминальный символ. Грамматика класса 3 имеет еще одно название – автоматная грамматика (сокращенно А-грамматика).

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

ω₁αω₂,

такой, что α является такой самой левой частью всей цепочки, которая совпадает с левой частью какого-либо из правил грамматики. Пусть это правило: α → β, тогда после его применения получится цепочка:

ω₁βω₂.

Если на каждом шаге порождение применяется только таким образом, то оно называется левым каноническим.

Грамматика называется однозначной, если для любой полученной ею цепочки языка существует единственная последовательность применения правил при левом каноническом порождении.

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

Свойством однозначности или неоднозначности могут обладать грамматики любого класса: от общего класса 0 до А-грамматик класса 3.