Расширенная классификация грамматик Хомского

В зависимости от вида правил грамматики различают:

тип 0 –грамматики фразовой структуры или грамматики «без ограничений»:

α ® β, где α Î V ⁺, β Î V *– в таких грамматиках допустимо наличие любых правил вывода, что свойственно грамматикам естественных языков;

тип 1 – контекстно-зависимые (неукорачивающие) грамматики:

α® β, где α Î V ⁺, β Î V *, | α | £ | β | – в этих грамматиках для правил вида α X β ® α x β возможность подстановки строки х вместо символа X определяется присутствием подстрок α и β, т. е. контекста, что также свойственно грамматикам естественных языков;

(расширение допускает не более одного правила вида A ® e, где A Î V_N);

тип 2 – контекстно-свободные грамматики:

A ® β, где A Î V_N, βÎ V * – поскольку в левой части правила стоит нетерминал, подстановки не зависят от контекста;

тип 3 – регулярная грамматика:

A ® α, A ® α B,где A, В Î V_N, α Î V_T;

(расширение допускает не более одного правила вида S ® e, но в этом случае аксиома не должна появляться в правых частях правил).

Классификация построена по правилам иерархии, т. е. грамматики типа 3 являются частным случаем грамматик типа 2 и т. п. (см. рисунок 3).

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

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

<целое>::= + <цбз>| - <цбз>|0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|

5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9

<цбз>::= 0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|

5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9.

Следовательно, язык описания целых десятичных чисел относится к типу 3.

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

Пример. Язык описания целых чисел. Из строки «+23» можно построить строки: 22222, 23232323 и т. д. того же языка.

Еще одно свойство языка позволяет сразу определить, что язык не относится к классу регулярных – это самовложение, т. е. наличие правил вида A Þ⁺ α₁ A α₂, где α₁, α₂ Î V ⁺.

Пример. Язык скобок, описываемый правилами: S ® (S), S ® SS, S ® e. Грамматика этого языка является грамматикой с самовложением, принадлежит классу КС и не приводима к регулярной.

Лемма о разрастании КС языков формулируется следующим образом: в строке, принадлежащей КС-языку, всегда можно найти две подстроки с ненулевой суммарной длиной, одновременное повторение которых произвольное количество раз порождает новую строку того же языка.

Пример. Язык скобок. Из строки «()» можно построить строку: ((())) и т. д. того же языка.

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

грамматики типа 3 распознаются конечными автоматами;

грамматики типа 2 распознаются автоматами с магазинной памятью;

грамматики типа 1 распознаются линейными ограниченными автоматами;

грамматики типа 0 распознаются машинами Тьюринга.

Поиск по сайту: