А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва

жүктеу/скачать 1,66 Mb.

Pdf көрінісі

бет	8/9
Дата	04.11.2023
өлшемі	1,66 Mb.
	#122042
түрі	Книга

1 2 3 4 5 6 7 8 9

Байланысты:
теория

часть входа обозначаем через A):
1) слово AS выводимо в грамматике;
2) любой левый вывод входного слова проходит через стадию AS
Эти свойства вместе будем обозначать «(И)».
Вначале A пусто, а S состоит из единственного символа | началь-
ного нетерминала.
Если в некоторый момент S начинается на терминал t и t = Next,
то можно выполнить команду Move и удалить символ t, являющийся
начальным в S, поскольку при этом AS не меняется.
Если S начинается на терминал t и t
̸
= Next, то входное слово не-
выводимо | ибо по условию любой его вывод должен проходить через
AS. (Это же справедливо и в случае Next = EOI.)
Если S пусто, то из условия (И) следует, что входное слово выводимо
тогда и только тогда, когда Next = EOI.
Остаётся случай, когда S начинается с некоторого нетерминала K.
По доказанному выше все левые выводы из S слов, начинающихся на
символ Next, начинаются с применения к S одного и того же правила |
того, для которого Next принадлежит направляющему множеству. Если
таких правил нет, то входное слово невыводимо. Если такое правило
есть, то нужно применить его к первому символу слова S | при этом
свойство (И) не нарушится. Приходим к такому алгоритму:
s := пустое слово;
error := false;
{error => входное слово невыводимо;}
{not error => (И)}
while (not error) and not ((Next=EOI) and (S пусто))
do begin
if (S начинается на терминал, равный Next) then begin
Move; удалить из S первый символ;
end else if (S начинается на терминал, не равный Next)
then begin
error := true;
end else if (S пусто) and (Next <> EOI) then begin
error := true;
end else if (S начинается на нетерминал и Next входит в
направляющее множество одного из правил для этого
нетерминала) then begin
применить это правило

15.3. Алгоритм разбора для LL(1)-грамматик
291
end else if (S начинается на нетерминал и Next не входит
в направляющее множество ни одного из правил для этого
нетерминала) then begin
error := true;
end else begin
{так не бывает}
end;
end;
{входное слово выводимо <=> not error}
Алгоритм заканчивает работу, поскольку при появлении терминала
в начале слова S происходит чтение со входа или остановка, а бесконеч-
ный цикл сменяющих друг друга нетерминалов в начале S означал бы,
что грамматика леворекурсивна. (А мы можем предполагать, согласно
предыдущей задаче, что это не так: нетерминалы, не встречающиеся
в выводах, а также нетерминалы, из которых не выводится непустого
слова, несложно удалить из грамматики.)
Замечания.
•
Приведённый алгоритм использует S как стек (все действия про-
изводятся с левого конца).
•
Действия двух последних вариантов внутри цикла не приводят
к чтению очередного символа со входа, поэтому их можно зара-
нее предвычислить для каждого нетерминала и каждого символа
Next. После этого на каждом шаге цикла будет читаться очеред-
ной символ входа.
•
При практической реализации удобно составить таблицу, в ко-
торой записаны варианты действий в зависимости от входного
символа и первого символа S, и небольшую программу, выполня-
ющую действия в соответствии с этой таблицей.
15.3.9. При проверке того, относится ли данная грамматика к типу
LL(1), необходимо вычислить Послед(𝑇 ) и Нач(𝑇 ) для всех нетермина-
лов 𝑇 . Как это сделать?
Решение. Пусть, например, в грамматике есть правило 𝐾
→
𝐿 𝑀 𝑁.
Тогда
Нач (𝐿)
⊂
Нач (𝐾),
Нач (𝑀)
⊂
Нач (𝐾),
если из 𝐿 выводимо пустое слово,
Нач (𝑁)
⊂
Нач (𝐾),
если из 𝐿 и 𝑀 выводимо пустое слово,

292
15. Контекстно-свободные грамматики
Послед (𝐾)
⊂
Послед (𝑁),
Послед (𝐾)
⊂
Послед (𝑀), если из 𝑁 выводимо пустое слово,
Послед (𝐾)
⊂
Послед (𝐿),
если из 𝑀 и 𝑁 выводимо пустое слово,
Нач (𝑁)
⊂
Послед (𝑀),
Нач (𝑀)
⊂
Послед (𝐿),
Нач (𝑁)
⊂
Послед (𝐿),
если из 𝑀 выводимо пустое слово.
Подобные правила позволяют шаг за шагом порождать множества
Нач(𝑇 ), а затем и Послед(𝑇 ), для всех терминалов и нетерминалов 𝑇 .
При этом началом служит
EOI
∈
Послед (𝐾)
для начального нетерминала 𝐾 и
𝑧
∈
Нач (𝑧)
для любого терминала 𝑧. Порождение заканчивается, когда приме-
нение правил перестаёт давать новые элементы множеств Нач(𝑇 )
и Послед(𝑇 ).

