Четыре типа грамматик по Хомскому

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

По классификации Хомского выделяют четыре типа грамматик.

Тип О: грамматики с фразовой структурой

На структуру их правил не накладывается никаких ограничений: для граммати­ки вида G(VT,VN,P,S), V - VNuVT правила имеют вид: а->р, где aeV⁺, (3eV*.

Это самый общий тип грамматик. В него подпадают все без исключения фор­мальные грамматики, но часть из них, к общей радости, может быть также отне­сена и к другим классификационным типам. Дело в том, что грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре.

Практического применения грамматики, относящиеся только к типу 0, не имеют.

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

В этот тип входят два основных класса грамматик.

Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNuVT имеют правила вида: сцАсхг-нх^аг, где a₁,a₂eV*, AeVN, (JeV⁴.

Неукорачивающие грамматики G(VT,VN,P,S), V = VNu VT имеют правила вида: a->(3, где a,(3eV⁺, |p|>|a|.

Структура правил КЗ-грамматик такова, что при построении предложений за­данного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Именно поэтому эти грамматики называют «контекстно-зависимы­ми». Цепочки 0ц и а₂ в правилах грамматики обозначают контекст (оц — левый контекст, а а₂ — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

Глава 9. Формальные языки и грамматики

Неукорачивающие грамматики имеют такую структуру правил, что при построе­нии предложений языка, заданного грамматикой, любая цепочка символов мо­жет быть заменена на цепочку символов не меньшей длины. Отсюда и название «неукорачивающие».

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

При построении компиляторов такие грамматики не применяются, поскольку языки программирования, рассматриваемые компиляторами, имеют более про­стую структуру и могут быть построены с помощью грамматик других типов.

Тип 2: контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNuVT имеют правила вида: А-»р\ где AeVN, peV⁺. Такие грамматики также иногда называют неукорачивающими контекстно-свободными (НКС) грамматиками (видно, что в правой части правила у них должен всегда стоять как минимум один символ).

Существует также почти эквивалентный им класс грамматик — укорачивающие контекстно-свободные (УКС) грамматики G(VT,VN,P,S), V = VNuVT, правила которых могут иметь вид: А—»р\ где AeVN, PeV*.

Разница между этими двумя классами грамматик заключается лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая це­почка (А.), а в НКС-грамматиках — нет. Отсюда ясно, что язык, заданный НКС-грамматикой, не может содержать пустой цепочки. Доказано, что эти два класса грамматик почти эквивалентны. В дальнейшем, когда речь будет идти о КС-грамматиках, уже не будет уточняться, какой класс грамматики (УКС или НКС) имеется в виду, если возможность наличия в языке пустой цепочки не имеет принципиального значения.

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

Внутри типа КС-грамматик кроме классов НКС и УКС выделяют еще целое множество различных классов грамматик, и все они относятся к типу 2. Далее, когда КС-грамматики и КС-языки будут рассматриваться более подробно, на не­которые из этих классов грамматик и их характерные особенности будет обраще­но особое внимание.

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

К типу регулярных относятся два эквивалентных класса грамматик: леволиней-ные и праволинейные.

Классификация HjbiKOB и грамматик.

Леволинейные грамматики G(VT,VNJP,S), V - VNuVT могут иметь правила двух видов: А-»Ву или А-»у, где A.BeVN, yeVT.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VNuVT могут иметь правила тоже двух видов: А-»уВ или А-»у, где A,BeVN, yeVT*.

Эти два класса грамматик эквивалентны и относятся к типу регулярных грам­матик.

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

Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена и к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являют­ся ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида «А->Ъ>, недопустимые в типе 1. В целом можно сказать, что сложность грамматики обратно пропорциональна тому максимально воз­можному номеру типа, к которому может быть отнесена грамматика. Граммати­ки, которые относятся только к типу 0, являются самыми сложными, а грамма­тики, которые можно отнести к типу 3 — самыми простыми.

Классификация языков

Языки классифицируются в соответствии с типами грамматик, с помощью кото­рых они заданы. Причем, поскольку один и тот же язык в общем случае может быть задан сколь угодно большим количеством грамматик, которые могут отно­ситься к различным классификационным типам, то для классификации самого языка среди всех его грамматик всегда выбирается грамматика с максимально возможным классификационным типом. Например, если язык L может быть за­дан грамматиками G, и G₂, относящимися к типу 1 (контекстно-зависимые), грамматикой G₃, относящейся к типу 2 (контекстно-свободные), и грамматикой G₄, относящейся к типу 3 (регулярные), то сам язык должен быть отнесен к типу 3 и является регулярным языком.

От классификационного типа языка зависит не только то, с помощью какой грамматики можно построить предложения этого языка, но также и то, насколь­ко сложно распознать эти предложения. Распознать предложения — значит по­строить распознаватель для языка (третий способ задания языка). Сами распо­знаватели, их структура и классификация будут рассмотрены далее, здесь же можно указать, что сложность распознавателя языка напрямую зависит от клас­сификационного типа, к которому относится язык.

Сложность языка убывает с возрастанием номера классификационного типа языка. Самыми сложными являются языки типа 0, самыми простыми — языки типа 3.

Согласно классификации грамматик, существуют также четыре типа языков.

Глава 9. Формальные языки и грамматики

Тип О: языки с фразовой структурой

Это самые сложные языки, которые могут быть заданы только грамматикой, от­носящейся к типу 0. Для распознавания цепочек таких языков требуются вычис­лители, равномощные машине Тьюринга. Поэтому можно сказать, что если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.

К сожалению, практически все естественные языки общения между людьми, строго говоря, относятся именно к этому типу языков. Дело в том, что структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и то же слово в естественном языке может не только иметь' разный смысл в зави­симости от контекста, но и играть различную роль в предложении. Именно по­этому столь велики сложности в автоматизации перевода текстов, написанных на естественных языках, а также отсутствуют (и видимо, никогда не появятся) компиляторы, которые бы воспринимали программы на основе таких языков.

Далее языки с фразовой структурой рассматриваться не будут.

Тип 1: контекстно-зависимые (КЗ) языки

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

Языки и грамматики, относящиеся к типу 1, применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, по­зволяют анализировать тексты с учетом контекстной зависимости в предложе­ниях входного языка (но они не учитывают содержание текста, поэтому в общем случае для точного перевода с естественного языка все же требуется вмешатель­ство человека). На основе таких грамматик может выполняться автоматизиро­ванный перевод с одного естественного языка на другой, ими могут пользоваться сервисные функции проверки орфографии и правописания в языковых процес­сорах.

В компиляторах КЗ-языки не используются, поскольку языки программирова­ния имеют более простую структуру, поэтому здесь они подробно не рассматри­ваются.

Тип 2: контекстно-свободные (КС) языки

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

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

Классификация языков и грамматик

Однако среди КС-языков существует много классов языков, для которых эта за­висимость линейна. Многие языки программирования можно отнести к одному из таких классов.

КС-языки подробно рассматриваются в главе «Контекстно-свободные языки» данного учебного пособия.

Тип 3: регулярные языки

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

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

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

Примеры классификации языков и грамматик

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

Далее приводятся примеры некоторых языков указанных типов.

Рассмотрим в качестве первого примера ту же грамматику для целых десятич­ных чисел со знаком G({0,l,2,3,4,5.6,7,8,9,-,+},{S,T,F}.P,S):

Р:

S -> Т | +Т | -Т

Т -» F | TF

F->0|l|2|3|4|5|6|7|8|9

По структуре своих правил данная грамматика G относится к контекстно-сво­бодным грамматикам (тип 2). Конечно, ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка Т— >¥ \ TF содержит правило Т—»TF, которое недопустимо для типа 3, и, хотя все остальные правила этому типу соот­ветствует, одного несоответствия достаточно.

Для того же самого языка (целых десятичных чисел со знаком) можно построить и другую грамматику G" ({0,1.2,3,4.5,6,7,8,9,-,+},{S,T},P,S):

Р:

S -> Т | +Т | -Т

Т -* 0 | 1 | 2 | 3 | 4 | 5 | б | 7 | 8 | 9 | ОТ | IT | 2Т | ЗТ | 4Т | 5Т | 6Т | 7Т | 8Т | 9Т По структуре своих правил грамматика G' является праволинейной и может быть отнесена к регулярным грамматикам (тип 3).

Для этого же языка можно построить эквивалентную леволинеиную грамматику (тип 3) G"({0.1,2,3,4,5,6,7,8_>9,-,+}_>{S,T},P,S):

Р:

Т -> * | - | X

S -> ТО | Т1 | Т2 | ТЗ | Т4 | Т5 | Тб! Т7 | Т8 | Т9 | SO | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

Следовательно, язык целых десятичных чисел со знаком, заданный грамматика­ми G, G' и G", относится к регулярным языкам (тип 3).

В качестве второго примера возьмем грамматику G₂({0,l},{A,S},P,S) с правила­ми Р:

S -» 0А1 ОА -* 00А1 А -» X

Эта грамматика относится к типу 0. Она определяет язык, множество предложе­ний которого можно было бы записать так: L(G₂) ⁼ {0ⁿlⁿ | n > 0}.

Для этого же языка можно построить также контекстно-зависимую грамматику G₂'({0,l},{A,S},P',S) с правилами Р':

S —» 0А1 | 01

ОА -> 00А1 | 001

Однако для того же самого языка можно использовать и контекстно-свободную грамматику G₂"({0,l},{S},P",S) с правилами Р":

S —> 0S1 | 01

Следовательно, язык L = {0ⁿlⁿ | n > 0} является контекстно-свободным (тип 2).

В третьем примере рассмотрим грамматику G₃({a,b,c},{B,C,D,S},P,S) с правила­ми Р:

S -> BD

В -> аВЬС | ab СЬ -» ЬС CD -> Dc bDc -> bcc abD -> abc

Эта грамматика относится к типу 1. Очевидно, что она является неукорачиваю-щей. Она определяет язык, множество предложений которого можно было бы за­писать так: L(G₃) = {aⁿbⁿcⁿ | n > 0}. Известно, что этот язык не является КС-язы­ком, поэтому для него нельзя построить грамматики типов 2 или 3.

Язык L - {aⁿbⁿcⁿ | п > 0} является контекстно-зависимым (тип 1).

Конечно, для произвольного языка, заданного некоторой грамматикой, в общем

случае довольно сложно так легко определить его тип. Не всегда можно так

ЦВМ

просто построить грамматику максимально возможного типа для произвольного языка. К тому же при строгом определении типа требуется еще доказать, что две грамматики (первоначально имеющаяся и вновь построенная) эквивалентны, а также то, что не существует для того же языка грамматики с большим по номе­ру типом. Это нетривиальная задача, которую не так легко решить. Для многих языков, и в частности для КС-языков и регулярных языков, сущест­вуют специальным образом сформулированные утверждения, которые позволя­ют проверить принадлежность языка к указанному типу. Такие утверждения (леммы) будут рассмотрены далее в соответствующих главах этого учебника. Тогда для произвольного языка достаточно лишь доказать нужное утверждение, и после этого можно точно утверждать, что данный язык относится к тому или иному типу. Преобразование грамматик в этом случае не требуется.

Тем не менее иногда возникает задача построения для имеющегося языка грам­матики более простого типа, чем данная. И даже в том случае, когда тип языка уже известен, эта задача остается нетривиальной и в общем случае не имеет фор­мального решения (проблема преобразования грамматик рассматривается далее).

Дата добавления: 2015-06-27