- •Змістовий модуль 1
- •Не 1.1. Структура системного програмного забезпечення Структура спз.
- •Місце ос в спз.
- •Поняття операційного середовища.
- •Операційні системи.
- •Системи керування файлами.
- •Інтерфейсні оболонки для взаємодії користувача з ос і програмні середовища.
- •Системи програмування.
- •Утиліти.
- •Основні функції ос.
- •Не 1.1. Базові поняття сучасних операційних систем Базові поняття операційної системи Linux. Файли, каталоги, робота з файлами. Права доступу до файлів і каталогів.Інструментарій.
- •Програми-фільтри. (немає) Командний інтерпретатор.
- •Змістовий модуль 2
- •Не 2.1. Загальна схема роботи компіляторів Визначення транслятора, компілятора, інтерпретатора.
- •Компілятор.
- •Різниця між інтерпретаторами і трансляторами.
- •Етапи трансляції.
- •Поняття проходу. Багатопрохідні і однопрохідні компілятори.
- •Не 2.2. Таблиці ідентифікаторів. Призначення та особливості побудови таблиць ідентифікаторів.
- •Найпростіші методики побудови таблиць ідентифікаторів.
- •Побудова таблиць ідентифікаторів методом бінарного дерева.
- •Не 2.3 Хеш-функції та хеш–адресація. Принципи роботи хеш-функцій.
- •Побудова таблиць ідентифікаторів на основі хеш-функцій.
- •Побудова таблиць ідентифікаторів методом ланцюжка.
- •Комбіновані способи побудови таблиць ідентифікаторів.
- •Змістовий модуль 3. Не 3.1.Кінцеві автомати. Визначення.
- •Детерміновані і недетерміновані кінцеві автомати.
- •Модель ка.
- •Розпізнавачі і перетворювачі. Визначення. Загальні поняття.
- •Класифікація розпізнавачів.
- •Не 3.2.Формальні мови та граматики. Способи завдання мов.
- •Операції над ланцюжками символів.(немає) Поняття мови.
- •Визначення формальної мови.
- •Визначення грамматики.
- •Класифікація граматик.
- •Способи задання схем грамтик Символічна, форма Наура-Бекуса, ітераційна форма й синтаксичні діаграми.
- •Чотири типи граматик по Хомському.
- •Правила побудови граматики із ланцюжка символів. (немає)
- •Змістовий модуль 4.
- •Не 4.1 Лексичні аналізатори (сканери).
- •Принципи побудови сканерів.
- •Призначення лексичного аналізатору.
- •Принципи побудови лексичних аналізаторів.
- •Граф кінцевого детермінованого автомата, що розпізнає граматику цілих чисел мови Сі(Немає) не 4.2.Синтаксичний та семантичний аналіз. Синтаксично-керований переклад.
- •Основні принципи роботи синтаксичних аналізаторів.
- •Дерево розбору. Перетворення дерева розбору в дерево операцій.
- •Призначення семантичного аналізу.
- •Етапи семантичного аналізу.
- •Ідентифікація лексичних одиниць мов програмування.
- •Розподіл пам’яті.
- •Не 4.3. Способи внутрішнього представлення програм Зв'язані облікові структури, що представляють синтаксичні дерева.
- •Багатоадресний код з явно іменованим результатом (тетради).
- •Багатоадресний код з неявно іменованим результатом (тріади).
- •Обернений (постфиксна) польський запис операцій.
- •Алгоритм Дейкстри.
- •Асемблерний код або машинні команди.
- •Розбір арифметичного виразу. Алгоритм Рутисхаузера.
- •Не 4.4 Генерація коду. Методи генерації коду.
- •Загальні принципи генерації коду.
- •Синтаксично керований переклад.
- •Змістовий модуль 5
- •Не 5.1. Керування процесами та ресурсами. Поняття обчислювального процесу та ресурсу.
- •Класифікація ресурсів.
- •Загальна схема виділення ресурсу.
- •Однопрограмний і мультипрограмний режими.
- •Основні риси мультипрограмного режиму.
- •Обчислювальні процеси.
- •Діаграма станів процесу.
- •Реалізація поняття послідовного процессу в ос.
- •Процеси і треди. (немає) Блок керування процесом.
- •Процеси в ос unix.
- •Події (переривання) - рушійна сила, що змінює стан процесів.
- •Механізм обробки переривань.
- •Функції механізму переривань.
- •Групи переривань.
- •Розподіл переривань по рівнях пріоритету.
- •Дисципліни обслуговування переривань.
- •Обробка переривань за участю супервізорів ос.
- •Не 5.2. Планування процесів та диспетчеризація задач. Функції ос, пов’язані з керуванням задач.
- •Організація черг процесів та ресурсів.
- •Priority queuing - (pq)
- •Стратегії планування.
- •Якість диспетчеризації та гарантії обслуговування.(Немає)
- •Безпріоритетні до: лінійні та циклічні.
- •Пріоритетні до: до з фіксованим пріоритетом та до з абсолютним пріоритетом.
- •Адаптивні до. (Немає) Визначення середнього часу знаходження заявки в системі. (Немає) Недоліки до з фіксованим пріоритетом.
- •Динамічне планування (диспетчеризація). (Немає) Диспетчеризація задач з використанням динамічних пріоритетів. Переваги і недоліки.
- •Критерії ефективності обчислювального процесу. (Немає) Методи підвищення продуктивності системи для багатопроцесорних систем.
- •Механізм динамічних пріоритетів в ос unix.
- •Змістовий модуль 6
- •Не 6.4. Керування пам’яттю. Пам'ять і відображення, віртуальний адресний простір.
- •Простий безперервний розподіл і розподіл з перекриттям (оверлейні структури).
- •Розподіл статичними і динамічними розділами.
- •Розділи з фіксованими границями. Розділи з рухливими границями.
- •Виділення пам'яті під новий розділ: перша придатна ділянка; сама придатна ділянка; сама невідповідна ділянка.
- •Сегментна, сторінкова і сегментно-сторінкова організація пам'яті. Сегментний спосіб організації віртуальної пам'яті.
- •Дисципліни заміщення: fifo; lru (1еаst recently used,); lfu (1еаst frequently used); random.
- •Сторінковий спосіб організації віртуальної пам'яті.
- •Сегментно-сторінковий спосіб організації віртуальної пам'яті.
- •Змістовий модуль 7
- •Не 7.1. Ос однопроцесорних кс. Класифікація ос.
- •Режими організації обчислювального процесу. (Немає) Основні принципи побудови операційних систем.
- •Принцип модульності.
- •Принцип функціональної вибірковості.
- •Принцип генерування ос.
- •Принцип відкритої і нарощуваний ос.
- •Принцип мобільності.
- •Принцип забезпечення безпеки обчислень.
Дерево розбору. Перетворення дерева розбору в дерево операцій.
Результатом роботи розпізнавача КС-граматики вхідної мови є послідовність правил граматики, застосованих для побудови вхідний ланцюжка. За знайденою послідовності, знаючи тип розпізнавача, можна побудувати ланцюжок виводу або дерево виводу. У цьому випадку дерево виведення виступає в якості дерева синтаксичного розбору і являє собою результат роботи синтаксичного аналізатора в компіляторі.
Проте ні ланцюжок виводу, ані дерево синтаксичного розбору не є метою роботи компілятора. Дерево висновку містить масу надлишкової інформації, яка для подальшої роботи компілятора не потрібно. Ця інформація включає в себе всі нетермінальні символи, які містяться і вузлах дерева, - після того, як дерево побудовано, вони не несуть ніякого смислового навантаження і не несуть для подальшої роботи інтересу.
Для повного уявлення про тип і структурі знайденої і розібраної синтаксичної конструкції вхідного мови в принципі достатньо знати послідовність номерів правил граматики, застосованих для її побудови. Однак форма подання цієї достатньої інформації може бути різною як залежно від реалізації самого компілятора, так від фази компіляції. Ця форма напивається внутрішнім поданням програми.
У синтаксичному дереві внутрішні вузли (вершини) відповідають операціям, а листя представляють собою операнди. Як правило, листя синтаксичного Дерена зляпати з записами в таблиці ідентифікаторів. Структура синтаксичного дерева відображає синтаксис мови програмування, на якому наш капа вихідна програма.
Синтаксичні дерева можуть бути побудовані компілятором для будь-якої частини вхідної програми. Не завжди синтаксичному дереву повинен відповідати фрагмент коду результуючої програми - наприклад, можлива побудова синтаксичних дерев для декларативної частини мови. У цьому випадку операції, наявні в дереві, не вимагають породження об'єктного коду, але несуть інформацію про дії, які повинен виконати сам компілятор над відповідними елементами. У тому випадку, коли синтаксичному дереву відповідає деяка послідовність операцій, що тягне породження фрагмента об'єктного коду, говорять про дерево операцій.
Дерево операцій можна безпосередньо побудувати з дерева виведення, породженого синтаксичним аналізатором. Для цього достатньо виключити з дерева виведення ланцюжка нетермінальних символів, а також вузли, що не несуть семантичного навантаження при генерації коду. Прикладом таких вузлів можуть бути різні дужки, які змінюють порядок виконання операції і операторів, але після побудови дерева ніякого смислового навантаження не несуть, гак яким не відповідає ніякий об'єктним код.
Те, який вузол в дерен є операцією, а який - операндом, ніяк неможливо визначити з граматики, яка описує синтаксис вхідного мови. Також нізвідки не випливає, яких операціях повинен відповідати об'єктний код в результуючій програмі, а яким - ні. Все це визначається тільки виходячи з семантики - «сенсу» - мови вхідної програми. Тому тільки розробник компілятора може чітко визначити, як при побудові дерева операції повинні відрізнятися операнди і самі операції, а також те, які операції є семантично незначущими для породження об'єктного коду.
Алгоритм перетворення дерева семантичного розбору і дерево операції можна уявити наступним чином.
Крок 1. Якщо у дереві більше не міститься вузлів, помічених нетермінальним символами, то виконання алгоритму завершено; інакше - перейти до кроку 2
Крок. 2. Вибрати крайній лівий вузол Дерена, позначений нетермінальним символом граматики і зробити його поточним. Перейти до кроку 3.
Крок 3. Якщо поточний вузол має тільки один нижележащий вузол, то поточний вузол необхідно видалити з Дерена, а пов'язаний з ним вузол приєднати до вузла вищого рівня (виключити з Дерена ланцюжок) і повернутися до кроку 1; інакше - перейти до кроку 4.
Крок 4. Якщо поточний вузол має нижележащий вузол (лист дерева), позначений термінальним символом, який не несе семантичного навантаження, тоді цей лист потрібно видалити з дерева і повернутися до кроку 3, інакше - перейти до кроку 5.
Крок 5. Якщо поточний вузол має один нижележащий вузол (лист дерева), позначений термінальним символом, що позначає знак операції, а інші вузли позначені як операнди, то лист, позначений знаком операції, треба видалити з дерева, поточний вузол позначити цим знаком операції і перейти до кроку 1; інакше - перейти до кроку 6.
Крок 6. Якщо серед нижчих вузлів для поточного вузла є вузли, помічені нетермінальним символами граматики, то необхідно вибрати крайній лівий серед цих вузлів, зробити його поточним розумом і перейти до кроку 3: інакше - виконання алгоритму завершено.