16. СИНТАКСИЧЕСКИЙ РАЗБОР
СЛЕВА НАПРАВО (LR)
Сейчас мы рассмотрим ещё один метод синтаксического разбора,
называемый LR(1)-разбором, а также некоторые упрощённые его ва-
рианты.
16.1. LR-процессы
Два отличия LR(1)-разбора от LL(1)-разбора: во-первых, строится
не левый вывод, а правый, во-вторых, он строится не с начала, а с
конца. (Вывод в КС-грамматике называется правым, если на каждом
шаге замене подвергается самый правый нетерминал.)
16.1.1. Докажите, что если слово, состоящее из терминалов, выво-
димо, то оно имеет правый вывод.
Нам будет удобно смотреть на правый вывод «задом наперёд». Опре-
делим понятие LR-процесса над словом 𝐴. В этом процессе, помимо 𝐴,
будет участвовать и другое слово 𝑆, которое может содержать как тер-
миналы, так и нетерминалы. Вначале слово 𝑆 пусто. В ходе LR-процесса
разрешены два вида действий:
(1) можно перенести первый символ слова 𝐴 (его называют очередным
символом и обозначают Next) в конец слова 𝑆, удалив его из 𝐴
(это действие называют сдвигом);
(2) если правая часть одного из правил грамматики оказалась концом
слова 𝑆, то разрешается заменить её на нетерминал, стоящий в ле-
вой части этого правила; при этом слово 𝐴 не меняется. (Это дей-
ствие называют свёрткой, или приведением.)
Отметим, что LR-процесс не является детерминированным: в одной
и той же ситуации могут быть разрешены разные действия.

294
16. Синтаксический разбор слева направо (LR)
Говорят, что LR-процесс на слове 𝐴 успешно завершается, если сло-
во 𝐴 становится пустым, а в слове 𝑆 остаётся единственный нетерми-
нал | начальный нетерминал грамматики.
16.1.2. Докажите, что для любого слова 𝐴 (из терминалов) успеш-
но завершающийся LR-процесс существует тогда и только тогда, когда
слово 𝐴 выводимо в грамматике. В ходе доказательства установите вза-
имно однозначное соответствие между правыми выводами и успешно
завершающимися LR-процессами.
Решение. При сдвиге слово 𝑆𝐴 не меняется, при свёртке слово 𝑆𝐴
подвергается преобразованию, обратному шагу вывода. Этот вывод
будет правым, так как сворачивается конец 𝑆, а в 𝐴 все символы |
терминальные. Таким образом, каждому LR-процессу соответствует
правый вывод. Обратное соответствие: пусть дан правый вывод. Пред-
ставим себе, что за последним нетерминалом в слове стоит перегород-
ка. Применив к этому нетерминалу правило грамматики, мы должны
сдвинуть перегородку влево (если правая часть правила кончается на
терминал). Разбивая этот сдвиг на отдельные шаги, получим процесс,
в точности обратный LR-процессу.
Поскольку в ходе LR-процесса все изменения в слове 𝑆 происходят
с правого конца, слово 𝑆 называют стеком LR-процесса.
Задача построения правого вывода для данного слова сводится, та-
ким образом, к правильному выбору очередного шага LR-процесса.
Нам нужно решить, будем ли мы делать сдвиг или свёртку, и если
свёртку, то по какому правилу | ведь подходящих правил может быть
несколько. В LR(1)-алгоритме это решение принимается на основе 𝑆
и первого символа слова 𝐴; если используется только 𝑆, то говорят
о LR(0)-алгоритме. (Точные определения см. ниже.)
Пусть фиксирована грамматика, в которой из любого нетерминала
можно вывести какое-либо слово из терминалов. (Это ограничение мы
будет всегда предполагать выполненным.)
Пусть K
→
U | одно из правил грамматики (K | нетерминал, U |
слово из терминалов и нетерминалов). Определим множество слов (из
терминалов и нетерминалов), называемое левым контекстом правила
K
→
U. (Обозначение: ЛевКонт(K
→
U).) По определению в него входят
все слова, которые являются содержимым стека непосредственно перед
свёрткой U в K в ходе некоторого успешно завершающегося LR-про-
цесса.
16.1.3. Переформулируйте это определение на языке правых выво-
дов.

16.1. LR-процессы
295
Решение. Рассмотрим все правые выводы вида
⟨
начальный нетерминал
⟩
XKA
→
XUA,
где A | слово из терминалов, X | слово из терминалов и нетерминалов.
Все возникающие при этом слова XU и образуют левый контекст прави-
ла K
→
U. Чтобы убедиться в этом, следует вспомнить, что мы предпо-
лагаем, что из любого нетерминала можно вывести какое-то слово из
терминалов, так что правый вывод слова XUA может быть продолжен
до правого вывода какого-то слова из терминалов.
16.1.4. Все слова из ЛевКонт(K
→
U) кончаются, очевидно, на U. До-
кажите, что если у всех них этот конец U отбросить, то полученное
множество слов не зависит от того, какое из правил для нетерминала K
выбрано. (Это множество обозначается Лев(K).)
Решение. Из предыдущей задачи ясно, что Лев(K) | это всё, что
может появиться в правых выводах левее самого правого нетермина-
ла K.
16.1.5. Докажите, что в предыдущей фразе можно отбросить слова
«самого правого»: Лев(K) | это всё то, что может появляться в правых
выводах левее любого вхождения нетерминала K.
Решение. Продолжив построение правого вывода, все нетерминалы
справа от K можно заменить на терминалы (а слева от K при этом ничего
не изменится).
16.1.6. Постройте грамматику, содержащую для каждого нетер-
минала K исходной грамматики нетерминал
⟨
ЛевK
⟩
, причём следую-
щее свойство должно выполняться для любого нетерминала K исходной
грамматики: в новой грамматике из
⟨
ЛевK
⟩
выводимы все элементы
Лев(K) и только они. (При этом терминалы и нетерминалы исходной
грамматики являются терминалами новой.)
Решение. Пусть P | начальный нетерминал грамматики. Тогда в
новой грамматике будет правило
⟨
ЛевP
⟩ →
(пустое слово)
Для каждого правила исходной грамматики, например, правила
K
→
L t M N
(L, M, N | нетерминалы, t | терминал),

