Формальные языки и грамматики.
СПО
СПО— это программы и комплексы программ, являющиеся общими для всех, кто совместно использует технические средства компьютера и применяемые как для автоматизации и разработки новых программ, так и для организации программ существующих.
Жизненный цикл СПО включает:
1. разработка (основная):
1) определение требований;
2) проектирование (основная):
а) разделение программ на части;
б) определение формы организации данных;
в) определение возможности модификаций (в процессе
разработки и эксплуатации);
г) обеспечение надежности;
3) фаза компоновки;
4) тестирование;
5) документирование
2. применение;
3. сопровождение (продолж-ся разработки):
1) включение новых функций;
2) модификация функций;
3) модификация оборудования;
4) исправление ошибок
Классификация СПО
1. Операционные системы (ОС).
2. Системы программирования.
3. Утилиты.
Операционная система
ОС - набор программ, которые обеспечивают возможности использования аппаратуры компьютера.
ОС — администратор ресурсов.
ОС делятся: 1) по назначению: а) общего; б) специального;
2) по количеству пользователей одновременно обслуживаемых системой:
а) однопользовательские; б) многопользовательские;
3) по числу процессов, которые могут одновременно выполняться под управлением ОС: а) однозадачные б) многозадачные;
4) по типу средств вычислительной техники, для управления ресурсами которых предназначены: а) однопроцессорные; б) многопроцессорные;
|
|
|
в) сетевые; г) распределительные;
5) по архитектурному принципу: а) микроядерные; б) монолитные
Функции ОС:
1) определяет интерфейс пользователя;
2) принимает от пользователя задания и их обрабатывает;
3) принимает и использует программные запросы на запуск, приостановку и остановку других программ;
4) осуществляет загрузку в операционную память подлежащих использованию программ;
5) осуществляет инициализацию программ;
6) идентифицирует все программы и данные;
7) обеспечивает работу системы управления файлами;
8) обеспечивает работу многозадачного режима выполнения программ;
9) осуществляет распределение памяти и организацию виртуальной памяти;
10) осуществляет планирование и диспетчеризацию задач;
11) организует механизм обмена сообщениями и данными;
12) обеспечивает защиту одной программы от влияния другой и сохранность данных;
13) осуществляет восстановление и информации и вычислительного процесса;
14) обеспечивает работу системы программирования
Требования, предъявляемые к ОС:
1. надежность,
2. защита,
3. эффективность,
4. предсказуемость,
5. удобство
|
|
|
Структура ОС:
| Ур. | Имя | Объекты | Примеры операций |
| 1 | Электронные схемы | Регистры, вентили, шины и т.д. | Очистка регистра, чтение содержимого ячейки памяти |
| 2 | Системы команд | Стек для вычислений, микропроцессорный интерпретатор, массивы | Загрузка, запись, переход, сложение, вычитание |
| 3 | Подпрограммы | Подпрограммные сегменты и стек вызовов | Обращение к сегменту, вызов возврата |
| 4 | Прерывания | Программа обработки прерываний | Активировать, маскировать, демаскировать |
| 5 | Элементарные процессы | Семафоры, списки готовности, элементарные процессы | Прочесть, записать, выделить, освободить |
| 6 | Локальная внешняя память | Блоки данных, каналы устройств | Прочесть, записать, выделить, освободить |
| 7 | Виртуальная память | Сегменты памяти | Прочесть, записать, загрузит |
Поскольку элементарный процесс может быть прерван в любой момент, требуется специальный механизм обеспечивающий приостановку процесса и его последующее возобновление.
Этот механизм включает:
1) «словосостояние программы»
2) структура данных, в которые могут входить сведения о содержимом всех регистров центр процесса
3) операция переключения контекста.
Семафоры - средства синхронизации процессов.
|
|
|
До 7 уровня ОС имеет дело с ресурсами 1-го компьютера
| 8 | Коммуникации | Конвейеры | Создать, уничтожить, открыть, закрыть, прочесть, записать |
| 9 | Уровень файловой системы | Файлы | Создать, уничтожить, открыть, закрыть, прочесть, записать |
| 10 | Устройство | Внешние устройства | Создать, уничтожить, открыть, закрыть, прочесть, записать |
| 11 | Каталоги | Каталоги | Создать, уничтожить, срезать, открепить, найти, распечатать |
| 12 | Процессы пользователей | Процессы пользователей | Выйти, уничтожить, приостановить, возобновить |
| 13 | Оболочка | Программная среда пользователя | Оператор на языке оболочки |
Программы уровня 6 имеют дело с дисковой памятью терм-х дорожек и секторов
Программы уровня 9 работают с более абстрактными объектами.
Каждый каталог представляет собой список элементов, в которых указано внешнее имя и внутреннее имя, которое хранится в двоичном коде.
На 13 уровне работает интерпретатор командного языка высокого уровня. На этом же уровне находится программа «слушатель», которая:
1) проводит синтаксический анализ каждой вводимой строки;
2) создает и активирует процесс пользователя для каждой программы и связывает его с конвейерами, файлами и устройствами.
|
|
|
Основные принципы построения ОС:
1) принцип модульности;
2) принцип функциональной избирательности;
3) генерируемости;
4) функциональной избыточности;
5) виртуализации (планировщики);
6) независимости программ от внешних устройств;
7) совместимости;
8) открытости и наращиваемости;
9) мобильности или переносимости;
10) обеспечение безопасности вычислений
Системы программирования
СП объединяют программы, связанные с решением языковых проблем и предназначенные для разработки ПО.
В СП входят:
1) трансляторы;
2) библиотеки программ;
3) редакторы;
4) компоновщики;
5) загрузчики;
6) отладчики
Системы обслуживания программ (утилиты) — это специальные системные программы, с помощью которых можно обслуживать саму ОС
Транслятор — это программа, которая переводит входную программу на исходном языке в эквивалентную на выходном результирующем языке.
Компилятор — это транслятор, кот осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд.
Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и сразу её выполняет (нет результирующего кода)
Компилятор с точки зрения формальных языков выполняет 2 основные функции:
1) он является распознавателем для языка исходной программы (генератором цепочек является автор входной программы);
2) является генератором для языка результирующей программы (распознавателем является вычислительная система)
Основными фазами компиляции являются:
Лексический анализ — это часть компилятора, которая читает литеры программы и строит из них слова лексемы исходного языка.
Синтаксический анализ — это основная часть компилятора на этапе анализа. Выделяет синтаксические конструкции языка.
Семантический анализ — это часть компилятора, проверяет текст программы с точки зрения семантики исходного языка.
Подготовка к генерации кода — фаза, на которой выполняется предварительные действия, связанные с синтезом текста результирующей программы, но еще не ведущие к порождению текста на исходном языке.
Генерация кода — непосредственное порождение результирующего кода — основная фаза. Включает оптимизацию кода – процесс, связанный с обработкой уже порожденного текста.
Таблица идентификаторов — набор данных, служащий для хранения информации об элементах исходной программы, которые потом используются для порождения текста результирующей программы. Существует несколько таблиц идентификаторов.
Проход — это процесс последовательного чтения данных из внешней памяти, их обработка и помещение во внешнюю память. Одна фаза компиляции — один проход.
Таблица идентификаторов.
Таблица идентификаторов — набор данных, служащий для хранения информации об элементах исходной программы. Существует несколько таблиц идентификаторов.
Организация ТИ:В зависимости от идентификатора может храниться различная информация:
1) Переменная – имя, тип, адрес
2) Константа – имя, если есть, адрес, значение;
3) Функция – количество аргументов, тип, имя, адрес
ТИ создается на фазе лексического анализа и заполняется последовательно. На фазе лексического анализа записываются типы идентификаторов. На фазе подготовки генерации кода — выделение памяти.
Основным критерием выбора способа организации ТИ является время поиска нужного элемента, т.к. основными функциями являются добавление и поиск (поиск происходит чаще)
1. Неупорядоченный список — в ТИ добавляются элементы в порядке поступления
(+) простота реализации
(–) непродуктивен при большом количестве элементов
2. Упорядоченный список — все элементы в ТИ упорядочены согласно естественному порядку по убыванию и возрастанию.
(+) сокращение времени поиска необходимого элемента
(–) требует упорядочить ТИ
3. Бинарное дерево ТИ имеет форму бинарного дерева. Каждый элемент или вершина — идентификатор. Корневой вершиной дерева является первый поступивший идентификатор.
Форма бинарного дерева зависит от порядка поступивших идентификаторов. Недостаток — дерево может выродиться в упорядоченный список.
КЭШ адресация
Согласно данному методу символ преобразуются в индекс элемента в массиве.
Кэширование — выполнение любых логических или арифметических операций над символом.
КЭШ адресация заключается в использовании значения возвращаемого КЭШ-функцией в качестве адреса ячейки из некоторого массива данных.
Размер массива данных должен соответствовать области значения КЭШ-функции.
Достоинства – эффективен, т.к. время поиска и время размещения — определяется только временем, затрачиваемым на вычисление КЭШ-функции.
Недостатки:
1) неэффективное использование объема памяти;
2) необходимость соответствующего разумного выбора КЭШ функции.
Коллизия— это ситуация, когда двум различным идентификаторам соответствует одно и то же значение КЭШ функции.
Способы разрешения коллизии (рекэширование).При возникновении коллизии вычисляется новое значение КЭШ-функции.
Формула рекэширования
hi(A)=(h(A)+pi)modNm,
Nm - максимальное значение из области кэширования,
pi – некоторое вычисл. целое число
А – идентификатор
h(A) – КЭШ-функция
hi(A) – новая КЭШ-функция
Метод простого рекэшированияhi(A)=(h(A)+i)modNm (вместо pi берем i)
(+) эффективен при неполном заполнении таблицы
(-) при совпадении КЭШ-адресов элементы в таблице начинают группироваться вокруг них, что
увеличивает число необходимых сравнений при поиске и размещении
Рекэширование с использованием псевдослучайных чисел (вместо pi берем последовательность целых псевдослучайных чисел р1, р2,р3…рn).
Метод цепочек
Здесь к ТИ добавляется дополненная КЭШ-таблица, в которой хранится либо пустое значение, либо значение указателя на некоторую область памяти из основной ТИ.
Достоинства:
1) нет необходимости заполнять пустыми значениями ТИ;
2) каждому идентификатору соответствует строго одна ячейка в ТИ, поскольку в ней нет пустых неиспользуемых ячеек.
В ТИ добавляется поле ссылки, в котором может содержаться указатель на любой элемент ТИ.
используется специальная переменная, которая всегда указывает на первую свободную ячейку основной ТИ.
Комбинированные методы. Используется дополнительное поле ссылки:
если коллизии не возникает, для выборки информации используется КЭШ-функция и поле ссылки остается пустым. если коллизия возникает, то через поле ссылки организуется поиск идентификаторов по одному из рассмотренных выше методов.
(+) Преимущество над цепочками: для хранения идентификаторов с совпадающими значениями КЭШ-функции используется область памяти не пересекающаяся с основной ТИ.
(-) Недостаток: необходимость работы с динамически распределенными областями памяти.
Формальные языки и грамматики.
Цепочки символов (строка) и операции над ними.
Цепочки символов — это произвольная последовательность символов, записанных один за другим.
Для ЦС важен состав, количество символов и порядок.
ЦС α и β равны α=β или совпадают, если они имеют один и тот же состав символов, одно и то же их количество, одинаковый порядок следования символов в цепочке.
Количество символов в цепочке называется длиной цепочки.
ЦС обладают следующими свойствами:
1. Конкатенация — объединение или сложение 2-х цепочек αβ
α=“BA”
β=“CL” => αβ=“BACL”
Операция конкатенации не обладает свойством коммут-ти αβ≠βα.
Обладает свойством ассоциативности (αβ)γ=α(βγ)
2. Обращение цепочки — запись символов цепочки в обратном порядке αR, α=“ВАСЯ” => αR=“ЯСАВ”
Для данной операции справедливо (αβ)R=αRβR
3. Итерация — повторение цепочки n раз
4.Пустая цепочка символов — это цепочка, не содержащая ни одного символа — λ для пустой цепочки справедливо:
1) |λ|=0;
2) для любого α: λα=αλ=α;
3) λR=λ;
4) для любого n≥0:λn=λ;
5) для любого α: α0=λ
Понятие языка
Язык — это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов.
Алфавит — счетное множество допустимых символов языка — V.
Цепочка символов α является цепочкой над алфавитом α(V), если в неё входят только символы принадлежащие множеству символов V.
V+ - множество всех цепочек над алфавитом V без λ
V* - множество всех цепочек над алфавитом с λ
V*=V+U{λ}
Язык L над алфавитом V — L(V) это некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V.
Цепочку символов, принадлежащую заданному языку, называют предложением.
Язык можно задать 3 способами:
1.перечисление всех допустимых цепочек;
2. указание способа порождения предложений языка(грамматика);
3. определение метода распознавания языка(распознаватель, автомат)
Лексика — совокупность слов (слов запас)
Синтаксис — набор правил, определяющий допустимые конструкции языка (определяет форму языка)
Семантика — раздел языка, определяющий значение предложений языка (определяет содержание языка)
Часто формальные языки лишены смысла. Языки программирования занимают некоторое промежуточное положение между формальными (знаки) и естественными (слова) языками
Для задания языка программирования необходимо решить след задачи:
1) определить допустимое множество символов языка;
2) определить множество правильных программ языка;
3) задать смысл для каждой правильной программы
Грамматика языка.
Грамматика — это описание способа построения предложений некоторого языка.
Правило или продукция — это упорядоченная пара цепочек символов (α,β),
в правилах важен порядок цепочек (α→β α порождает β).
Язык заданной грамматикой G=L(G).
Грамматика определяется четверкой: G(VT,VN,P,S),где
VT- множество терминальных символов,
VN - множество нетерминальных символов,
P - множество правил,
S-целевой символ грамматики.
Рекурсия выражается в том, что 1 из нетерминальных символов определяется сам через себя. Рекурсия может быть явной и не явной.
Дата добавления: 2018-05-31; просмотров: 433; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!