Презентация Элементы теории языков. Лекция 24 онлайн

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Элементы теории языков. Лекция 24 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 25 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

Презентации » Устройства и комплектующие » Элементы теории языков. Лекция 24

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

25 слайдов
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

288.59 kB
Просмотров:

69
Скачиваний:

0
Автор:

неизвестен

Слайды и текст к этой презентации:

№1 слайд

Содержание слайда: элементы теории языков лекция 24

№2 слайд

Содержание слайда: План лекции Описание синтаксиса языков БНФ, РБНФ, синтаксические диаграммы Формальные грамматики Классификация грамматик по Хомскому Распознавание языков Синтаксический анализатор, нис- и восходящий разбор, полный перебор правил подстановки Определение языков с помощью автоматов

№3 слайд

Содержание слайда: Форма Бекуса-Наура описания синтаксиса формальных языков Джон Бекус (John Backus, 1924-2007) Руководил созданием первого компилятора для языка Фортран

№4 слайд

Содержание слайда: Форма Бекуса-Наура описания синтаксиса формальных языков Описание синтаксиса языков программирования Терминальные символы Нетерминальные символы Правила вида <нетерм.символ> ::= <посл.симв.1> | <посл.симв.2> | . . . | <посл.симв.n>

№5 слайд

Содержание слайда: Пример БНФ № 1 <цифра> ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' <знак> ::= '+'|'-'| <число без знака> ::= <цифра>| <цифра> <число без знака> <число> ::= <знак> <число без знака> Множество строк, которые описывает <число>: 0, 1, ..., 9, +0, +1, ..., +9, -0, -1, ..., -9, 00, 01, ..., 09, +00, +01, ..., +09, -00, -01, ..., -09, ...

№6 слайд

Содержание слайда: Пример БНФ № 2 Какое множество строк описывает <ппс> ? <ппс> ::= | '('<ппс>')' | <ппс><ппс>

№7 слайд

Содержание слайда: Пример БНФ № 3 Опишите БНФ при помощи БНФ

№8 слайд

Содержание слайда: Расширенная БНФ [<посл.симв.>] Необязательная последовательность символов {<посл.симв.>} Повторение последовательности символов

№9 слайд

Содержание слайда: Грамматики Формальный язык – это произвольное множество цепочек, составленных из символов некоторого конечного алфавита Произвольное -- бесконечное, конечное или пустое Грамматика – это конечное описание формального языка

№10 слайд

Содержание слайда: Определение грамматики Грамматика – это набор из четырех элементов Множество терминальных символов Алфавит языка Множество нетерминальных символов Вспомогательные символы, не входящие в описываемый язык Множество правил вида ЛЧ --> ПЧ, где ЛЧ – послед. терминалов и нетерминалов, содержащая >= 1 нетерминал ПЧ – любая последовательность нетерминалов Стартовый нетерминал С

№11 слайд

Содержание слайда: Применение правил грамматики Цепочка Ц2 получается из цепочки Ц1 применением правила ЛЧ --> ПЧ, если Ц1 имеет вид х ЛЧ у, а Ц2 имеет вид х ПЧ у Пример Цепочка ааАВвв получается из аАВв применением правила АВ --> аАВв

№12 слайд

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

№13 слайд

Содержание слайда: Примеры грамматик Язык {a+a, a+a+a, a+a+a+a, …} T = {a, +}, N = {S, A}, стартовый символ S, правила S --> aA A --> +aA A -->+a Пример вывода а+а+a S п1 aA п2 a+aA п3 а+а+а

№14 слайд

Содержание слайда: Примеры грамматик Язык {a, aaaa, aaaaaaaaa, …} – строки из n^2 символов а T = {a}, N = {S, S', A, B, C, L, R}, стартовый символ S, правила S --> LS'R S' --> AS'B S' --> AB AB --> BAC AC --> CA CB --> BC LB --> L AR --> R LC --> aL LR -->

№15 слайд

Содержание слайда: Классификация грамматик по Хомскому Ноам Хомски (Ноум Чомски, Noam Chomsky), 1928 Классификация (иерархия) грамматик по сложности распознавания описываемых ими языков

№16 слайд

Содержание слайда: Классификация грамматик по Хомскому – тип 0 Тип 0 – произвольные грамматики Любое рекурсивно перечислимое множество можно описать как язык с грамматикой типа 0 Нетривиальный результат Любой язык с грамматикой типа 0 является рекурсивно перечислимым множеством Почему? Есть языки с грамматикой типа 0, для которых проверка принадлежности алгоритмически неразрешима

№17 слайд

Содержание слайда: Классификация грамматик по Хомскому – тип 1 Тип 1 – контекстно-зависимые грамматики αAβ→αγβ, где α, β произвольные цепочки, γ непустая цепочка, A нетерминал Правила можно привести к виду α→β, где α, β непустые цепочки и 1≤|α|≤|β| Неукорачивающие грамматики Принадлежность любой цепочки языку м.б. проверена алгоритмом Аналог рекурсивных множеств

№18 слайд

Содержание слайда: Классификация грамматик по Хомскому – тип 2 Тип 2 – контекстно-свободные грамматики A→β, где β цепочка терминалов и нетерминалов, A нетерминал Описание языков программирования Эквивалентны БНФ Автоматическая генерация алгоритмов распознавания Рекурсивный спуск Быстрые LL и LR парсеры для языков со специальными КС грамматиками

№19 слайд

Содержание слайда: LL анализатор языка с КС грамматикой Лента Входной буфер, он же анализируемая цепочка Стек Промежуточные данные синтаксического анализа Таблица синтаксического анализа Либо правило грамматики для символа на вершине стека и текущего символа на ленте Либо пометка об отсутствии правила для такой пары символов

№20 слайд

Содержание слайда: LL анализатор языка с КС грамматикой Грамматика T={+,(,),1}, N={S,F}, правила S --> F S --> (S+F) F --> 1 Таблица ($ -- вспомогательный терминал "конец стека")

№21 слайд

Содержание слайда: LL анализатор языка с КС грамматикой -- пример

№22 слайд

Содержание слайда: LL анализатор языка с КС грамматикой Пока не конец Вершина стека нетерминал В таблице находим правило грамматики на пересечении столбца и строки, соответствующих нетерминалу на вершине стека и текущему символу на ленте, и кладем в стек цепочку из правой части правила Если в указанной ячейке таблицы правило отсутствует, то сообщаем об ошибке Вершина стека терминал Сравниваем его с текущим символом на ленте Если они равны, то удаляем символ с ленты и из стека Иначе ошибка Вершина $ Текущий символ на ленте $, то конец Иначе ошибка

№23 слайд

Содержание слайда: LL анализатор языка с КС грамматикой – построение таблицы Не успел :( A --> aX A --> zAat

№24 слайд

Содержание слайда: Классификация грамматик по Хомскому – тип 3 Тип 3 – регулярные грамматики A→ γB или A→γ, где γ цепочка терминалов, А и В нетерминалы Правила можно привести к виду A→ Bγ Для любого языка с регулярной грамматикой можно построить конечный автомат, распознающий этот язык Любой конечный автомат задает язык с регулярной грамматикой

№25 слайд

Содержание слайда: Заключение Описание синтаксиса языков БНФ, РБНФ, синтаксические диаграммы Формальные грамматики Классификация грамматик по Хомскому Распознавание языков Нис- и восходящий разбор, полный перебор правил подстановки Определение языков с помощью автоматов

Скачать все slide презентации Элементы теории языков. Лекция 24 одним архивом:

Скачать

Похожие презентации