Компиляторы. Формальные языки и грамматики. Классификация Хомского.

По класс. Хомского выделяют 4 грамматики:

1.Тип 0 (ноль). G=(VT,NV,P,S) V=VNUVT

V называется грамматикой типа 0, если на ее правила вывода не оказывается никаких ограничений. Правила имеют вид: α->β где αЄV*, βЄV*.

2.Тип 1. Грамматику типа 1 можно определить как контекстно зависимую, либо как неукорачивающую. Грамматика называется контекстно зависимой, если каждое правило из P имеет вид: α1A α2-> α1βα2, где α1α2βЄV* AЄVN βЄB. Грамматика называется неукорачивающей, если каждое правило из P имеет вид: α1->β, где α,βЄV+ |β|>=| α|

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

3. Тип 2. Грамматику типа 2 можно определить как контекстно свободную либо как укорачивающую контекстно свободную. Грамматика называется контекстно свободной если любое правило из P имеет вид: A-> β AЄVN β ЄV+

Грамматика называется, укорачивающей контекстно свободной, если любое правило из P имеет вид: A-> β AЄVN β ЄV+

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

4. Тип 3. Грамматику типа 3, можно определить либо как праволинейную либо как леволенейную. Грамматика называется праволенейной, если любое правило из P имеет вид: A->γβ A->γ A,BЄVN, γЄVT

Грамматика G называется леволенейной, если каждое из правил имеет вид: A->γβ A->γ A,BЄVN, γЄVT.

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

Язык L(G) является языком типа R если его можно описать грамматикой типа К. Языки классифицируются в соответствии с типами грамматик, с помощью которых они созданы.

*Тип 0 – это языки с фразовой структурой (самые сложные языки, разговорные). *Тип 1 – контекстнозависимые языки. Время на распознавание предолжений языка экспоненциально зависит от длины исходной цепочки символов. Языки и грамматики типа 1 применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, позволяют анализировать тексты с учетом контекстной зависимости в предложениях входного языка. *Тип 2 – контекстно свободные языки. КС языки лежат в основе синтаксических конструкций большинства современных языком программирования. На их основе функционируют некоторые сложные командные процессоры, допускающие управляющие команды цикла и условия. Эти обстоятельства определяют распространенность данного класса языков. В общем случае время на распознавание предложений языка, относящегося к типу 2 полиноминально зависит от исходной цепочки символов, но среди КС языков существует много классно языков, для которых эта зависимость линейна. *Тип 3 – регулярные языки. Время на распознавание предложений всегда линейно зависит от длины исходной цепочки символов. Данные языки лежат в основе простейших конструкций языков программирования, на их основе строятся мнемокоды команд. Для работы с регулярными языками можно использовать регулярные множества и выражения, а так же конечные автоматы.