А. шень Издание шестое, дополненное Москва

Название	А. шень Издание шестое, дополненное Москва
Дата	17.09.2022
Размер	1.62 Mb.
Формат файла
Имя файла	shen-progbook.pdf
Тип	Книга #681926
страница	19 из 19

1 ... 11 12 13 14 15 16 17 18 19

(2) Если ситуация [L → U V, t] согласована с SJ (согласно прави- лу (1)), а V начинается на нетерминал K, то SJ принадлежит
Лев(K, s) для всех терминалов s, которые могут начинать слова, выводимые из слова V ∖ K (слово V без первой буквы K),
а также для s = t, если из V ∖ K выводится пустое слово.
(3) Если SJ входит в Лев(L, t) для некоторых L и t, причём
L → V | правило грамматики и V начинается на нетерми- нал K, то SJ принадлежит Лев(K, s) для всех терминалов s,
которые могут начинать слова, выводимые из V ∖ K, а также для s = t, если из V ∖ K выводится пустое слово.

16.4. LR(1)-грамматики, LALR(1)-грамматики
309 16.4.5. Дайте определение LR(1)-конфликтов типа сдвиг/свёртка и свёртка/свёртка.
Решение. Пусть дана некоторая грамматика. Пусть S | произволь- ное слово из терминалов и нетерминалов. Если множество Сост(S) со- держит ситуацию, в которой справа от подчёркивания стоит терми- нал t, то говорят, что для пары ⟨S, t⟩ возможен сдвиг. (Это определение не изменилось по сравнению с SLR(1)-случаем | вторые компоненты пар из Сост(S) не учитываются.)
Если в Сост(S) есть ситуация, в которой справа от подчёркивания ничего нет, а вторым членом пары является терминал t, то говорят,
что для пары ⟨S, t⟩ LR(1)-возможна свёртка (по соответствующему правилу). Говорят, что для пары ⟨S, t⟩ возникает LR(1)-конфликт типа сдвиг/свёртка, если возможны и сдвиг, и свёртка. Говорят, что для па- ры ⟨S, t⟩ возникает LR(1)-конфликт типа свёртка/свёртка, если есть несколько правил, по которым возможна свёртка.

Грамматика называется LR(1)-грамматикой, если в ней нет LR(1)- конфликтов типа сдвиг/свёртка и свёртка/свёртка ни для одной пары
⟨
S, t⟩.
16.4.6. Постройте алгоритм проверки выводимости слова в LR(1)- грамматике.
Решение. Как и раньше, на каждом шаге LR-процесса можно одно- значно определить, какой шаг только и может быть следующим.

Полезно (в частности, для LALR(1)-разбора, см. ниже) понять, как связаны понятия LR(0) и LR(1)-согласованности.
16.4.7. Сформулируйте и докажите соответствующее утверждение.
Ответ. Пусть фиксирована некоторая грамматика. Слово S из тер- миналов и нетерминалов является LR(0)-согласованным с ситуацией
K → U V тогда и только тогда, когда оно LR(1)-согласовано с парой
[K → U V, t] для некоторого терминала t (или для t = EOI). То же самое другими словами: Лев(K) есть объединение Лев(K, t) по всем t. В по- следней форме это совсем ясно.

Замечание. Таким образом, функция Сост(S) в LR(1)-смысле явля- ется расширением функции Сост(S) в LR(0)-смысле: Сост
LR(0)
(S) полу- чается из Сост
LR(1)
(S), если во всех парах выбросить вторые члены.
Теперь мы можем дать определение LALR(1)-грамматики. Пусть фиксирована некоторая грамматика, S | слово из нетерминалов и тер- миналов, t | некоторый терминал (или EOI). Будем говорить, что для

310 16. Синтаксический разбор слева направо (LR)
пары ⟨S, t⟩ LALR(1)-возможна свёртка по некоторому правилу, если существует другое слово S
1
с Сост
LR(0)
(S
0
) = Сост
LR(0)
(S
1
), причём для пары ⟨S
1
, t⟩ LR(1)-возможна свёртка по рассматриваемому правилу.
Далее определяются конфликты (естественным образом), и граммати- ка называется LALR(1)-грамматикой, если конфликтов нет.
16.4.8. Докажите, что любая SLR(1)-грамматика является также и
LALR(1)-грамматикой, а любая LALR(1)-грамматика является также и LR(1)-грамматикой.
[Указание. Это | простое следствие определений.]