296
16. Синтаксический разбор слева направо (LR)
в новую грамматику мы добавим правила
⟨
ЛевL
⟩ → ⟨
ЛевK
⟩
⟨
ЛевM
⟩ → ⟨
ЛевK
⟩
L t
⟨
ЛевN
⟩ → ⟨
ЛевK
⟩
L t M
и аналогично поступим с другими правилами. Смысл новых правил
таков: пустое слово может появиться слева от P; если слово X может
появиться слева от K, то X может появиться слева от L, XLt может по-
явиться слева от M, XLtM | слева от N. Индукцией по длине правого
вывода легко проверить, что всё, что может появиться слева от како-
го-то нетерминала, появляется в соответствии с этими правилами.
16.1.7. Почему в предыдущей задаче важно, что мы рассматриваем
только правые выводы?
Ответ. В противном случае следовало бы учитывать преобразова-
ния, происходящие внутри слова, стоящего слева от K.
16.1.8. Для данной грамматики постройте алгоритм, который по
любому слову выясняет, каким из множеств Лев(K) оно принадлежит.
(Замечание для знатоков. Существование такого алгоритма | и да-
же конечного автомата, то есть индуктивного расширения с конечным
числом значений, см. раздел
1.3
, | вытекает из предыдущей задачи,
так как построенная в ней грамматика имеет специальный вид: в пра-
вых частях всего один нетерминал, причём он стоит у левого края. Тем
не менее мы приведём явное построение.)
Решение. Будем называть ситуацией данной грамматики одно из её
правил, в правой части которого отмечена одна из позиций (до первой
буквы, между первой и второй буквой, . . . , после последней буквы).
Например, правило
K
→
L t M N
(K, L, M, N | нетерминалы, t | терминал) порождает пять ситуаций
K
→
L t M N
K
→
L t M N
K
→
L t M N
K
→
L t M N
K
→
L t M N
(позиция указывается знаком подчёркивания).
Будем говорить, что слово S согласовано с ситуацией K
→
U V, если
S кончается на U, то есть S = TU при некотором T, и, кроме того, T при-
надлежит Лев(K). (Смысл этого определения примерно таков: в стеке S

16.1. LR-процессы
297
подготовлена часть U для будущей свёртки UV в K.) В этих терминах
ЛевКонт(K
→
X) | это множество всех слов, согласованных с ситуацией
K
→
X , а Лев(K) | это множество всех слов, согласованных с ситуацией
K
→
X (где K
→
X | любое правило для нетерминала K).
Эквивалентное определение в терминах LR-процесса: S согласовано
с ситуацией K
→
U V, если существует успешный LR-процесс, в котором
события развиваются так:
•
в ходе процесса в стеке появляется слово S, и оно оканчивается
на U;
•
некоторое время S не затрагивается, а справа от него появляет-
ся V;
•
UV сворачивается в K;
•
процесс продолжается и успешно завершается.
16.1.9. Докажите эквивалентность этих определений.
[Указание. Если S = TU и T принадлежит Лев(K), то можно получить
в стеке сначала T, потом U, потом V, потом свернуть UV в K и затем
успешно завершить процесс. (Мы используем несколько раз тот факт,
что из любого нетерминала что-то да выводится: благодаря этому мы
можем добавить в стек любое слово.)]
Наша цель | построение алгоритма, распознающего принадлеж-
ность произвольного слова к Лев(K). Рассмотрим функцию, сопоста-
вляющую с каждым словом S (из терминалов и нетерминалов) множе-
ство всех согласованных с ним ситуаций. Это множество назовём со-
стоянием, соответствующим слову S. Будем обозначать его Сост(S).
Достаточно показать, что функция Сост(S) индуктивна, то есть что
значение Сост(SJ), где J | терминал или нетерминал, может быть вы-
числено, если известно Сост(S) и символ J. (Мы видели ранее, как при-
надлежность к Лев(K) выражается в терминах этой функции.) Значение
Сост(SJ) вычисляется по таким правилам:
(1) Если слово S согласовано с ситуацией K
→
U V, причём
слово V начинается на букву J, то есть V = JW, то SJ согла-
совано с ситуацией K
→
UJ W.

298
16. Синтаксический разбор слева направо (LR)
Это правило полностью определяет все ситуации с непустой левой
половиной (то есть не начинающиеся с подчёркивания), согласованные
с SJ. Осталось определить, для каких нетерминалов K слово SJ принад-
лежит Лев(K). Это делается по двум правилам:
(2) Если ситуация L
→
U V согласована с SJ (согласно прави-
лу (1)), а V начинается на нетерминал K, то SJ принадлежит
Лев(K).
(3) Если SJ входит в Лев(L) для некоторого L, причём L
→
→
V | правило грамматики и V начинается на нетерминал K,
то SJ принадлежит Лев(K).
Заметим, что правило (3) можно рассматривать как аналог правила
(2): в указанных в (3) предположениях ситуация L
→
V согласована
с SJ, а V начинается на нетерминал K.
Корректность этих правил в общем-то очевидна, если хорошень-
ко подумать. Единственное, что требует некоторых пояснений | это
то, почему с помощью правил (2) и (3) обнаружатся все терминалы K,
для которых SJ принадлежит Лев(K). Попытаемся это объяснить. Рас-
смотрим правый вывод, в котором SJ стоит слева от K. Откуда мог
взяться в нём нетерминал K? Если правило, которое его породило, по-
родило также и конец слова SJ, то принадлежность SJ к Лев(K) будет
обнаружена по правилу (2). Если же K было первой буквой слова, поро-
ждённого каким-то другим нетерминалом L, то | благодаря правилу
(3) | достаточно установить принадлежность SJ к Лев(L). Осталось
применить те же рассуждения к L и так далее.
В терминах LR-процесса то же самое можно сказать так. Сначала
нетерминал K может участвовать в нескольких свёртках, не затраги-
вающих SJ (они соответствуют применению правила (3) ), но затем он
обязан подвергнуться свёртке, затрагивающей SJ (что соответствует
применению правила (2) ).
Осталось выяснить, какие ситуации согласованы с пустым словом,
то есть для каких нетерминалов K пустое слово принадлежит Лев(K).
Это определяется по следующим правилам:
(1) начальный нетерминал таков;
(2) если K таков и K
→
V | правило грамматики, причём
слово V начинается с нетерминала L, то и L таков.

