- •Введение
- •1. Основные понятия системного программного обеспечения
- •1.1. Понятия прикладного и системного программного обеспечения
- •1.2. Состав системного программного обеспечения
- •2. Состав и архитектура операционных систем
- •2.1. Состав операционных систем
- •2.2. Архитектура ос
- •3. Процессы и потоки
- •3.1. Концепция процессов и потоков
- •3.2. Многозадачность. Формы программной работы
- •3.3. Подсистема управления процессами и потоками
- •3.4. Роль процессов, потоков и волокон в многозадачности
- •3.5. Создание процессов
- •3.6. Потоки и их модели
- •3.7. Планирование и синхронизация процессов и потоков
- •3.7.1. Виды планирования
- •3.7.2. Алгоритмы планирования потоков
- •3.7.3. Алгоритмы приоритетного планирования
- •3.7.4. Взаимоисключения
- •3.7.5. Семафоры
- •3.7.6. Тупики
- •4. Управление памятью
- •4.1. Функции ос по управлению памятью
- •4.2. Классификация методов распределения памяти
- •4.3. Распределение памяти без использования внешней памяти
- •4.4. Методы структуризации виртуальной памяти
- •4.4.1. Страничная организация виртуальной памяти
- •4.4.2. Сегментная организация виртуальной памяти
- •4.4.3. Странично-сегментная организация памяти
- •5. Файловые системы
- •5.1. Цели и задачи файловой системы
- •5.2. Организация файлов и доступ к ним
- •5.3. Логическая организация файла
- •5.4. Каталоговые системы
- •5.5. Основные возможности файловой системы ntfs
- •5.6. Структура тома с файловой системой ntfs
- •5.7. Возможности ntfs по ограничению доступа к файлам и каталогам
- •6. Управление вводом-выводом
- •6.1. Физическая организация устройств ввода-вывода
- •6.2. Организация программного обеспечения ввода-вывода
- •6.3. Обработка прерываний
- •6.4. Драйверы устройств
- •6.5. Независимый от устройств слой ос
- •6.6. Пользовательский слой программного обеспечения
- •7. Построение операционных систем
- •7.1. Принципы построения операционных систем
- •7.1.1. Принцип модульности
- •7.1.2. Принцип функциональной избирательности
- •7.1.3. Принцип генерируемости ос
- •7.1.4. Принцип функциональной избыточности
- •7.1.5. Принцип виртуализации
- •7.1.6. Принцип независимости программ от внешних устройств
- •7.1.7. Принцип совместимости
- •7.1.8. Принцип открытой и наращиваемой ос
- •7.1.9. Принцип мобильности
- •7.1.10. Принцип обеспечения безопасности вычислений
- •7.2. Построение интерфейсов операционных систем
- •7.3. Интерфейс прикладного программирования
- •7.3.1. Реализация функций api на уровне ос
- •7.3.2. Реализация функций api на уровне системы программирования
- •7.3.3. Реализация функций api с помощью внешних библиотек
- •7.4. Классификация системных вызовов
- •7.5. Интерфейс пользователя
- •7.6. Пользовательский интерфейс приложений
- •7.7. Архитектура, управляемая событиями
- •8. Семейство операционных систем unix
- •8.1. Основные понятия системы unix
- •8.1.1. Виртуальная машина
- •8.1.2. Пользователь
- •8.1.3. Интерфейс пользователя
- •8.1.4. Привилегированный пользователь
- •8.1.5. Команды
- •8.1.6. Процессы
- •8.1.7. Выполнение процессов
- •8.1.8. Структура файловой системы
- •8.2. Операционная система Linux
- •9.1.2. Определение компилятора. Отличие компилятора от транслятора
- •9.1.3. Определение интерпретатора. Разница между интерпретаторами и трансляторами
- •9.1.4. Этапы трансляции. Общая схема работы транслятора
- •9.1.5. Понятие прохода. Многопроходные и однопроходные компиляторы
- •9.2. Таблицы идентификаторов. Организация таблиц идентификаторов
- •9.2.1. Назначение таблиц идентификаторов
- •9.2.2. Принципы организации таблиц идентификаторов
- •9.2.3. Простейшие методы построения таблиц идентификаторов
- •9.2.4. Построение таблиц идентификаторов по методу бинарного дерева
- •9.2.8. Комбинированные способы построения таблиц идентификаторов
- •9.3. Лексические анализаторы
- •9.3.1. Назначение лексического анализатора
- •9.3.2. Принципы построения лексических анализаторов
- •9.3.3. Определение границ лексем
- •9.3.4. Выполнение действий, связанных с лексемами
- •9.4. Формальные языки и грамматики
- •9.4.1. Первичные понятия
- •9.4.2. Примеры, иллюстрирующие первичные понятия
- •9.4.3. Типы формальных языков и грамматик
- •9.4.3.1. Грамматики типа 0
- •9.4.3.2. Грамматики типа 1
- •9.4.3.3. Грамматики типа 2
- •9.4.3.4. Грамматики типа 3
- •9.4.3.5. Вывод в кс-грамматиках и правила построения дерева вывода
- •9.4.3.6. Синтаксический разбор
- •9.4.3.7. Левый и правый выводы
- •9.4.3.8. Неоднозначные и эквивалентные грамматики
- •9.4.4. Способы задания схем грамматик
- •9.4.4.1. Форма Наура-Бэкуса
- •9.4.4.2. Итерационная форма
- •9.4.4.3. Синтаксические диаграммы
- •9.4.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
- •9.4.5.1. Рекомендации по построению грамматик
- •9.4.5.2. Описание списков
- •9.4.5.3. Пример построения грамматик
- •9.4.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
- •9.4.5.5. Грамматики для арифметических выражений
- •9.4.5.6. Грамматика для описаний
- •9.4.5.7. Грамматика, задающая последовательность операторов присваивания
- •9.4.5.8. Грамматики, описывающие условные операторы и операторы цикла
- •9.4.5.9. Бесскобочные выражения
- •9.4.5.10. Префиксная польская запись
- •9.4.5.11. Вычисление префиксных польских записей
- •9.4.5.12. Постфиксная польская запись
- •9.4.5.13. Вычисление постфиксных записей
- •9.5. Конечные автоматы и регулярные грамматики
- •9.6. Макроязыки и макрогенерация
- •9.6.1. Определения макрокоманд и макрогенерации
- •9.6.2. Примеры макрокоманд
- •9.6.3. Макроязыки и препроцессоры
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
9.4.2. Примеры, иллюстрирующие первичные понятия
Рассмотрим несколько примеров, иллюстрирующих введенные понятия:
а) Задана грамматика Г1. 0 и требуется определить язык, порождаемый этой грамматикой:
Г1. 0: Vт = {a, b, c}, Va = {<I>}, R = {<I> abc}.
Схема грамматики содержит одно правило, поэтому Г1. 0 порождает язык из одного слова
L(Г1. 0) = {abc}.
б) Задана грамматика Г1. 1 и требуется определить язык, порождаемый этой грамматикой .
Г1. 1 : Vт = {a, b, c}, Va = {<I>, <B>, <C>}
R = { <I> a<B>,
<B> <C>d,
<B> dc,
<C> $}.
Построим все выводы в этой грамматике:
<I> a<B> a<C>d ad,
<I> a<B> adc.
Следовательно язык L(Г1. 1) = {adc, ad}.
в) Задана грамматика Г1. 2 и требуется определить язык, порождаемый этой грамматикой .
Г1. 2 : Va = {<I>, <A>}, Vт = {0, 1},
R = {<I> 0<A>1,
0<A> 00<A>1,
<A> $}.
Рассмотрим несколько выводов с помощью правил грамматики Г1. 2. Применяя первое и третье правила, получаем:
<I> 0<A>1 01.
Применяя два раза первое правило и третье, имеем
<I> 0<A>1 00<A>11 0011.
В общем случае, применяя K раз первое правило, получим в результате цепочку, содержащую K нулей и K единиц.
Следовательно, язык, порождаемый грамматикой Г1. 2, содержит всевозможные цепочки, в которых число нулей равно числу единиц.
г) Задана грамматика Г1. 3 и требуется построить язык, порождаемый этой грамматикой.
Г1. 3 : Vт = {a, b}, Va = {<I>, <A>},
R = { <I> a<A>,
<A> b<A>}.
Попытка построения вывода в этой грамматике приводит нас к цепочке:
<I> a<A> ab<A> abb<A> ... ,
которая оказывается бесконечной. Другими словами, Г1. 3 порождает пустой язык.
9.4.3. Типы формальных языков и грамматик
В теории формальных языков выделяются 4 типа грамматик, которым соответствуют 4 типа языков. Эти грамматики выделяются путем наложения усиливающихся ограничений на правила грамматики.
9.4.3.1. Грамматики типа 0
Грамматики типа 0, которые называют грамматиками общего вида, не имеют никаких ограничений на правила порождения. Любое правило
r =
может быть построено с использованием произвольных цепочек (Vт Va)*. Например,
<T><W> <W><T>
или
x<A>b<C><D> x<H><D>.
9.4.3.2. Грамматики типа 1
Грамматики типа 1, которые называют также контекстно-зависимыми грамматиками, не допускают использования любых правил.
Правила вывода в таких грамматиках должны иметь вид:
1<A>2 12, где
- 1,2 - цепочки, возможно пустые, из множества (Vт Va)*,
- символ <А> Va ,
- цепочка w (Vт Va)*.
Цепочки 1 и2 остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику – контекстно зависимой.
Грамматики типа 1 значительно удобнее на практике, чем грамматики типа 0, поскольку в левой части правила заменяется всегда один нетерминальный символ, который можно связать с некоторым синтаксическим понятием, в то время как в грамматике типа 0 можно заменять сразу несколько символов, в том числе и терминальных.
Например, грамматика:
Г1. 4:
Vт = {a, b, c, d}, Va = {<I>, <A>, <B>}
R = { <I> aA<I>,
A<I> AA<I>,
AAA A<B>A,
A b,
b<B>A bcdA,
b<I> ba }
является контекстно-зависимой, поскольку второе и шестое правила имеют непустой левый контекст, а третье и пятое правила содержат оба контекста.
Вывод в такой грамматике может иметь вид:
<I> a<A><I> a<A><A><I> ab<A><I> abb<I> abba.