Типы грамматик

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

Соответствующий тип грамматики по Хомскому определяется ограничениями, которые налагаются на продукцию Р.

В (таблице 30) приводятся типы грамматик, типы языков и автоматы, которые могут быть описаны с помощью грамматики данного типа.

 

Таблица 28 – Классификация языков по Хомскому

Тип грамматики Ограничение Языки Автоматы
Тип 0 Нет ограничений рекурсивно-перечислимые языки машины Тьюринга
Тип 1 Длина цепочки β больше или равна длине цепочки α Контекстно-зависимые, или грамматики непосредственных составляющих (НС-языки) Линейно-ограниченные автоматы
Тип 2 Цепочка α состоит из одного символа Бесконтекстные или контекстно-свободные грамматики (КС-языки) Автомат с магазинной памятью
Тип 3 Цепочка β состоит либо из одного терминального и одного нетерминального символа, либо из одного терминального символа Регулярные языки Конечные автоматы

 

Тип 0 грамматик— самый общий тип грамматик, к нему относятся все без исключения формальные грамматики.

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

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

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

Одна и та же грамматика, в общем случае, может быть отнесена к нескольким классификационным типам (например, все формальные грамматики относятся к типу 0). Для классификации грамматики всегда выбирают максимально возможный тип, которому она удовлетворяет, поскольку сложность грамматики обратно пропорциональна номеру типа к которому она относится. Так, грамматики типа 0 являются самыми сложными, а грамматики типа 3 — самыми простыми.