Теория и практика языков программирования. Орлов С.А.

СПб.: 2013. — 688 с.

Учебник посвящен систематическому изложению теории и практики языков программирования. Он отражает классическое содержание учебной дисциплины по языкам программирования. Все сложные вопросы поясняются законченными примерами. Кроме того, здесь предлагается полный комплекс задач и упражнений по узловым вопросам. В российских стандартах третьего поколения (компьютерного направления) учебник охватывает базисные разделы следующих дисциплин: теория формальных языков, теория автоматов и формальных языков, языки программирования, программирование, объектно-ориентированное программирование, логическое и функциональное программирование, теория вычислительных процессов.
Учебник предназначен для студентов инженерного, бакалаврского и магистерского уровней компьютерных специальностей, может быть полезен преподавателям и исследователям/разработчикам трансляторов и другого программного обеспечения.
Рекомендовано Санкт-Петербургским институтом информатики и автоматизации Российской академии наук (СПИИРАН) в качестве учебника по направлению «Информатика и вычислительная техника».

Формат: pdf

Размер: 4,7 Мб

Скачать: drive.google

ОГЛАВЛЕНИЕ
Введение 15
Благодарности 21
Глава 1. Определение и проблемы языков программирования 22
Для чего нужно изучать принципы построения языков программирования 22
Аппарат абстракции-конкретизации 23
Исходное определение языка программирования 24
Практическое определение языка программирования 25
Технологическое определение языка программирования 26
Области применения языков программирования 27
Научные вычисления 27
Обработка деловой информации 28
Искусственный интеллект 28
Системная область 29
Веб-обработка 29
Критерии эффективности языков программирования 30
Читабельность 31
Легкость создания программ 33
Надежность 34
Стоимость 35
Способы построения критериев эффективности 37
Нормализация частных показателей 39
Учет приоритета частных показателей 39
Заключительные замечания 40
Контрольные вопросы и упражнения 40
Глава 2. Виртуальные машины и трансляция языков 42
Аппаратная организация компьютеров 42
Принцип программного управления 43
Структура виртуальной машины 44
Порядок функционирования виртуальной машины 45
Понятие виртуальной машины 46
Трансляторы и интерпретация 47
Иерархия виртуальных машин 51
Этапы трансляции 52
Анализ исходной программы 54
Синтез объектной программы 58
Контрольные вопросы 60
Глава 3. Виды языков программирования 62
Парадигмы программирования 62
Императивные языки программирования 63
Язык Fortran 64
ЯзыкС 65
Функциональные языки программирования 67
Язык LISP 69
Логические языки программирования 70
Язык Prolog 72
Объектно-ориентированные языки программирования 73
Язык Smalltalk 74
Язык разметки HTML 75
Скриптовые языки 78
Общие характеристики скриптовых языков 80
Язык Perl 82
Язык JavaScript 84
ЯзыкРНР 85
Язык Python 86
ЯзыкЯиЬу 87
fl3biKLua 88
Гибридные языки разметки/программирования 91
flsbiKXSLT 92
ЯзыЫЭР 96
Контрольные вопросы и упражнения 97
Глава 4. Выражения и присваивания в языках программирования 98
Нотации выражений 98
Префиксная нотация выражения 99
Постфиксная нотация выражения 101
Инфиксная нотация выражения 102
Смешанная нотация 103
Сравнение нотаций для записи выражений 103
Присваивание 103
Порядок вычисления операндов в выражении 105
Контрольные вопросы и упражнения 107
Глава 5. Действия и операторы в программах 109
Базовые операторы 109
Операторы перехода 112
Потокуправления 113
Составные операторы 115
Условные операторы 116
Вложенность условных операторов 117
Операторы выбора 121
Организация повторения операторов 125
Операторы цикла с заданным числом повторений 126
Оператор for языка Python 128
Циклы с заданным числом повторений в функциональных языках 129
Операторы цикла без заданного числа повторений 129
Бесконечные циклы и механизмы управления ими 129
Циклы с предусловием 132
Циклы с постусловием 133
Универсальность оператора for в языках С, C++, С# и Java 134
Охраняемые структуры управления Дейкстры 136
Инварианты 138
Программирование с инвариантами 139
Контрольные вопросы и упражнения 141
Глава 6. Средства представления синтаксиса языков программирования 144
Особенности определения языка программирования 144
Качество синтаксиса языка 146
Легкость чтения 146
Легкость написания 147
Легкость трансляции 147
Отсутствие неоднозначности 148
Синтаксические элементы языка 148
Набор символов 148
Идентификаторы 151
Константы и литералы 152
Символы операций 154
Ключевые и зарезервированные слова 155
Необязательные слова 156
Комментарии 156
Пробелы 156
Разделители и скобки 156
Выражения 157
Операторы 157
Лексемы и лексический синтаксис 157
Абстрактный синтаксис и абстрактные синтаксические деревья 158
Грамматики в языках программирования 161
Контекстно-свободная грамматика 161
Форма Бэкуса—Haypa(BNF) 162
Деревья разбора 163
Синтаксическая неоднозначность 165
Неоднозначность повисшего Else 165
Выводы — линейная форма грамматического разбора 166
Списки в инфиксных выражениях 167
Переход к конкретному синтаксису 168
Обработка ассоциативности и приоритетности 171
Расширенная BNF 173
Синтаксические схемы 175
Точки с запятой и пустые операторы 177
Контрольные вопросы и упражнения 178
Глава 7. Формальная семантика языков программирования 182
Семантика языка программирования 182
Синтезируемые атрибуты 183
Порядок вычислений 185
Выводы 185
Атрибутные грамматики 185
Операционная семантика 188
Аксиоматическая семантика 189
Аксиома присваивания 191
Применение аксиомы присваивания 192
Правило консеквенции (упрощения) 192
Правило вывода для последовательности 193
Применение правила вывода для последовательности 194
Правило вывода для условного оператора 194
Применение правила вывода для условного оператора 194
Вычисление предусловия для цикла FOR 195
Правило вывода для оператора цикла WHILE 196
Требования к инварианту цикла 196
Определение инварианта цикла по индукции 196
Пример доказательства цикла 197
Общий случай определения инварианта цикла 198
Денотационная семантика 200
Семантическая функция отображения двоичных чисел 201
Семантическая функция отображения десятичных чисел 201
Состояние программы 202
Выражения 203
Операторы присваивания 204
Логические циклы с предусловием 204
Контрольные вопросы и упражнения 205
Глава 8. Типизация данных 209
Объекты данных 209
Переменные и константы 210
Типы данных 211
Элементарные типы данных 213
Объявления 216
Статический контрольтипов 218
Динамический контрольтипов 219
Обзор составных типов данных 220
Системы типизации данных 221
Атрибуты переменной 222
Связывание 224
Динамическое связывание типов 225
Время жизни 228
Тип выражения 232
Контрольные вопросы и упражнения 233
Глава 9. Скалярные типы данных 236
Перечисления 236
Целые и вещественные типы 238
Десятичные числа 241
Поддиапазоны 241
Логический тип 242
Символьные типы 243
Стиль программирования в языке С. Преобразование типов 244
Контрольные вопросы и упражнения 244
Глава 10. Составные типы данных 246
Массивы 246
Разновидности массивов 248
Инициализация массива 251
Атрибуты и операции простого массива 252
Операции над массивами в скриптовых языках 253
Прямоугольные массивы и массивы массивов 253
Сечения массивов 256
Статические массивы языка С 259
Ассоциативные массивы 259
Строки символов 261
Записи 265
Записи и массивы со вложенными структурами 268
Сравнение массивов и записей 269
Объединения и вариантные записи 270
Вариантные записи ослабляют надежность типов? 273
Множества 275
Кортежи 276
Списки 277
Контрольные вопросы и упражнения 280
Глава 11. Указатели 282
Основные понятия 282
Операции над указателями в языке Pascal 283
Динамические связные структуры данных 284
Повисшие указатели и утечки памяти 285
Безопасность указателей в Паскале 286
Указатели как посредники 287
Перестановка указателей и перемещение данных 288
Указатели в языке Ada 288
Массивы и указатели в языках С и C++ 291
Динамическое распределение памяти 294
Гибкость указателей в языке С 295
Ссылочный тип 296
Реализация указателей 297
Контрольные вопросы и упражнения 298
Глава 12. Преобразования типов данных 300
Эквивалентность типов данных 300
Преобразование типа и явное приведение 306
Явные приведения типа в языке C++ 308
Оператор staticcast 309
Оператор constcast 309
Оператор reinterpret_cast 310
Оператор dynamiccast 311
Совместимость типов и неявное приведение 311
Уровень типизации языка 315
Контрольные вопросы и упражнения 319
Глава 13. Подпрограммы 320
Разновидности подпрограмм 320
Объявление подпрограммы 322
Вызов подпрограммы 325
Рекурсия — множественные выполнения подпрограммы 328
Преимущества подпрограмм 328
Методы передачи параметров 329
Передача параметров по значению 333
Передача параметров по ссылке 334
Эффект передачи параметров по ссылке с помощью указателей языка С 336
Передача по значению-результату 337
Передача по результату 339
Правила области видимости для имен 340
Статическая область видимости и переименование локальных переменных 342
Макрорасширение и динамическая область видимости 342
Конфликты именования 343
Передача параметров— текстуальная подстановка 343
Передача параметров по имени и статическая область видимости 344
Реализация методов передачи параметров 345
Методы передачи параметров в популярных языках программирования 346
Проверка типов параметров 349
Массивы в качестве параметров 350
Подпрограммы в качестве параметров 352
Проверка типов параметров при вызовах подпрограммы 352
Организация области видимости для выполнения
переданной подпрограммы 354
Типы возвращаемых значений 355
Количество возвращаемых значений 356
Побочные эффекты функций 356
Полиморфизм в языках программирования 356
Параметрический полиморфизм 357
Полиморфизм включения или полиморфизм подтипов 359
Перегрузка и неявное приведение 360
Реализация полиморфизма 360
Перегруженные подпрограммы 361
Родовые подпрограммы 363
Родовые подпрограммы в языке Ada 363
Родовые подпрограммы в языке C++ 367
Родовые методы в языке Java 369
Родовые методы в языке С# 371
Родовые функции в языке F# 371
Замыкания 372
Контрольные вопросы и упражнения 374
Глава 14. Управление подпрограммами 376
Вложенные области видимости объявлений 376
Связывания при выполнении подпрограмм 381
Поток управления между активациями подпрограмм 381
Деревья активации 382
Формат записи активации 383
Размещение и освобождение в куче 385
Повторное использование свободного пространства 386
Уплотнение свободного пространства 387
Фрагментация памяти в куче 387
Размещение и освобождение в стеке 388
Размещение статических переменных в период компиляции 389
Управление подпрограммами в языке С 389
Управление подпрограммами в языке Pascal 391
Дисплеи для быстрого доступа к информации 395
Контрольные вопросы и упражнения 397
Глава 15. Абстрактные типы данных 400
Абстракция процесса 400
Инкапсуляция и абстракция данных 401
Абстрактные типы данных 403
АТД в языке Ada 405
АТД в языке C++ 408
АТД в языке Java 410
АТД в языке С# 411
АТД в языке Ruby 413
Параметрический полиморфизм в АТД 416
Родовые АТД в языке Ada 416
Классы-шаблоны в языке C++ 418
Родовые классы в языке Java 420
Родовые классы в языке С# 422
Синтаксические контейнеры для множества типов 422
Контейнеры в языке С 423
Контейнеры в языке C++ 423
Пакеты языка Ada 424
Сборки языка С# 426
Пространства имен 427
Пространства имен в языке C++ 427
Пакеты в языке Java 428
Пространства имен в языке Ada 429
Модули в языке Ruby 430
Контрольные вопросы и упражнения 430
Глава 16. Объектно-ориентированное и аспектно-ориентированное программирование 432
Основные понятия объектно-ориентированного подхода к программированию 432
Классы 433
Отношения между классами 436
Деревья наследования классов 442
Объекты 443
Отношения между объектами 446
Возможности наследования и полиморфизм 448
Природа наследования 450
Иерархия наследования в различных языках 452
Принцип подстановки Барбары Дисков 452
Корректность наследования 453
Переопределение и виртуальные методы 454
Интерфейсы и абстрактные классы 455
Формы наследования 456
Вариации на тему наследования 460
Сообщения и объекты 462
Синтаксис пересылки сообщений 462
Сообщения в языках со статической и динамической типизацией 463
Доступ к получателю внутри метода 464
Создание объектов и конструкторы 466
Связывание сообщения и метода 468
Переопределение методов 472
Замещение методов 472
Уточнение методов 475
ООП на языке C++ 477
Единичное наследование 478
Множественное наследование 481
Динамическое связывание 482
ООП на языке Ада 484
Расширяемые типы 484
Классы 484
Абстрактные классы и интерфейсы 486
Надклассовые типы 489
Наследование от родового класса 489
ООП на языке Java 492
Единичное наследование 493
Смешанное наследование 494
Вложенные классы 495
ООП на языке С# 496
Наследование 496
Динамическое связывание 496
Вложенные классы 497
ООП на языке Ruby 497
Наследование 499
Динамическое связывание 499
Реализация объектно-ориентированных классов и объектов 500
Организация памяти для сохранения объекта 500
Динамическое связывание сообщений с методами 500
Особенности аспектно-ориентированного подхода 503
Базовые понятия АОП 507
Аспекты 509
Жизнь без аспектов 509
Жизнь с аспектами 510
Программирование нааспектно-ориентированном языке AspectJ 514
Конструкции пересечения языка AspectJ 516
Альтернативный синтаксис ©AspectJ 519
Контрольные вопросы и упражнения 520
Глава 17. Аппарат исключений 523
Характеристика исключений 523
Этапы работы с определяемыми исключениями 526
Потоки управления при обработке исключений 528
Многоуровневая система исключений 529
Обработка исключений в языке C++ 531
Связывание исключений с обработчиками 531
Оформление функций в C++ 532
Обработка исключений в языке Java 533
Классы исключений 533
Обработчики исключений 533
Связывание исключений с обработчиками 534
Секция finally 535
Обработка исключений в языке С# 536
Контрольные вопросы и упражнения 536
Глава 18. Ввод-вывод и файлы 537
Характеристика аппарата ввода-вывода 538
Пакеты ввода-вывода языка Ада 539
Процедуры ввода языка Ада 540
Процедуры вывода языка Ада 541
Организация файлов и средства управления ими 543
Текстовые файлы 546
Двоичные файлы последовательного доступа 552
Двоичные файлы прямого доступа 554
Потоки ввода-вывода 556
Объектно-ориентированный ввод-вывод в языке C++ 560
Потоковая библиотека ввода-вывода 561
Стандартные потоки 563
Форматирование потоков 565
Ошибки потоков 568
Файловые потоки 569
Строковые потоки 575
Контрольные вопросы и упражнения 577
Глава 19. Основные понятия параллельного программирования 578
Процессы и потоки 578
Задачи языка Ада 582
Синхронизация процессов на основе разделяемых переменных 585
Семафоры 586
Мониторы 588
Защищенные объекты 589
Синхронизация процессов на основе сообщений 592
«Развязка» взаимодействия задач при рандеву 596
Селективный прием selective accept 596
Временной вызов входа 601
Условный вызов входа 601
Асинхронный отбор 601
Потоки языка Java 602
Класс Thread 602
Приоритеты 604
Семафоры 604
Синхронизация конкуренции 605
Синхронизация взаимодействия 606
Неблокирующая синхронизация 608
Явная блокировка 609
Потоки вС# 610
Основные операции над потоками 610
Синхронизация потоков 612
Контрольные вопросы и упражнения 613
Глава 20. Функциональное программирование 615
Особенности функциональных языков программирования 615
Выводы 618
Язык Scheme — классический функциональный подход 619
Выражения языка Scheme 619
Специальные формы 621
Создание функций 623
Динамическая проверка типа 624
Хвостовая и не хвостовая рекурсия 625
Структуры данных в языке Scheme 626
Программирование в языке Scheme 627
Функции высшего порядка 628
Статическая область видимости 630
Настройка —специализация языка Scheme 631
Язык ML — функциональный подход со статической типизацией 632
Функции и величины языка ML 633
Списки в языке ML 634
Проверка типов в языке ML 636
Ввод и вывод в языке ML 637
Типы данных 638
Функции высшего порядка и карризация 639
Отложенные вычисления 642
Нестрогие функции 642
Специальные формы для отложенных вычислений 643
Ленивые вычисления 645
Контрольные вопросы и упражнения 646
Глава 21. Логическое программирование 648
Исчисление предикатов 648
Компоненты исчисления предикатов первого порядка 649
Запись утверждений в исчислении предикатов 650
Правила вывода исчисления предикатов первого порядка 651
Специфика логического программирования 652
Формулы Хорна 652
Резолюция и унификация 656
Язык Prolog 659
Нотация и структуры данных 659
Выполнение в среде языка Prolog 660
Арифметика 661
Унификация 662
Стратегия поиска в языке Prolog 664
Циклы и структуры управления 665
Проблемы языка Prolog 669
Проблема проверки вхождения при унификации 669
Проблема замкнутого мира 669
Проблема логического отрицания 670
Формулы Хорна не выражают всю логику утверждений 671
Информация управления в логическом программировании 672
Контрольные вопросы и упражнения 673
Заключение 675
Список литературы 677
Алфавитный указатель 683