Презентация на тему: Классификация грамматик и языков
Кафедра «Автоматизированные станочные системы»Dept. of Automated Manufacturing Systems Классификация грамматик и языков
4 типа грамматик по Хомскому: V+ — множество всех цепочек над алфавитом V без λ;V* — множество всех цепочек над алфавитом V, включая λ. Ноам Хомский(Noam Chomsky)
При построении предложений КЗ-грамматик один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Цепочки α1 и α2 в правилах грамматики обозначают контекст (α1— левый контекст, а α2 — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.
Неукорачивающие грамматики имеют такую структуру правил, что при построении предложений языка, заданного грамматикой, любая цепочка символов может быть заменена на цепочку символов не меньшей длины. КС-грамматики широко используются при описании синтаксических конструкций языков программирования. Синтаксис большинства известных языков программирования основан именно на КС-грамматиках
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д. Для классификации грамматик всегда выбирают максимально возможный тип, к которому она может быть отнесена. Сложность грамматики обратно пропорциональна номеру типа, к которому относится грамматика. Грамматики, которые относятся только к типу 0, являются самыми сложными, а грамматики, которые можно отнести к типу 3 — самыми простыми.
Классификация языковТип 0: языки с фразовой структуройЭто самые сложные языки, которые могут быть заданы только грамматикой, относящейся к типу 0. Если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.К сожалению, все естественные языки относятся к фразовым. Структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и то же слово в естественном языке может не только иметь разный смысл, в зависимости от контекста, но и играть различные роли в предложении. Именно поэтому столь велики сложности в автоматизации перевода текстов, написанных на естественных языках
Тип 1: контекстно-зависимые (КЗ) языкиТип 1 — второй по сложности тип языков. В общем случае время на распознавание предложений языка, относящегося к типу 1, экспоненциально зависит от длины исходной цепочки символов.Языки и грамматики, относящиеся к типу 1, применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, позволяют анализировать тексты с учетом контекстной зависимости в предложениях входного языка (но они не учитывают содержание текста, поэтому для точного перевода с естественного языка требуется вмешательство человека). На основе таких грамматик может выполняться автоматизированный перевод с одного естественного языка на другой, ими могут пользоваться сервисные функции проверки орфографии и правописания в языковых процессорах.
Тип 2: контекстно-свободные (КС) языкиКС-языки лежат в основе синтаксических конструкций большинства современных языков программирования, Тип 3: регулярные языкиРегулярные языки — самый простой тип языков. Поэтому они являются самым широко используемым типом языков в области вычислительных систем. Время на распознавание предложений регулярного языка линейно зависит от длины входной цепочки символов. Регулярные языки лежат в основе простейших конструкций языков программирования (идентификаторов, констант и т. п.), кроме того, на их основе строятся языки ассемблеров, а также командные процессоры, символьные управляющие команды и другие подобные структуры.
Чем все это безобразие распознавать Для языков с фразовой структурой (тип 0) необходим распознаватель, имеющий неограниченную внешнюю память. Поэтому для языков данного типа нельзя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Практического применения языки с фразовой структурой не имеют.Для контекстно-зависимых языков (тип 1) распознавателями являются двусторонние недетерминированные автоматы с ограниченной памятью. Количество шагов, необходимых автомату для распознавания входной цепочки, экспоненциально зависит от длины этой цепочки.
Экспоненциальная зависимость времени разбора от длины цепочки существенно ограничивает применение распознавателей для контекстно-зависимых языков. Такие распознаватели применяются для автоматизированного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны.Для контекстно-свободных языков (тип 2) распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешнейпамятью — МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усовершенствований алгоритма можно добиться полиномиальной (кубической) зависимости времени, необходимого на разбор входной цепочки, от длины этойцепочки. Следовательно, можно говорить о полиномиальной сложности распознавателя для КС-языков.
Пример: грамматика целых десятичных чисел По структуре своих правил данная грамматика G1 относится к контекстно-свободным грамматикам (тип 2). Ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка Т F | TF содержит правило Т TF, которое недопустимо для типа 3, и хотя все остальные правила этому типу соответствуют, одного несоответствия достаточно.
Та же грамматика, но по-другому: По структуре своих правил данная грамматика G1 является праволинейной и относится к типу 3. Та же грамматика, но леволинейная:
