Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. XLVIII. Андейский циклический крест. Четыре стороны основания.
  2. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ
  3. БАНДА ЧЕТЫРЕХ
  4. Беседа 19. На день святых четыредесяти мучеников
  5. Ваши взаимоотношения должны пройти четыре стадии создания союза
  6. ВАШИ ПЕРВЫЕ ЧЕТЫРЕ ЗАНЯТИЯ
  7. Во все дни поста святыя четыредесятницы, кроме субботы и недели и святаго дня Благовещения, святая литургия да бывает не иная, как преждеосвященных даров.
  8. ВТОРОЙ ПЕРИОД ИЗ ЧЕТЫРЕХ ДНЕЙ
  9. Второй этап начинается с четырех—четырех с половиной лет.
  10. Вы — лучшие люди на земле”, а было нас тысяча четыреста (человек), и если бы я мог видеть сегодня, то обязательно показал бы вам то место (, где стоит это) дерево1».
  11. ГЕРМЕТИЧЕСКИЕ НАУКИ. ГРАММАТИКА, ПОЭТИКА, РИТОРИКА
  12. Грабля номер четыре: Обобщения.



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

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

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

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

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

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

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

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

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

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

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


Глава 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, и G2, относящимися к типу 1 (контекстно-зависимые), грамматикой G3, относящейся к типу 2 (контекстно-свободные), и грамматикой G4, относящейся к типу 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).

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

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

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

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

S —» 0А1| 01

ОА -> 00А1 | 001

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

S —> 0S1 | 01

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

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

S -> BD

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

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

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

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

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


ЦВМ

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

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





Дата добавления: 2015-06-27; Просмотров: 778; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.225.59.242
Генерация страницы за: 0.01 сек.