- •Системное программное обеспечение
- •Разд. 1. Операционные системы и среды
- •Тема 1.1. Структура программного обеспечения вычислительной системы
- •Тема 1.2 Назначение, функции и структура операционной системы
- •1.2.1 Типы ос. Системы реального времени и операционные системы реального времени
- •Тема 1.3. Управление временем центрального процессора
- •Рекомендуется всегда проверять возвращаемое значение Res. Получение и использование процессом ссылок на себя
- •Использование потоков при разработке приложений
- •1.3.3 Синхронизация взаимодействующих потоков
- •Interlocked – функции.
- •Семафорные примитивы Дейкстры
- •Решение проблемы критических участков с помощью семафорных примитивов Дейкстры
- •1.3.4 Синхронизации потоков средствами операционной системы
- •Пример 2
- •Пример 3 Поток_1 Поток_2
- •1.3.5. Проблема тупиков и методы борьбы с тупиками
- •Взаимного исключения, при котором процессы имеют монопольный доступ к ресурсам;
- •Ожидания, при котором процесс, запрашивающий ресурс, ждет до тех пор, пока запрос не будет удовлетворен, удерживая ранее полученные ресурсы;
- •Методы борьбы с тупиками
- •Тема 1.4 Управление памятью
- •Защищенный режим процессоров Intel и его возможности
- •1.4.2. Реализация многозадачного режима в защищенном режиме процессоров фирмы Intel
- •Аппаратная поддержка многозадачности
- •Обработка прерываний в реальном режиме. Вектора прерываний.
- •Режимы работы мп 386
- •Системный режим
- •Особенности s – режима.
- •Организация виртуальной памяти
- •Управление страничной памятью в ос ms Windows
- •Линейный адрес
- •1.4.4. Разделы в виртуальном адресном пространстве процесса
- •Области применения dll
- •Основные dll ms Windows:
- •Создание dll
- •Использование dll (импорт функций из dll)
- •Неявная загрузка dll (неявное подключение)
- •Явная загрузка dll
- •Выполнение процедур инициализации и деинициализации Dll
- •Тема 1.6 Структура ms Windows и драйверы режима ядра
- •Тема 1.7 Управление вводом-выводом и файловые системы Win32
- •Эволюция файловых систем эвм
- •Раздел 2. Программирование в операционной среде
- •Тема 2.1. Ассемблеры и макроязыки
- •2.1.1. Этапы подготовки программы к выполнению
- •Операнды команд
- •Алгоритмы работы Ассемблеров
- •Двухпроходный Ассемблер - 1-й проход
- •2.1.2. Макроязыки
- •Заголовок макроопределения
- •Окончание макроопределения
- •Локальные переменные макроопределения
- •Присваивание значений переменным макроопределения
- •Оператор безусловного перехода и метки макроопределения
- •Тема 2.2.Трансляторы
- •2.3.1. Трансляторы. Компиляторы и интерпретаторы. Мобильность программного обеспечения
- •Тема 2.3 Формальные языки и грамматики
- •Синтаксический и лексический анализатор
- •Детерминированные и недетерминированные автоматы
- •Алгоритм синтаксического анализа
- •Пример 1
- •Пример 2
Синтаксический и лексический анализатор
Одной из особенностей такого подхода к разбору строк является то, что анализ выполняется по мере считывания символов, с использованием информации о текущем символе и символах, прочитанных ранее. Синтаксический анализатор — это программа или часть программы, выполняющая синтаксический анализ, на первом шаге которого выполняется лексический анализ, далее строится дерево разбора. Синтаксический анализатор входит в структуру транслятора. Конструкции, распознаваемые лексическим анализатором описываются автоматной грамматикой и регулярными выражениями. На первом этапе лексического анализа происходит построение конечного автомата по регулярному выражению, затем строится таблица переходов для конечного автомата, а далее входной поток символов интерпретируется анализатором в выходной поток лексем. Определим понятие конечного автомата.
Конечным автоматом-распознавателем называется следующий набор объектов А={S,X,So,δ,F}, где:
S – конечное непустое множество состояний
Х – конечное непустое множество входных сигналов(входной алфавит)
So – начальное состояние
δ:S*X→S – функция переходов
F – множество заключительных состояний
Конечный автомат-распознаватель А допускает входную цепочку α, принадлежащую алфавиту, если α переводит его из начального в одно из заключительных состояний.
Регулярные множества и автоматные языки
Рассмотрим класс множеств цепочек над конечным словарем. Эти множества называются регулярными. Пусть V1,V2 – множества цепочек.Тогда операции над этими множествами:
V1 U V2 (операция объединения);
V1V2 (операция конкатенации или склеивания);
V*=V0 U V1 U V2 U… (итерация);
Класс регулярных выражений над конечным словарем:
Ǿ и ε
{a} для любого а из V
если R1 ,R2 регулярные, то:
R1+R2;
R1R2;
R1*,R2* ;
Регулярное выражение – это конечная формула, схематично показывающая,как было построено соответствующее ей регулярное множество с помощью перечисленных операций, задающая бесконечное множество цепочек, т.е. язык.
Построение автомата по заданной грамматике
Теорема Клини: Классы регулярных множеств и автоматных языков совпадают.
Детерминированные и недетерминированные автоматы
Важным аспектом является преобразование недетерминированного конечного автомата к детерминированному. Недетерминированные конечноавтоматные распознаватели могут быть двух типов: либо существует переход, помеченный пустой цепочкой ε, либо из одного состояния выходят несколько переходов, помеченных одним и тем же символом (возможны оба случая).
Теорема 3: Для любого недетерминированного конечноавтоматного распознавателя существует эквивалентный ему детерминированный.
Алгоритм построения эквивалентного детерминированного конечного автомата.
Приведение недетерминированного автомата к автомату без ε-переходов.
Определение: ε-замыканием состояния s называется множество всех состояний, которые достижимы из s без подачи входного сигнала. Множеством состояний полученного автомата являются ε-замыкания состояний автомата с ε-переходами.
Построение по полученному автомату без ε-переходов эквивалентного ему детерминированного автомата, допускающего тот же язык. В качестве начального (конечного) состояния искомого автомата выбрать множество начальных(конечных) состояний исходного автомата.
