Трансляция современных языков программирования монографии устанавливается естественная связь между математической лингвистикой и методами трансляции современных языков программирования. Проводится последовательный алгоритмический подход к рассматриваемым конструкциям, что позволяет приблизить элементы теории языков к потребностям практики. Изложение сопровождается многочисленными задачами для самостоятельного решения. Книга полезна широкому кругу программистов и может служить ценным пособием для студентов и аспирантов, изучающих системное программирование. ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В предлагаемойвниманию читателей монографии Ф. Вайнгартена ' освещается взаимопроникновение двух научных дисциплин: мето-дов трансляции языкдв программирования и теории формальных ,- Грамматик, которая является одной из основ трансляции. Автору ', удалось при сравнительно небольшом объеме книги четко, строго , и в то же. время достаточно наглядно проанализировать и система-тизиррвать накопленный за многие годы теоретиками и создателя-- ми"-математического обеспечения опыт .разработки эффективных алгоритмов трансляции, базирующихся на грамматическом разборе 'входной строки. (Заметим, что обычно под трансляцией понимается .„ весь комплекс проблем перевода исходной программы в эквивалентную программу. В данной книге нашла отражение только та существенная, но далеко не исчерпывающая часть этих проблем, 1 которая может быть сведена к грамматическому разбору.)
Читателям, которые привыкли иметь дело со «словесными» описаниями математического обеспечения ЭВМ, может показаться необычной последовательно проводимая автором формализация •изложения. Однако, она не должна вызывать особых затруднений, так как основывается на несложных математических построениях с применением элементарных понятий теории множеств. Преимуществами такого способа изложения являются четкость, лаконичность, и единообразие описания различных алгоритмических конструкций, а также, выпуклое выявление основных принципов. Хорошо продумана логическая структура книги. В главе 1 вводятся основные общие понятия, относящиеся к .трансляции и к структурам данных. ' '
„„Глава 2 посвящена трансляции арифметических выражений. На этом"этапе рассмотрена весьма простая постановка задачи трансляции, что позволяет, сразу выявить существо дела.
В главе_3 вводятся формальные модели грамматик. Заметим, что автор избегает традиционной методики изложения теории формальных грамматик в соответствии с ее историческим развитием и пере-' лосит более специальные аспекты этой теории в последнюю часть книги. . .;
? Глава 4 посвящена тем свойствам формальных грамматик, которые имеют непосредственное отношение к проблеме трансляции.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ,...............• . . 5
\
Предисловие............................ 8
1. Предварительные определения................... 1)
1.1. Трансляция......................... 13
1.2. Структуры данных....................... 14
1.3. Математические понятия—множества * ........... 16
1.4. Строки . . . '........................ 18
1:5. Графы . ...........................- 20
1.6. Деревья.............!• • •........... 22
1.7. Обходы деревьев.......... ."............ 24
Задачи............................... 26
2. Трансляция арифметических выражений . ............. 28
2.1. Тройки . ,......................... 28
2.2. Ранние методы........................ 30
2.3. Стековые методы....................... 33
Задачи............................... 36
3. Формальные модели грамматик.................. . 38
-3.1. Синтаксис и семантика , . "...........-........'• -38
3.2. Терминальные символы и синтаксические переменные...... 39
3.3. Синтезирование строк..................... 41
3.4. Определение грамматик.................... 43
3.5. Специальные классы грамматик . ............... 49
. Задачи..............*..'...•........... 53
4. Свойства формальных грамматик.............../. . . 56
4.1. Локализованная структура . ................. 56
4.2. Использование свойства локализации
4.3. Независимость порядка правил поде-
4.4. Графическое представление цепочек правил подстановки
4.3. Независимость порядка правил подстановки; каноническая форма 62
4.5. Двоичные деревья трансляции................. 68
4.6. Свойства двоичных деревьев трансляции........... 69
4.7. Фразы
.... -г—............................. 72
4.8. е-свободные языки. . :................... 73
Задачи..........................-..... 76
5. Структура двоичных деревьев трансляции.............• 79
5.1. Скелеты............ ............... 80
5.2. Упорядочение скелетов.................... 8.2
5.3. Построение скелетов..................... 84
5.4. Расширенный алгоритм цепочек................ 87
Задачи................................. 91
6. Грамматический разбор сверху вниз................. 95
6г1. Упорядочение поиска цепочек................. 95
6.2. Структура данных-...................... 98
6.3. Алгоритм разбора сверху вниз................. 102
6.4. Неоднозначность результата.................. 106
Задачи............................... 108
109
7. Грамматический разбор снизу вверх...............
7.1. Поиск основ......................... '110
7.2. Подстановки и отход..................... 111
7.3. Пример грамматического разбора снизу вверх......... 112
7.4. Структуры данных...................... ИЗ
7.5. Алгоритм разбора снизу вверх................ 114
7.6. Восстановление . ...................... 117
Задачи........'....................... 117
8. Грамматический разбор слева направо............... 119
8.1. Интуитивное описание.............;...... 119
i ' 8.2. Состояния и множества состояний ............... 121
i 8.3. Построение множеств состояний — прямое.......... 122
f 8.4. Построение множеств состояний — замыкание......... 122
i 8.5. Построение множеств состояний — косвенное......... 124
i 8.6. Алгоритм.......................... 125
| 8.7. Состояния и скелеты...................... 127
8.8. Восстановление дерева трансляции...............129
8.9. Пример........................... 131
8.10. Характеристики алгоритма................ . 1#6
Задачи......-........................ . 137
Ограниченные грамматики ,.................... 139
9.1. Прогноз в параллельном грамматическом разборе ....... 140
9.2. Вычисление правых контекстов................ 141
9.3. РН(к)-грамматики...................... 144
9.4. Аналитические и синтетические контексты........... 144
9.5. ЬК(к)-грамматики............v.......... . 146
Мдачи............................... 148
10. Контекстно-ограниченные грамматики
10.1. Грамматический разбор снизу вверх и контекст....... . 152
10.2. Контексты, ограниченные справа............. . 154
10.3. RBC-алгоритм............... ........ 157
10.4. Пример RBC-трансляции . < . .'........'...... 159
10.5. Ограниченные,- контексты.................. 161
Задачи......".....................,. . . . 163
11. Грамматики предшествования................... 165
11.1. Отношения предшествования . , ............. . 167
11.2. Вычисление отношений предшествования — пример...... 168
11.3. Вычисление отношений предшествования — алгоритм ..... 170
11.4. Грамматики предшествования. . .............. 172
• 11.5. Алгоритм трансляции.................... 174
11.6. Функции предшествования................. . 177
Задачи.............................. . 179
Список литературы . . . ...................... 182
Предметный указатель....................... 185