6.3.3 Иерархия языков

Продукции позволяют осуществлять самые pазные трансформации строк. Чаще всего языки делят на четыре типа, в зависимости от ограничений, налагаемых на грамматику.

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

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

Если левая часть продукции ограничивается одним нетерминальным символом, то ее применение не зависит от контекста, в котором этот символ появляется в исходной строке. Грамматика с таким ограничением называется грамматикой типа 2 или контекстно-свободной грамматикой.

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

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

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