16.2. LR(0)-грамматики
299
16.1.10. Проделайте описанный анализ для грамматики
E
→
E + T
E
→
T
T
→
T * F
T
→
F
F
→
x
F
→
( E )
(задающей тот же язык, что и грамматика примера 3, с.
Решение. Множества Сост(S) для различных S приведены в таблице
на с.
еся значениями функции Сост(S) на словах, стоящих слева и справа от
знака равенства, одинаковы.
Правило определения Сост(SJ), если известны Сост(S) и J (здесь S |
слово из терминалов и нетерминалов, J | терминал или нетерминал),
таково:
надо найти Сост(S) в правой колонке, взять соответствую-
щее ему слово T в левой колонке, приписать к нему J и взять
множество, стоящее напротив слова TJ (если слово TJ в та-
блице отсутствует, то Сост(SJ) пусто).
16.2. LR(0)-грамматики
Напомним, что наша основная цель | это поиск вывода заданного
слова, или, другими словами, поиск успешного LR-процесса над ним. Во
всех рассматриваемых нами грамматиках успешный LR-процесс (над
данным словом) единствен. Искать этот единственный успешный про-
цесс мы будем постепенно: в каждый момент мы смотрим, какой шаг
возможен следующим. Для этого на грамматику надо наложить допол-
нительные требования, и сейчас мы рассмотрим простейший случай
так называемых LR(0)-грамматик. Мы уже знаем:
(1) В успешном LR-процессе возможна свёртка по правилу
K
→
U при содержимом стека S тогда и только тогда, когда
S принадлежит ЛевКонт(K
→
U) или, другими словами, когда
слово S согласовано с ситуацией K
→
U .

300
16. Синтаксический разбор слева направо (LR)
Слово S Сост(S)
пустое
E
→
E+T E
→
T T
→
T*F
T
→
F F
→
x F
→
(E)
E
E
→
E +T
T
E
→
T
T
→
T *F
F
T
→
F
x
F
→
x
(
F
→
( E) E
→
E+T E
→
T
T
→
T*F T
→
F F
→
x F
→
(E)
E+
E
→
E+ T T
→
T*F T
→
F
F
→
x F
→
(E)
T*
T
→
T* F F
→
x F
→
(E)
(E
F
→
(E ) E
→
E +T
(T
= T
(F
= F
(x
= x
((
= (
E+T
E
→
E+T
T
→
T *F
E+F
= F
E+x
= x
E+(
= (
T*F
T
→
T*F
T*x
= x
T*(
= (
(E)
F
→
(E)
(E+
= E+
E+T*
= T*
К задаче

16.2. LR(0)-грамматики
301
Аналогичное утверждение про сдвиг гласит:
(2) В успешном LR-процессе при содержимом стека S воз-
можен сдвиг с очередным символом a тогда и только тогда,
когда S согласовано с некоторой ситуацией K
→
U aV.
16.2.1. Докажите это.
[Указание. Пусть произошёл сдвиг и к стеку S добавилась буква a.
Рассмотрите первую свёртку, затрагивающую эту букву.]
Рассмотрим некоторую грамматику и произвольное слово S из тер-
миналов и нетерминалов. Если множество Сост(S) содержит ситуацию,
в которой справа от подчёркивания стоит терминал, то говорят, что
для слова S возможен сдвиг. Если в Сост(S) есть ситуация, в которой
справа от подчёркивания ничего нет, то говорят, что для слова S воз-
можна свёртка (по соответствующему правилу). Говорят, что для сло-
ва S возникает конфликт типа сдвиг/свёртка, если возможны и сдвиг,
и свёртка. Говорят, что для слова S возникает конфликт типа свёрт-
ка/свёртка, если есть несколько правил, по которым возможна свёртка.
Грамматика называется LR(0)-грамматикой, если в ней нет кон-
фликтов типа сдвиг/свёртка и свёртка/свёртка ни для одного слова S.
16.2.2. Является ли приведённая выше грамматика LR(0)-грамма-
тикой?
Решение. Нет, не является. Для слов T и E+T имеются конфликты
типа сдвиг/свёртка.
16.2.3. Являются ли LR(0)-грамматиками такие:
(а) T
→
0
T
→
T1
T
→
TT2
T
→
TTT3
(б) T
→
0
T
→
1T
T
→
2TT
T
→
3TTT
Решение. Являются, см. таблицы на с.
{
(конфликтов нет).
Эта задача показывает, что LR(0)-грамматики могут быть как ле-
ворекурсивными, так и праворекурсивными.
16.2.4. Пусть дана LR(0)-грамматика. Докажите, что у любого сло-
ва существует не более одного правого вывода. Постройте алгоритм
проверки выводимости в LR(0)-грамматике.

302
16. Синтаксический разбор слева направо (LR)
Слово S Сост(S)
пустое
Т
→
0 T
→
T1 T
→
TT2 T
→
TTT3
0
Т
→
0
Т
Т
→
Т 1 T
→
T T2 T
→
T TT3
Т
→
0 T
→
T1 T
→
TT2 T
→
TTT3
T1
T
→
T1
TT
T
→
TT 2 T
→
TT T3
T
→
T 1 T
→
T T2 T
→
T TT3
T
→
0 T
→
T1 T
→
TT2 T
→
TTT3
TT2
T
→
TT2
TTT
T
→
TTT 3 T
→
TT 2 T
→
TT T3
T
→
T 1 T
→
T T2 T
→
T TT3
Т
→
0 T
→
T1 T
→
TT2 T
→
TTT3
TT0
= 0
TTT3
T
→
TTT3
TTT2
= TT2
TTTT
= TTT
TTT0
= 0
(а)
Слово S Сост(S)
пустое
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
0
Т
→
0
1
Т
→
1 T
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
2
T
→
2 TT
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
3
T
→
3 TTT
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
(б), начало
К задаче

16.2. LR(0)-грамматики
303
Слово S Сост(S)
1T
T
→
1T
10
= 0
11
= 1
12
= 2
13
= 3
2T
T
→
2T T
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
20
= 0
21
= 1
22
= 2
23
= 3
3T
T
→
3T TT
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
30
= 0
31
= 1
32
= 2
33
= 3
2TT
T
→
2TT
2T0
= 0
2T1
= 1
2T2
= 2
2T3
= 3
3TT
T
→
3TT T
T
→
0 T
→
1Т T
→
2ТТ T
→
3ТТТ
3T0
= 0
3T1
= 1
3T2
= 2
3T3
= 3
3TTT
T
→
3TTT
3TT0
= 0
3TT1
= 1
3TT2
= 2
3TT3
= 3
(б), окончание

304
16. Синтаксический разбор слева направо (LR)
Решение. Пусть дано произвольное слово. Будем строить LR-про-
цесс над ним по шагам. Пусть текущее состояние стека LR-процесса
равно S. Нам надо решить, делать сдвиг или свёртку (и если свёрт-
ку, то по какому правилу). Согласно определению LR(0)-граммати-
ки, в нашем состоянии S возможен либо только сдвиг, либо толь-
ко свёртка (причём лишь по одному правилу). Таким образом, поиск
возможных продолжений LR-процесса происходит детерминированно
(на каждом шаге можно определить, какое действие только и воз-
можно).
16.2.5. Что произойдёт, если анализируемое слово не имеет вывода
в данной грамматике?
Ответ. Либо на некотором шаге не будет возможен ни сдвиг, ни
свёртка, либо все возможные сдвиги будет иметь неподходящий оче-
редной символ.
Замечания. 1. При реализации этого алгоритма нет необходимости
каждый раз заново вычислять множество Сост(S) для текущего значе-
ния S. Эти множества можно также хранить в стеке (в каждый момент
хранятся множества Сост(T) для всех начал T текущего слова S).
2. На самом деле само слово S можно не хранить | достаточно
хранить множества ситуаций Сост(T) для всех его начал T (включая
само S).
В алгоритме проверки выводимости в LR(0)-грамматике мы ис-
пользуем не всю информацию, которую могли бы. В этом алгорит-
ме для каждого состояния известно заранее, что в нём возможен то-
лько сдвиг или только свёртка (причём в последнем случае извест-
но, по какому правилу). Более изощрённый алгоритм мог бы при-
нимать решение о выборе между сдвигом и свёрткой, посмотрев
на очередной символ (Next). Глядя на состояние, можно сказать,
при каких значениях Next возможен сдвиг (это те терминалы, ко-
торые в ситуациях этого состояния стоят непосредственно за под-
чёркиванием). Сложнее воспользоваться информацией о символе Next
для решения вопроса о том, возможна ли свёртка. Для этого есть
упрощённый метод (грамматики, к которым он применим, называ-
ют SLR(1)-грамматиками [сокращение от Simple LR(1)]) и полный
метод (более сложный, но использующий всю возможную информа-
цию; грамматики, к которым он применим, называют LR(1)-грам-
матиками). Есть и промежуточный класс грамматик, называемый
LALR(1).

16.3. SLR(1)-грамматики
305
16.3. SLR(1)-грамматики
Напомним, что для любого нетерминала K мы определяли (с.
множество Послед(K) тех терминалов, которые могут стоять непосред-
ственно за K в выводимом (из начального нетерминала) слове; в это мно-
жество добавляют также символ EOI, если нетерминал K может стоять
в конце выводимого слова.
16.3.1. Докажите, что если в данный момент LR-процесса послед-
ний символ стека S равен K, причём процесс этот может в дальнейшем
успешно завершиться, то Next принадлежит Послед(K).
Решение. Этот факт является непосредственным следствием опре-
деления (вспомним соответствие между правыми выводами и LR-про-
цессами).
Рассмотрим некоторую грамматику, произвольное слово S из терми-
налов и нетерминалов и терминал x. Если множество Сост(S) содержит
ситуацию, в которой справа от подчёркивания стоит терминал x, то
говорят, что для пары
⟨
S, x
⟩
возможен сдвиг. Если в Сост(S) есть си-
туация K
→
U , причём x принадлежит Послед(K), то говорят, что для
пары
⟨
S, x
⟩
SLR(1)-возможна свёртка (по правилу K
→
U). Говорят, что
для пары
⟨
S, x
⟩
возникает SLR(1)-конфликт типа сдвиг/свёртка, если
возможны и сдвиг, и свёртка. Говорят, что для пары
⟨
S, x
⟩
возникает
SLR(1)-конфликт типа свёртка/свёртка, если есть несколько правил,
по которым возможна свёртка.
Грамматика называется SLR(1)-грамматикой, если в ней нет
SLR(1)-конфликтов типа сдвиг/свёртка и свёртка/свёртка ни для од-
ной пары
⟨
S, x
⟩
.
16.3.2. Пусть дана SLR(1)-грамматика. Докажите, что у любого
слова существует не более одного правого вывода. Постройте алгоритм
проверки выводимости в SLR(1)-грамматике.
Решение. Аналогично случаю LR(0)-грамматик, только при выборе
между сдвигом и свёрткой учитывается очередной символ (Next).
16.3.3. Проверьте, является ли приведённая выше на с.
грамма-
тика (с нетерминалами E, T и F) SLR(1)-грамматикой.
Решение. Да, является, так как оба конфликта, мешающие ей быть
LR(0)-грамматикой, разрешаются с учётом очередного символа: и для
слова T, и для слова E+T сдвиг возможен только при Next = *, а символ *
не принадлежит ни Послед(E) =
{
EOI, +, )
}
, ни Послед(T) =
{
EOI, +, *, )
}
,
и поэтому при Next = * свёртка невозможна.

306
16. Синтаксический разбор слева направо (LR)
16.4. LR(1)-грамматики, LALR(1)-грамматики
Описанный выше SLR(1)-подход используют не всю возможную ин-
формацию при выяснении того, возможна ли свёртка. Именно, он от-
дельно проверяет, возможна ли свёртка при данном состоянии стека S
и отдельно | возможна ли свёртка по данному правилу при данном
символе Next. Между тем эти проверки не являются независимыми:
обе могут дать положительный ответ, но тем не менее свёртка при
стеке S и очередном символе Next невозможна. В LR(1)-подходе этот
недостаток устраняется.
LR(1)-подход состоит вот в чём: все наши определения и утвержде-
ния модифицируются так, чтобы учесть, какой символ стоит справа
от разворачиваемого нетерминала (другими словами, чему равен Next
при свёртке).
Пусть K
→
U | одно из правил грамматики, а t | некоторый тер-
минал или спецсимвол EOI (который мы домысливаем в конце вход-
ного слова). Определим множество ЛевКонт(K
→
U, t) как множество
всех слов, которые являются содержимым стека непосредственно пе-
ред свёрткой U в K в ходе успешного LR-процесса, при условии Next = t
(в момент свёртки).
Если отбросить у всех слов из ЛевКонт(K
→
U) их конец U, то полу-
чится множество всех слов, которые могут появиться в правых выводах
перед нетерминалом K, за которым стоит символ t. Это множество (не
зависящее от того, какое из правил K
→
U для нетерминала K выбрано)
мы будем обозначать Лев(K, t).
16.4.1. Напишите грамматику для порождения множеств Лев(K, t).
Решение. Её нетерминалами будут символы
⟨
ЛевK t
⟩
для каждого
нетерминала K и для каждого терминала t (а также для t = EOI). Её
правила таковы. Пусть P | начальный нетерминал исходной грамма-
тики. Тогда в новой грамматике будет правило
⟨
ЛевP EOI
⟩ →
(пустое слово).
Каждое правило исходной грамматики порождает несколько правил но-
вой. Например, для правила
K
→
L u M N
(L, M, N | нетерминалы, u | терминал) в новую грамматику мы доба-
вим правила
⟨
ЛевL u
⟩ → ⟨
ЛевK x
⟩

16.4. LR(1)-грамматики, LALR(1)-грамматики
307
(для всех терминалов x);
⟨
ЛевM s
⟩ → ⟨
ЛевK y
⟩
L u
(для всех s, которые могут начинать слова, выводимые из N, и для
всех y, а также для всех пар s = y, если из N выводимо пустое слово);
⟨
ЛевN s
⟩ → ⟨
ЛевK s
⟩
L u M
(для всех терминалов s).
16.4.2. Как меняется определение ситуации?
Решение. Ситуацией называется пара
[ситуация в старом смысле, терминал или EOI]
16.4.3. Как изменится определение согласованности?
Решение. Слово S из терминалов и нетерминалов согласовано с си-
туацией [K
→
U V, t] (здесь t | терминал или EOI), если S кончается
на U, то есть S = TU, и, кроме того, T принадлежит Лев(K, t).
16.4.4. Каковы правила для индуктивного вычисления множества
Сост(S) ситуаций, согласованных с данным словом S?
Ответ.
(1) Если слово S согласовано с ситуацией [K
→
U V, t], причём
слово V начинается на букву J, то есть V = JW, то слово SJ
согласовано с ситуацией [K
→
UJ W, t].
Это правило полностью определяет все ситуации с непустой левой
половиной (то есть не начинающиеся с подчёркивания), согласованные
с SJ. Осталось определить, для каких нетерминалов K и терминалов t
слово SJ принадлежит Лев(K, t). Это делается по двум правилам:
(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 выводится пустое слово.

308
16. Синтаксический разбор слева направо (LR)
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). Будем говорить, что для

16.5. Общие замечания о разных методах разбора
309
пары
⟨
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)-грамматикой, то лучше её не трогать, а разбирать как
есть. При этом могут оказаться полезные средства автоматического

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

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

Предметный указатель
𝐴
*
-алгоритм поиска
151
AND-OR-дерево
224
backtracking
60
Borland
4
LALR(1)-грамматика
309
LL(1)-грамматика
288
LL(1)-разбор
285
LR(0)-грамматика
301
LR(1)-грамматика
308
LR-процесс
293
NP-полнота
70
SLR(1)-грамматика
305
Turbo Pascal
4
,
29
АВЛ-дерево
257
автомат конечный
90
,
177
,
189
| | недетерминированный
194
азбука Морзе
230
алгоритм Маккрейта
202
| чередующихся цепей
174
алфавит
179
,
229
альфа-бета-процедура
222
,
223
Б-дерево
266
билеты счастливые, число
58
биномиальный коэффициент
136
ближайшая сумма
31
Бойера { Мура алгоритм
185
бридж-ит, игра
216
буква
229
|, частота
230
быстрое умножение
28
величина потока
161
{
164
,
166
вершина графа
106
,
130
вершинное покрытие
176
ветвей и границ метод
60
вращение левое, правое
258
| малое, большое
258
вывод в грамматике
268
| левый
285
| правый
293
выводимость в КС-грамматике,
полиномиальный алгоритм
272
выигрышные позиции
211
выпуклая оболочка
81
,
110
выражение
271
| регулярное
192
высота
250
гауссовы числа
17
Гейла игра
216
голландский флаг
36
Горнера схема
26
грамматика LALR(1)
309
| LL(1)
288
| LR(0)
301

314
Предметный указатель
калькулятор стековый
144
Каталана число
55
,
59
,
137
Кёнига теорема
176
Кнута { Морриса { Пратта
алгоритм
181
код
229
| Грея
49
| однозначный
229
| префиксный
230
|, средняя длина
231
| Хаффмана
234
{
236
| Шеннона { Фано
236
{
238
кодовое слово
229
количество различных
24
,
80
комментарии вложенные
91
|, удаление
91
конец слова
179
конечный автомат
90
,
177
,
189
| | недетерминированный
194
контекстно-свободная
грамматика
268
конфликт свёртка/свёртка
301
,
305
,
308
| сдвиг/свёртка
301
,
305
,
308
коэффициент биномиальный
136
Крафта { Макмиллана
неравенство
230
{
233
крестики-нолики, игра
215
критическое ребро
170
КС-грамматика
268
Лев(𝐾)
295
Лев(𝐾, 𝑡)
306
ЛевКонт(𝐾
→
𝑈)
294
ЛевКонт(𝐾
→
𝑈, 𝑡)
306
левый контекст правила
294
Маккрейта алгоритм
198
,
202
максимальное паросочетание
172
,
174
{
176
максимальный поток
163
,
168
массив
23
| с минимальным элементом
115
| суффиксов
207
матриц произведение
149
матрица цен
149
матрицы, порядок умножения
138
медиана, поиск
88
,
133
метод потенциалов
151
минимальный разрез
163
,
169
минимум, поиск
84
многоугольника триангуляция
57
многочлен, значение
26
|, производная
27
|, умножение
27
,
28
множество, представление
240
,
243
| | деревом
249
|, реализация в битовом массиве
111
| | перечнем
112
| регулярное
193
|, тип данных
111
множитель
271
моделирование, очередь событий
116
монотонных последовательностей
перечисление
47
Морзе азбука
230
наибольший общий делитель
11
наименьшее общее кратное
13
Напр(𝐾
→
𝑉 )
288
Нач(𝑋)
276
,
287
начало слова
179
неассоциативное произведение
139
недетерминированный конечный
автомат
194
неориентированный граф
130
неравенство Крафта {
Макмиллана
230
{
233

Предметный указатель
315
нетерминал
268
нижние оценки числа сравнений
84
ним, игра
210
НОД
11
НОК
13
обмен значений
8
образец, поиск
177
обратная перестановка
35
| польская запись
144
обход дерева
60
,
219
| | рекурсивный
127
общий элемент (в упорядоченных
массивах)
31
опечатки, поиск
248
ориентированный граф
106
орфография, проверка
248
остаточная сеть
164
остаточный граф
164
,
169
открытая адресация
241
очередь
103
| из двух стеков
104
| приоритетная
115
|, реализация в массиве
103
|, ссылочная реализация
108
ошибка: индекс за границей
29
,
34
,
35
,
73
,
75
паросочетание
172
{
176
паскаль, язык
4
,
29
Паскаля треугольник
57
,
136
перебор с возвратами
60
|, сокращение
222
пересечение регулярных
множеств
196
| упорядоченных массивов
31
перестановка обратная
35
,
53
| частей массива
25
|, чётность
35
перестановок перечисление
44
,
52
,
124
период десятичной дроби
20
поддерево
250
подмножеств перечисление
44
,
45
подпоследовательность
максимальная возрастающая
41
| общая
40
|, проверка
40
подслово
179
|, поиск
181
,
184
,
185
,
187
позиции в суффиксном дереве
199
| проигрышные и выигрышные
211
поиск 𝐴
*
-алгоритм
151
| 𝑘-го по порядку
88
,
133
,
256
| в глубину
153
| в ширину
114
,
152
| двоичный
33
| кратчайшего пути
146
| минимума
84
| образца
185
,
187
,
189
| одного из слов
190
| подслова
177
,
181
,
184
,
185
,
187
| представителя большинства
88
Посл(𝑋)
276
Послед(𝑋)
287
последовательности монотонные,
перечисление
125
последовательность, содержащая
все слова длины 𝑛
108
постфиксная запись
144
потенциал
151
поток
157
{
159
| через разрез
161
потомок вершины
121
права авторские
4
предпоток
163
приведение
293
приоритетная очередь
115

316
Предметный указатель
программа сжатия информации
239
программирование динамическое
135
,
137
,
272
проигрышные позиции
211
произведение многочленов
27
| неассоциативное
56
,
139
пропускная способность
158
| | разреза
163
{
166
простые множители
15
путей число
150
Рабина алгоритм
187
разбиений на слагаемые
перечисление
48
,
126
| | число
57
разбор LL(1)
285
| LR(1)
293
|, общий КС-алгоритм
272
|, рекурсивный спуск
274
разложение на множители
15
размещения с повторениями
43
,
123
разрез
157
,
158
,
161
расстановки функция
240
расширение индуктивное
39
ребро графа
130
регулярное выражение
192
| множество
193
| |, дополнение
196
| |, пересечение
196
рекурсивная программа
117
рекурсивный спуск
274
рекурсия
117
|, устранение
135
ретроспективный анализ игры
226
рюкзак, заполнение
70
,
140
свёртка
293
связная компонента
неориентированного графа
130
| | ориентированного графа
113
,
131
,
152
связный граф
106
сдвиг
293
сеть
157
,
158
,
161
сжатие информации
239
сжатое суффиксное дерево
198
символ
229
|, код
229
| начальный
268
| нетерминальный
268
| терминальный
268
ситуация грамматики
296
скобки, правильность
98
,
269
скобок расстановка
56
слагаемое
271
слияние упорядоченных массивов
30
слово
179
| выводимое
268
сортировка 𝑛 log 𝑛
73
| деревом
75
,
115
| квадратичная
72
|, нижняя оценка сложности
82
| слиянием
73
,
80
| топологическая
128
,
155
| Хоара (быстрая)
80
,
132
| | нерекурсивная
143
| цифровая
83
|, число сравнений
82
Сост(𝑆)
297
составные символы, замена
90
сочетаний число
57
,
136
ссылки суффиксные
200
стек
96
|, два в массиве
100
| отложенных заданий
141
|, реализация в массиве
97
|, ссылочная реализация
100

Предметный указатель
317
стековый калькулятор
144
степень, быстрое вычисление
9
|, вычисление
9
|, рекурсивная программа
118
сток
159
стратегия в игре
213
| позиционная
213
суммарная величина потока
161
{
164
,
166
суммирование массива
рекурсивное
120
суффикс
198
суффиксное дерево
196
,
198
суффиксные ссылки
200
суффиксный массив
207
счастливые билеты, число
58
теорема Кёнига
176
| Форда { Фалкерсона
163
| Холла о представителях
176
| Цермело
213
терминал
268
| направляющий
288
топологическая сортировка
128
,
155
треугольник Паскаля
136
триангуляция многоугольника
57
,
137
упорядоченное дерево
250
факториал
11
|, рекурсивная программа
117
ферзей расстановка
60
Фибоначчи последовательность
11
,
137
,
257
| |, быстрое вычисление
11
Флойда алгоритм
147
,
196
Форда { Беллмана алгоритм
146
функция индуктивная
38
| расстановки
240
ханойские башни, нерекурсивная
программа
140
| |, рекурсивная программа
119
Хаффмана код
234
{
236
хеш-функция
240
|, универсальное семейство
245
,
247
хеширование
240
|, оценка числа действий
245
| с открытой адресацией
241
| со списками
243
| универсальное
245
Хоара сортировка
80
,
132
| | нерекурсивная
143
хорды окружности
57
целые точки в круге
18
цена игры
211
,
213
| |, вычисление
219
Цермело теорема
213
цикл эйлеров (по всем рёбрам
графа)
106
циркуляция
171
частота буквы
230
чётность перестановки
35
число Каталана
55
,
59
,
137
| общих элементов
28
| разбиений
57
| сочетаний
57
| счастливых билетов
58
Шеннона { Фано код
236
{
238
энтропия Шеннона
236
язык контекстно-свободный
268
| не контекстно-свободный
270

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

Указатель имён
319
Хопкрофт (Hopcroft, J.) 70, 311
Цвик (Zwick, U.) 166
Шеннон (Shannon, C.) 217, 236
Штрассен (Strassen, V.) 27
Эдмондс (Edmonds, J. R.) 169, 171,
172, 174

Научно-популярное издание
Александр Шень
ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ
Оригинал-макет: В. Шувалов
Дизайн обложки: У. Сопова
В соответствии с Федеральным законом Ђ 436-ФЗ
от 29 декабря 2010 года издание маркируется знаком
6
+
Подписано в печать 17.09.2020 г. Формат 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,66 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9