PPt4Web Хостинг презентаций

Главная / Информатика / Классификация грамматик и языков
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

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

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию



№ слайда 1 Кафедра «Автоматизированные станочные системы»Dept. of Automated Manufacturing S
Описание слайда:

Кафедра «Автоматизированные станочные системы»Dept. of Automated Manufacturing Systems Классификация грамматик и языков

№ слайда 2 4 типа грамматик по Хомскому: V+ — множество всех цепочек над алфавитом V без λ;
Описание слайда:

4 типа грамматик по Хомскому: V+ — множество всех цепочек над алфавитом V без λ;V* — множество всех цепочек над алфавитом V, включая λ. Ноам Хомский(Noam Chomsky)

№ слайда 3 При построении предложений КЗ-грамматик один и тот же нетерминальный символ може
Описание слайда:

При построении предложений КЗ-грамматик один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Цепочки α1 и α2 в правилах грамматики обозначают контекст (α1— левый контекст, а α2 — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

№ слайда 4 Неукорачивающие грамматики имеют такую структуру правил, что при построении пред
Описание слайда:

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

№ слайда 5 Регулярные грамматики используются при описании простейших конструкций языков пр
Описание слайда:

Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д. Для классификации грамматик всегда выбирают максимально возможный тип, к которому она может быть отнесена. Сложность грамматики обратно пропорциональна номеру типа, к которому относится грамматика. Грамматики, которые относятся только к типу 0, являются самыми сложными, а грамматики, которые можно отнести к типу 3 — самыми простыми.

№ слайда 6 Классификация языковТип 0: языки с фразовой структуройЭто самые сложные языки, к
Описание слайда:

Классификация языковТип 0: языки с фразовой структуройЭто самые сложные языки, которые могут быть заданы только грамматикой, относящейся к типу 0. Если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.К сожалению, все естественные языки относятся к фразовым. Структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и то же слово в естественном языке может не только иметь разный смысл, в зависимости от контекста, но и играть различные роли в предложении. Именно поэтому столь велики сложности в автоматизации перевода текстов, написанных на естественных языках

№ слайда 7 Тип 1: контекстно-зависимые (КЗ) языкиТип 1 — второй по сложности тип языков. В
Описание слайда:

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

№ слайда 8 Тип 2: контекстно-свободные (КС) языкиКС-языки лежат в основе синтаксических кон
Описание слайда:

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

№ слайда 9 Чем все это безобразие распознавать Для языков с фразовой структурой (тип 0) нео
Описание слайда:

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

№ слайда 10 Экспоненциальная зависимость времени разбора от длины цепочки существенно ограни
Описание слайда:

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

№ слайда 11 Пример: грамматика целых десятичных чисел По структуре своих правил данная грамм
Описание слайда:

Пример: грамматика целых десятичных чисел По структуре своих правил данная грамматика G1 относится к контекстно-свободным грамматикам (тип 2). Ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка Т F | TF содержит правило Т TF, которое недопустимо для типа 3, и хотя все остальные правила этому типу соответствуют, одного несоответствия достаточно.

№ слайда 12 Та же грамматика, но по-другому: По структуре своих правил данная грамматика G1
Описание слайда:

Та же грамматика, но по-другому: По структуре своих правил данная грамматика G1 является праволинейной и относится к типу 3. Та же грамматика, но леволинейная:

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru