Языки программирования и методы трансляции: учебное пособие для вузов, 3-е издание
Год издания: 2021
Автор: Свердлов С. З.
Издательство: Лань
ISBN: 978-5-8114-8195 -8
Серия: Высшее образование
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Количество страниц: 562
Описание: В книге рассматриваются вопросы сравнительного анализа языков программирования и конструирования компиляторов.
Первая часть книги содержит обзор языков высокого уровня и связанных с их эволюцией технологий структурного, модульного и объектно-ориентированного программирования. Проводится сравнительный анализ языков, в том числе на основе объективных критериев, даются экспертные оценки.
Вторая тема книги — конструирование компиляторов. Обсуждаются все элементы транслятора и этапы реализации языка от спецификации до формирования машинного кода.
Книга адресуется студентам вузов, специализирующимся по компьютерным технологиям, программистам-практикам и всем, кто интересуется программированием.
Оглавление
Оглавление
ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ ............................................... 9
ОТ АВТОРА ..................................................................................... 11
ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ
ВЫСОКОГО УРОВНЯ ........................................................................ 12
ЯЗЫК И ЕГО РЕАЛИЗАЦИЯ ............................................................... 12
КОМПИЛЯТОР, ИНТЕРПРЕТАТОР, КОНВЕРТОР .................................... 13
Метаязыки ...................................................................................... 18
ГЕНЕАЛОГИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ....................................... 19
ПЕРВОЕ ПОКОЛЕНИЕ ЯЗЫКОВ ............................................................ 20
Фортран .......................................................................................... 20
Алгол-60 ........................................................................................... 30
Кобол ................................................................................................ 40
ДВЕ ПОПЫТКИ ОБЪЯТЬ НЕОБЪЯТНОЕ ................................................. 42
ПЛ/1 ................................................................................................. 42
Алгол-68 ........................................................................................... 47
ИНТЕРАКТИВНОЕ ПРОГРАММИРОВАНИЕ ДЛЯ ВСЕХ ................................ 55
Бейсик .............................................................................................. 56
СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ .................................................... 69
Основы структурного программирования ............................................. 73
Паскаль ............................................................................................ 87
Язык Си ............................................................................................ 96
МОДУЛЬНОСТЬ, НАДЕЖНОСТЬ, АБСТРАКЦИЯ ..................................... 106
Ада ................................................................................................. 106
Модула-2 ........................................................................................ 112
Абстрактные типы данных ........................................................... 119
ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ .................. 121
Язык программирования Си++ ................................................... 132
Язык программирования Оберон ................................................ 139
Язык программирования Ява ....................................................... 152
Язык программирования Си# ...................................................... 166
Примеры использования объектной технологии ................................ 171
ЯЗЫКИ-КОНЦЕПЦИИ ......................................................................... 202
Форт .............................................................................................. 203
Лисп ............................................................................................... 206
Пролог ............................................................................................ 207
Смолток ........................................................................................ 207
ЯЗЫКИ ИНТЕРНЕТА .......................................................................... 209
HTML ............................................................................................. 209
Ява и аплеты ................................................................................. 210
Скриптовые языки ....................................................................... 212
Языки CGI-программирования ...................................................... 213
Языки активных серверных страниц ............................................ 217
Языки Интернета: повторение пройденного................................. 219
КАКОЙ ЯЗЫК ЛУЧШЕ. СРАВНИТЕЛЬНАЯ ОЦЕНКА ЯЗЫКОВ
ПРОГРАММИРОВАНИЯ ............................................................... 221
Арифметика синтаксиса ............................................................. 223
Важнейшие языки ........................................................................ 230
ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ ........................... 231
ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ ............................................ 231
Основные термины и определения ............................................. 231
Примеры языков ........................................................................... 233
Порождающие грамматики (грамматики Н. Хомского) ...................... 234
Еще несколько определений ......................................................... 238
Дерево вывода ............................................................................... 240
Задача разбора .............................................................................. 241
Для чего надо решать задачу разбора ....................................... 242
Домино Де Ремера ........................................................................ 242
Разновидности алгоритмов разбора .......................................... 244
Эквивалентность и однозначность грамматик ....................... 245
Иерархия грамматик Н. Хомского ............................................. 247
АВТОМАТНЫЕ ГРАММАТИКИ И ЯЗЫКИ ............................................ 250
Граф автоматной грамматики .................................................. 250
Конечные автоматы .................................................................... 252
Преобразование недетерминированного конечного автомата
(НКА) в детерминированный конечный автомат (ДКА)............. 253
Таблица переходов детерминированного конечного
автомата ............................................................................ 256
Программная реализация автоматного распознавателя ........ 257
Дерево разбора в автоматной грамматике .............................. 258
Пример автоматного языка ....................................................... 259
Синтаксические диаграммы автоматного языка .................... 262
Регулярные выражения и регулярные множества ................... 264
Эквивалентность регулярных выражений и автоматных
грамматик .............................................................................. 266
Для чего нужны регулярные выражения .................................... 267
Регулярные выражения как языки .............................................. 268
Расширенная нотация для регулярных выражений .................. 268
КОНТЕКСТНО-СВОБОДНЫЕ (КС) ГРАММАТИКИ И ЯЗЫКИ ............... 269
Однозначность КС-грамматики ................................................ 269
Алгоритмы распознавания КС-языков ....................................... 270
Распознающий автомат для КС-языков .................................... 271
Самовложение в КС-грамматиках ............................................. 271
Синтаксические диаграммы КС-языков .................................... 272
Определение языка с помощью синтаксических диаграмм ........ 275
Синтаксический анализ КС-языков методом рекурсивного
спуска ................................................................................... 278
Требование детерминированного распознавания ...................... 286
LL-грамматики ............................................................................. 287
Левая и правая рекурсия .............................................................. 288
Синтаксический анализ арифметических выражений .................... 288
Включение действий в синтаксис ............................................... 296
Обработка ошибок при трансляции .......................................... 306
Табличный LL(1)-анализатор ...................................................... 310
Рекурсивный спуск и табличный анализатор ............................ 319
ТРАНСЛЯЦИЯ ВЫРАЖЕНИЙ .............................................................. 320
Польская запись ............................................................................ 320
Алгоритм вычисления выражений в обратной польской
записи ..................................................................................... 321
Перевод выражений в обратную польскую запись ................... 324
Интерпретация выражений ....................................................... 326
Семантическое дерево выражения ............................................ 327
Упражнения для самостоятельной работы .................................. 339
ГЛАВА 3. ТРАНСЛЯЦИЯ ЯЗЫКОВ
ПРОГРАММИРОВАНИЯ ................................................................. 346
ОПИСАНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ..................................... 346
Метаязыки .................................................................................... 347
БНФ ............................................................................................... 347
Синтаксические диаграммы ....................................................... 348
Расширенная форма Бэкуса — Наура (РБНФ) .......................... 348
Описания синтаксиса языков семейства Си ............................. 349
Описания синтаксиса языка Ада ................................................ 350
ЯЗЫК ПРОГРАММИРОВАНИЯ «О» ..................................................... 351
Краткая характеристика языка «О» ................................................ 351
Синтаксис «О» ............................................................................. 352
Пример программы на «О» .......................................................... 354
СТРУКТУРА КОМПИЛЯТОРА ............................................................. 355
Многопроходные и однопроходные трансляторы ............................... 357
КОМПИЛЯТОР ЯЗЫКА «О» ................................................................ 359
Вспомогательные модули компилятора ............................................. 361
ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР (СКАНЕР) ........................................... 363
Виды и значения лексем ............................................................... 365
Лексический анализатор языка «О» ........................................... 366
СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР ..................................................... 383
КОНТЕКСТНЫЙ АНАЛИЗ ................................................................... 387
Таблица имен ................................................................................. 388
Контекстный анализ модуля ...................................................... 397
Трансляция списка импорта ........................................................ 400
Трансляция описаний .................................................................... 402
Контекстный анализ выражений .............................................. 405
Контекстный анализ операторов .............................................. 409
ГЕНЕРАЦИЯ КОДА ............................................................................. 412
Виртуальная машина ................................................................... 412
Архитектура виртуальной машины ........................................... 413
Программирование в коде виртуальной машины ...................... 420
Реализация виртуальной машины ............................................... 425
Генератор кода ............................................................................ 431
Распределение памяти ................................................................. 433
Генерация кода для выражений .................................................. 435
Генерация кода для операторов .................................................. 448
Завершение генерации .................................................................. 458
Назначение адресов переменным ................................................ 459
ТРАНСЛЯЦИЯ ПРОЦЕДУР .................................................................. 462
Расширенный набор команд виртуальной машины .................. 463
Процедуры без параметров и локальных переменных .............. 464
Процедуры с параметрами-значениями без локальных
переменных ....................................................................................... 466
Процедуры с параметрами-значениями и локальными
переменными .................................................................................... 470
Простейшая оптимизация кода ................................................. 472
Процедуры-функции с параметрами-значениями
и локальными переменными ............................................................ 472
Трансляция оператора RETURN ................................................. 475
Особенность трансляции параметров-переменных ................. 475
Пример программы на языке «О с процедурами» ..................... 477
КОНСТРУКЦИЯ ПРОСТОГО АССЕМБЛЕРА ......................................... 482
Язык ассемблера виртуальной машины ..................................... 482
Реализация ассемблера ................................................................ 488
АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ И МОБИЛЬНОСТЬ
ТРАНСЛЯТОРОВ .................................................................................... 496
Автоматический анализ и преобразование грамматик ............................. 496
Автоматическое построение компилятора и его частей ............................. 497
Использование языков высокого уровня ................................................. 503
Самокомпилятор. Раскрутка ................................................................... 506
Примеры раскрутки .............................................................................. 510
Унификация промежуточного представления ......................................... 511
ПРИЛОЖЕНИЕ. ЯЗЫК ПРОГРАММИРОВАНИЯ
ОБЕРОН-2 ............................................................................................ 517
ОТ ПЕРЕВОДЧИКА .............................................................................. 517
1. ВВЕДЕНИЕ ..................................................................................... 519
2. СИНТАКСИС .................................................................................. 520
3. СЛОВАРЬ И ПРЕДСТАВЛЕНИЕ ........................................................ 520
4. ОБЪЯВЛЕНИЯ И ОБЛАСТИ ДЕЙСТВИЯ ........................................... 522
5. ОБЪЯВЛЕНИЯ КОНСТАНТ .............................................................. 523
6. ОБЪЯВЛЕНИЯ ТИПОВ .................................................................... 524
6.1. Основные типы ...................................................................... 524
6.2. Тип массив .............................................................................. 525
6.3. Тип запись ............................................................................... 526
6.4. Тип указатель ........................................................................ 527
6.5. Процедурные типы ................................................................ 527
7. ОБЪЯВЛЕНИЯ ПЕРЕМЕННЫХ ......................................................... 527
8. ВЫРАЖЕНИЯ ................................................................................. 528
8.1. Операнды ................................................................................ 528
8.2. Операции ................................................................................ 529
9. ОПЕРАТОРЫ .................................................................................. 532
9.1. Присваивания ......................................................................... 533
9.2. Вызовы процедур ................................................................... 533
9.3. Последовательность операторов ............................................. 534
9.4. Операторы IF ........................................................................ 534
9.5. Операторы CASE .................................................................. 535
9.6. Операторы WHILE ................................................................ 535
9.7. Операторы REPEAT ............................................................. 536
9.8. Операторы FOR .................................................................... 536
9.9. Операторы LOOP ................................................................. 537
9.10. Операторы возврата и выхода .......................................... 537
9.11. Операторы WITH .............................................................. 538
10. ОБЪЯВЛЕНИЯ ПРОЦЕДУР ...................................................... 538
10.1. Формальные параметры .................................................... 539
10.2. Процедуры, связанные с типом ......................................... 541
10.3. Стандартные процедуры ................................................... 542
11. МОДУЛИ .............................................................................. 544
ПРИЛОЖЕНИЕ A: ОПРЕДЕЛЕНИЕ ТЕРМИНОВ ................................... 546
Целые типы ................................................................................... 546
Вещественные типы .................................................................... 546
Числовые типы ............................................................................. 546
Одинаковые типы ........................................................................ 546
Равные типы ................................................................................. 547
Поглощение типов ........................................................................ 547
Расширение типов (базовый тип) .............................................. 547
Совместимость по присваиванию .............................................. 547
Совместимость массивов ........................................................... 548
Совместимость выражений ....................................................... 548
Совпадение списков формальных параметров .......................... 549
ПРИЛОЖЕНИЕ B: СИНТАКСИС ОБЕРОНА-2 ...................................... 549
ПРИЛОЖЕНИЕ C: МОДУЛЬ SYSTEM ............................................... 551
ПРИЛОЖЕНИЕ D: СРЕДА ОБЕРОН ..................................................... 553
D1. Команды ................................................................................. 553
D2. Динамическая загрузка модулей .............................................. 555
D3. Сбор мусора ........................................................................... 555
D4. Смотритель ........................................................................... 556
D5. Структуры данных времени выполнения .................................. 556
ЛИТЕРАТУРА ................................................................................. 558