16.4.9. Постройте алгоритм проверки выводимости в LALR(1)- грамматике, который хранит в стеке меньше информации, чем соот- ветствующий LR(1)-алгоритм.
[Указание. Достаточно хранить в стеке множества Сост
LR(0)
(S),
поскольку согласно определению LALR(1)-возможность свёртки ими определяется. (Так что сам алгоритм ничем не отличается от SLR(1)- случая, кроме таблицы возможных свёрток.)]

16.4.10. Приведите пример LALR(1)-грамматики, которая не явля- ется SLR(1)-грамматикой.

16.4.11. Приведите пример LR(1)-грамматики, которая не является
LALR(1)-грамматикой.

16.5. Общие замечания о разных методах разбора
Применение этих методов на практике имеет свои хитрости и тон- кости, которых мы не касались. (Например, таблицы следует хранить по возможности экономно.) Часто оказывается также, что для неко- торого входного языка наиболее естественная грамматика не является
LL(1)-грамматикой, но является LR(1)-грамматикой, а также может быть заменена на LL(1)-грамматику без изменения языка. Какой из этих вариантов выбрать, не всегда ясно. Дилетантский совет: если Вы сами проектируете входной язык, то не следует выпендриваться и упо- треблять одни и те же символы для разных целей | и тогда обычно не- сложно написать LL(1)-грамматику или рекурсивный анализатор. Если же входной язык задан заранее с помощью LR(1)-грамматики, не явля- ющейся LL(1)-грамматикой, то лучше её не трогать, а разбирать как есть. При этом могут оказаться полезные средства автоматического

16.5. Общие замечания о разных методах разбора
311
порождения анализаторов, наиболее известными из которых являются yacc (UNIX) и bison (GNU).
Большое количество полезной и хорошо изложенной информации о теории и практике синтаксического разбора имеется в книге Ахо,
Сети и Ульмана (см. список книг для чтения).

Книги для чтения
А. Ахо, Р. Сети, Дж. Ульман. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001.
А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычисли- тельных алгоритмов. М.: Мир, 1979.
Н. Вирт. Систематическое программирование. Введение. М.: Мир, 1977.
Н. Вирт. Алгоритмы + структуры данных = программы. М.: Мир,
1985.
Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. СПб.:
Невский диалект, 2003.
Д. Грис. Наука программирования. М.: Мир, 1984.
М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые за- дачи. М.: Мир, 1982.
Э. Дейкстра. Дисциплина программирования. М.: Мир, 1978.
С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. М.: МЦНМО,
2014.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.
М.: МЦНМО, 2000.
А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков.
М.: Наука, 1988.
В. Липский. Комбинаторика для программистов. М.: Мир, 1988.
Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Те- ория и практика. М.: Мир, 1980.
Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. Введение в теорию автома- тов, языков и вычислений. М.: Вильямс, 2002.

Предметный указатель
𝐴
*
-алгоритм поиска
151
AND-OR-дерево
225
backtracking
60
Borland
4
LALR(1)-грамматика
310
LL(1)-грамматика
289
LL(1)-разбор
286
LR(0)-грамматика
302
LR(1)-грамматика
309
LR-процесс
294
NP-полнота
70
SLR(1)-грамматика
306
Turbo Pascal
4
,
29
АВЛ-дерево
258
автомат конечный
90
,
178
,
190
| | недетерминированный
195
азбука Морзе
231
алгоритм Маккрейта
203
| чередующихся цепей
174
алфавит
180
,
230
альфа-бета-процедура
223
,
224
Б-дерево
267
билеты счастливые, число
58
биномиальный коэффициент
136
ближайшая сумма
31
Бойера { Мура алгоритм
186
бридж-ит, игра
217
буква
230
|, частота
231
быстрое умножение
28
величина потока
161
{
164
,
166
вершина графа
106
,
130
вершинное покрытие
176
ветвей и границ метод
60
вращение левое, правое
259
| малое, большое
259
вывод в грамматике
269
| левый
286
| правый
294
выводимость в КС-грамматике,
полиномиальный алгоритм
273
выигрышные позиции
212
выпуклая оболочка
81
,
110
выражение
272
| регулярное
193
высота
251
гауссовы числа
17
Гейла игра
217
голландский флаг
36
Горнера схема
26
грамматика LALR(1)
310
| LL(1)
289
| LR(0)
302

Предметный указатель
315
Каталана число
55
,
59
,
137
Кёнига теорема
176
Кнута { Морриса { Пратта алгоритм
182
код
230
| Грея
49
| однозначный
230
| префиксный
231
|, средняя длина
232
| Хаффмана
235
{
237
| Шеннона { Фано
237
{
239
кодовое слово
230
количество различных
24
,
80
комментарии вложенные
91
|, удаление
91
конец слова
180
конечный автомат
90
,
178
,
190
| | недетерминированный
195
контекстно-свободная грамматика
269
конфликт свёртка/свёртка
302
,
306
,
309
| сдвиг/свёртка
302
,
306
,
309
коэффициент биномиальный
136
Крафта { Макмиллана неравенство
231
{
234
крестики-нолики, игра
216
критическое ребро
171
КС-грамматика
269
Лев(𝐾)
296
Лев(𝐾, 𝑡)
307
ЛевКонт(𝐾 → 𝑈)
295
ЛевКонт(𝐾 → 𝑈, 𝑡)
307
левый контекст правила
295
Маккрейта алгоритм
199
,
203
максимальное паросочетание
173
{
176
максимальный поток
164
,
169
массив
23
| с минимальным элементом
115
| суффиксов
208
матриц произведение
149
матрица цен
149
матрицы, порядок умножения
138
медиана, поиск
88
,
133
метод потенциалов
151
минимальный разрез
164
,
169
минимум, поиск
84
многоугольника триангуляция
57
многочлен, значение
26
|, производная
27
|, умножение
27
,
28
множество, представление
241
,
244
| | деревом
250
|, реализация в битовом массиве
111
| | перечнем
112
| регулярное
194
|, тип данных
111
множитель
272
моделирование, очередь событий
116
монотонных последовательностей перечисление
47
Морзе азбука
231
наибольший общий делитель
11
наименьшее общее кратное
13
Напр(𝐾 → 𝑉 )
289
Нач(𝑋)
277
,
288
начало слова
180
неассоциативное произведение
139
недетерминированный конечный автомат
195
неориентированный граф
130
неравенство Крафта {
Макмиллана
231
{
234
нетерминал
269

316
Предметный указатель нижние оценки числа сравнений
84
ним, игра
211
НОД
11
НОК
13
обмен значений
8
образец, поиск
178
обратная перестановка
35
| польская запись
144
обход дерева
60
,
220
| | рекурсивный
127
общий элемент (в упорядоченных массивах)
31
опечатки, поиск
249
ориентированный граф
106
орфография, проверка
249
остаточная сеть
164
,
165
остаточный граф
165
,
170
открытая адресация
242
очередь
103
| из двух стеков
104
| приоритетная
115
|, реализация в массиве
103
|, ссылочная реализация
108
ошибка: индекс за границей
29
,
34
,
35
,
73
,
75
паросочетание
173
{
176
паскаль, язык
4
,
29
Паскаля треугольник
57
,
136
перебор с возвратами
60
|, сокращение
223
пересечение регулярных множеств
197
| упорядоченных массивов
31
перестановка обратная
35
,
53
| частей массива
25
|, чётность
35
перестановок перечисление
44
,
52
,
124
период десятичной дроби
20
поддерево
251
подмножеств перечисление
44
,
45
подпоследовательность максимальная возрастающая
41
| общая
40
|, проверка
40
подслово
180
|, поиск
182
,
185
,
186
,
188
позиции в суффиксном дереве
200
| проигрышные и выигрышные
212
поиск 𝐴
*
-алгоритм
151
| 𝑘-го по порядку
88
,
133
,
257
| в глубину
153
| в ширину
114
,
152
| двоичный
33
| кратчайшего пути
146
| минимума
84
| образца
186
,
188
,
190
| одного из слов
191
| подслова
178
,
182
,
185
,
186
,
188
| представителя большинства
88
Посл(𝑋)
277
Послед(𝑋)
288
последовательности монотонные,
перечисление
125
последовательность, содержащая все слова длины 𝑛
108
постфиксная запись
144
потенциал
151
поток
157
,
159
| через разрез
162
потомок вершины
121
права авторские
4
предпоток
164
приведение
294
приоритетная очередь
115
программа сжатия информации
240

Предметный указатель
317
программирование динамическое
135
,
137
,
273
проигрышные позиции
212
произведение многочленов
27
| неассоциативное
56
,
139
пропускная способность
159
| | разреза
163
,
164
,
166
простые множители
15
путей число
150
Рабина алгоритм
188
разбиений на слагаемые перечисление
48
,
126
| | число
57
разбор LL(1)
286
| LR(1)
294
|, общий КС-алгоритм
273
|, рекурсивный спуск
275
разложение на множители
15
размещения с повторениями
43
,
123
разрез
157
,
159
,
162
расстановки функция
241
расширение индуктивное
39
ребро графа
130
регулярное выражение
193
| множество
194
| |, дополнение
197
| |, пересечение
197
рекурсивная программа
117
рекурсивный спуск
275
рекурсия
117
|, устранение
135
ретроспективный анализ игры
227
рюкзак, заполнение
70
,
140
свёртка
294
связная компонента неориентированного графа
130
| | ориентированного графа
113
,
131
,
152
связный граф
106
сдвиг
294
сеть
157
,
159
,
162
сжатие информации
240
сжатое суффиксное дерево
199
символ
230
|, код
230
| начальный
269
| нетерминальный
269
| терминальный
269
ситуация грамматики
297
скобки, правильность
98
,
270
скобок расстановка
56
слагаемое
272
слияние упорядоченных массивов
30
слово
180
| выводимое
269
сортировка 𝑛 log 𝑛
73
| деревом
75
,
115
| квадратичная
72
|, нижняя оценка сложности
82
| слиянием
73
,
80
| топологическая
128
,
155
| Хоара (быстрая)
80
,
132
| | нерекурсивная
143
| цифровая
83
|, число сравнений
82
Сост(𝑆)
298
составные символы, замена
90
сочетаний число
57
,
136
ссылки суффиксные
201
стек
96
|, два в массиве
100
| отложенных заданий
141
|, реализация в массиве
97
|, ссылочная реализация
100
стековый калькулятор
144
степень, быстрое вычисление
9

318
Предметный указатель
|, вычисление
9
|, рекурсивная программа
118
сток
160
стратегия в игре
214
| позиционная
214
суммарная величина потока
161
{
164
,
166
суммирование массива рекурсивное
120
суффикс
199
суффиксное дерево
197
,
199
суффиксные ссылки
201
суффиксный массив
208
счастливые билеты, число
58
теорема Кёнига
176
| Форда { Фалкерсона
164
| Холла о представителях
176
,
177
| Цермело
214
терминал
269
| направляющий
289
топологическая сортировка
128
,
155
треугольник Паскаля
136
триангуляция многоугольника
57
,
137
упорядоченное дерево
251
факториал
11
|, рекурсивная программа
117
ферзей расстановка
60
Фибоначчи последовательность
11
,
137
,
258
| |, быстрое вычисление
11
Флойда алгоритм
147
,
197
Форда { Беллмана алгоритм
146
функция индуктивная
38
| расстановки
241
ханойские башни, нерекурсивная программа
140
| |, рекурсивная программа
119
Хаффмана код
235
{
237
хеш-функция
241
|, универсальное семейство
246
,
248
хеширование
241
|, оценка числа действий
246
| с открытой адресацией
242
| со списками
244
| универсальное
246
Хоара сортировка
80
,
132
| | нерекурсивная
143
хорды окружности
57
целые точки в круге
18
цена игры
212
,
214
| |, вычисление
220
Цермело теорема
214
цикл эйлеров (по всем рёбрам графа)
106
циркуляция
172
частота буквы
231
чётность перестановки
35
число Каталана
55
,
59
,
137
| общих элементов
28
| разбиений
57
| сочетаний
57
| счастливых билетов
58
Шеннона { Фано код
237
{
239
энтропия Шеннона
238
язык контекстно-свободный
269
| не контекстно-свободный
271

Указатель имён
Адельсон-Вельский, Г. М. 258
Ахо (Aho, A. V.) 70, 197, 311, 312
Баур (Baur, W.) 27
Брудно, А. Л. 25, 228
Вазирани (Vasirani, U.) 312
Вайнцвайг, М. Н. 40
Варсанофьев, Д. В. 40, 248
Вирт (Wirth, N.) 312
Вьюгин, М. В. 42
Гарднер (Gardner, M.) 217
Гасфилд (Gus˛eld, D.) 312
Гейл (Gale, D.) 217, 219
Грис (Gries, D.) 25, 31, 34, 41, 312
Гросс (Gross, Oliver) 218
Гэри (Garey, M. R.) 70, 312
Дасгупта (Dasgupta, S.) 312
Дейкстра (Dijkstra, E. W.) 13, 21,
36, 312
Део (Deo, N.) 268, 312
Джонсон (Johnson, D. S.) 70, 312
Диментман, А. М. 40
Звонкин, А. К. 141
Звонкин, Д. 14
Карп (Karp, R. M.) 169, 171, 172,
174
Каталан (Catalan, C. E.) 55, 59,
137
Кёниг (K}onig, D.) 176
Кнут (Knuth, D. E.) 182
Коган, А. Г. 37
Кормен (Cormen, T.) 312
Крафт (Kraft, L. C.) 231, 233
Кушниренко, А. Г. 25, 27, 38, 104,
105, 312
Ландис, Е. М. 258
Лебедев, Г. В. 312
Лейзерсон (Leiserson, C.) 312
Липский (Lipski, W.) 312
Лисовский, Анджей 141
Макмиллан (McMillan, B.) 231,
233
Матиясевич, Ю. В. 4, 21, 182
Мотвани (Motvani, R.) 312
Нивергельт (Nievergelt, J.) 268,
312
Пападимитриу
(Papadimitriou,
C.) 312
Паскаль (Pascal, B.) 4, 136
Рейнгольд (Reingold, E. M.) 268,
312
Ривест (Rivest, R.) 312
Сети (Sethi, R.) 197, 311, 312
Сэвич (Walter Savitch) 132
Торхов, Ю. Н. 4
Ульман (Ullman, J. D.) 70, 197, 311,
312
Фалкерсон (Fulkerson, D. R.) 164,
166{168, 171, 175, 176
Фано (Fano, R. M.) 237
Форд (Ford, L. R., Jr.) 164, 166{
168, 171, 175, 176
Хоар (Hoare, C. A. R.) 3, 132, 143

320
Предметный указатель
Холл (Hall, P.) 176, 177
Хопкрофт (Hopcroft, J.) 70, 312
Цвик (Zwick, U.) 167
Шеннон (Shannon, C.) 218, 237,
238
Штрассен (Strassen, V.) 27
Эдмондс (Edmonds, J. R.) 169, 171,
172, 174

Научно-популярное издание
Александр Шень
ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ
Оригинал-макет: В. Шувалов
Дизайн обложки: У. Сопова
Подписано в печать 25.08.2016 г. Формат 60 × 90 1
/
16
. Бумага офсетная.
Печать офсетная. Печ. л. 20. Тираж 2000 экз. Заказ Ђ
Издательство Московского центра непрерывного математического образования.
119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-08-04.
Отпечатано в ООО «Типография "Миттель Пресс\».
г. Москва, ул. Руставели, д. 14, стр. 6.
Тел./факс +7 (495) 619-08-30, 647-01-89.
E-mail: mittelpress@mail.ru
Книги издательства МЦНМО можно приобрести в магазине
«Математическая книга», Москва, Большой Власьевский пер., д. 11.
Тел. (495) 745-80-31. E-mail: biblio@mccme.ru

1 ... 11 12 13 14 15 16 17 18 19