Языки программирования Скачать
презентацию
<<  Классы объектов C История развития языков программирования  >>
Классификация грамматик и языков
Классификация грамматик и языков
4 типа грамматик по Хомскому:
4 типа грамматик по Хомскому:
4 типа грамматик по Хомскому:
4 типа грамматик по Хомскому:
При построении предложений КЗ-грамматик один и тот же нетерминальный
При построении предложений КЗ-грамматик один и тот же нетерминальный
Неукорачивающие грамматики имеют такую структуру правил, что при
Неукорачивающие грамматики имеют такую структуру правил, что при
Регулярные грамматики используются при описании простейших конструкций
Регулярные грамматики используются при описании простейших конструкций
Фото из презентации «Грамматика языков» к уроку информатики на тему «Языки программирования»

Автор: Dmitry Troitsky. Чтобы познакомиться с фотографией в полном размере, нажмите на её эскиз. Чтобы можно было использовать все фотографии на уроке информатики, скачайте бесплатно презентацию «Грамматика языков» со всеми фотографиями в zip-архиве размером 103 КБ.

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

Грамматика языков

содержание презентации «Грамматика языков»
Сл Текст Эф Сл Текст Эф
1Классификация грамматик и языков. Кафедра3 7процессорах. Троицкий Д.И. Лингвистическое и3
«Автоматизированные станочные системы» Dept. of программное обеспечение САПР. 7.
Automated Manufacturing Systems. Лекция 9. Троицкий 8Тип 2: контекстно-свободные (КС) языки КС-языки3
Д.И. Лингвистическое и программное обеспечение САПР. 1. лежат в основе синтаксических конструкций большинства
24 типа грамматик по Хомскому: V+ — множество всех4 современных языков программирования, Тип 3: регулярные
цепочек над алфавитом V без ?; V* — множество всех языки Регулярные языки — самый простой тип языков.
цепочек над алфавитом V, включая ?. Троицкий Д.И. Поэтому они являются самым широко используемым типом
Лингвистическое и программное обеспечение САПР. 2. языков в области вычислительных систем. Время на
3При построении предложений КЗ-грамматик один и тот2 распознавание предложений регулярного языка линейно
же нетерминальный символ может быть заменен на ту или зависит от длины входной цепочки символов. Регулярные
иную цепочку символов в зависимости от того контекста, языки лежат в основе простейших конструкций языков
в котором он встречается. Цепочки ?1 и ?2 в правилах программирования (идентификаторов, констант и т. п.),
грамматики обозначают контекст (?1— левый контекст, а кроме того, на их основе строятся языки ассемблеров, а
?2 — правый контекст), в общем случае любая из них (или также командные процессоры, символьные управляющие
даже обе) может быть пустой. Говоря иными словами, команды и другие подобные структуры. Троицкий Д.И.
значение одного и того же символа может быть различным Лингвистическое и программное обеспечение САПР. 8.
в зависимости от того, в каком контексте он 9Чем все это безобразие распознавать. Для языков с3
встречается. При построении компиляторов такие фразовой структурой (тип 0) необходим распознаватель,
грамматики не применяются. Троицкий Д.И. имеющий неограниченную внешнюю память. Поэтому для
Лингвистическое и программное обеспечение САПР. 3. языков данного типа нельзя гарантировать, что за
4Неукорачивающие грамматики имеют такую структуру3 ограниченное время на ограниченных вычислительных
правил, что при построении предложений языка, заданного ресурсах распознаватель завершит работу и примет
грамматикой, любая цепочка символов может быть заменена решение о том, принадлежит или не принадлежит входная
на цепочку символов не меньшей длины. КС-грамматики цепочка заданному языку. Практического применения языки
широко используются при описании синтаксических с фразовой структурой не имеют. Для
конструкций языков программирования. Синтаксис контекстно-зависимых языков (тип 1) распознавателями
большинства известных языков программирования основан являются двусторонние недетерминированные автоматы с
именно на КС-грамматиках. Троицкий Д.И. Лингвистическое ограниченной памятью. Количество шагов, необходимых
и программное обеспечение САПР. 4. автомату для распознавания входной цепочки,
5Регулярные грамматики используются при описании3 экспоненциально зависит от длины этой цепочки. Троицкий
простейших конструкций языков программирования: Д.И. Лингвистическое и программное обеспечение САПР. 9.
идентификаторов, констант, строк, комментариев и т. д. 10Экспоненциальная зависимость времени разбора от1
Для классификации грамматик всегда выбирают максимально длины цепочки существенно ограничивает применение
возможный тип, к которому она может быть отнесена. распознавателей для контекстно-зависимых языков. Такие
Сложность грамматики обратно пропорциональна номеру распознаватели применяются для автоматизированного
типа, к которому относится грамматика. Грамматики, перевода и анализа текстов на естественных языках,
которые относятся только к типу 0, являются самыми когда временные ограничения на разбор текста
сложными, а грамматики, которые можно отнести к типу 3 несущественны. Для контекстно-свободных языков (тип 2)
— самыми простыми. Троицкий Д.И. Лингвистическое и распознавателями являются односторонние
программное обеспечение САПР. 5. недетерминированные автоматы с магазинной (стековой)
6Классификация языков. Тип 0: языки с фразовой3 внешней памятью — МП-автоматы. При простейшей
структурой Это самые сложные языки, которые могут быть реализации алгоритма работы такого автомата он имеет
заданы только грамматикой, относящейся к типу 0. Если экспоненциальную сложность, однако путем некоторых
язык относится к типу 0, то для него невозможно усовершенствований алгоритма можно добиться
построить компилятор, который гарантированно выполнял полиномиальной (кубической) зависимости времени,
бы разбор предложений языка за ограниченное время на необходимого на разбор входной цепочки, от длины этой
основе ограниченных вычислительных ресурсов. К цепочки. Следовательно, можно говорить о полиномиальной
сожалению, все естественные языки относятся к фразовым. сложности распознавателя для КС-языков. Троицкий Д.И.
Структура и значение фразы естественного языка может Лингвистическое и программное обеспечение САПР. 10.
зависеть не только от контекста данной фразы, но и от 11G1{0,1,2,3,4,5,6,7,8,9,-,+},{s, т, f},p1,s): p1: s2
содержания того текста, где эта фраза встречается. Одно ? т | +т | -т т ? f | tf f ? 0 | 1 | 2 | 3 | 4 | 5 | 6
и то же слово в естественном языке может не только | 7 | 8 | 9. По структуре своих правил данная
иметь разный смысл, в зависимости от контекста, но и грамматика G1 относится к контекстно-свободным
играть различные роли в предложении. Именно поэтому грамматикам (тип 2). Ее можно отнести и к типу 0, и к
столь велики сложности в автоматизации перевода типу 1, но максимально возможным является именно тип 2,
текстов, написанных на естественных языках. Троицкий поскольку к типу 3 эту грамматику отнести никак нельзя:
Д.И. Лингвистическое и программное обеспечение САПР. 6. строка Т ? F | TF содержит правило Т ? TF, которое
7Тип 1: контекстно-зависимые (КЗ) языки Тип 1 —3 недопустимо для типа 3, и хотя все остальные правила
второй по сложности тип языков. В общем случае время на этому типу соответствуют, одного несоответствия
распознавание предложений языка, относящегося к типу 1, достаточно. Пример: грамматика целых десятичных чисел.
экспоненциально зависит от длины исходной цепочки Троицкий Д.И. Лингвистическое и программное обеспечение
символов. В компиляторах КЗ-языки не используются. САПР. 11.
Языки и грамматики, относящиеся к типу 1, применяются в 12G1' ({0,1,2,3,4,5,6,7,8,9,-,+},{s, т},p1',s): p1':5
анализе и переводе текстов на естественных языках. s ? т | +т | -т т ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Распознаватели, построенные на их основе, позволяют 9 | 0т | 1t | 2т | 3т | 4т | 5т | 6т | 7т | 8т | 9т. По
анализировать тексты с учетом контекстной зависимости в структуре своих правил данная грамматика G1 является
предложениях входного языка (но они не учитывают праволинейной и относится к типу 3. Та же грамматика,
содержание текста, поэтому для точного перевода с но леволинейная: G1'' ({0,1,2,3,4,5,6,7,8,9,-,+},{S,
естественного языка требуется вмешательство человека). Т},P1'',S): P1': Т ? + | - | ? S ? T0 | T1 | T2 | T3 |
На основе таких грамматик может выполняться T4 | T5 | T6 | T7 | T8 | T9 | S0 | S1 | S2 | S3 | S4 |
автоматизированный перевод с одного естественного языка S5 | S6 | S7 | S8 | S9. Та же грамматика, но
на другой, ими могут пользоваться сервисные функции по-другому: Троицкий Д.И. Лингвистическое и программное
проверки орфографии и правописания в языковых обеспечение САПР. 12.
12 «Грамматика языков» | Грамматика языков 35
http://900igr.net/fotografii/informatika/Grammatika-jazykov/Grammatika-jazykov.html
cсылка на страницу
Урок

Информатика

126 тем
Фото
Презентация: Грамматика языков | Тема: Языки программирования | Урок: Информатика | Вид: Фото