В предлагаемойвниманию читателей монографии Ф. Вайнгартена освещается взаимопроникновение двух научных дисциплин: методов трансляции языков программирования и теории формальных грамматик, которая является одной из основ трансляции. Автору удалось при сравнительно небольшом объеме книги четко, строго и в то же время достаточно наглядно проанализировать и систематизировать накопленный за многие годы теоретиками и создателями математического обеспечения опыт разработки эффективных алгоритмов трансляции, базирующихся на грамматическом разборе входной строки. (Заметим, что обычно под трансляцией понимается весь Ки,„,п>текс проблем перевода исходной программы в эквивалентную программу. В данной книге нашла отражение только та существенная, но далеко не исчерпывающая часть этих проблем, которая может быть сведена к грамматическому разбору.)
Читателям, которые привыкли иметь дело со «словесными» описаниями математического обеспечения ЭВМ, может показаться -необычной последовательно проводимая автором формализация изложения. Однако она не должна вызывать особых затруднений, так как основывается на несложных математических построениях с применением элементарных понятий теории множеств. Преимуществами такого способа изложения являются четкость, -лаконичность и единообразие описания различных алгоритмических конструкций, а также, выпуклое.выявление основных принципов. Хорошо продумана логическая структура книги. В главе 1 вводятся основные общие понятия, относящиеся к трансляции и к структурам данных.
I лава 2 посвящена трансляции арифметических выражений. На этом этапе рассмотрена весьма простая постановка задачи трансляции, что позволяет, сразу выявить существо дела.
ts главе 3 вводятся формальные модели грамматик. Заметим, что нш^ Избегает традиционной методики изложения теории формаль-носиГ^лММа™К В соответствии с ее историческим развитием и перекниги е спеЧиальные аспекты этой теории в последнюю часть
т->
торые^им 4 ПОСВЯ1чена тем свойствам формальных грамматик, ко-имеют непосредственное отношение к проблеме трансляции.
В первую очередь автор обсуждает возможности использования локализованной структуры контекстно-свободных грамматик, допускающих независимый параллельный разбор различных частей предложения. Далее внимание концентрируется на деревьях грамматического разбора; при этом четко прослеживается связь этих деревьев с решением соответствующей задачи трансляции. Автор особо останавливается на свойствах двоичных деревьев трансляции, которые наиболее удобны для представления в машинной памяти'.
В последующих главах обсуждается трансляция предложений, порождаемых контекстно-свободными грамматиками. Далее на грамматики накладываются специальные ограничения, позволяющие получать более быстрые трансляторы.
В главе 5 вводятся и изучаются необходимые для последующих рассмотрений характеристики структуры двоичных деревьев трансляции.
Глава 6 посвящена алгоритму грамматического разбора сверху вниз. В литературе имеется много вариантов такого универсального алгоритма.. Выбранный автором вариант отличается простотой и наглядностью, что дает читателю возможность получить качественную картину изучаемого процесса. В главах 7 и 8 описаны другие универсальные алгоритмы разбора предложений в произвольных контекстно-свободных языках, обеспечивающие во многих случаях более эффективную трансляцию.
Часто на практике приходится иметь дело, с языками программирования, для которых не требуется всего многообразия возможностей, заложенных в понятии произвольной контекстно-свободной грамматики. К таким языкам удается применять специальные более эффективные методы трансляции, которые существенно сокращают или полностью исключают трудоемкие «пробы и ошибки», неизбежные при использовании универсальных методов разбора предложений в произвольном контекстно-свободном языке.
В главе 9 на языки накладываются некоторые естественные ограничения, что позволяет ускорить алгоритмы разбора за счет использования контекстной информации.
В главе 10 вводятся несколько более сильные ограничения, которые позволяют транслировать тексты на соответствующих контекстно-ограниченных языках только «наверняка», т. е. не затрачивая времени на неудачные попытки разбора. Еще большей эффективности трансляции удается добиться при использований грамматик предшествования, которым посвящена последняя глава книги.
Углубленному восприятию излагаемого материала способствуют удачно подобранные задачи для самостоятельного решения, которые приводятся в конце каждой главы. •
При переводе английских терминов на русский язык мы стара'; лись придерживаться прецедентов, имеющихся в русской литер*')
туре по теории формальных грамматик. При отсутствии единообпя зия в русской терминологии мы выбирали более распространенные" а в нескольких случаях более естественные, с нашей точки зрения' варианты. В частности, английский термин backtracking означаю щии продвижение по дереву в обратном направлении по?ле неудач" ГномГхоГ^^^
перевода (возврат, обратное npS^J^npTSS^1?™ менее подходящими. ' надбавляются нам
» В. В. Мартынюк
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ................... g
Предисловие............................. 8
1. Предварительные определения , , ................. ц
.1. Трансляция . . ....................... 13
.2. Структуры данных...................... 14
.3. Математические понятия — множества . ........... 16
.4. Строки . . . -........................ 18
: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. Синтаксис и семантика.................... чо
3.2. Терминальные символы и синтаксические переменные...... **
3.3. Синтезирование строк..................... ,\
3.4. Определение грамматик.................... 1д
3.5. Специальные классы грамматик................ со
. Задачи..............^................
4. Свойства формальных грамматик...............'• '
56
4.1. Локализованная структура . ,................ 59
4.2. Использование свойства локализации...........' ' ' g2
4.3. Независимость порядка правил подстановки; каноническая форм ^
4.4. Графическое представление цепочек правил подстановки . • •
4.5. Двоичные деревья трансляции. ,............... 6i
4.6. Свойства двоичных деревьев трансляции........... 6?
4.7. Фразы........................... . 7?
4.8. е-свободные языки...................... 7Э
Задачи............................... 76
5. Структура двоичных деревьев трансляции............. 79
5.1. Скелеты . .......................... SO
5.2. Упорядочение скелетов.................... 82
5.3. Построение скелетов..................... 84
5.4. Расширенный алгоритм цепочек................ 87
Задачи............................... 91
6. Грамматический разбор сверху вниз................. 95
6.1. Упорядочение поиска цепочек................. 95
6.2. Структура данных...................... 98
6.3. Алгоритм разбора сверху вниз................. 102
6.4. Неоднозначность результата.................. 106
Задачи............................... 108
7. Грамматический разбор снизу вверх................ 109
7.1. Поиск основ......................... 110
7.2. Подстановки и отход..................... 111
7.3. Пример грамматического разбора снизу вверх......... 112
7.4. Структуры данных...................... 113
7.5. Алгоритм разбора снизу вверх................ 114
7.6. Восстановление....................... 117
Задачи............................... 117
8. Грамматический разбор слева направо............... 119
8.1. Интуитивное описание..............•...... 119
8.2. Состояния и множества состояний ............ . . 121
8.3. Построение множеств состояний — прямое.......... 122
8.4. Построение множеств состояний — замыкание......... 122
8.5. Построение множеств состояний — косвенное......... 124
8.6. Алгоритм.......................... 125
8.7. Состояния и скелеты................,..... 127
8.8. Восстановление дерева трансляции.............. 129
8.9. Пример........................... 131
8.10. Характеристики алгоритма................ . 136
«дачи............................... 137
• Ограниченные грамматики ,................... . 139
9.1. Прогноз в параллельном грамматическом разборе ....... 140
9.2. Вычисление правых контекстов................ 141
9.3. РК(1<)-грамматики...................... 144
9.4. Аналитические и синтетические контексты........... 144
9.5. Ь1?(к)-грамматики...................... 146
аДачи.......,..............."......... 148
10. Контекстно-ограниченные грамматики .............. 151
10.1. Грамматический разбор снизу вверх и контекст....... . 152
10.2. Контексты, ограниченные справа.............. 154
10.3. RBC-алгоритм..............'......... 157
10.4. Пример RBC-трансляции . t . ;........'...... 159
10.5. Ограниченные, контексты.................. 161
Задачи......~...................... . . . 163
11. Грамматики предшествования . ,................. 165
11.1. Отношения предшествования . t .............. 167
11.2. Вычисление отношений предшествования — пример...... 168
11.3. Вычисление отношений предшествования—-алгоритм..... 170
11.4. Грамматики предшествования................ 172
- 11.5. Алгоритм трансляции.................... 174
11.6. Функции предшествования.................. 177
Задачи.............................. . 179
Список литературы......................... 182
Предметный указатель .........'.............. 185
Цена: 100руб.
