- •Системное программное обеспечение
- •Разд. 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
Алгоритм синтаксического анализа
На входе алгоритма дан конечный автомат, заданный либо диаграммой переходов, представляющей собой граф автомата, либо таблицей переходов. В нем кодируется информация о возможных последовательностях цепочек, которые будут распознаваться синтаксическим анализатором.
Все эти цепочки представляют собой регулярные выражения, поскольку по теореме Клини класс языков, распознаваемых автоматом, и класс регулярных множеств совпадают.
Сканирование (из исходного текста строятся лексемы, реализуется в виде конечного автомата)
построение эквивалентного детерминированного автомата (поскольку по теореме для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный).(Шаг 1).
строится таблица переходов для полученного конечного автомата.(Шаг 2).
поток символов интерпретируется в выходной поток лексем (обработка потока символов в соответствии с заданной автоматной грамматикой).(Шаг 3).
Оценка (конструируются токены, проход по символам лексемы для получения значения токена).(Шаг 4).
Построение дерева разбора (результат синтаксического анализа).(Шаг 5).
Рассмотрим работу алгоритма на двух примерах.
Пример 1
Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 1.
Конечный автомат в Примере 1 распознает цепочки языка (а+bb)(a+b)*. Это недетерминированный конечный автомат. Построим для него эквивалентный автомат без ε-переходов,заменив состояния автомата ε-замыканием.
Таблица переходов для эквивалентного детерминированного автомата.
|
a |
b |
po={qo;q1} |
p2 |
p1 |
p1={q2} |
|
p2 |
p2={q2;q3} |
p3 |
p2 |
p3={qo;q1;q2;q3} |
p3 |
p2 |
(Шаг
1 + Шаг 2).
Построим автоматную грамматику для языка из Примера 1.(Шаг 3).
Po->bP1|aP2; P2->bP2|aP3; P3->bP2|aP3; P1->bP2
Рассмотрим пример вывода цепочки bbab: (Шаг 4). Po->bP1->bbP2->bbaP3->bbabP2.
Построение дерева вывода цепочки автоматного языка выполняется сверху вниз. Корень дерева помечается начальным состоянием Ро. Если в исходной грамматике построить соответствующий детерминированный конечный автомат, то символ, помечающий каждый следующий узел, совпадает с меткой состояния, в которое переходит автомат на очередном шаге.
(Шаг
5).
Пример 2
Рассмотрим пример построения по синтаксической диаграмме детерминированного конечного автомата. Конечный автомат в Примере 2 распознает цепочки языка b+(а+bb)(b+ab)*a. Синтаксическая диаграмма для данного автомата представлена на рисунке.
Построим детерминированный конечный автомат по алгоритму, описанному выше.
Эквивалентный автомат без ε-переходов.
Таблица переходов для эквивалентного автомата из Примера 2.
|
a |
b |
p1{1} |
p3 |
p2 |
p2{2;6} |
|
p3 |
p3{3;4;7} |
p2 |
p3 |
Эквивалентный
детерминированный автомат. (Шаг 1 + Шаг
2).
Построим автоматную грамматику для языка из Примера 2.(Шаг 3).
P1->bP2|aP3; P2->bP3; P3->bP3|aP2;
Рассмотрим пример вывода цепочки bbab:(Шаг 4). P1->bP2->bbP3->bbaP2->bbabP3.
Построение дерева разбора для цепочки bbab, распознаваемой автоматом Приме
ра 2. (Шаг 5)
.
