Проблема тупиков и методы борьбы с ними
43. Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов
44. Примеры тупиковых ситуаций и причины их возникновения
Пример тупика на ресурсах типа СR
Пример тупика на ресурсах типа СR и SR
Пример тупика на ресурсах типа SR
45. Формальные модели для изучения проблемы тупиковых ситуаций
Сети Петри
Вычислительные схемы
Модель пространства состояний системы
46. Методы борьбы с тупиками
Предотвращение тупиков
Обход тупиков
Обнаружение тупика
Современные операционные системы
47. Семейство операционных систем UNIX
Общая характеристика семейства операционных систем UNIX, особенности архитектуры семейства ОС UNIX
Основные понятия системы UNIX
Функционирование системы UNIX
Файловая система
Межпроцессные коммуникации в UNIX
Операционная система Linux
48. Семейство операционных систем OS/2 Warp компании IBM
Особенности архитектуры и основные возможности OS/2 Warp
Особенности интерфейса OS/2 Warp
Серверная операционная система OS/2 Warp 4.5
49. Сетевая ОС реального времени QNX
Архитектура системы QNX
Основные механизмы QNX для организации распределенных вычислений
Часть II. Трансляторы, формальные языки и грамматики
Формальные языки и грамматики
1. Языки и цепочки символов. Способы задания языков
Цепочки символов. Операции над цепочками символов
Понятие языка. Формальное определение языка
Способы задания языков
|
|
|
Синтаксис и семантика языка
Особенности языков программирования
2. Определение грамматики. Форма Бэкуса--Наура
Понятие о грамматике языка
Формальное определение грамматики. Форма Бэкуса--Наура
Принцип рекурсии в правилах грамматики
Другие способы задания грамматик
3. Классификация языков и грамматик
Классификация грамматик. Четыре типа грамматик по Хомскому
Классификация языков
Примеры классификации языков и грамматик
4. Цепочки вывода. Сентенциальная форма
Вывод. Цепочки вывода
Сентенциальная форма грамматики. Язык, заданный грамматикой
Левосторонний и правосторонний выводы
Дерево вывода. Методы построения дерева вывода
5. Проблемы однозначности и эквивалентности грамматик
Однозначные и неоднозначные грамматики
Эквивалентность и преобразование грамматик
Правила, задающие неоднозначность в грамматиках
6. Распознаватели. Задача разбора
Общая схема распознавателя
Виды распознавателей
Классификация распознавателей по типам языков
Задача разбора (постановка задачи)
Регулярные языки
7. Регулярные языки и грамматики
Леволинейные и праволинейные грамматики. Автоматные грамматики
Алгоритм преобразования регулярной грамматики к автоматному виду
|
|
|
Пример преобразования регулярной грамматики к автоматному виду
8. Конечные автоматы
Определение конечного автомата
Детерминированные и недетерминированные конечные автоматы
Преобразование конечного автомата к детерминированному виду
Минимизация конечных автоматов
9. Регулярные множества и регулярные выражения
Определение регулярного множества
Регулярные выражения. Свойства регулярных выражений
Уравнения с регулярными коэффициентами
10. Способы задания регулярных языков
Три способа задания регулярных языков
Связь регулярных выражений и регулярных грамматик
Связь регулярных выражений и конечных автоматов
Связь регулярных грамматик и конечных автоматов
Пример построения конечного автомата на основе заданной грамматики
11. Свойства регулярных языков
Свойства регулярных языков
Лемма о разрастании для регулярных языков
Контекстно-свободные языки
12. Распознаватели КС-языков. Автоматы с магазинной памятью
Определение МП-автомата
Эквивалентность языков МП-автоматов и КС-грамматик
Детерминированные МП-автоматы
13. Свойства КС-языков
Свойства произвольных КС-языков
Свойства детерминированных КС-языков
|
|
|
Лемма о разрастании КС-языков
14. Преобразование КС-грамматик. Приведенные грамматики
Преобразование грамматик. Цель преобразования.
Приведенные грамматики
Удаление недостижимых символов
Удаление бесплодных символов
Устранение ? -правил
Устранение цепных правил
15. КС-грамматики в нормальной форме
Грамматики в нормальной форме Хомского
Устранение левой рекурсии. Грамматики в нормальной форме Грейбах
16. Распознаватели КС-языков с возвратом
Принципы работы распознавателей с возвратом
Нисходящий распознаватель с возвратом
Распознаватель на основе алгоритма "сдвиг-свертка"
17. Табличные распознаватели для КС-языков
Общие принципы работы табличных распознавателей
Алгоритм Кока--Янгера--Касами
Алгоритм Эрли (основные принципы)
18. Принципы построения распознавателей КС-языков без возвратов
Классы КС-языков и грамматик
19. Нисходящие распознаватели КС-языков без возвратов
Левосторонний разбор по методу рекурсивного спуска
Определение LL(k)-грамматики
Принципы построения распознавателей для LL(k)-грамматик
Алгоритм разбора для LL(1)-грамматик
20. Восходящие распознаватели КС-языков без возвратов
Определение LR(k)-грамматики
|
|
|
Принципы построения распознавателей для LR(k)-грамматик
Грамматики предшествования (основные принципы)
Грамматики простого предшествования
Грамматики операторного предшествования
21. Соотношение классов КС-языков и КС-грамматик
Особенности восходящих и нисходящих распознавателей
Отношения между классами КС-грамматик
Отношения между классами КС-языков
Дата добавления: 2018-05-12; просмотров: 522; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!