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

Нажмите для полного просмотра!

Элементы теории языков. Лекция 24, слайд №1

Элементы теории языков. Лекция 24, слайд №2

Элементы теории языков. Лекция 24, слайд №3

Элементы теории языков. Лекция 24, слайд №4

Элементы теории языков. Лекция 24, слайд №5

Элементы теории языков. Лекция 24, слайд №6

Элементы теории языков. Лекция 24, слайд №7

Элементы теории языков. Лекция 24, слайд №8

Элементы теории языков. Лекция 24, слайд №9

Элементы теории языков. Лекция 24, слайд №10

Элементы теории языков. Лекция 24, слайд №11

Элементы теории языков. Лекция 24, слайд №12

Элементы теории языков. Лекция 24, слайд №13

Элементы теории языков. Лекция 24, слайд №14

Элементы теории языков. Лекция 24, слайд №15

Элементы теории языков. Лекция 24, слайд №16

Элементы теории языков. Лекция 24, слайд №17

Элементы теории языков. Лекция 24, слайд №18

Элементы теории языков. Лекция 24, слайд №19

Элементы теории языков. Лекция 24, слайд №20

Элементы теории языков. Лекция 24, слайд №21

Элементы теории языков. Лекция 24, слайд №22

Элементы теории языков. Лекция 24, слайд №23

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

Элементы теории языков. Лекция 24, слайд №25

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Элементы теории языков. Лекция 24. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

элементы теории языков лекция 24

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 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...$

Описание слайда:

Примеры грамматик Язык {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

Описание слайда:

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