Книга посвящена формальному описанию языков программирования. Подробно рассмотрены средства описания синтаксиса (грамматики X омского, формулы Бэкуса—Наура), однако основное внимание уделено Венскому методу формального описания семантики языков программирования. Представлен как сам Венский метод, так и ряд его необычных приложений, иллюстрирующих мощь, удобство и точность предлагаемых изобразительных средств.
Книга, безусловно, будет полезна всем, кто занимается системным и теоретическим программированием, разработчикам новых языков программирования и машин, а также аспирантам и студентам соответствующих специальностей.
ОТ РЕДАКТОРА ПЕРЕВОДА
Эта книга о Венском методе формального описания языков программирования (Венском метаязыке). Метод был разработан в 1968 году в Венской лаборатории IBM под руководством Лукаса на основе идей, восходящих к Маккарти. Первым применением этого метода было вполне удовлетворительное по полноте и строгости формальное описание такого мощного языка программирования, как PL/I. Впоследствии его средствами были описаны АЛГОЛ 60, ФОРТРАН и другие языки.
Метод создавался для описания языков, но последние являются столь сложными и многоплановыми, что всякий метод их описания автоматически оказывается пригодным и для многих других целей. В частности, Венский метод годится для описания и машин, и алгоритмов, и структур данных. Его очень полезно применять для обучения основам программирования (особенно системного). Этими завидными качествами Венский метод обязан прежде всего положенной в его основу хорошо разработанной концепции абстрактных объектов, позволяющей концентрировать внимание лишь на существенном и игнорировать второстепенные детали.
Отметим, однако, что Венский метод выражает лишь процедурный (операционный) подход к описанию языков и уже поэтому ограничен. Это признают и его авторы, и автор книги, который во введении говорит о другом многообещающем подходе— аксиоматическом, разработанном Виртом и Хоаром1).
Существование других подходов не умаляет достоинств Венского метода, а лишь лучше выделяет ту область, где он пока вне конкуренции—это описание абстрактных процессов, в частности, процессов интерпретации программ на языках программирования.
Предлагаемая книга рассчитана прежде всего на специалистов—научных сотрудников и аспирантов, занимающихся теорией формальных языков, теорией трансляции, алгоритмов и программ.
Еще один подход можно найти в работе: Кауфман В. Ш., Левин В. А., естественный подход к проблеме описания контекстных условий, «Вестник «и у», серия «Вычислительная математика и кибернетика», вып. 2, 1977.
ОГЛАВЛЕНИЕ
От редактора перевода........................ 5
Предисловие к английскому изданию................. 7
Введение. Цели............................ 11
Глава I. Основные понятия............... 17
1.1. Элементы символической логики............... 17
1.2. Условные выражения.................... 26
1.3. Элементы теории множеств................. 29
1.4. Элементы алгебры...................... 34
Литература к главе I...................... 37
Глава II. Формальные языки.............. 39
2.1. Грамматики и языки.................... 39
2.2. Алголоподобные языки и фрагмент PL............ 46
2.3. Синтаксические графы.................... 52
2.4. Конечные автоматы..................... 57
Литература к главе II...................... 64
Глава III. Разбор................... 66
3.1. Системы конечных автоматов................ 66
3.2. Магазинные автоматы.................... 77
3.3. Магазинные преобразователи ................ 91
Литература к главе III..................... 96
Глава IV. Структуры данных............... 98
4.1. Почему нам необходима теория структур данных....... 99
4.2. Аксиомы структур данных................. 101
4.3. Теоретико-множественная модель структур данных...... ПО
4.4. Размеченные деревья.................... 120
Литература к главе IV..................... 126
Глава V. Классы структур данных........... 128
5.1. Обозначения......................... 128
5.2. Абстрактные грамматики.................. 134
5.3. Списки . . -........................ 142
5.4. Структурная индукция................... 146
Литература к главе V ..............,....... 156
Глава VI. Преобразования языка . ........... 158
6.1. Элементы языков программирования............. 161
6.2. Преобразованные абстрактные грамматики.......... 174
Литература к главе VI..................... 178
Глава VII. Интерпретирующие автоматы. Часть I .... 180
7.1. Управление......................... 182
7.2. Интерпретирующие функции и функция перехода....... 192
7.3. Внешняя среда, хранилища, счетчик отличительных имен и склад............................ 198
7.4. Схемы команд PL-машины.................. 203
7.5. Действия PL-машины.................... 210
Литература к главе VII..................... 218
Глава VIII. Интерпретирующие автоматы. Часть II ... 220
8.1. Вторая PL-машина.......... ........... 221
8.2. Сдвоенный автомат...........,' . ,....... 230
8.3. Отделенное управление................... 240
Литература к главе VIII . . .................. 252
Глава IX. Взаимодействующие последовательные процессы 254
9.1. Абстрактный синтаксис................... 256
9.2. Схемы команд....................... 266
9.3. Система абстрактных процессоров.............. 269
Литература к главе IX . :................... 278
Список литературы................ . ........ 280
Предметный указатель........................ 284
Цена: 200руб.
