Предисловие ........,.................. 7
Введение............................. 8
Глава 1. Основные понятия и обозначения.............. 10
1.1. Введение........................ 10
1.2. Выражения [типа оператор/операнд............ И
1.3. Переменные и лямбда-выражения.............. 16
1.4. Структуры данных................... 18
1.5. Дополнительные формы выражений............ 21
1.6. Примеры....................... 28
1.7. Упрощение выражений................. 32
1.8. Лямбда-преобразование................. 36
1.9. Комбинаторы ..................... 40
1.10. Рекурсивные функции................. 42
1.11. Преобразование к комбинаторам............. 45
Ссылки и библиография................. 47
Глава 2. Структуры программ.................... 48
2.1. Введение........................ 48
2.2. Программы обратной польской записи........... "49
2.3. Значения идентификаторов................ 52
2.4. Вычисление комбинаций................. 54
2.5. Компилятор комбинаций,............... 57
2.6. Блоки и процедуры.................., 59
2.7. Вычисление выражений................. 62
2.8. Компиляция выражений................. 66
2.9. Методы повышения эффективности программ........ 72
2.10. Метки и операторы перехода............... 81
2.11. Совмещение, присваивание и копирование......... 86
2.12. Другие методы вычисления выражений.......... 94
Ссылки и библиография................ . 97
Глава 3. Структуры данных.................... 98
3.1. Введение ....................... 98
3.2. Основные понятия................... 100
3.3. Некоторые простые структуры.............. 105
3.4. Списки ........................ 107
3.5. Списковые структуры................... 115
3.6. Деревья и леса..................... 117
3.7. Бинарные деревья....................122
3.8. Комбинации .,,,.,,,,.......... , . , 125
5
. 3.9. Веса деревьев...................... 127
3.10. Последовательности, сопрограммы и потоки........ 128
3.11. Комбинаторные конфигурации.............. 140
Ссылки и библиография................. 147
Глава 4. Грамматический разбор................... 148
4.1. Введение ........................ 148
4.2. Конечные автоматы и регулярные выражения. ....... 149
4.3. Контекстно-свободные языки............... 155
4.4. Выражения, описывающие я,зыки............. 158
4.5. Нисходящий грамматический разбор........... . 161
4.6. Левоугольный восходящий грамматический разбор..... 175
4.7. Правоугольный восходящий грамматический разбор..... 182
Библиография...................... 191
Глава S. Сортировка........................ 193
5.1. Введение........................ 193
5.2. Векторы упорядочения.................. 195
i. 5.3. Деревья двоичного поиска................. 204
5.4. Двоичная вставка.................... 208
i 5.5. Быстрая сортировка................... 210
5.6. Обмен по основанию системы счисления и память типа drie», 212
5.7. Вставка дерева и его перестройка.............. 214
5.8. Упорядочение с помощью дерева сортировки......... 221
.*! 5.9. Сортировка на лентах................... 225
Ссылки и библиография................. 242
Указатель программ........................ 244
Предметный указатель.............'.......... 247
ПРЕДИСЛОВИЕ
Область системного программирования возникла главным образом как результат труда многих программистов и исследователей, чья творческая энергия привела к созданию практических обслуживающих системных программ. Это было обусловлено бурным развитием вычислительной техники. На ранних стадиях программирование развивалось как вид искусства, где каждый программист создавал собственные программы решения задач с кратким описанием, которыми кроме него самого могли пользоваться лишь его непосредственные коллеги. В 1968 году Ашер Оплер, работая в то время в фирме ИБМ, пришел к выводу, что знания в области программирования следует привести к форме, доступной для всех системных программистов. Исследуя состояние данного вопроса, он убедился, что имеется достаточно оснований для систематизации рассматриваемого материала. По его рекомендации фирма ИБМ решила субсидировать Серию Системного Программирования,1 что дало возможность собирать, систематизировать и освещать в печати принципы и методы, имеющие важное значение для всех пользователей ЭВМ.
Серия задумана как постоянно продолжающийся ряд Моно-. графий, отражающих личные взгляды авторов на предмет изложения, которые не всегда совпадают с мнением фирмы ИБМ. Каждая из книг задумана как изложение отдельного курса, но может служить и справочным пособием. Серия состоит из трех уровней: обширный вводный материал в книгах, посвященных основам программирования; более сложный материал в книгах по программному обеспечению; наконец, специальные вопросы в книгах, посвященных науке программирования. Как правило, книги Серии удовлетворяют и начинающих и опытных программистов, а также специалистов по математическому обеспечению вычислительных машин.
Таким образом, книги Серии отражают современное состояние в этой области и могут стать основой для изучения системного программирования.
Элизабет Бунин
