РЫБИНСКАЯ ГОСУДАРСТВЕННАЯ АВИАЦИОННАЯ
ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ
ИМЕНИ П. А. СОЛОВЬЕВА
Л. В. ТОНКИЙ
СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
КУРС ЛЕКЦИЙ
Часть 1
РЫБИНСК
2010
УДК 681.3.06
Тонкий Л. В. Системное программное обеспечение. Часть 1. – Рыбинск, 2010. – 73 с.
В настоящем пособии рассматриваются вопросы классификации системного программного обеспечения и его местоположение в компьютерной системе. Кроме того, дано подробное описание формальных языков и грамматик в системе программирования, рассмотрены принципы построения трансляторов и лексических анализаторов. Материал изложен в виде 10лекций.
Подготовлено на кафедре «Вычислительные системы» Рыбинской государственной авиационной технологической академии имени П. А. Соловьева в качестве учебного пособия для студентов заочной и очной формы обучения по специальности 230101 «Вычислительные машины, комплексы, системы и сети».
РЕЦЕНЗЕНТЫ:
ООО НПП «ЛАМА»;
ведущий инженер ООО «ИС Криста» Фавстов А. И.
СОДЕРЖАНИЕ
Лекция №1 5
Предисловие П.1. Место системного программного обеспечения в компьютерной системе 5
П.2. Структура СПО 6
П.3. Хакеры как движущая сила развития СПО 11
Лекция №2 12
1. Формальные языки и грамматики в системе программирования 12
1.1. Структура систем программирования 12
1.2. Языки и цепочки символов. Способы задания языков 13
1.2.1. Общие представления о языках 13
1.2.2. Цепочки символов. Операции над цепочками символов 14
1.2.3. Формальное определение языка 16
1.2.4. Способы задания языков 17
Лекция №3 18
1.3. Грамматики и распознаватели 18
1.3.1. Порождающая грамматика 18
1.3.2. Запись правил грамматики с использованием метасимволов 22
Лекция №4 23
1.3.3. Распознаватели 23
1.3.4. Классификация распознавателей 25
1.3.4.1. Классификация распознавателей по компонентам 25
1.3.4.2. Классификация распознавателей по типу языков 27
Лекция №4 30
Лекция №5 35
1.3.5. Примеры классификации языков и грамматик 35
Лекция № 6 38
1.4. Технология формирования предложений языка 38
1.4.1. Выводимость цепочек 38
1.4.2. Сентенциальная форма грамматики 40
1.4.3. Левосторонний и правосторонний выводы 41
1.4.4. Дерево вывода и методы его построения 41
1.4.5. Проблема однозначности грамматик 43
Лекция 7 48
2. Принципы построения трансляторов 48
2.1. Основные определения 48
2.1.1. Формальное определение транслятора 48
2.1.2. Формальное определение компилятора 49
2.1.3. Интерпретаторы 51
2.2. Общая схема работы компилятора 51
2.3. Варианты построения компиляторов 55
2.3.1. Общие подходы в построении компиляторов 55
2.3.2. Понятие прохода 55
2.3.3. Однопроходные и многопроходные компиляторы 56
2.4. Особенности построения интерпретаторов и их взаимодействие с компиляторами 56
Лекция 8 58
3. Лексический анализ 58
3.1. Лексические анализаторы (сканеры) 58
3.1.1. Назначение сканера 58
3.1.2. Принципы построения сканеров 61
Лекция 9 63
3.1.3. Сканер как конечный автомат 63
Лекция 10 68
3.2. Взаимодействие сканера с таблицей идентификаторов 68
3.2.1.Назначение и особенности построения таблиц идентификаторов 68
3.2.2. Простейшие методы построения таблиц идентификаторов 69
3.2.3. Построение таблиц идентификаторов по методу бинарного дерева 70
СПИСОК ЛИТЕРАТУРЫ 74