ISBN 5-94723-562-5
> В книге рассматриваются основные теоретические принципы и реализующие их технологии, лежащие в основе современных средств разработки программного обеспечения. Содержится вся необходимая информация о трансляторах, компиляторах, интерпретаторах, а также о других составляющих сметем программирования, начиная от базовых теоретических сведений до современных технологий разработки распределенных программ.
Книга ориентирована прежде всего на студентов, обучающихся в технических вузах по специальностям, связанным с вычислительной техникой. Но она будет также полезна всем, чья деятельность так или иначе связана с разработкой программного обеспечения. Разработчики системных программ могут почерпнуть в ней для себя немало полезных сведений, а прикладные программисты более детально познакомятся с принципами функционирования инструментов, которыми они пользуются, что в любом случае будет способствовать повышению качества создаваемых ими программных средств.
Допущено Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по специальностям «Вычислительные машины, комплексы, системы и сети» и «Автоматизированные системы обработки информации и управления» направления подготовки дипломированных специалистов «Информатика и вычислительная техника».
ББК 72.973-018я7 УДК 681.3.06(075)
Содержание
Предисловие........................10
Введение ..... .................... 12
От издательства.................................13
Глава 1. Формальные языки и грамматики..........14
Языки и цепочки символов. Способы задания языков...............14
Цепочки символов. Операции над цепочками символов...........14
Понятие языка. Формальное определение языка...............16
Способы задания языков. Синтаксис и семантика языка........... 17
Особенности языков программирования.................. . 19
Грамматики и распознаватели..........................20
Формальное определение грамматики. Форма Бэкуса—Наура........20
Принцип рекурсии в правилах грамматики..................22
Другие способы задания грамматик.....................23
Распознаватели. Общая схема распознавателя ...............26
, Виды распознавателей............................29
Задача разбора................................ 30
Классификация языков и грамматик.......................31
Классификация грамматик. Четыре типа грамматик по Хомскому......32
Классификация языков............................34
•Классификация распознавателей.......................36
Примеры классификации языков и грамматик................38
Цепочки вывода. Сентенциальная форма.....................41
Вывод. Цепочки вывода............................41
Сентенциальная форма грамматики. Язык, заданный грамматикой.....43
Левосторонний и правосторонний выводы..................44
-л Дерево вывода. Методы построения дерева вывода.............44
Проблемы однозначности и эквивалентности грамматик.............46
Однозначные и неоднозначные грамматики.................46
Проверка однозначности и эквивалентности грамматик...........48
Правила, задающие неоднозначность в грамматиках.............50
Контрольные вопросы и задачи..........................50
Вопросы...................................50
Задачи ..........................• • .,. ...... 5.1
Глава 2. Основные принципы построения трансляторов . ... 54
Трансляторы, компиляторы и интерпретаторы — общая схема работы...... 54
• Определения транслятора, компилятора, интерпретатора.......... 54
Этапы трансляции. Общая схема работы транслятора............ 58
;• Понятие прохода. Многопроходные и однопроходные компиляторы..... 61
Современные компиляторы и интерпретаторы.................. 63
Компиляторы с языков высокого уровня................... 63
Интерпретаторы. Особенности построения интерпретаторов........ 67
" Трансляторы с языка ассемблера («ассемблеры»).............. 70
-'•'г' Макроязыки и макрогенерация........................ 73
•Таблицы идентификаторов. Организация таблиц идентификаторов....... 77
Назначение и особенности построения таблиц идентификаторов...... 77
Простейшие методы построения таблиц идентификаторов ......... 79
Построение таблиц идентификаторов по методу бинарного дерева..... 80
Хэш-функции и хэш-адресация........................ 83
Комбинированные способы построения таблиц идентификаторов...... 91
.Контрольные вопросы и задачи.......................... 93
" Вопросы................................... 93
Задачи .................................... 94
Глава 3. Лексические анализаторы..............96
Лексические анализаторы (сканеры). Принципы построения сканеров......96
• Назначение лексического анализатора....................96
• Принципы построения лексических анализаторов...............98
Регулярные языки и грамматики.........................103
?' Регулярные и автоматные грамматики ...................103
Конечные автоматы.............................107
" Детерминированные и недетерминированные конечные автоматы.....109
Минимизация конечных автоматов.....................112
Регулярные множества и регулярные выражения..............114
".' Свойства регулярных языков ........................120
Построение лексических анализаторов......................121
> Три способа задания регулярных языков..................121
;, Построение регулярного выражения для языка, заданного
; леволинейной грамматикой........................122
ч Построение конечного автомата на основе леволинейной грамматики ... 124
Примеры построения лексических анализаторов..............129
, Автоматизация построения лексических анализаторов (программа LEX) . . . 139 Контрольные вопросы и задачи.........................141
Вопросы....................................141
,. Задачи....................................142
Глава 4. Синтаксические анализаторы ...........144
Основные принципы работы синтаксических анализаторов...........144
: Назначение синтаксических анализаторов .................144
Автоматы с магазинной памятью......................145
Построение синтаксических анализаторов.................148
Преобразование КС-грамматик. Приведенные грамматики........... 153
;> Преобразование грамматик. Цель преобразования.............153
Приведенные грамматики . ......................... 154
Удаление бесплодных символов...... ................. 154
Удаление недостижимых символов..................... 155
Устранение Х-правил ............................-156
Устранение цепных правил......,..................158
Устранение левой рекурсии.........................160
Синтаксические распознаватели с возвратом ..................162
Принципы работы распознавателей с возвратом............ . .162
Нисходящий распознаватель с возвратом..................164
Распознаватель на основе алгоритма «сдвиг-свертка»....... . , . . 170
Нисходящие распознаватели КС-языков без возвратов.............176
Левосторонний разбор по методу рекурсивного спуска...........176
Расширенные варианты метода рекурсивного спуска............180
1ЦК)-грамматики ..............................184
Синтаксический разбор для Щ1)-грамматик................187
Восходящие распознаватели КС-языков без возвратов.............197.
ЛР(К)-грамматики........ ...................... 198
Синтаксический разбор для 1Р(0)-грамматик................203
Синтаксический разбор для 1_Р(1)-грамматик................209
8ЬР(1)и1А1Р(1)-грамматики........................214
Автоматизация построения синтаксических анализаторов (программа YACC)..............................221
Синтаксические распознаватели на основе грамматик предшествования . . . . 223
Общие принципы грамматик предшествования................ 223
Грамматики простого предшествования...................224
Грамматики операторного предшествования................234
Контрольные вопросы и задачи.........................245
Вопросы.................................. . 245
Задачи....................................247
Глава 5. Генерация и оптимизация кода ...........249
Семантический анализ и подготовка к генерации кода . . ...........249
Назначение семантического анализа ....................249
• Этапы семантического анализа...................... . 250
Идентификация лексических единиц языков программирования......256
Распределение памяти.............................259
Принципы распределения памяти......................259
Виды переменных и областей памяти....................260
Виды областей памяти. Статическое и динамическое связывание . . ... 263 Дисплей памяти процедуры (функции). Стековая организация
дисплея памяти..............................267
Исключительные ситуации и их обработка................. 272
Память для типов данных (РТП-информация)................279
Генерация кода. Методы генерации кода....................281
Общие принципы генерации кода......................281
Синтаксически управляемый перевод....................282
Способы внутреннего представления программ ........:.....285
Обратная польская запись операций....................291
Схемы СУ-перевода............. , ............•
Оптимизация кода. Основные методы оптимизации...............301
К;,, Общие принципы оптимизации кода....................301
>$ Оптимизация линейных участков программы................305
|;> Другие методы оптимизации программ....................312
* '(' Машинно-зависимые методы оптимизации.................319
2 контрольные вопросы и задачи.........................321
н> Вопросы...................................321
К Т*1 Задачи.................. ..................324
$»'
|Глава в. Современные системы программирования.....327
, Понятие и структура системы программирования................. 327
i •' Понятие о системе программирования...................327
' Возникновение систем программирования..................328
* Появление интегрированных сред разработки ...............330
, - Структура современной системы программирования............332
Принципы функционирования систем программирования............335
'' Функции текстовых редакторов в системах программирования.......335
' Компилятор как составная часть системы программирования .......338
Компоновщик. Назначение и функции компоновщика . . ;.........339
, Загрузчики и отладчики. Функции загрузчика.......'.........341
библиотеки подпрограмм............................345
Библиотеки подпрограмм как составная часть систем программирования . . 345
Статические библиотеки подпрограмм...................347
Динамические библиотеки подпрограмм..................348
Ресурсы пользовательского интерфейса. Редакторы ресурсов.......350
Мобильность и переносимость программного обеспечения ........351
Разработка приложений в архитектуре «клиент-сервер».............357
i История возникновения приложений с архитектурой «клиент-сервер» . . . 357
Структура приложения, построенного в архитектуре «клиент-сервер»......358
Современные серверы данных. Язык запросов данных...........360
Принципы создания приложений в архитектуре «клиент-сервер»......363
Разработка программ в многоуровневой архитектуре..............365
Принципы разработки приложений в многоуровневой архитектуре.....365
Технологии взаимодействия с сервером приложений............367
Организация серверов приложений.....................371
Возможности многоуровневой архитектуры.................372
, Разработка программного обеспечения для сети Интернет.........373
Контрольные вопросы и задачи.........................382
Вопросы...................................382
Задачи....................................384
Указатель литературы...................386
Алфавитный указатель...................390
Цена: 150руб.
