Используя эту задачу, несложно составить рекурсивную программу для отыскания длин кодовых слов. С каждым вызовом число букв будет уменьшаться, пока мы не сведём задачу к случаю двух букв, когда оптимальный код состоит из слов 0 и 1. Затем можно найти и сами кодовые слова (согласно задаче 12.2.3). Но проще объединить эти действия и сразу искать кодовые слова: ведь замена числа $n$ на два числа $n+1$ соответствует замене кодового слова $P$ на два слова $P0$ и $P1$ на единицу большей длины (и эта последняя замена сохраняет префиксность кода).

Код, построенный таким методом, называется кодом Хаффмана. Мы доказали, что он имеет минимальную среднюю длину среди всех кодов (для данных частот букв). В следующей задаче оценивается число операций, необходимых для построения кода Хаффмана.

**12.3.6.** Покажите, что можно обработать частоты $p_1, \dots, p_k$, сделав $O(k \log k)$ операций, после чего $i$-е кодовое слово можно указать за время, пропорциональное его длине.

[Указание. Заметим, что оценка времени довольно сильная: только на сортировку чисел $p_i$ уже уходит $O(k \log k)$ действий. Поэтому, применяя предыдущую задачу, нужно использовать результаты сортировки $k$ чисел при сортировке меньшего количества чисел. Это можно сделать с помощью очереди с приоритетами, вынимая два минимальных числа и добавляя их сумму за $O(\log k)$ действий. Это позволяет определить, какие две буквы надо соединять в одну на каждом шаге. Параллельно с соединением букв можно строить дерево кодов, проводя рёбра (помеченные 0 и 1) от соединённой буквы к каждой из её половинок. При этом требуется $O(1)$ действий на каждом шаге. После завершения построение прослеживать код любой буквы можно символically.

## 12.4. Код Шеннона – Фано

Мы видели, как можно построить оптимальный код (имеющий минимальную среднюю длину) для данного набора частот. Однако эта конструкция не даёт никакой оценки для средней длины оптимального кода (как функции от частот $p_i$). Следующие задачи указывает такую оценку (с абсолютной погрешностью не более 1).

**12.4.1.** Покажите, что для любых положительных частот $p_1, \dots, p_k$ (в сумме равных единице) существует код средней длиной не более $H(p_1, \dots, p_k) + 1$, где функция $H$ (называемая энтропией Шеннона)
определяется формулой

$$H(p_1, \dots, p_n) = p_1(-\log_2 p_1) + \dots + p_k(-\log_2 p_k)$$

**Решение.** Если частоты $p_i$ представляют собой целые (отрицательные) степени двойки, то это утверждение почти очевидно. Положим $n_i = -\log p_i$ (здесь и далее все логарифмы двоичные). Тогда $2^{-n_i} = p_i$ и потому для чисел $n_i$ выполнено неравенство Крафта–Макмиллана. По задаче 12.2.3 можно построить префиксный код с длинами кодовых слов $n_1, \dots, n_k$, и средняя длина этого кода будет равна $H(p_1, \dots, p_k)$ (и даже единицу добавлять не надо).

Эта единица пригодится, если $\log p_i$ не целые. В этом случае надо взять наименьшее $n_i$, при котором $2^{-n_i} \le p_i$. Для таких $n_i$ выполняется неравенство Крафта–Макмиллана, и они больше $-\log p_i$ не более чем на единицу (потому и после усреднения ухудшение будет не более чем на единицу). $\square$

Построенный на основе этой задачи код называется кодом Шенкона–Фано<fnref n="1" />. Это построение легко извлекается из решения задачи 12.2.3: рассматривая числа $n_i = -[\log p_i]$ (наименьшие целые числа, для которых $2^{-n_i} \le p_i$) в порядке убывания, мы отводим для каждого из них кодовое слово и соответствующий участок отрезка $[0, 1]$ слева направо.

При этом мы проигрываем в длине кода (по сравнению с оптимальным кодом) не более единицы: как мы сейчас увидим, средняя длина любого (в том числе и оптимального) кода не меньше $H(p_1, \dots, p_k)$.

**12.4.2.** (Для знакомых с математическим анализом) Докажите, что (при данных положительных частотах, в сумме дающих единицу) средняя длина любого (однозначного) кода не меньше $H(p_1, \dots, p_k)$.

**Решение.** Имея в виду неравенство Крафта–Макмиллана, мы должны доказать такой факт: если

$$2^{-n_1} + \dots + 2^{-n_k} \le 1,$$

TO

$$p_1 n_1 + \dots + p_k n_k \ge H(p_1, \dots, p_k).$$

<footnote n="1">¹Хотя это название и употребительно, оно не вполне правильно с исторической точки зрения. Описанное построение было предложено Шенконом; Фано предложил другой метод построения кода, в котором буквы упорядочиваются по убыванию частот и разбиваются на две группы в таком месте, чтобы суммы частот в группах были как можно ближе друг к другу. Буквы первой группы кодируются кодами, начинающимися с нуля, а второй — кодами, начинающимися с единицы. Процесс повторяется рекурсивно для каждой группы.</footnote>
Это верно для любых $n_i$, не обязательно целых. Удобно перейти от $n_i$ к величинам $q_i = 2^{-n_i}$; интересующее нас утверждение тогда гласит, что если $p_1, \dots, p_k$ и $q_1, \dots, q_k$ — два набора положительных чисел, и сумма чисел в каждом равна единице, то

$$p_1(-\log q_1) + \dots + p_k(-\log q_k) \ge p_1(-\log p_1) + \dots + p_k(-\log p_k).$$

Другими словами, выражение

$$p_1(-\log q_1) + \dots + p_k(-\log q_k)$$

(рассматриваемое при фиксированных $p_i$ как функция на множестве всех положительных $q_1, \dots, q_k$, в сумме равных единице) достигает минимума при $q_i = p_i$. Область определения этой функции есть внутренность симплекса (треугольника при $n = 3$, тетраэдра при $n = 4$ и т. д.) и при приближении к границе одно из $q_i$ становится малым, а его минус логарифм уходит в бесконечность. Значит, минимум функции достигается внутри области. В точке минимума градиент $(-p_1/q_1, \dots, -p_n/q_n)$ должен быть перпендикулярен плоскости, на которой функция определена (наче сдвиг вдоль этой плоскости уменьшал бы функцию), то есть все $p_i/q_i$ равны. Поскольку $\sum p_i = \sum q_i = 1$, то это означает, что $p_i = q_i$.

Другое объяснение: функция $\log$ выпукла вверх, поэтому для любых неотрицательных коэффициентов $\alpha_i$, в сумме равных единице, и для любых точек $x_i$ из области определения логарифма выполняется неравенство

$$\log \left( \sum \alpha_i x_i \right) \ge \sum \alpha_i \log x_i.$$

Остаётся положить $\alpha_i = p_i$, $x_i = q_i/p_i$; в левой части будет логарифм единицы, то есть нуль, а $\sum p_i \log(q_i/p_i)$ есть как раз разность между левой и правой частями доказываемого неравенства. $\square$

Велика ли экономия от использования кодов, описанных в этом разделе? Это, конечно, зависит от частот букв: если они все одинаковые, то никакой экономии не будет. Легко заметить, что в русском языке разные буквы имеют разную частоту. Если, скажем, в текстах (ТЕХ-файлах) этой книжки (на момент эксперимента) оставить только 33 строчные русские буквы от «а» до «я», а все остальные символы не учитывать, то самой частой буквой будет буква «о» (частота 0,105), а самой редкой — твёрдый знак (частота 0,00019). Значение энтропии Шеннона при этом будет равно 4,454 (сравните с 5 битами, необходимыми для кодирования 32 букв). Выигрыш не так велик. Он будет
больше, если учитывать также и другие символы (прописные буквы, знаки препинания и др.), которые встречаются в тексте гораздо реже. Наконец, можно кодировать не буквы, а двухбуквенные комбинации или ещё что-нибудь. Именно так поступают популярные программы сжатия информации (типа zip), которые позволяют сократить многие тексты в полтора-два раза (а некоторые другие файлы данных — и в большее число раз).

12.4.3. Компания М. утверждает, что её новая программа супер-сжатия файлов позволяет сжать любой файл длиной больше 100 000 байтов по крайней мере на 10% без потери информации (можно восстановить исходный файл по его сжатому варианту). Докажите, что она врёт. ☐
# 13. ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ. ХЕШИРОВАНИЕ

## 13.1. Хеширование с открытой адресацией

В главе 6 было указано несколько представлений для множеств, элементами которых являются целые числа произвольной величины. Однако в любом из них хотя бы одна из операций проверки принадлежности, добавления и удаления элемента требовала количества действий, пропорционального числу элементов множества. На практике это бывает слишком много. Существуют способы, позволяющие получить для всех трёх упомянутых операций оценку $C \log n$. Один из таких способов мы рассмотрим в следующей главе. В этой главе мы разберём способ, которые хотя и приводит к $Cn$ действиям в худшем случае, но зато «в среднем» требует значительно меньшего их числа. (Мы не будем уточнять слов «в среднем», хотя это и можно сделать.) Этот способ называется хешированием.

Пусть нам необходимо представлять множества элементов типа T, причём число элементов в них заведомо меньше $n$. Выберем некоторую функцию $\hbar$, определённую на значениях типа T и принимающую значения $0...n-1$. Было бы хорошо, чтобы эта функция принимала на элементах будущего множества по возможности более разнообразные значения. (Худший случай — это когда её значения на всех элементах хранимого множества одинаковы.) Эту функцию будем называть хеш-функцией, или, как ещё говорят, функцией расстановки.

Введём два массива

```c
val: array [0..n-1] of T;
used: array [0..n-1] of boolean;
```

(мы позволяем себе писать $n-1$ в качестве границы в определении типа,
хотя в паскале это не разрешается). В этих массивах будут храниться элементы множества: оно равно множеству всех `val[i]` для тех `i`, для которых `used[i]`, причём все эти `val[i]` различны. По возможности мы будем хранить элемент `t` на месте `h(t)`, считая это место «исконным» для элемента `t`. Однако может случиться так, что новый элемент, который мы хотим добавить, претендует на уже занятое место (для которого `used` истинно). В этом случае мы отыщем ближайшее справа свободное место и запишем элемент туда. («Справа» значит «в сторону увеличения индексов»; дойдя до края, мы перескакиваем в начало.) По предположению, число элементов всегда меньше `n`, так что пустые места заведомо будут.

Формально говоря, в любой момент должно соблюдаться такое требование: для любого элемента множества участок справа от его исконного места до его фактического места полностью заполнен.

Благодаря этому проверка принадлежности заданного элемента `t` осуществляется легко: встав на `h(t)`, двигаемся направо, пока не дойдём до пустого места или до элемента `t`. В первом случае элемент `t` отсутствует в множестве, во втором — присутствует. Если элемент отсутствует, то его можно добавить на найденное пустое место. Если присутствует, то можно его удалить (положив `used = false`).

**13.1.1.** В предыдущем абзаце есть ошибка. Найдите её и исправьте.

**Решение.** Дело в том, что при удалении требуемое свойство «отсутствия пустот» может нарушиться. Поэтому будем делать так. Создав дыру, будем двигаться направо, пока не натолкнёмся на элемент, стоящий не на исконном месте, или на ещё одно пустое место. Во втором случае на этом можно успокоиться. В первом случае посмотрим, не нужно ли найденный элемент поставить на место дыры. Если нет, то продолжаем поиск, если да, то затыкаем им старую дыру. При этом образуется новая дыра, с которой делаем всё то же самое. ☐

**13.1.2.** Напишите программы проверки принадлежности, добавления и удаления.

**Решение.**

```pascal
function принадлежит (t: T): boolean;
  var i: integer;
begin
  i := h (t);
  while used [i] and (val [i] <> t) do begin
    i := (i + 1) mod n;
  end; {not used [i] or (val [i] = t)}
```
принадлежит := used [i] and (val [i] = t);
end;

procedure добавить (t: T);

var i: integer;

begin

i := h (t);

while used [i] and (val [i] <> t) do begin

i := (i + 1) mod n;

end; {not used [i] or (val [i] = t)}

if not used [i] then begin

used [i] := true;

val [i] := t;

end;

end;

procedure исключить (t: T);

var i, gap: integer;

begin

i := h (t);

while used [i] and (val [i] <> t) do begin

i := (i + 1) mod n;

end; {not used [i] or (val [i] = t)}

if used [i] and (val [i] = t) then begin

used [i] := false;

gap := i;

i := (i + 1) mod n;

{gap - дыра, которая может закрыться одним из i,i+1,...}

while used [i] do begin

if i = h (val[i]) then begin

{на своём месте, ничего не делать}

end else if dist(h(val[i]),i) < dist(gap,i) then begin

{gap...h(val[i])...i, ничего не делать}

end else begin

used [gap] := true;

val [gap] := val [i];

used [i] := false;

gap := i;

end;

i := (i + 1) mod n;

end;

end;

end;

Здесь dist (a,b) — измеренное по часовой стрелке (слева направо)
расстояние от a до b, то есть

$$ \mathrm{dist}(a,b) = (b-a+n) \mod n. $$

(Мы прибавили n, так как функция mod правильно работает при положительном делимом.) ☐

**13.1.3.** Существует много вариантов хеширования. Один из них таков: обнаружив, что исконное место (обозначим его i) занято, будем искать свободное не среди i + 1, i + 2, ..., а среди r(i), r(r(i)), r(r(r(i))), ..., где r — некоторое отображение {0, ..., n - 1} в себя. Какие при этом будут трудности?

**Ответ.** (1) Не гарантируется, что если пустые места есть, то мы их найдём. (2) При удалении неясно, как заполнять дыры. (На практике во многих случаях удаление не нужно, так что такой способ также применяется. Считается, что удачный подбор функции r может предотвратить образование «скоплений» занятых ячеек.) ☐

**13.1.4.** Пусть для хранения множества всех правильных русских слов в программе проверки орфографии используется хеширование. Что нужно добавить, чтобы к тому же уметь находить английский перевод любого правильного слова?

**Решение.** Помимо массива val, элементы которого являются русскими словами, нужен параллельный массив их английских переводов. ☐

## 13.2. Хеширование со списками

На хеш-функцию с k значениями можно смотреть как на способ свести вопрос о хранении одного большого множества к вопросу о хранении нескольких меньших. Именно, если у нас есть хеш-функция с k значениями, то любое множество разбивается на k подмножеств (возможно, пустых), соответствующих возможным значениям хеш-функции. Вопрос о проверке принадлежности, добавлении или удалении для большого множества сводится к такому же вопросу для одного из меньших (чтобы узнать, для какого, надо посмотреть на значение хеш-функции).

Эти меньшие множества удобно хранить с помощью ссылок; их суммарный размер равен числу элементов хешируемого множества. Следующая задача предлагает реализовать этот план.

**13.2.1.** Пусть хеш-функция принимает значения 1...k. Для каждого значения хеш-функции рассмотрим список всех элементов множе-
ства с данным значением хеш-функции. Будем хранить эти k списков с помощью переменных

Содержание: array [1..n] of T;
Следующий: array [1..n] of 1..n;
ПервСвоб: 1..n;
Вершина: array [1..k] of 1..n;

так же, как мы это делали для k стеков ограниченной суммарной длины. Напишите соответствующие программы. (Удаление по сравнению с открытой адресацией упрощается.)

**Решение.** Перед началом работы надо положить Вершина[i] = 0 для всех i = 1...k, и связать все места в список свободного пространства, положив ПервСвоб = 1 и Следующий[i] = i+1 для i = 1...n-1, а также Следующий[n] = 0.

```pascal
function принадлежит (t: T): boolean;
  var i: integer;
begin
  i := Вершина[h(t)];
  {осталось искать в списке, начиная с i}
  while (i <> 0) and (Содержание[i] <> t) do begin
    i := Следующий[i];
  end; { (i=0) or (Содержание[i] = t)}
  принадлежит := (i<>0) and (Содержание[i]=t);
end;
```

```pascal
procedure добавить (t: T);
  var i: integer;
begin
  if not принадлежит(t) then begin
    i := ПервСвоб;
    {ПервСвоб <> 0 - считаем, что не переполняется}
    ПервСвоб := Следующий[ПервСвоб]
    Содержание[i]:=t;
    Следующий[i]:=Вершина[h(t)];
    Вершина[h(t)]:=i;
  end;
end;
```

```pascal
procedure исключить (t: T);
  var i, pred: integer;
begin
  i := Вершина[h(t)]; pred := 0;
```
```
{осталось искать в списке, начиная с i; pred -
предыдущий, если он есть, и 0, если нет}
while (i <> 0) and (Содержание[i] <> t) do begin
  pred := i; i := Следующий[i];
end; {(i=0) or (Содержание[i] = t)}
if i <> 0 then begin
  {Содержание[i]=t, элемент есть, надо удалить}
  if pred = 0 then begin
    {элемент оказался первым в списке}
    Вершина[h(t)] := Следующий[i];
  end else begin
    {Следующий[pred] := Следующий[i]
      Следующий[i] := ПервСвоб;
      ПервСвоб:=i;
    }
  end;
end;
end;
```

**13.2.2.** (Для знакомых с теорией вероятностей.) Пусть хеш-функция с $k$ значениями используется для хранения множества, в котором в данный момент $n$ элементов. Докажите, что математическое ожидание числа действий в предыдущей задаче не превосходит $C(1 + n/k)$, если добавляемый (удаляемый, искомый) элемент $t$ выбран случайно, причём все значения $h(t)$ имеют равные вероятности (равные $1/k$).

**Решение.** Если $l(i)$ — длина списка, соответствующего хеш-значению $i$, то число операций не превосходит $C(1 + l(h(t)))$; усредняя, получаем искомый ответ, так как $\sum_i l(i) = n$. $\square$

Эта оценка основана на предложении о равных вероятностях. Однако в конкретной ситуации всё может быть совсем не так, и значения хеш-функции могут «скучиваться»: для каждой конкретной хеш-функции есть «неудачные» ситуации, когда число действий оказывается большим. Приём, называемый **универсальным хешированием**, позволяет обойти эту проблему. Идея состоит в том, что берётся семейство хеш-функций, причём любая ситуация оказывается неудачной лишь для небольшой части этого семейства.

Пусть $H$ — семейство функций, каждая из которых отображает множество $T$ в множество из $k$ элементов (например, $0...k-1$). Говорят, что $H$ — **универсальное семейство хеш-функций**, если для любых двух различных значений $s$ и $t$ из множества $T$ вероятность события $h(s) = h(t)$ для случайной функции $h$ из семейства $H$ равна $1/k$. (Друг-
гими словами, те функции из $H$, для которых $h(s) = h(t)$, составляют $1/k$-ю часть всех функций в $H$.)

**Замечание.** Более сильное требование к семейству $H$ могло бы составлять в том, чтобы для любых двух различных элементов $s$ и $t$ множества $T$ значения $h(s)$ и $h(t)$ случайной функции $h$ являются независимыми случайными величинами, равномерно распределёнными на $0...k-1$.

**13.2.3.** Пусть $t_1, \dots, t_n$ — произвольная последовательность различных элементов множества $T$. Рассмотрим количество действий, происходящих при помещении элементов $t_1, \dots, t_n$ в множество, хешируемое с помощью функции $h$ из универсального семейства $H$. Докажите, что среднее количество действий (усреднение — по всем $h$ из $H$) не превосходит $Cn(1+n/k)$.

**Решение.** Обозначим через $m_i$ количество элементов последовательности, для которых хеш-функция равна $i$. (Числа $m_0, \dots, m_{k-1}$ зависят, конечно, от выбора хеш-функции.) Количество действий, которое мы хотим оценить, с точностью до постоянного множителя равно $m_0^2 + m_1^2 + \dots + m_{k-1}^2$. (Если $s$ чисел попадают в одну хеш-ячейку, то для этого требуется примерно $1 + 2 + \dots + s$ действий.) Эту же сумму квадратов можно записать как число пар $(p, q)$, для которых $h(t_p) = h(t_q)$. Последнее равенство, если его рассматривать как событие при фиксированных $p$ и $q$, имеет вероятность $1/k$ при $p \ne q$, поэтому среднее значение соответствующего члена суммы равно $1/k$, а для всей суммы получаем оценку порядка $n^2/k$, а точнее $n + n^2/k$, если учесть члены с $p = q$. $\square$

Эта задача показывает, что на каждый добавляемый элемент приходится в среднем $C(1+n/k)$ операций. В этой оценке дробь $n/k$ имеет смысл «коэффициента заполнения» хеш-таблицы.

**13.2.4.** Докажите аналогичное утверждение для произвольной последовательности операций добавления, поиска и удаления (а не только для добавления, как в предыдущей задаче).

[Указание. Будем представлять себе, что в ходе поиска, добавления и удаления элемент проталкивается по списку своих коллег с тем же хеш-значением, пока не найдёт своего двойника или не дойдёт до конца списка. Будем называть $i-j$- столкновением столкновение $t_i$ с $t_j$. (Оно либо произойдёт, либо нет — в зависимости от $h$.) Общее число действий примерно равно числу всех происшедших столкновений плюс число элементов. При $t_i \ne t_j$ вероятность $i-j$- столкновения не превосходит $1/k$. Осталось проследить за столкновениями между равными
элементами. Фиксируем некоторое значение х из множества Т и посмотрим на связанные с ним операции. Они идут по циклу: добавление — проверки — удаление — добавление — проверки — удаление — ... Столкновения происходят между добавляемым элементом и следующими за ним проверками (до удаления включительно), поэтому общее их число не превосходит числа элементов, равных х.] ☐

Теперь приведём примеры универсальных семейств. Очевидно, для любых конечных множеств А и В семейство всех функций, отображающих А в В, является универсальным. Однако этот пример с практической точки зрения бесполезен: для запоминания случайной функции из этого семейства нужен массив, число элементов в котором равно числу элементов в множестве А. (А если мы можем себе позволить такой массив, то никакого хеширования не требуется!)

Более практические примеры универсальных семейств могут быть построены с помощью несложных алгебраических конструкций. Через $\mathbb{Z}_p$ мы обозначаем множество вычетов по простому модулю $p$, т. е. $\{0, 1, ..., p-1\}$; арифметические операции в этом множестве выполняются по модулю $p$. Универсальное семейство образуют все линейные функционалы на $\mathbb{Z}_p^n$ со значениями в $\mathbb{Z}_p$. Более подробно, пусть $a_1, ..., a_n$ — произвольные элементы $\mathbb{Z}_p$; рассмотрим отображение

$$h: \langle x_1 \dots x_n \rangle \mapsto a_1 x_1 + \dots + a_n x_n.$$

Мы получаем семейство из $p^n$ отображений $\mathbb{Z}_p^n \to \mathbb{Z}_p$ параметризованное наборами $\langle a_1 \dots a_n \rangle$.

**13.2.5. Докажите, что это семейство является универсальным.**

[Указание. Пусть х и у — различные точки пространства $\mathbb{Z}_p^n$. Какова вероятность того, что случайный функционал принимает на них одинаковые значения? Другими словами, какова вероятность того, что он равен нулю на их разности х – у? Ответ даётся таким утверждением: пусть u — ненулевой вектор; тогда все значения случайного функционала на нём равновероятны.] ☐

В следующей задаче множество $\mathbb{B} = \{0, 1\}$ рассматривается как множество вычетов по модулю 2.

**13.2.6. Семейство всех линейных отображений из $\mathbb{B}^n$ в $\mathbb{B}^m$ является универсальным.** ☐

Родственные хешированию идеи неожиданно оказываются полезными в следующей ситуации (рассказал Д. Варсанофьев). Пусть мы хо-
тим написать программу, которая обнаруживала (большинство) опечаток в тексте, но не хотим хранить список всех правильных словоформ. Предлагается поступить так: выбрать некоторое $N$ и набор функций $f_1, \dots, f_k$, отображающих русские слова в $1, \dots, N$. В массиве из $N$ битов положим все биты равными нулю, кроме тех, которые являются значением какой-то функции набора на какой-то правильной словоформе. Теперь приближённый тест на правильность словоформы таков: проверить, что значения всех функций набора на этой словоформе попадают на места, занятые единицами. (Этот тест может не заметить некоторых ошибок, но все правильные словоформы будут одобры.)
# 14. ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ. ДЕРЕВЬЯ. СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ

## 14.1. Представление множеств с помощью деревьев

### Полное двоичное дерево. $T$-деревья

Нарисуем точку. Из неё проведём две стрелки (влево вверх и вправо вверх) в две другие точки. Из каждой из этих точек проведём по две стрелки и так далее. Полученную картинку (в $n$-м слое будет $2^{n-1}$ точек) называют полным двоичным деревом. Нижнюю точку называют корнем. У каждой вершины есть два сына (две вершины, в которые идут стрелки) — левый и правый. У всякой вершины, кроме корня, есть единственный отец.

Пусть выбрано некоторое конечное множество вершин полного двоичного дерева, содержащее вместе с каждой вершиной и всех её предков. Пусть на каждой вершине этого множества написано значение фиксированного типа $T$ (то есть задано отображение множества вершин в множество значений типа $T$). То, что получится, будем называть $T$-деревом. Множество всех $T$-деревьев обозначим $\text{Tree}(T)$.

**Рекурсивное определение.** Всякое непустое $T$-дерево разбивается на три части: корень (несущий пометку из $T$), левое и правое поддеревья (которые могут быть пустыми). Это разбиение устанавливает взаимно однозначное соответствие между множеством непустых $T$-деревьев и произведением $T \times \text{Tree}(T) \times \text{Tree}(T)$. Обозначив через empty пустое дерево, можно написать

$$ \text{Tree}(T) = \{\text{empty}\} + T \times \text{Tree}(T) \times \text{Tree}(T). $$
## Поддеревья. Высота

Фиксируем некоторое $T$-дерево. Для каждой его вершины $x$ определено её левое поддерево (левый сын вершины $x$ и все его потомки), правое поддерево (правый сын вершины $x$ и все его потомки) и поддерево с корнем в $x$ (вершина $x$ и все её потомки).

<figure><img src="image_116.png" /></figure>

Левое и правое поддеревья вершины $x$ могут быть пустыми, а поддерево с корнем в $x$ всегда непусто (содержит по крайней мере $x$). Высотой поддерева будем считать максимальную длину цепи $y_1...y_n$ его вершин, в которой $y_{i+1} — сын y_i$ для всех $i$. (Высота дерева из одного корня равна единице, высота пустого дерева — нулю.)

## Упорядоченные $T$-деревья

Пусть на множестве значений типа $T$ фиксирован порядок. Назовём $T$-дерево упорядоченным, если выполнено такое свойство: для любой вершины $x$ все пометки в её левом поддереве меньше пометки в $x$, а все пометки в её правом поддереве больше пометки в $x$.

<figure><img src="image_117.png" /></figure>

### 14.1.1. Докажите, что в упорядоченном дереве все пометки различны.

[Указание. Индукция по высоте дерева.]

<figure><img src="image_118.png" /></figure>

## Представление множеств с помощью деревьев

Каждое дерево будем считать представлением множества всех пометок на его вершинах. При этом одно и то же множество может иметь различные представления.
Если дерево упорядочено, то каждый элемент может легко «найти своё место» в дереве: придя в какую-то вершину и сравнив себя с тем, кто там находится, элемент решает, идти ему налево или направо.

<figure><img src="image_119.png" /></figure>

Начав с корня и двигаясь по этому правилу, он либо обнаружит, что такой элемент уже есть, либо найдёт место, в котором он должен быть.

Всюду далее мы предполагаем, что на значениях типа T задан порядок, и рассматриваем только упорядоченные деревья.

## Хранение деревьев в программе

Можно было бы сопоставить вершины полного двоичного дерева с числами 1, 2, 3, ... (считая, что левый сын $k$ есть $2k$, правый сын $k$ есть $2k + 1$) и хранить пометки в массиве `val[1..n]`. Однако этот способ неэкономен, поскольку тратится место на хранение пустых вакансий в полном двоичном дереве.

Более экономен такой способ. Введём три массива:

```
val: array [1..n] of T;
left, right: array [1..n] of 0..n;
```

($n$ — максимальное возможное число вершин дерева) и переменную `root:0..n`. Каждая вершина хранимого $T$-дерева будет иметь номер — число от 1 до $n$. Разные вершины будут иметь разные номера. Пометка в вершине с номером $x$ равна $val[x]$. Корень имеет номер `root`. Если вершина с номером $i$ имеет сыновей, то их номера равны `left[i]` и `right[i]`. Отсутствующим сыновьям соответствует число 0. Аналогичным образом значение `root=0` соответствует пустому дереву.

Для хранения дерева используется лишь часть массива; для тех $i$, которые свободны (не являются номерами вершин), значения $val[i]$ безразличны. Нам будет удобно, чтобы все свободные числа были «свызаны в список»: первое хранится в специальной переменной `free:0..n`, а следующее за $i$ свободное число хранится в $left[i]$, так что свободны числа

`free, left[free], left[left[free]], ...`
Для последнего свободного числа i значение left[i] равно 0. Равенство free=0 означает, что свободных чисел больше нет.

**Замечание.** Мы использовали для связывания свободных вершин в список массив left, но, конечно, с тем же успехом можно было использовать массив right.

Вместо значения 0 (обозначающего отсутствие вершины) можно было бы воспользоваться любым другим числом вне 1..n. Чтобы подчеркнуть это, будем вместо 0 использовать константу null=0.

**14.1.2.** Составьте программу, определяющую, содержится ли элемент t:T в упорядоченном дереве (хранимом так, как только что описано).

### Решение.

```pascal
if root = null then begin
  ..не принадлежит
end else begin
  x := root;
  {инвариант: остаётся проверить наличие t в непустом
   поддереве с корнем x}
  while ((t < val [x]) and (left [x] <> null)) or
         ((t > val [x]) and (right [x] <> null)) do begin
    if t < val [x] then begin {left [x] <> null}
      x := left [x];
    end else begin {t > val [x], right [x] <> null}
      x := right [x];
    end;
  end;
  {либо t = val [x], либо t отсутствует в дереве}
  ..ответ = (t = val [x])
end;
```

**14.1.3.** Упростите решение, используя следующий трюк. Расширим область определения массива val, добавив ячейку с номером null и положим val[null]=t.

### Решение.

```pascal
val [null] := t;
x := root;
while t <> val [x] do begin
  if t < val [x] then begin
    x := left [x];
  end else begin
```
```
| x := right [x];
end;
end;
..ответ: (x <> null).
```

<figure><img src="image_120.png" /></figure>

**14.1.4.** Составьте программу добавления элемента t в множество, представленное упорядоченным деревом (если элемент t уже есть, ничего делать не надо).

**Решение.** Определим процедуру `get_free` (var i:integer), дающую свободное (не являющееся номером) число i и соответствующим образом корректирующую список свободных чисел.

```pascal
procedure get_free (var i: integer);
begin
  {free <> null}
  i := free;
  free := left [free];
end;
```

С её использованием программа приобретает такой вид:

```pascal
if root = null then begin
  get_free (root);
  left [root] := null; right [root] := null;
  val [root] := t;
end else begin
  x := root;
  {инвариант: осталось добавить t к непустому поддереву с
   корнем в x}
  while ((t < val [x]) and (left [x] <> null)) or
         ((t > val [x]) and (right [x] <> null)) do begin
    if t < val [x] then begin
      x := left [x];
    end else begin {t > val [x]}
      x := right [x];
    end;
  end;
  if t <> val [x] then begin {т нет в дереве}
    get_free (i);
    left [i] := null; right [i] := null;
    val [i] := t;
    if t < val [x] then begin
      left [x] := i;
    end else begin {t > val [x]}
```
```pascal
right [x] := i;
end;
end;
end;
```

14.1.5. Составьте программу удаления элемента t из множества представленного упорядоченным деревом (если его там нет, ничего делать не надо).

Решение.

```pascal
if root = null then begin
  {дерево пусто, ничего делать не надо}
end else begin
  x := root;
  {осталось удалить t из поддерева с корнем в x; поскольку
   это может потребовать изменений в отце x, введём
   переменные father: 1..n и direction: (l, r);
   поддерживаем такой инвариант: если x не корень, то father
   - его отец, a direction равно 1 или r в зависимости от
   того, левым или правым сыном является x}
  while ((t < val [x]) and (left [x] <> null)) or
         ((t > val [x]) and (right [x] <> null)) do begin
    if t < val [x] then begin
      father := x; direction := l;
      x := left [x];
    end else begin {t > val [x]}
      father := x; direction := r;
      x := right [x];
    end;
  end;
  {t = val [x] или t нет в дереве}
  if t = val [x] then begin
    ..удаление вершины x с отцом father и
    направлением direction
  end;
end;
```

Удаление вершины использует процедуру

```pascal
procedure make_free (i: integer);
begin
  left [i] := free;
  free := i;
end;
```
Она включает число i в список свободных. При удалении различаются 4 случая в зависимости от наличия или отсутствия сыновей у удаляемой вершины.

```pascal
if (left [x] = null) and (right [x] = null) then begin
  {x - лист, т.е. не имеет сыновей}
  make_free (x);
  if x = root then begin
    root := null;
  end else if direction = 1 then begin
    left [father] := null;
  end else begin {direction = r}
    right [father] := null;
  end;
end else if (left[x]=null) and (right[x] <> null) then begin
  {x удаляется, а right [x] занимает место x}
  make_free (x);
  if x = root then begin
    root := right [x];
  end else if direction = 1 then begin
    left [father] := right [x];
  end else begin {direction = r}
    right [father] := right [x];
  end;
end else if (left[x] <> null) and (right[x]=null) then begin
  ..симметрично
end else begin {left [x] <> null, right [x] <> null}
  ..удалить вершину с двумя сыновьями
end;
```

Удаление вершины с двумя сыновьями нельзя сделать просто так, но её можно предварительно поменять с вершиной, пометка на которой является непосредственно следующим (в порядке возрастания) элементом за пометкой на x.

```pascal
y := right [x];
father := x; direction := r;
{теперь father и direction относятся к вершине y}
while left [y] <> null do begin
  father := y; direction := l;
  y := left [y];
end;
{val [y] - минимальная из пометок, больших val [x],
  у не имеет левого сына}
```
val [x] := val [y];

...удалить вершину у (как удалять вершину, у которой нет левого сына, мы уже знаем)

<figure><img src="image_121.png" /></figure>

14.1.6. Упростите эту программу, заметив, что некоторые случаи (например, первые два из четырёх) можно объединить. ☐

<figure><img src="image_122.png" /></figure>

14.1.7. Используйте упорядоченные деревья для представления функций, область определения которых — конечные множества значений типа T, а значения имеют некоторый тип U. Операции: вычисление значения на данном аргументе, изменение значения на данном аргументе, доопределение функции на данном аргументе, исключение элемента из области определения функции.

Решение. Делаем как раньше, добавив ещё один массив

func_val: array [1..n] of U;

если `val[x] = t`, `func_val[x] = u`, то значение хранимой функции на `t` равно `u`. ☐

<figure><img src="image_123.png" /></figure>

14.1.8. Предположим, что необходимо уметь также отыскивать к-й элемент множества (в порядке возрастания), причём количество действий должно быть не более $C \cdot (\text{высота дерева})$. Какую дополнительную информацию надо хранить в вершинах дерева?

Решение. В каждой вершине будем хранить число всех её потомков. Добавление и исключение вершины требует коррекции лишь на пути от корня к этой вершине. В процессе поиска к-й вершины поддерживается такой инвариант: искомая вершина является s-й вершиной поддерева с корнем в x (здесь $s$ и $x$ — переменные). ☐

<figure><img src="image_124.png" /></figure>

## Оценка количества действий

Для каждой из операций (проверки, добавления и исключения) количество действий не превосходит $C \cdot (\text{высота дерева})$. Для «ровно подstriженного» дерева (когда все листья на одной высоте) высота по порядку величины равна логарифму числа вершин. Однако для криво-бокого дерева всё может быть гораздо хуже: в наихудшем случае все вершины образуют цепь и высота равна числу вершин. Так случится, если элементы множества добавляются в возрастающем или убывающем порядке. Можно доказать, однако, что при добавлении элементов «в случайном порядке» средняя высота дерева будет не больше $C \log(\text{число вершин})$. Если этой оценки «в среднем» мало, необходимы дополнительные действия по поддержанию «сбалансированности» дерева. Об этом см. в следующем пункте.
## 14.2. Сбалансированные деревья

Дерево называется сбалансированным (или АВ.Л-деревом в честь изобретателей этого метода Г. М. Адельсона-Вельского и Е. М. Ландиса), если для любой его вершины высоты левого и правого поддеревьев этой вершины отличаются не более чем на 1. (В частности, когда одного из сыновей нет, другой — если он есть — обязан быть листом.)

**14.2.1. Найдите минимальное и максимальное возможное количество вершин в сбалансированном дереве высоты $n$.

**Решение.** Максимальное число вершин равно $2^n - 1$. Если $m_n$ — минимальное число вершин, то, как легко видеть, $m_{n+2} = 1 + m_n + m_{n+1}$, откуда $m_n = \Phi_{n+2} - 1$ ($\Phi_n$ — $n$-е число Фибоначчи, $\Phi_1 = 1$, $\Phi_2 = 1$, $\Phi_{n+2} = \Phi_n + \Phi_{n+1}$). $\square$

**14.2.2. Докажите, что сбалансированное дерево с $n$ вершинами имеет высоту не больше $C \log n$ для некоторой константы $C$, не зависящей от $n$.

**Решение.** Индукцией по $n$ легко доказать, что $\Phi_{n+2} \ge a^n$, где $a$ — больший корень квадратного уравнения $a^2 = 1 + a$, то есть $a = (\sqrt{5} + 1)/2$. Остаётся воспользоваться предыдущей задачей. $\square$

### Вращения

Мы хотим восстанавливать сбалансированность дерева после включения и удаления элементов. Для этого необходимы какие-то преобразования дерева, не меняющие множества пометок на его вершинах и не нарушающие упорядоченности, но способствующие лучшей сбалансированности. Опишем несколько таких преобразований.

<figure><img src="image_125.png" /></figure>

Пусть вершина $a$ имеет правого сына $b$. Обозначим через $P$ левое поддерево вершины $a$, через $Q$ и $R$ — левое и правое поддеревья вершины $b$. Упорядоченность дерева требует, чтобы $P < a < Q < b < R$ (точнее сле-
довало бы сказать «любая пометка на $P$ меньше пометки на $a$», «пометка на $a$ меньше любой пометки на $Q$» и т. д., но мы позволим себе этого не делать). Точно того же требует упорядоченность дерева с корнем $b$, его левым сыном $a$, в котором $P$ и $Q$ — левое и правое поддеревья $a$, $R$ — правое поддерево $b$. Поэтому первое дерево можно преобразовать во второе, не нарушая упорядоченности. Такое преобразование назовём **малым правым вращением** (правым — поскольку существует симметричное, левое, малым — поскольку есть и большое, которое мы сейчас опишем).

Пусть $b$ — правый сын $a$, $c$ — левый сын $b$, $P$ — левое поддерево $a$, $Q$ и $R$ — левое и правое поддеревья $c$, $S$ — правое поддерево $b$. Тогда $P < a < Q < c < R < b < S$.

<figure><img src="image_126.png" /></figure>

Такой же порядок соответствует дереву с корнем $c$, имеющим левого сына $a$ и правого сына $b$, для которого $P$ и $Q$ — поддеревья вершины $a$, $a$ и $R$ — поддеревья вершины $b$. Соответствующее преобразование будем называть **большим правым вращением**. (Аналогично определяется симметричное ему большое левое вращение.)

### 14.2.3. Дано дерево, сбалансированное всюду, кроме корня, в котором разница высот равна 2 (т. е. левое и правое поддеревья корня сбалансированы и их высоты отличаются на 2). Докажите, что оно может быть превращено в сбалансированное одним из четырёх описанных преобразований, причём высота его останется прежней или уменьшиться на 1.

**Решение.** Пусть более низким является, например, левое поддерево, и его высота равна $k$. Тогда высота правого поддерева равна $k + 2$. Обозначим корень через $a$, а его правого сына (он обязательно есть) через $b$. Рассмотрим левое и правое поддеревья вершины $b$. Одно из них обязательно имеет высоту $k + 1$, а другое может иметь высоту $k$ или $k + 1$ (меньше $k$ быть не может, так как поддеревья сбалансированы).
Если высота левого поддерева равна $k + 1$, а правого — $k$, то потребуется большое правое вращение; в остальных случаях помогает малое. Вот как выглядят три случая балансировки дерева:

<figure><img src="image_127.png" /></figure>

<figure><img src="image_128.png" /></figure>

### 14.2.4. В сбалансированное дерево добавили или из него удалили лист. Докажите, что можно восстановить сбалансированность с помощью нескольких вращений, причём их число не больше высоты дерева.

**Решение.** Будем доказывать более общий факт:

**Лемма.** Если в сбалансированном дереве $X$ одно из его поддеревьев $Y$ заменили на сбалансированное дерево $Z$, причём высота $Z$ отличается от высоты $Y$ не более чем на 1, то полученное такой «прививкой» дерево можно превратить в сбалансированное вращениями (причём количество вращений не превосходит высоты, на которой делается прививка).

Частным случаем прививки является замена пустого поддерева на лист или наоборот, так что достаточно доказать эту лемму.

**Доказательство леммы.** Индукция по высоте, на которой делается прививка. Если она происходит в корне (заменяется всё дерево цели-
ком), то всё очевидно («привой» сбалансирован по условию). Пусть заменяется некоторое поддерево, например, левое поддерево некоторой вершины x. Возможны два случая.

1) После прививки сбалансированность в вершине x не нарушилась (хотя, возможно, нарушилась сбалансированность в предках x: высота поддерева с корнем в x могла измениться). Тогда можно сослаться на предположение индукции, считая, что мы прививали целиком поддерево с корнем в x.

2) Сбалансированность в x нарушилась. При этом разница высот равна 2 (больше она быть не может, так как высота Z отличается от высоты Y не более чем на 1). Разберём два варианта.

<figure><img src="image_129.png" /><figcaption>(а)</figcaption></figure>

<figure><img src="image_130.png" /><figcaption>(б)</figcaption></figure>

а) Выше правое (не заменявшееся) поддерево вершины x. Пусть высота левого (т. е. Z) равна k, правого — k + 2. Высота старого левого поддерева вершины x (т. е. Y) была равна k + 1. Поддерево с корнем x имело в исходном дереве высоту k + 3, и эта высота не изменилась после прививки.

По предыдущей задаче вращение преобразует поддерево с корнем в x в сбалансированное поддерево высоты k + 2 или k + 3. То есть высота поддерева с корнем x — в сравнении с его прежней высотой — не изменилась или уменьшилась на 1, и мы можем воспользоваться предположением индукции.

б) Выше левое поддерево вершины x. Пусть высота левого (т. е. Z) равна k + 2, правого — k. Высота старого левого поддерева (т. е. Y) была равна k + 1. Поддерево с корнем x в исходном дереве X имело высоту k + 2, после прививки она стала равна k + 3. После подходящего вращения (см. предыдущую задачу) поддерево с корнем в x станет сбалансированым, его высота будет равна k + 2 или k + 3, так что изменение высоты по сравнению с высотой поддерева с корнем x в дереве X не превосходит 1 и можно сослаться на предположение индукции. ☐
### 14.2.5. Составьте программы добавления и удаления элементов, сохраняющие сбалансированность. Число действий не должно превосходить $C$ (высота дерева). Разрешается хранить в вершинах дерева дополнительную информацию, необходимую при балансировке.

**Решение.** Будем хранить для каждой вершины разницу между высотой её правого и левого поддеревьев:

$$ \text{diff } [i] = (\text{высота правого поддерева вершины } i) - (\text{высота левого поддерева вершины } i). $$

Нам потребуются четыре процедуры, соответствующие большим и малым правым и левым вращениями. Но вначале два замечания. (1) Нам нужно, чтобы при вращении поддерева номер его корня не менялся. (В противном случае потребовалось бы корректировать информацию в отце корня, что нежелательно.) Этого можно достичь, так как номера вершин дерева можно выбирать независимо от их значений. (На картинках номер указан сбоку от вершины, а значение — внутри.)

<figure><img src="image_131.png" /></figure>

<figure><img src="image_132.png" /></figure>

(2) После преобразований мы должны также изменить соответственно значения в массиве `diff`. Для этого достаточно знать высоты деревьев $P, Q, \dots$ с точностью до константы, поэтому можно предполагать, что одна из высот равна нулю.
Вот процедуры вращений:

```pascal
procedure SR (a:integer); {малое правое вращение с корнем а}
  var b: 1..n; val_a,val_b: T; h_P,h_Q,h_R: integer;
begin
  b := right [a]; {b <> null}
  val_a := val [a]; val_b := val [b];
  h_Q := 0; h_R := diff[b]; h_P := (max(h_Q,h_R)+1)-diff[a];
  val [a] := val_b; val [b] := val_a;
  right [a] := right [b] {поддерево R}
  right [b] := left [b] {поддерево Q}
  left [b] := left [a] {поддерево P}
  left [a] := b;
  diff [b] := h_Q - h_P;
  diff [a] := h_R - (max (h_P, h_Q) + 1);
end;
```

```pascal
procedure BR(a:integer); {большое правое вращение с корнем а}
  var b,c: 1..n; val_a,val_b,val_c: T;
    h_P,h_Q,h_R,h_S: integer;
begin
  b := right [a]; c := left [b]; {b,c <> null}
  val_a := val [a]; val_b := val [b]; val_c := val [c];
  h_Q := 0; h_R := diff[c]; h_S := (max(h_Q,h_R)+1)+diff[b];
  h_P := 1 + max (h_S, h_S-diff[b]) - diff [a];
  val [a] := val_c; val [c] := val_a;
  left [b] := right [c] {поддерево R}
  right [c] := left [c] {поддерево Q}
  left [c] := left [a] {поддерево P}
  left [a] := c;
  diff [b] := h_S - h_R;
  diff [c] := h_Q - h_P;
  diff [a] := max (h_S, h_R) - max (h_P, h_Q);
end;
```

Левые вращения (большое и малое) записываются симметрично.

Процедуры добавления и удаления элементов пишутся как раньше, но только добавление и удаление должно сопровождаться коррекцией массива `diff` и восстановлением сбалансированности.

При этом используется процедура с такими свойствами:

**дано:** левое и правое поддеревья вершины с номером а сбалансированы, в самой вершине разница высот не больше 2, в поддереве с корнем а массив `diff` заполнен привильно;
**надо:** поддерево с корнем а сбалансировано и массив `diff` соответственно изменён, `d` — изменение его высоты (равно 0 или -1); в остальной части всё осталось как было — в частности, значения `diff`.

```pascal
procedure balance (a: integer; var d: integer);
begin {-2 <= diff[a] <= 2}
  if diff [a] = 2 then begin
    b := right [a];
    if diff [b] = -1 then begin
      BR (a); d := -1;
      end else if diff [b] = 0 then begin
        SR (a); d := 0;
        end else begin {diff [b] = 1}
          SR (a); d := -1;
        end;
    end else if diff [a] = -2 then begin
      b := left [a];
      if diff [b] = 1 then begin
        BL (a); d := -1;
        end else if diff [b] = 0 then begin
          SL (a); d := 0;
          end else begin {diff [b] = -1}
            SL (a); d := -1;
          end;
    end else begin {-2 < diff [a] < 2, ничего делать не надо}
      d := 0;
    end;
  end;
end;
```

Восстановление сбалансированности требует движения от листьев к корню, поэтому будем хранить в стеке путь от корня дерева к рассматриваемой в данный момент вершине. Элементами стека будут пары `(вершина, направление движения из неё)`, т. е. значения типа

```pascal
record
  vert: 1..n; {вершина}
  direction: (l, r); {l - левое, r - правое}
end;
```

Программа добавления элемента `t` теперь выглядит так:

```pascal
if root = null then begin
  get_free (root);
  left[root] := null; right[root] := null; diff[root] := 0;
end;
```
```c
val[root] := t;
end else begin
    x := root;
    ..сделать стек пустым
    {инвариант: осталось добавить t к непустому поддереву с
    корнем в x; стек содержит путь к x}
    while ((t < val [x]) and (left [x] <> null)) or
           ((t > val [x]) and (right [x] <> null)) do begin
        if t < val [x] then begin
            ..Добавить в стек пару <x, 1>
            x := left [x];
        end else begin {t > val [x]}
            ..Добавить в стек пару <x, r>
            x := right [x];
        end;
    end;
    if t <> val [x] then begin {т нет в дереве}
        get_free (i); val [i] := t;
        left [i] := null; right [i] := null; diff [i] := 0;
        if t < val [x] then begin
            ..Добавить в стек пару <x, 1>
            left [x] := i;
        end else begin {т > val [x]}
            ..Добавить в стек пару <x, r>
            right [x] := i;
        end;
    d := 1;
    {инвариант: стек содержит путь к изменившемуся
    поддереву, высота которого увеличилась по сравнению
    с высотой в исходном дереве на d (=0 или 1); это
    поддерево сбалансировано; значения diff для его
    вершин правильны; в остальном дереве всё осталось
    как было - в частности, значения diff}
    while (d <> 0) and ..стек непуст do begin {d = 1}
        ..взять из стека пару в <v, direct>
        if direct = 1 then begin
            if diff [v] = 1 then begin
                c := 0;
            end else begin
                c := 1;
            end;
            diff [v] := diff [v] - 1;
        end else begin
            {direct = r}
```
```pascal
if diff [v] = -1 then begin
  c := 0;
  end else begin
  c := 1;
  end;
  diff [v] := diff [v] + 1;
end;

{с = изменение высоты поддерева с корнем в v по сравнению с исходным деревом; массив diff содержит правильные значения для этого поддерева; возможно нарушение сбалансированности в v}
balance (v, d1); d := c + d1;
end;
end;
end;
```

Легко проверить, что значение d может быть равно только 0 или 1 (но не -1): если c=0, то diff [v]=0 и балансировка не производится.

Программа удаления строится аналогично. Её основной фрагмент таков:

```pascal
{инвариант: стек содержит путь к изменившемуся поддереву, высота которого изменилась по сравнению с высотой в исходном дереве на d (=0 или -1); это поддерево сбалансировано; значения diff для его вершин правильны; в остальном дереве всё осталось как было - в частности, значения diff}
while (d <> 0) and ..стек непуст do begin
  {d = -1}
  ..взять из стека пару в <v, direct>
  if direct = 1 then begin
    if diff [v] = -1 then begin
      c := -1;
      end else begin
      c := 0;
      end;
      diff [v] := diff [v] + 1;
    end else begin {direct = r}
      if diff [v] = 1 then begin
        c := -1;
        end else begin
        c := 0;
      end;
      diff [v] := diff [v] - 1;
    end;
  end;
```
```c
{
    c = изменение высоты поддерева с корнем в v по
        сравнению с исходным деревом; массив diff содержит
        правильные значения для этого поддерева;
        возможно нарушение сбалансированности в v}
    balance (v, d1);
    d := c + d1;
end;
```

Легко проверить, что значение `d` может быть равно только 0 или -1 (но не -2): если `c=-1`, то `diff[v]=0` и балансировка не производится.

Отметим также, что наличие стека делает излишними переменные `father` и `direction` (их роль теперь играет вершина стека). ☐

### 14.2.6. Докажите, что при добавлении элемента

(а) второй из трёх случаев балансировки (см. рисунок на с. 259) невозможен;

(б) полная балансировка требует не более одного вращения (после чего всё дерево становится сбалансированным), в то время как при удалении элемента может понадобиться много вращений. ☐

**Замечание.** Мы старались записать программы добавления и удаления так, чтобы они были как можно более похожими друг на друга. Используя специфику каждой из них, можно многое упростить.

Существуют и другие способы представления множеств, гарантирующие число действий порядка $\log n$ на каждую операцию. Опишем один из них (называемый Б-деревьями).

До сих пор каждая вершина содержала один элемент хранимого множества. Этот элемент служил границей между левым и правым поддеревом. Будем теперь хранить в вершине $k \ge 1$ элементов множества (число $k$ может меняться от вершины к вершине, а также при добавлении и удалении новых элементов, см. далее). Эти $k$ элементов служат разделителями для $k+1$ поддеревьев. Пусть фиксировано некоторое число $t \ge 1$. Будем рассматривать деревья, обладающие такими свойствами:

1) Каждая вершина содержит от $t$ до $2t$ элементов (за исключением корня, который может содержать любое число элементов от 0 до $2t$).

2) Вершина с $k$ элементами либо имеет $k+1$ сыновей, либо не имеет сыновей вообще (является листом).

3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он попадает, неполон (т. е. содержит менее 2t элементов), то нет проблем. Если он полон, то 2t + 1 элемент (все элементы листа и новый элемент) разбиваем на два листа по t элементов и разделяющий их серединный элемент. Этот серединный элемент надо добавить в вершину предыдущего уровня. Это возможно, если в ней менее 2t элементов. Если и она полна, то её разбивают на две, выделяют серединный элемент и т. д. Если в конце концов мы захотим добавить элемент в корень, а он окажется полным, то корень расщепляется на две вершины, а высота дерева увеличивается на 1.

Удаление элемента, находящегося не в листе, сводится к удалению непосредственно следующего за ним, который находится в листе. Поэтому достаточно научиться удалять элемент из листа. Если лист при этом становится слишком маленьким, то его можно пополнить за счёт соседнего листа — если только и он не имеет минимально возможный размер t. Если же оба листа имеют размер t, то на них вместе 2t элементов, вместе с разделителем — 2t + 1. После удаления одного элемента остаётся 2t элементов — как раз на один лист. Если при этом вершина предыдущего уровня становится меньше нормы, процесс повторяется и т. д.

### 14.2.7. Реализуйте описанную схему хранения множеств, убедившись, что она также позволяет обойтись $C \log n$ действий для операций включения, исключения и проверки принадлежности. □

### 14.2.8. Можно определять сбалансированность дерева иначе: требовать, чтобы для каждой вершины её левое и правое поддеревья имели не слишком сильно отличающиеся количества вершин. (Преимущество такого определения состоит в том, что при вращениях не нарушается сбалансированность в вершинах, находящихся ниже точки вращения.) Реализуйте на основе этой идеи способ хранения множеств, гарантирующий оценку в $C \log n$ действий для включения, удаления и проверки принадлежности.

> [Указание. Он также использует большие и малые вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део «Комбинаторные алгоритмы».] □
# 15. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ

## 15.1. Общий алгоритм разбора

Чтобы определить то, что называют контекстно-свободной грамматикой (КС-грамматикой), надо:

* указать конечное множество А, называемое алфавитом; его элементы называют символами; конечные последовательности символов называют словами (в данном алфавите);

* разделить все символы алфавита А на две группы: терминальные («окончательные») и нетерминальные («промежуточные»);

* выбрать среди нетерминальных символов один, называемый начальным;

* указать конечное число правил грамматики, каждое из которых должно иметь вид $K \to X$, где K — некоторый нетерминальный символ, а X — слово (в него могут входить и терминальные, и нетерминальные символы).

Пусть фиксирована КС-грамматика (мы часто будем опускать префикс «КС-», так как других грамматик у нас не будет). Выводом в этой грамматике называется последовательность слов $X_0, X_1, ..., X_n$, в которой $X_0$ состоит из одного символа, и этот символ — начальный, а $X_{i+1}$ получается из $X_i$ заменой некоторого нетерминального символа K на слово X по одному из правил грамматики. Слово, составленное из терминальных символов, называется выводимым, если существует вывод, который им кончается. Множество всех выводимых слов (из терминальных символов) называется языком, порождаемым данной грамматикой.
В этой и следующей главе нас будет интересовать такой вопрос: дана КС-грамматика; построить алгоритм, который по любому слову проверяет, выводимо ли оно в этой грамматике.

**Пример 1.** Алфавит:

( ) [ ] E

(четыре терминальных символа и один нетерминальный символ E). Начальный символ: E. Правила:

E → (E)
E → [E]
E → EE
E →

(в последнем правиле справа стоит пустое слово).

Примеры выводимых слов:

(пустое слово)
( )
([])
()[[]]
[()[]()[]]

Примеры невыводимых слов:

( )
)(
[]
([)]

Эта грамматика встречалась в разделе 6.1 (где выводимость в ней проверялась с помощью стека).

**Пример 2.** Другая грамматика, порождающая тот же язык:

Алфавит: ( ) [ ] T E

Правила:

E →
E → TE
T → (E)
T → [E]
Начальным символом во всех приводимых далее примерах будем считать символ, стоящий в левой части первого правила (в данном случае это символ Е), не оговаривая этого особо.

Для каждого нетерминального символа можно рассмотреть множество всех слов из терминальных символов, которые из него выводятся (аналогично тому, как это сделано для начального символа в определении выводимости в грамматике). Каждое правило грамматики можно рассматривать как свойство этих множеств. Покажем это на примере только что приведённой грамматики. Пусть T и E — множества слов (из скобок), выводимых из нетерминалов T и Е соответственно. Тогда правилам грамматики соответствуют такие свойства:

<table><tr><td>E →</td><td>E содержит пустое слово</td></tr><tr><td>E → TE</td><td>если слово А принадлежит T,<br>а слово В принадлежит E, то<br>слово AB принадлежит E</td></tr><tr><td>T → [E]</td><td>если А принадлежит E, то слово<br>[A] принадлежит T</td></tr><tr><td>T → (E)</td><td>если А принадлежит E, то слово<br>(A) принадлежит T</td></tr></table>

Сформулированные свойства множеств E, T не определяют эти множества однозначно (например, они остаются верными, если в качестве E и T взять множество всех слов). Однако можно доказать, что множества, задаваемые грамматикой, являются минимальными среди удовлетворяющих этим условиям.

**15.1.1.** Сформулируйте точно и докажите это утверждение для произвольной контекстно-свободной грамматики. ☐

**15.1.2.** Постройте грамматику, в которой выводимы слова
(a) 00..0011..11 (число нулей равно числу единиц);
(b) 00..0011..11 (число нулей вдвое больше числа единиц);
(в) 00..0011..11 (число нулей больше числа единиц);
(и только они). ☐

**15.1.3.** Докажите, что не существует КС-грамматики, в которой были бы выводимы слова вида 00..0011..1122..22, в которых числа нулей, единиц и двоек равны, и только они.

[Указание. Докажите следующую лемму о произвольной КС-грамматике: для любого достаточно длинного слова F, выводимого в этой грамматике, существует такое его представление в виде АВСDE, что
любое слово вида AB... BCD... DE, где B и D повторены одинаковое число раз, также выводимо в этой грамматике. (Это можно установить, найдя нетерминальный символ, оказывающийся своим собственным «наследником» в процессе вывода.)]

Нетерминальный символ можно рассматривать как «родовое имя» для выводимых из него слов. В следующем примере для наглядности в качестве нетерминальных символов использованы фрагменты русских слов, заключённые в угловые скобки. (С точки зрения грамматики каждый такой фрагмент — один символ!)

**Пример 3.** Алфавит:

терминалы: + * ( ) x

нетерминалы: 〈выр〉 〈оствыр〉 〈слаг〉 〈остслаг〉 〈множ〉

Правила:

〈выр〉 → 〈слаг〉 〈оствыр〉

〈оствыр〉 → + 〈выр〉

〈оствыр〉 →

〈слаг〉 → 〈множ〉 〈остслаг〉

〈остслаг〉 → * 〈слаг〉

〈остслаг〉 →

〈множ〉 → x

〈множ〉 → ( 〈выр〉 )

Согласно этой грамматике, выражение 〈выр〉 — это последовательность слагаемых 〈слаг〉, разделённых плюсами, слагаемое — это последовательность множителей 〈множ〉, разделённых звёздочками (знаками умножения), а множитель — это либо буква x, либо выражение в скобках.

**15.1.4.** Приведите пример другой грамматики, задающей тот же язык.

**Ответ.** Вот один из вариантов:

〈выр〉 → 〈выр〉 + 〈выр〉

〈выр〉 → 〈выр〉 * 〈выр〉

〈выр〉 → x

〈выр〉 → ( 〈выр〉 )

<figure><img src="image_133.png" /></figure>

Эта грамматика хоть и проще, но в некоторых отношениях хуже, о чём мы ещё будем говорить.
**15.1.5.** Дана произвольная КС-грамматика. Постройте алгоритм проверки принадлежности задаваемому ей языку, работающий полиномиальное время (т. е. число действий не превосходит полинома от длины проверяемого слова; полином может зависеть от грамматики).

**Решение.** Заметим, что требование полиномиальности исключает возможность решения, основанном на переборе всех возможных выводов. Тем не менее полиномиальный алгоритм существует. Поскольку практического значения он не имеет (используемые на практике КС-грамматики обладают дополнительными свойствами, позволяющими строить более эффективные алгоритмы), мы изложим лишь общую схему решения.

(1) Пусть в грамматике есть нетерминалы $K_1, \dots, K_n$. Построим новую грамматику с нетерминалами $K'_1, \dots, K'_n$ так, чтобы выполнялось такое свойство: из $K'_i$ выводятся (в новой грамматике) те же слова, что из $K_i$ в старой, за исключением пустого слова, которое не выводится.

Чтобы выполнить такое преобразование грамматики, надо выяснить, из каких нетерминалов исходной грамматики выводится пустое слово, а затем каждое правило заменить на совокупность правил, получающихся, если в правой части опустить какие-либо из нетерминалов, из которых выводится пустое слово, а у остальных поставить штрихи. Например, если в исходной грамматике было правило

$$K \to L M N,$$

причём из L и N выводится пустое слово, а из M нет, то это правило надо заменить на правила

$$K' \to L' M' N'$$

$$K' \to M' N'$$

$$K' \to L' M'$$

$$K' \to M'$$

(2) Итак, мы свели дело к грамматике, где ни из одного нетерминала не выводится пустое слово. Теперь устраним «циклы» вида

$$K \to L$$

$$L \to M$$

$$M \to N$$

$$N \to K$$

(в правой части каждого правила один символ, и эти символы образуют цикл произвольной длины): это легко сделать, отождествив все входящие в цикл нетерминалы.
(3) Теперь проверка принадлежности какого-либо слова языку, порождённому грамматикой, может выполняться так: для каждого подслова проверяемого слова и для каждого нетерминала выясняем, порождается ли это подслово этим нетерминалом. При этом подслова проверяются в порядке возрастания длин, а нетерминалы — в таком порядке, чтобы при наличии правила $K \to L$ нетерминал $L$ проверялся раньше нетерминала $K$. (Это возможно в силу отсутствия циклов.) Поясним этот процесс на примере.

Пусть в грамматике есть правила

$K \to L$
$K \to M N L$

и других правил, содержащих $K$ в левой части, нет. Мы хотим узнать, выводится ли данное слово $A$ из нетерминала $K$. Это будет так в одном из случаев:

* если $A$ выводится из $L$;

* если $A$ можно разбить на непустые слова $B, C, D$, для которых $B$ выводится из $M, C$ выводится из $N$, а $D$ выводится из $L$.

Вся эта информация уже есть (слова $B, C, D$ короче $A$, а $L$ рассмотрен до $K$).

Легко видеть, что число действий этого алгоритма полиномиально. Степень полинома зависит от числа нетерминалов в правых частях правил и может быть понижена, если грамматику преобразовать к форме, в которой правая часть каждого правила не более 2 нетерминалов (это легко сделать, вводя новые нетерминалы: например, правило $K \to LMK$ можно заменить на $K \to LN$ и $N \to MK$, где $N$ — новый нетерминал). ☐

**15.1.6.** Рассмотрим грамматику с единственным нетерминалом $K$, нетерминалами $0, 1, 2, 3$ и правилами

$K \to 0$
$K \to 1 K$
$K \to 2 K K$
$K \to 3 K K K$

Как проверить выводимость слова в этой грамматике, читая слово слева направо? (Число действий при прочтении одной буквы должно быть ограничено.)
**Решение.** Хранится целая переменная n, инвариант: слово выводимо ⇔ непрочитанная часть представляет собой конкатенацию (соединение) n выводимых слов. ☐

**15.1.7.** Тот же вопрос для грамматики

К → 0

К → К 1

К → К К 2

К → К К К 3

<figure><img src="image_134.png" /></figure>

## 15.2. Метод рекурсивного спуска

В отличие от алгоритма предыдущего раздела (представляющего чисто теоретический интерес), алгоритмы на основе рекурсивного спуска часто используются на практике. Этот метод применим, однако, далеко не ко всем грамматикам. Мы обсудим необходимые ограничения позднее.

Идея метода рекурсивного спуска такова. Для каждого нетерминала K мы строим процедуру ReadK, которая — в применении к любому входному слову x — делает две вещи:

* находит наибольшее начало z слова x, которое может быть началом выводимого из K слова;

* сообщает, является ли найденное слово z выводимым из K.

Прежде чем описывать этот метод более подробно, договоримся о том, как процедуры получают сведения о входном слове и как сообщают о результатах своей работы. Мы предполагаем, что буквы входного слова поступают к ним по одной, т. е. имеется граница, отделяющая «прочитанную» часть от «непрочитанной». Будем считать, что есть функция (без параметров)

### Next: Symbol

дающая первый непрочитанный символ. Её значениями могут быть терминальные символы, а также специальный символ EOI (End Of Input — конец входа), означающий, что всё слово уже прочитано. Вызов этой функции, разумеется, не сдвигает границы между прочитанной и непрочитанной частью — для этого есть процедура Move, которая сдвигает границу на один символ. (Она применима, если Next<>EOI.) Пусть, наконец, имеется булевская переменная b.
Теперь мы можем сформулировать наши требования к процедуре ReadK. Они состоят в следующем:

* ReadK прочитывает из оставшейся части слова максимальное начало А, являющееся началом некоторого слова, выводимого из K;

* значение b становится истинным или ложным в зависимости от того, является ли А выводимым из К или лишь невыводимым началом выводимого (из К) слова.

Для удобства введём такую терминологию: выводимое из К слово будем называть К-словом, а любое начало любого выводимого из К слова — К-началом. Два сформулированных требования вместе будем выражать словами «ReadK корректна для К».

Начнём с примера. Пусть правило

$$K \to L M$$

является единственным правилом грамматики, содержащим К в левой части, пусть L, M — нетерминалы и ReadL, ReadM — корректные (для них) процедуры.

Рассмотрим такую процедуру:

```
procedure ReadK;
begin
    ReadL;
    if b then begin
        ReadM;
    end;
end;
```

15.2.1. Приведите пример, когда эта процедура будет некорректной для К.

**Ответ.** Пусть из L выводится любое слово вида 00...00, а из M выворачивается лишь слово 01. Тогда из К выводится слово 00001, но процедура ReadK этого не заметит. ☐

Укажем достаточные условия корректности процедуры ReadK. Для этого нам понадобятся некоторые обозначения. Пусть фиксированы КС-грамматика и некоторый нетерминал N этой грамматики. Рассмотрим N-слово А, которое имеет собственное начало В, также являю-
щеся N-словом (если такие есть). Для любой пары таких слов А и В
рассмотрим терминальный символ, идущий в А непосредственно за В.
Множество всех таких терминалов обозначим Посл(N). (Если никакое
N-слово не является собственным началом другого N-слова, то множе-
ство Посл(N) пусто.)

15.2.2. Укажите (а) Посл(Е) для примера 1 (с. 269); (б) Посл(Е) и Посл(Т) для примера 2 (с. 269); (в) Посл(⟨слаг⟩) и Посл(⟨множ⟩) для примера 3 (с. 271);

Ответ. (а) Посл(Е) = {[, (}. (б) Посл(Е) = {[, (; Посл(Т) пусто (ни-
какое Т-слово не является началом другого). (в) Посл(⟨слаг⟩) = {\*};
Посл(⟨множ⟩) пусто. ☐

Кроме того, для каждого нетерминала N обозначим через Нач(N)
множество всех терминалов, являющихся первыми буквами непустых
N-слов. Это обозначение — вместе с предыдущим — позволит дать
достаточное условие корректности процедуры ReadK в описанной выше
ситуации.

15.2.3. Докажите, что если Посл(L) не пересекается с Нач(M) и мно-
жество всех М-слов непусто, то ReadK корректна.

Решение. Рассмотрим два случая.

(1) Пусть после ReadL значение переменной b ложно. В этом слу-
чае ReadL читает со входа максимальное L-начало А, не являющееся
L-словом. Оно является К-началом (здесь важно, что множество М-слов
непусто.). Будет ли оно максимальным К-началом среди начал входа?
Если нет, то А является началом слова BC, где В есть L-слово, С есть
М-начало и BC — более длинное начало входа, чем А. Если В длиннее А,
то А — не максимальное начало входа, являющееся L-началом, что про-
тиворечит корректности ReadL. Если В = А, то А было бы L-словом,
а это не так. Значит, В короче А, С непусто и первый символ слова С
следует в А за последним символом слова В, т. е. Посл(L) пересекается
с Нач(M). Противоречие. Итак, А максимально. Из сказанного следу-
ет также, что А не является К-словом. Корректность процедуры ReadK
в этом случае проверена.

(2) Пусть после ReadL значение переменной b истинно. Тогда прочи-
танное процедурой ReadK начало входа имеет вид AB, где А есть L-сло-
во, а В есть М-начало. Тем самым AB есть К-начало. Проверим его мак-
симальность. Пусть С есть большее К-начало. Тогда либо С есть L-на-
чало (что невозможно, так как А было максимальным L-началом), либо
C = А'В', где А' — L-слово, В' — М-начало. Если А' короче А, то В' не-
пусто и начинается с символа, принадлежащего и Нач(M), и Посл(L),
что невозможно. Если $A'$ длиннее $A$, то $A$ — не максимальное L-начало. Итак, $A' = A$. Но в этом случае $B'$ есть продолжение $B$, что противоречит корректности ReadM. Таким образом, $AB$ — максимальное K-начало. Остаётся проверить правильность выдаваемого процедурой ReadK значения переменной $b$. Если оно истинно, то это очевидно. Если оно ложно, то $B$ не есть М-слово, и надо проверить, что $AB$ — не K-слово. В самом деле, если бы выполнялось $AB = A'B'$, где $A' = L$-слово, $B' = M$-слово, то $A'$ не может быть длиннее $A$ (ReadL читает максимальное слово), $A'$ не может быть равно $A$ (тогда $B'$ равно $B$ и не является М-словом) и $A'$ не может быть короче $A$ (тогда первый символ $B'$ принадлежит и Нач(M), и Посл(L)). Задача решена. ☐

Перейдём теперь к другому частному случаю. Пусть в КС-грамматике есть правила

$K \to L$
$K \to M$
$K \to N$

и других правил с левой частью K нет.

### 15.2.4. Считая, что ReadL, ReadM и ReadN корректны (для L, M и N) и что множества Нач(L), Нач(M) и Нач(N) не пересекаются, напишите процедуру, корректную для K.

**Решение.** Схема процедуры такова:

```
procedure ReadK;
begin
    if (Next принадлежит Нач(L)) then begin
        ReadL;
    end else if (Next принадлежит Нач(M)) then begin
        ReadM;
    end else if (Next принадлежит Нач(N)) then begin
        ReadN;
    end else begin
        b := true или false в зависимости от того,
        выводимо ли пустое слово из K или нет
    end;
end;
```

Докажем, что ReadK корректно реализует K. Если Next не принадлежит ни одному из множеств Нач(L), Нач(M), Нач(N), то пустое слово является
наибольшим началом входа, являющимся К-началом. Если Next принад-
лежит одному (и, следовательно, только одному) из этих множеств, то
максимальное начало входа, являющееся К-началом, непусто и читается
соответствующей процедурой. ☐

15.2.5. Используя сказанное, составьте процедуру распознавания выражений для грамматики (пример 3, с. 271):

⟨выр⟩ → ⟨слаг⟩ ⟨оствыр⟩
⟨оствыр⟩ → + ⟨выр⟩
⟨оствыр⟩ →
⟨слаг⟩ → ⟨множ⟩ ⟨остслаг⟩
⟨остслаг⟩ → * ⟨слаг⟩
⟨остслаг⟩ →
⟨множ⟩ → x
⟨множ⟩ → ( ⟨выр⟩ )

Решение. Эта грамматика не полностью подпадает под рассмотрен-
ные частные случаи: в правых частях есть комбинации терминалов и не-
терминалов

+ ⟨выр⟩

и группы из трёх символов

( ⟨ выр ⟩ )

В грамматике есть также несколько правил с одной левой частью и с
правыми частями разного рода, например

⟨оствыр⟩ → + ⟨выр⟩
⟨оствыр⟩ →

Эти ограничения не являются принципиальными. Так, правило типа
K → L M N можно было бы заменить на два правила K → L Q и Q → M N,
терминальные символы в правой части — на нетерминалы (с един-
ственным правилом замены на соответствующие терминалы). Несколь-
ко правил с одной левой частью и разнородными правыми также можно
свести к уже разобранному случаю: например,

```
K → L M N
K → P Q
K →
```

можно заменить на правила

```
K → K₁
K → K₂
K → K₃
K₁ → L M N
K₂ → P Q
K₃ →
```

Но мы не будем этого делать — а сразу же запишем то, что получится, если подставить описания процедур для новых терминальных символов в места их использования. Например, для правила

```
K → L M N
```

это даёт процедуру

```
procedure ReadK;
begin
    ReadL;
    if b then begin
        ReadM;
    end;
    if b then begin
        ReadN;
    end;
end;
```

Для её корректности надо, чтобы Посл(L) не пересекалось с Нач(MN) (которое равно Нач(M), если из M не выводится пустое слово, и равно объединению Нач(M) и Нач(N), если выводится), а также чтобы Посл(M) не пересекалось с Нач(N).

Аналогичным образом правила

```
K → L M N
K → P Q
K →
```
приводят к процедуре

procedure ReadK;
begin
  if (Next принадлежит Нач(LMN)) then begin
    ReadL;
    if b then begin ReadM; end;
    if b then begin ReadN; end;
  end else if (Next принадлежит Нач(PQ)) then begin
    ReadP;
    if b then begin ReadQ; end;
  end else begin
    b := true;
  end;
end;

корректность которой требует, чтобы Нач(LMN) не пересекалось с Нач(PQ).

Читая приведённую далее программу, полезно иметь в виду соот-
ветствие между русскими и английскими словами:

<table>
  <tr>
    <td>ВЫРАЖЕНИЕ</td>
    <td>EXPRESSION</td>
  </tr>
  <tr>
    <td>ОСТАТОК ВЫРАЖЕНИЯ</td>
    <td>REST OF EXPRESSION</td>
  </tr>
  <tr>
    <td>СЛАГАЕМОЕ</td>
    <td>ADDITIVE TERM</td>
  </tr>
  <tr>
    <td>ОСТАТОК СЛАГАЕМОГО</td>
    <td>REST OF ADDITIVE TERM</td>
  </tr>
  <tr>
    <td>МНОЖИТЕЛЬ</td>
    <td>FACTOR</td>
  </tr>
  <tr>
    <td>procedure ReadSymbol (c: Symbol);</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;b := (Next = c);</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;if b then begin</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Move;</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end;</td>
    <td></td>
  </tr>
  <tr>
    <td>end;</td>
    <td></td>
  </tr>
  <tr>
    <td>procedure ReadExpr;</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;ReadAdd;</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;if b then begin ReadRestExpr; end;</td>
    <td></td>
  </tr>
  <tr>
    <td>end;</td>
    <td></td>
  </tr>
  <tr>
    <td>procedure ReadRestExpr;</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;if Next = '+' then begin</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ReadSymbol ('+');</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if b then begin ReadExpr; end;</td>
    <td></td>
  </tr>
  <tr>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end else begin</td>
    <td></td>
  </tr>
</table>
```pascal
  | b := true;
  end;
end;

procedure ReadAdd;
  ReadFact;
  if b then begin ReadRestAdd; end;
end;

procedure ReadRestAdd;
  if Next = '*' then begin
    ReadSymb ('*');
    if b then begin ReadAdd; end;
  end else begin
    b := true;
  end;
end;

procedure ReadFact;
  if Next = 'x' then begin
    ReadSymb ('x');
  end else if Next = '(' then begin
    ReadSymb ('(');
    if b then begin ReadExpr; end;
    if b then begin ReadSymb (')'); end;
  end else begin
    b := false;
  end;
end;
```

Осталось обсудить проблемы, связанные с взаимной рекурсивностью этих процедур (одна использует другую и наоборот). В паскале это допускается, только требуется дать предварительное описание процедур («forward»). Как всегда для рекурсивных процедур, помимо доказательства того, что каждая процедура работает правильно в предположении, что используемые в ней вызовы процедур работают правильно, надо доказать отдельно, что работа завершается. (Это не очевидно: если в грамматике есть правило K → KK, то из K ничего не выводится, Посл(K) и Нач(K) пусты, но написанная по нашим канонам процедура

```pascal
procedure ReadK;
begin
  ReadK;
  if b then begin
```
```
| ReadK;
end;
end;
```

не заканчивает работы.)

В данном случае процедуры `ReadRestExpr`, `ReadRestAdd`, `ReadFact` либо завершаются, либо уменьшают длину непрочитанной части входа. Поскольку любой цикл вызовов включает одну из них, то зацикливание невозможно. ☐

### 15.2.6. Пусть в грамматике имеются два правила с нетерминалом K в левой части, имеющих вид

```
K → L K
K →
```

по которым K-слово представляет собой конечную последовательность L-слов, причём множества `Посл(L)` и `Нач(K)` (в данном случае равное `Нач(L)`) не пересекаются. Используя корректную для L процедуру `ReadL`, напишите корректную для K процедуру `ReadK`, не используя рекурсии.

**Решение.** По нашим правилам следовало бы написать

```
procedure ReadK;
begin
    if (Next принадлежит Нач(L)) then begin
        ReadL;
        if b then begin ReadK; end;
    end else begin
        b := true;
    end;
end;
```

завершение работы гарантируется тем, что перед рекурсивным вызовом длина непрочитанной части уменьшается.

Эта рекурсивная процедура эквивалентна нерекурсивной:

```
procedure ReadK;
begin
    b := true;
    while b and (Next принадлежит Нач(L)) do begin
        ReadL;
    end;
end;
```
Формально можно проверить эту эквивалентность так. Завершаемость в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной процедуры эквивалентно нерекурсивной в предположении, что её рекурсивный вызов эквивалентен вызову нерекурсивной процедуры. Подставим:

```pascal
if (Next принадлежит Нач(L)) then begin
  ReadL;
  if b then begin
    b := true;
    while b and (Next принадлежит Нач(L)) do begin
      ReadL;
    end;
  end;
end else begin
  b := true;
end;
```

Первую команду `b:=true` можно выкинуть (в этом месте и так `b` истинно). Вторую команду можно перенести в начало:

```pascal
b := true;
if (Next принадлежит Нач(L) then begin
  ReadL;
  if b then begin
    while b and (Next принадлежит Нач(L)) do begin
      ReadL;
    end;
  end;
end;
```

Теперь внутренний `if` можно выкинуть (если `b` ложно, цикл `while` всё равно не выполняется) и добавить в условие внешнего `if` условие `b` (которое всё равно истинно).

```pascal
b := true;
if b and (Next принадлежит Нач(L)) then begin
  ReadL;
  while b and (Next принадлежит Нач(L)) do begin
    ReadL;
  end;
end;
```

что эквивалентно приведённой выше нерекурсивной процедуре (из которой вынесена первая итерация цикла). □
**15.2.7.** Докажите корректность приведённой выше нерекурсивной программы непосредственно, без ссылок на рекурсивную.

**Решение.** Рассмотрим наибольшее начало входа, являющееся К-началом. Оно представляется в виде конкатенации (последовательного приписывания) нескольких непустых L-слов и, возможно, одного непустого L-начала, не являющегося L-словом. Инвариант цикла: прочитано несколько из них; $b \Leftrightarrow$ (последнее прочитанное является L-словом).

Сохранение инварианта: если осталось последнее слово, это очевидно; если осталось несколько, то за первым L-словом (из числа оставшихся) идёт символ из Нач(L), и потому это слово — максимальное начало входа, являющееся L-началом. ☐

На практике при записи грамматики используют сокращения. Если правила для какого-то нетерминала К имеют вид

$$ 
\begin{array}{l}
K \to L K \\
K \to
\end{array}
$$

(т. е. К-слова — это последовательности L-слов), то этих правил не пишут, а вместо К пишут L в фигурных скобках. Несколько правил с одной левой частью и разными правыми записывают как одно правило, разделяя альтернативные правые части вертикальной чертой.

Например, рассмотренная выше грамматика для 〈выр〉 может быть записана так:

$$ 
\begin{array}{l}
\langle \text{выр} \rangle \to \langle \text{слаг} \rangle \{ + \langle \text{слаг} \rangle \} \\
\langle \text{слаг} \rangle \to \langle \text{множ} \rangle \{ * \langle \text{множ} \rangle \} \\
\langle \text{множ} \rangle \to x \mid ( \langle \text{выр} \rangle )
\end{array}
$$

**15.2.8.** Напишите процедуру, корректную для 〈выр〉, следуя этой грамматике и используя цикл вместо рекурсии, где можно.

**Решение.**

```pascal
procedure ReadSymb (c: Symbol);
  b := (Next = c);
  if b then begin Move; end;
end;

procedure ReadExpr;
  begin
    ReadAdd;
```
```pascal
while b and (Next = '+') do begin
  Move; ReadAdd;
end;
end;
```

procedure ReadAdd;

begin

ReadFact;
  while b and (Next = '*') do begin

Move; ReadFact;
end;

end;

procedure ReadFact;

begin

if Next = 'x' do begin

Move; b := true;

end else if Next = '(' then begin

Move; ReadExpr;

if b then begin ReadSymb (')'); end;

end else begin

b := false;

end;

end;

<figure><img src="image_135.png" /></figure>

15.2.9. В последней процедуре команду `b:=true` можно опустить. Почему?

**Решение.** Можно предполагать, что все процедуры вызываются при `b=true`. ☐

## 15.3. Алгоритм разбора для LL(1)-грамматик

В этом разделе мы рассмотрим ещё один метод проверки выводимости в КС-грамматике, называемый по традиции LL(1)-разбором. Вот его идея в одной фразе: можно считать, что в процессе вывода мы всегда заменяем самый левый нетерминал и нужно лишь выбрать одно из правил; если нам повезёт с грамматикой, то выбрать правило можно, глядя на первый символ выводимого из этого нетерминала слова. Говоря более формально, дадим такое

**Определение.** Левым выводом (слова в грамматике) называется вывод, в котором на каждом шаге замене подвергается самый левый из нетерминалов.
**15.3.1.** Для каждого выводимого слова (из терминалов) существует его левый вывод.

**Решение.** Различные нетерминалы заменяются независимо; если в процессе вывода появилось слово ...K...L..., где K, L — нетерминалы, то замены K и L можно производить в любом порядке. Поэтому можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся раньше. (Формально говоря, надо доказывать индукцией по длине вывода такой факт: если из некоторого нетерминала K выводится некоторое слово A, то существует левый вывод A из K.) ☐

**15.3.2.** В грамматике с 4 правилами

(1) E →

(2) E → TE

(3) T → (E)

(4) T → [E]

найдите левый вывод слова A = [()([])] и докажите, что он единствен.

**Решение.** На первом шаге можно применить только правило (2):

$$E \rightarrow TE$$

Что будет дальше с T? Так как слово A начинается на [, то может примениться только правило (4):

$$E \rightarrow TE \rightarrow [E]E$$

Первое E должно замениться на TE (иначе вторым символом была бы скобка ]):

$$E \rightarrow TE \rightarrow [E]E \rightarrow [TE]E$$

и T должно заменяться по (3):

$$E \rightarrow TE \rightarrow [E]E \rightarrow [TE]E \rightarrow [(E)E]E$$

Далее первое E должно замениться на пустое слово (иначе третьей буквой слова будет ( или [ — только на эти символы может начинаться слово, выводимое из T):

$$E \rightarrow TE \rightarrow [E]E \rightarrow [TE]E \rightarrow [(E)E]E \rightarrow [()E]E$$

и далее

... → [()TE]E → [() (E)E]E → [() (TE)E]E → [() ([E]E)E]E →
→ [()([]E)E]E → [()([)]E]E → [()([)))E]E → [()([)))] ☐
Что требуется от грамматики, чтобы такой метод поиска левого вывода был применим? Пусть, например, на очередном шаге самым левым нетерминалом оказался нетерминал K, т. е. мы имеем слово вида AKU, где A — слово из терминалов, а U — слово из терминалов и нетерминалов. Пусть в грамматике есть правила

$$ 
\begin{align*}
K &\to LMN \\
K &\to PQ \\
K &\to R
\end{align*}
$$

Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор, глядя на первый символ той части входного слова, которая выводится из KU.

Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются непустые слова, выводимые из LMN. (Это множество равно Нач(L), объединенному с Нач(M), если из L выводится пустое слово, а также с Нач(N), если из L и из M выводится пустое слово.) Чтобы описанный метод был применим, надо, чтобы Нач(LMN), Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть так, например, что из LMN будет выведено пустое слово, а из слова U будет выведено слово, начинающееся на букву из Нач(PQ). Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было да- но только для слова из терминалов. Оно очевидным образом обобщается на случай слов из терминалов и нетерминалов. Можно также говорить о выводимости одного слова (содержащего терминалы и нетерминалы) из другого. (Если говорится о выводимости слова без указания того, откуда оно выводится, то всегда подразумевается выводимость в грам- матике, т. е. выводимость из начального нетерминала.)

Для каждого слова X из терминалов и нетерминалов через Нач(X) обозначаем множество всех терминалов, с которых начинаются непу- стые слова из терминалов, выводимые из X. (В случае, если из любого нетерминала выводится хоть одно слово из терминалов, не играет роли, рассматриваем ли мы при определении Нач(X) слова только из терми- налов или любые слова. Мы будем предполагать далее, что это условие выполнено.)

Для каждого нетерминала K через Посл(K) обозначим множество терминалов, которые встречаются в выводимых (в грамматике) словах сразу же за K. (Не смешивать с Посл(K) предыдущего раздела!) Кроме того, в Посл(K) включается символ EOI, если существует выводимое слово, оканчивающееся на K.
Для каждого правила

$K \to V$

(где K — нетерминал, V — слово, содержащее терминалы и нетерминалы) определим множество направляющих терминалов, обозначаемое $\text{Напр}(K \to V)$. По определению оно равно $\text{Нач}(V)$, к которому добавляемо Послед(K), если из V выводится пустое слово.

**Определение.** Грамматика называется LL(1)-грамматикой, если для любых правил $K \to V$ и $K \to W$ с одинаковыми левыми частями множества $\text{Напр}(K \to V)$ и $\text{Напр}(K \to W)$ не пересекаются.

**15.3.3.** Является ли грамматика

$K \to K \#$

$K \to$

(выводимыми словами являются последовательности диезов) LL(1)-грамматикой?

**Решение.** Нет: символ # принадлежит множествам направляющих символов для обоих правил (для второго — поскольку # принадлежит Послед(K)). ☐

**15.3.4.** Напишите LL(1)-грамматику для того же языка.

**Решение.**

$K \to \# K$

$K \to$

Как говорят, «леворекурсивное» правило заменено на «праворекурсивное».

Следующая задача показывает, что для LL(1)-грамматики существует не более одного возможного продолжения левого вывода.

**15.3.5.** Пусть дано выводимое в LL(1)-грамматике слово X, в котором выделен самый левый нетерминал K: $X = AKS$, где A — слово из терминалов, S — слово из терминалов и нетерминалов. Пусть существуют два различных правила грамматики с нетерминалом K в левой части, и мы применили их к выделенному в X нетерминалу K, затем продолжили вывод и в конце концов получили два слова из терминалов, начинающихся на А. Докажите, что в этих словах за началом А идут разные буквы. (Здесь к числу букв мы относим EOI.)
**Решение.** Эти буквы принадлежат направляющим множествам различных правил. ☐

**15.3.6.** Докажите, что если слово выводимо в LL(1)-грамматике, то его левый вывод единствен.

**Решение.** Предыдущая задача показывает, что на каждом шаге левый вывод продолжается однозначно. ☐

**15.3.7.** Грамматика называется леворекурсивной, если из некоторого нетерминала K выводится слово, начинающееся с K, но не совпадающее с ним. Докажите, что леворекурсивная грамматика, в которой из каждого нетерминала выводится хотя бы одно непустое слово из терминалов и для каждого нетерминала существует вывод (начинающийся с начального нетерминала), в котором он встречается, не является LL(1)-грамматикой.

**Решение.** Пусть из K выводится KU, где K — нетерминал, а U — непустое слово. Можно считать, что это левый вывод (другие нетерминалы можно не заменять). Рассмотрим вывод

K ↦ KU ↦ KUU ↦ ...

(знак ↦ обозначает несколько шагов вывода) и левый вывод K ↦ A, где A — непустое слово из терминалов. На каком-то шаге второй вывод отклоняется от первого, а между тем по обоим путям может быть получено слово, начинающееся на A (в первом случае это возможно, так как сохраняется нетерминал K, который может впоследствии быть заменён на A). Это противоречит возможности однозначного определения правила, применяемого на очередном шаге поиска левого вывода. (Однозначность выполняется для выводов из начального нетерминала, и надо воспользоваться тем, что K по предположению встречается в таком выводе.) ☐

Таким образом, к леворекурсивным грамматикам (кроме тривиальных случаев) LL(1)-метод неприменим. Их приходится преобразовывать в эквивалентные LL(1)-грамматики — или пользоваться другими методами распознавания.

**15.3.8.** Используя сказанное, постройте алгоритм проверки выводимости слова из терминалов в LL(1)-грамматике.

**Решение.** Мы следуем описанному выше методу поиска левого вывода, храня лишь часть слова, находящуюся правее уже прочитанной
части входного слова. Другими словами, мы храним слово S из терминалов и нетерминалов, обладающее такими свойствами (прочитанную часть входа обозначаем через А):

1) слово AS выводимо в грамматике;

2) любой левый вывод входного слова проходит через стадию AS

Эти свойства вместе будем обозначать «(И)».

Вначале А пусто, а S состоит из единственного символа — начального нетерминала.

Если в некоторый момент S начинается на терминал t и t = Next, то можно выполнить команду Move и удалить символ t, являющийся начальным в S, поскольку при этом AS не меняется.

Если S начинается на терминал t и t ≠ Next, то входное слово не выводимо — ибо по условию любой его вывод должен проходить через AS. (Это же справедливо и в случае Next = EOI.)

Если S пусто, то из условия (И) следует, что входное слово выводимо тогда и только тогда, когда Next = EOI.

Остаётся случай, когда S начинается с некоторого нетерминала К. По доказанному выше все левые выводы из 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
                    применить это правило
```
```
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), необходимо вычислить Послед(T) и Нач(T) для всех нетерминалов T. Как это сделать?

**Решение.** Пусть, например, в грамматике есть правило $K \to LMN$. Тогда

Нач($L$) $\subset$ Нач($K$),
Нач($M$) $\subset$ Нач($K$), если из $L$ выводимо пустое слово,
Нач($N$) $\subset$ Нач($K$), если из $L$ и $M$ выводимо пустое слово,
Послед (K) ⊂ Послед (N),

Послед (K) ⊂ Послед (M), если из N выводимо пустое слово,

Послед (K) ⊂ Послед (L), если из M и N выводимо пустое слово,

Нач (N) ⊂ Послед (M),

Нач (M) ⊂ Послед (L),

Нач (N) ⊂ Послед (L), если из M выводимо пустое слово.

Подобные правила позволяют шаг за шагом порождать множества Нач(T), а затем и Послед(T), для всех терминалов и нетерминалов T.
При этом началом служит

$$EOI \in \text{Послед}(K)$$

для начального нетерминала K и

$$z \in \text{Нач}(z)$$

для любого терминала z. Порождение заканчивается, когда применение правил перестаёт давать новые элементы множеств Нач(T) и Послед(T). □
# 16. СИНТАКСИЧЕСКИЙ РАЗБОР СЛЕВА НАПРАВО (LR)

Сейчас мы рассмотрим ещё один метод синтаксического разбора, называемый LR(1)-разбором, а также некоторые упрощённые его варианты.

## 16.1. LR-процессы

Два отличия LR(1)-разбора от LL(1)-разбора: во-первых, строится не левый вывод, а правый, во-вторых, он строится не с начала, а с конца. (Вывод в КС-грамматике называется *правым*, если на каждом шаге замене подвергается самый правый нетерминал.)

**16.1.1.** Докажите, что если слово, состоящее из терминалов, выворачившегося оно на indeed, это оно имеет правый вывод. ☐

Нам будет удобно смотреть на правый вывод «задом наперёд». Определением понятие LR-процесса над словом А. В этом процессе, помимо А, будет участвовать и другое слово S, которое может содержать как терминалы, так и нетерминалы. Вначале слово S пусто. В ходе LR-процесса разрешены два вида действий:

(1) можно перенести первый символ слова А (его называют *очередным символом* и обозначают *Next*) в конец слова S, удалив его из А (это действие называют *сдвигом*);

(2) если правая часть одного из правил грамматики оказалась концом слова S, то разрешается заменить её на нетерминал, стоящий в левой части этого правила; при этом слово А не меняется. (Это действие называют *свёрткой*, или *приведением*.)

Отметим, что LR-процесс не является детерминированным: в одной и той же ситуации могут быть разрешены разные действия.
Говорят, что LR-процесс на слове *А* успешно завершается, если слово *А* становится пустым, а в слове *S* остаётся единственный нетерминал — начальный нетерминал грамматики.

16.1.2. Докажите, что для любого слова *А* (из терминалов) успешно завершающийся LR-процесс существует тогда и только тогда, когда слово *А* выводимо в грамматике. В ходе доказательства установите взаимно однозначное соответствие между правыми выводами и успешно завершающимися LR-процессами.

**Решение.** При сдвиге слово *SA* не меняется, при свёртке слово *SA* подвергается преобразованию, обратному шагу вывода. Этот вывод будет правым, так как сворачивается конец *S*, а в *А* все символы — терминальные. Таким образом, каждому LR-процессу соответствует правый вывод. Обратное соответствие: пусть дан правый вывод. Представим себе, что за последним нетерминалом в слове стоит перегородка. Применив к этому нетерминалу правило грамматики, мы должны сдвинуть перегородку влево (если правая часть правила кончается на терминал). Разбивая этот сдвиг на отдельные шаги, получим процесс, в точности обратный LR-процессу. ☐

Поскольку в ходе LR-процесса все изменения в слове *S* происходят с правого конца, слово *S* называют стеком LR-процесса.

Задача построения правого вывода для данного слова сводится, таким образом, к правильному выбору очередного шага LR-процесса. Нам нужно решить, будем ли мы делать сдвиг или свёртку, и если свёртку, то по какому правилу — ведь подходящих правил может быть несколько. В LR(1)-алгоритме это решение принимается на основе *S* и первого символа слова *А*; если используется только *S*, то говорят о LR(0)-алгоритме. (Точные определения см. ниже.)

Пусть фиксирована грамматика, в которой из любого нетерминала можно вывести какое-либо слово из терминалов. (Это ограничение мы будет всегда предполагать выполненным.)

Пусть $K \to U$ — одно из правил грамматики ($K$ — нетерминал, $U$ — слово из терминалов и нетерминалов). Определим множество слов (из терминалов и нетерминалов), называемое левым контекстом правила $K \to U$. (Обозначение: ЛевКонт($K \to U$).) По определению в него входят все слова, которые являются содержимым стека непосредственно перед свёрткой $U$ в $K$ в ходе некоторого успешно завершающегося LR-процесса.

16.1.3. Переформулируйте это определение на языке правых выводов.
**Решение.** Рассмотрим все правые выводы вида

⟨начальный нетерминал⟩ ↦ XKA → XUA,

где А — слово из терминалов, Х — слово из терминалов и нетерминалов. Все возникающие при этом слова ХU и образуют левый контекст правила K → U. Чтобы убедиться в этом, следует вспомнить, что мы предполагаем, что из любого нетерминала можно вывести какое-то слово из терминалов, так что правый вывод слова XUA может быть продолжен до правого вывода какого-то слова из терминалов. ☐

**16.1.4.** Все слова из ЛевКонт(K → U) кончаются, очевидно, на U. Докажите, что если у всех них этот конец U отбросить, то полученное множество слов не зависит от того, какое из правил для нетерминала К выбрано. (Это множество обозначается Лев(K).)

**Решение.** Из предыдущей задачи ясно, что Лев(K) — это всё, что может появиться в правых выводах левее самого правого нетерминала K. ☐

**16.1.5.** Докажите, что в предыдущей фразе можно отбросить слова «самого правого»: Лев(K) — это всё то, что может появляться в правых выводах левее любого вхождения нетерминала K.

**Решение.** Продолжив построение правого вывода, все нетерминалы справа от K можно заменить на терминалы (а слева от K при этом ничего не изменится). ☐

**16.1.6.** Постройте грамматику, содержащую для каждого нетерминала K исходной грамматики нетерминал ⟨ЛевK⟩, причём следующее свойство должно выполняться для любого нетерминала К исходной грамматики: в новой грамматике из ⟨ЛевK⟩ выводимы все элементы Лев(K) и только они. (При этом терминалы и нетерминалы исходной грамматики являются терминалами новой.)

**Решение.** Пусть P — начальный нетерминал грамматики. Тогда в новой грамматике будет правило

⟨ЛевP⟩ → (пустое слово)

Для каждого правила исходной грамматики, например, правила

K → LtMN (L, M, N — нетерминалы, t — терминал),
в новую грамматику мы добавим правила

⟨Лев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.** Для данной грамматики постройте алгоритм, который по любому слову выясняет, каким из множеств Лев(К) оно принадлежит.

(Замечание для знатоков. Существование такого алгоритма — и же конечного автомата, то есть индуктивного расширения с конечным числом значений, см. раздел 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 принадлежит Лев(К). (Смысл этого определения примерно таков: в стеке S
подготовлена часть U для будущей свёртки UV в К.) В этих терминах ЛевКонт(K → X) — это множество всех слов, согласованных с ситуацией K → X_, а Лев(K) — это множество всех слов, согласованных с ситуацией K → _X (где K → X — любое правило для нетерминала К).

Эквивалентное определение в терминах LR-процесса: S согласовано с ситуацией K → U_V, если существует успешный LR-процесс, в котором события развиваются так:

* в ходе процесса в стеке появляется слово S, и оно оканчивается на U;

* некоторое время S не затрагивается, а справа от него появляется V;

* UV сворачивается в K;

* процесс продолжается и успешно завершается.

### 16.1.9. Докажите эквивалентность этих определений.

[Указание. Если S = TU и T принадлежит Лев(K), то можно получить в стеке сначала T, потом U, потом V, потом свернуть UV в К и затем успешно завершить процесс. (Мы используем несколько раз тот факт, что из любого нетерминала что-то да выводится: благодаря этому мы можем добавить в стек любое слово.)] □

Наша цель — построение алгоритма, распознающего принадлежность произвольного слова к Лев(K). Рассмотрим функцию, сопоставляющую с каждым словом S (из терминалов и нетерминалов) множество всех согласованных с ним ситуаций. Это множество назовём составием, соответствующим слову S. Будем обозначать его Сост(S). Достаточно показать, что функция Сост(S) индуктивна, то есть что значение Сост(SJ), где J — терминал или нетерминал, может быть вычислено, если известно Сост(S) и символ J. (Мы видели ранее, как принадлежность к Лев(K) выражается в терминах этой функции.) Значение Сост(SJ) вычисляется по таким правилам:

(1) Если слово S согласовано с ситуацией K → U_V, причём слово V начинается на букву J, то есть V = JW, то SJ согласовано с ситуацией K → UJ_W.
Это правило полностью определяет все ситуации с непустой левой половиной (то есть не начинающиеся с подчёркивания), согласованные с SJ. Осталось определить, для каких нетерминалов K слово SJ принадлежит Лев(К). Это делается по двум правилам:

(2) Если ситуация L → U_V согласована с SJ (согласно правилу (1)), а V начинается на нетерминал К, то SJ принадлежит Лев(К).

(3) Если SJ входит в Лев(L) для некоторого L, причём L → V — правило грамматики и V начинается на нетерминал К, то SJ принадлежит Лев(К).

Заметим, что правило (3) можно рассматривать как аналог правила (2): в указанных в (3) предположениях ситуация L → _V согласована с SJ, а V начинается на нетерминал К.

Корректность этих правил в общем-то очевидна, если хорошенько подумать. Единственное, что требует некоторых пояснений — это то, почему с помощью правил (2) и (3) обнаружатся все терминалы К, для которых SJ принадлежит Лев(К). Попытаемся это объяснить. Рассмотрим правый вывод, в котором SJ стоит слева от К. Откуда мог взиться в нём нетерминал К? Если правило, которое его породило, породило также и конец слова SJ, то принадлежность SJ к Лев(К) будет обнаружена по правилу (2). Если же К было первой буквой слова, порождённого каким-то другим нетерминалом L, то — благодаря правилу (3) — достаточно установить принадлежность SJ к Лев(L). Осталось применить те же рассуждения к L и так далее.

В терминах LR-процесса то же самое можно сказать так. Сначала нетерминал К может участвовать в нескольких свёртках, не затрагивающих SJ (они соответствуют применению правила (3)), но затем он обязан подвергнуться свёртке, затрагивающей SJ (что соответствует применению правила (2)).

Осталось выяснить, какие ситуации согласованы с пустым словом, то есть для каких нетерминалов K пустое слово принадлежит Лев(К). Это определяется по следующим правилам:

(1) начальный нетерминал таков;

(2) если K таков и K → V — правило грамматики, причём слово V начинается с нетерминала L, то и L таков. ☐
16.1.10. Проделайте описанный анализ для грамматики

<figure><img src="image_136.png" /></figure>

(задающей тот же язык, что и грамматика примера 3, с. 271).

**Решение.** Множества Cост(S) для различных S приведены в таблице на с. 300. Знак равенства означает, что множества ситуаций, являющихся значениями функции Cост(S) на словах, стоящих слева и справа от знака равенства, одинаковы.

Правило определения Cост(SJ), если известны Cост(S) и J (здесь S — слово из терминалов и нетерминалов, J — терминал или нетерминал), таково:

надо найти Cост(S) в правой колонке, взять соответствующее ему слово T в левой колонке, приписать к нему J и взять множество, стоящее напротив слова TJ (если слово TJ в таблице отсутствует, то Cост(SJ) пусто).

<figure><img src="image_137.png" /></figure>

16.2. LR(0)-грамматики

Напомним, что наша основная цель — это поиск вывода заданного слова, или, другими словами, поиск успешного LR-процесса над ним. Во всех рассматриваемых нами грамматиках успешный LR-процесс (над данным словом) единствен. Искать этот единственный успешный процесс мы будем постепенно: в каждый момент мы смотрим, какой шаг возможен следующим. Для этого на грамматику надо наложить дополнительные требования, и сейчас мы рассмотрим простейший случай так называемых LR(0)-грамматик. Мы уже знаем:

(1) В успешном LR-процессе возможна свёртка по правилу K → U при содержимом стека S тогда и только тогда, когда S принадлежит ЛевКонт(K → U) или, другими словами, когда слово S согласовано с ситуацией K → U.
<table><thead><tr><th>Слово S</th><th>Сост(S)</th></tr></thead><tbody><tr><td>пустое</td><td>E → _E+T E → _T T → _T*F<br>T → _F F → _x F → _E</td></tr><tr><td>E</td><td>E → E_+T</td></tr><tr><td>T</td><td>E → T_ T → T_*F</td></tr><tr><td>F</td><td>T → F_</td></tr><tr><td>x</td><td>F → x_</td></tr><tr><td>(</td><td>F → _E) E → _E+T E → _T<br>T → _T*F T → _F F → _x F → _E</td></tr><tr><td>E+</td><td>E → E_+T T → _T*F T → _F<br>F → _x F → _E</td></tr><tr><td>T*</td><td>T → T*_F F → _x F → _E</td></tr><tr><td>(E</td><td>F → (E_) E → E_+T</td></tr><tr><td>(T</td><td>= T</td></tr><tr><td>(F</td><td>= F</td></tr><tr><td>(x</td><td>= x</td></tr><tr><td>((</td><td>= (</td></tr><tr><td>E+T</td><td>E → E+T_ T → T_*F</td></tr><tr><td>E+F</td><td>= F</td></tr><tr><td>E+x</td><td>= x</td></tr><tr><td>E+(</td><td>= (</td></tr><tr><td>T*F</td><td>T → T*F_</td></tr><tr><td>T*x</td><td>= x</td></tr><tr><td>T*(</td><td>= (</td></tr><tr><td>(E)</td><td>F → (E)_</td></tr><tr><td>(E+</td><td>= E+</td></tr><tr><td>E+T*</td><td>= T*</td></tr></tbody></table>

К задаче 16.1.10
Аналогичное утверждение про сдвиг гласит:

(2) В успешном LR-процессе при содержимом стека S воз-
можен сдвиг с очередным символом a тогда и только тогда,
когда S согласовано с некоторой ситуацией K → U_aV.

16.2.1. Докажите это.

[Указание. Пусть произошёл сдвиг и к стеку S добавилась буква a.
Рассмотрите первую свёртку, затрагивающую эту букву.]

Рассмотрим некоторую грамматику и произвольное слово S из тер-
миналов и нетерминалов. Если множество Cост(S) содержит ситуацию,
в которой справа от подчёркивания стоит терминал, то говорят, что
для слова S возможен сдвиг. Если в Cост(S) есть ситуация, в которой
справа от подчёркивания ничего нет, то говорят, что для слова S воз-
можна свёртка (по соответствующему правилу). Говорят, что для сло-
ва S возникает конфликт типа сдвиг/свёртка, если возможны и сдвиг,
и свёртка. Говорят, что для слова S возникает конфликт типа свёрт-
ка/свёртка, если есть несколько правил, по которым возможна свёртка.

Грамматика называется LR(0)-грамматикой, если в ней нет кон-
фликтов типа сдвиг/свёртка и свёртка/свёртка ни для одного слова S.

16.2.2. Является ли приведённая выше грамматика LR(0)-грамматикой?

Решение. Нет, не является. Для слов T и E+T имеются конфликты
типа сдвиг/свёртка. ☐

16.2.3. Являются ли LR(0)-грамматиками такие:

(a)
Т → 0
Т → T1
Т → TT2
Т → TTT3

(б)
Т → 0
Т → 1T
Т → 2TT
Т → 3TTT

Решение. Являются, см. таблицы на с. 302–303 (конфликтов нет). ☐

Эта задача показывает, что LR(0)-грамматики могут быть как ле-
ворекурсивными, так и праворекурсивными.

16.2.4. Пусть дана LR(0)-грамматика. Докажите, что у любого сло-
ва существует не более одного правого вывода. Постройте алгоритм
проверки выводимости в LR(0)-грамматике.
<table><thead><tr><th>Слово S</th><th>Сост(S)</th></tr></thead><tbody><tr><td>пустое</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>0</td><td>T → _0</td></tr><tr><td>T</td><td>T → T_1 T → T_T2 T → T_TT3</td></tr><tr><td>T1</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>TT</td><td>T → TT_2 T → TT_T3</td></tr><tr><td>T → T_1</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>TT2</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>TTT</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>TTO</td><td>= 0</td></tr><tr><td>TTT3</td><td>T → _0 T → _T1 T → _TT2 T → _TTT3</td></tr><tr><td>TTT2</td><td>= TT2</td></tr><tr><td>TTTT</td><td>= TTT</td></tr><tr><td>TTT0</td><td>= 0</td></tr></tbody></table>

(a)

<table><thead><tr><th>Слово S</th><th>Сост(S)</th></tr></thead><tbody><tr><td>пустое</td><td>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>0</td><td>T → _0</td></tr><tr><td>1</td><td>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>2</td><td>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>3</td><td>T → _0 T → _1T T → _2TT T → _3TTT</td></tr></tbody></table>

(б), начало

К задаче 16.2.3.
<table><thead><tr><th>СЛОВО S</th><th>СОСТ(S)</th></tr></thead><tbody><tr><td>1T</td><td>T → 1T_</td></tr><tr><td>10</td><td>= 0</td></tr><tr><td>11</td><td>= 1</td></tr><tr><td>12</td><td>= 2</td></tr><tr><td>13</td><td>= 3</td></tr><tr><td>2T</td><td>T → 2T_T<br>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>20</td><td>= 0</td></tr><tr><td>21</td><td>= 1</td></tr><tr><td>22</td><td>= 2</td></tr><tr><td>23</td><td>= 3</td></tr><tr><td>3T</td><td>T → 3T_TT<br>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>30</td><td>= 0</td></tr><tr><td>31</td><td>= 1</td></tr><tr><td>32</td><td>= 2</td></tr><tr><td>33</td><td>= 3</td></tr><tr><td>2TT</td><td>T → 2TT_</td></tr><tr><td>2T0</td><td>= 0</td></tr><tr><td>2T1</td><td>= 1</td></tr><tr><td>2T2</td><td>= 2</td></tr><tr><td>2T3</td><td>= 3</td></tr><tr><td>3TT</td><td>T → 3TT_T<br>T → _0 T → _1T T → _2TT T → _3TTT</td></tr><tr><td>3T0</td><td>= 0</td></tr><tr><td>3T1</td><td>= 1</td></tr><tr><td>3T2</td><td>= 2</td></tr><tr><td>3T3</td><td>= 3</td></tr><tr><td>3TTT</td><td>T → 3TTT_</td></tr><tr><td>3TT0</td><td>= 0</td></tr><tr><td>3TT1</td><td>= 1</td></tr><tr><td>3TT2</td><td>= 2</td></tr><tr><td>3TT3</td><td>= 3</td></tr></tbody></table>

(б), окончание
**Решение.** Пусть дано произвольное слово. Будем строить 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)-грамматики

Напомним, что для любого нетерминала K мы определяли (с. 287) множество Послед(К) тех терминалов, которые могут стоять непосредственно за K в выводимом (из начального нетерминала) слове; в это множество добавляют также символ EOI, если нетерминал K может стоять в конце выводимого слова.

**16.3.1. Докажите, что если в данный момент LR-процесса последний символ стека S равен K, причём процесс этот может в дальнейшем успешно завершиться, то Next принадлежит Послед(К).**

**Решение.** Этот факт является непосредственным следствием определения (вспомним соответствие между правыми выводами и LR-процессами). □**

Рассмотрим некоторую грамматику, произвольное слово S из терминалов и нетерминалов и терминал х. Если множество Сост(S) содержит ситуацию, в которой справа от подчёркивания стоит терминал х, то говорят, что *для пары (S, x)* возможен сдвиг. Если в Сост(S) есть ситуация K → U, причём х принадлежит Послед(К), то говорят, что *для пары (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.** Проверьте, является ли приведённая выше на с. 299 грамматика (с нетерминалами E, T и F) SLR(1)-грамматикой.

**Решение.** Да, является, так как оба конфликта, мешающие ей быть LR(0)-грамматикой, разрешаются с учётом очередного символа: и для слова T, и для слова E+T сдвиг возможен только при $Next = *,$ а символ * не принадлежит ни Послед(E) = {$EOI, +,}$), ни Послед(T) = {$EOI, +, *,}$), и поэтому при $Next = *$ свёртка невозможна. □**
### 16.4. LR(1)-грамматики, LALR(1)-грамматики

Описанный выше SLR(1)-подход используют не всю возможную информацию при выяснении того, возможна ли свёртка. Именно, он отдельно проверяет, возможна ли свёртка при данном состоянии стека S и отдельно — возможна ли свёртка по данному правилу при данном символе Next. Между тем эти проверки не являются независимыми: обе могут дать положительный ответ, но тем не менее свёртка при стеке S и очередном символе Next невозможна. В LR(1)-подходе этот недостаток устраняется.

LR(1)-подход состоит вот в чём: все наши определения и утверждения модифицируются так, чтобы учесть, какой символ стоит справа от разворачиваемого нетерминала (другими словами, чему равен Next при свёртке).

Пусть $K \to U$ — одно из правил грамматики, а $t$ — некоторый терминал или спецсимвол EOI (который мы домысливаем в конце входного слова). Определим множество ЛевКонт($K \to U, t$) как множество всех слов, которые являются содержимым стека непосредственно перед свёрткой $U$ в $K$ в ходе успешного LR-процесса, при условии $Next = t$ (в момент свёртки).

Если отбросить у всех слов из ЛевКонт($K \to U$) их конец $U$, то получится множество всех слов, которые могут появиться в правых выводах перед нетерминалом $K$, за которым стоит символ $t$. Это множество (не зависящее от того, какое из правил $K \to U$ для нетерминала $K$ выбрано) мы будем обозначать Лев($K, t$).

#### 16.4.1. Напишите грамматику для порождения множеств Лев($K, t$).

**Решение.** Её нетерминалами будут символы $\langle$ЛевК$t\rangle$ для каждого нетерминала $K$ и для каждого терминала $t$ (а также для $t = EOI$). Её правила таковы. Пусть $P$ — начальный нетерминал исходной грамматики. Тогда в новой грамматике будет правило

$$ \langle \text{ЛевРEOI} \rangle \to \text{(пустое слово).} $$

Каждое правило исходной грамматики порождает несколько правил новой. Например, для правила

$$ K \to LuMN $$

($L, M, N$ — нетерминалы, $u$ — терминал) в новую грамматику мы добавим правила

$$ \langle \text{ЛевL}u \rangle \to \langle \text{ЛевК}x \rangle $$
(для всех терминалов x);

⟨ЛевМs⟩ → ⟨ЛевКу⟩ Lu

(для всех s, которые могут начинать слова, выводимые из N, и для всех y, а также для всех пар s = y, если из N выводимо пустое слово);

⟨ЛевN s⟩ → ⟨ЛевК s⟩ LuM

(для всех терминалов s).

<figure><img src="image_138.png" /></figure>

16.4.2. Как меняется определение ситуации?

**Решение.** Ситуацией называется пара

[ситуация в старом смысле, терминал или EOI]

<figure><img src="image_139.png" /></figure>

16.4.3. Как изменится определение согласованности?

**Решение.** Слово S из терминалов и нетерминалов согласовано с ситуацией [K → U_V, t] (здесь t — терминал или EOI), если S кончается на U, то есть S = TU, и, кроме того, T принадлежит Лев(K, t). ☐

<figure><img src="image_140.png" /></figure>

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 выводится пустое слово. ☐

<figure><img src="image_141.png" /></figure>
16.4.5. Дайте определение LR(1)-конфликтов типа сдвиг/свёртка и свёртка/свёртка.

Решение. Пусть дана некоторая грамматика. Пусть S — произвольное слово из терминалов и нетерминалов. Если множество Cост(S) содержит ситуацию, в которой справа от подчёркивания стоит терминал t, то говорят, что для пары (S, t) возможен сдвиг. (Это определение не изменилось по сравнению с SLR(1)-случаем — вторые компоненты пар из Cост(S) не учитываются.)

Если в Cост(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). То же самое другими словами: Лев(К) есть объединение Лев(К, t) по всем t. В последней форме это совсем ясно. ☐

Замечание. Таким образом, функция Cост(S) в LR(1)-смысле является расширением функции Cост(S) в LR(0)-смысле: Cост_{LR(0)}(S) получается из Cост_{LR(1)}(S), если во всех парах выбросить вторые члены.

Теперь мы можем дать определение LALR(1)-грамматики. Пусть фиксирована некоторая грамматика, S — слово из нетерминалов и терминалов, t — некоторый терминал (или EOI). Будем говорить, что для
пары ⟨S, t⟩ LALR(1)-возможна свёртка по некоторому правилу, если существует другое слово S₁ с Сост<sub>LR(0)</sub>(S₀) = Сост<sub>LR(0)</sub>(S₁), причём для пары ⟨S₁, t⟩ LR(1)-возможна свёртка по рассматриваемому правилу. Далее определяются конфликты (естественным образом), и грамматика называется LALR(1)-грамматикой, если конфликтов нет.

16.4.8. Докажите, что любая SLR(1)-грамматика является также и LALR(1)-грамматикой, а любая LALR(1)-грамматика является также и LR(1)-грамматикой.

[Указание. Это — простое следствие определений.]

<figure><img src="image_142.png" /></figure>

16.4.9. Постройте алгоритм проверки выводимости в LALR(1)-грамматике, который хранит в стеке меньше информации, чем соответствующий LR(1)-алгоритм.

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

<figure><img src="image_143.png" /></figure>

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

<figure><img src="image_144.png" /></figure>

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

<figure><img src="image_145.png" /></figure>

16.5. Общие замечания о разных методах разбора

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

— SLR(1) 305

— выражений 271

— контекстно-свободная 268

— леворекурсивная 289

граф, вершина 106, 130

— двудольный 155, 173

—, кратчайшие пути 146

— неориентированный 130

— ориентированный 106

—, ребро 130

—, связная компонента 113, 130, 152

— связный 106

Грея коды 49

датчик поворота 51

двоичный поиск 33

двудольный граф 155, 173

Дейкстры алгоритм (кратчайшие пути) 148, 150

дек, реализация в массиве 105

—, ссылочная реализация 110

деление с остатком 10

— — быстрое 22

дерево 60

—, AND-OR- 224

—, Б-дерево 266

—, вершина 121

—, высота 122

—, двоичное 75

—, корень 121

—, обход 62, 123, 127, 142

— — нерекурсивный 141

— подслов 196

— позиций 60

— —, реализация 67

— полное двоичное 249

—, рекурсивная обработка 122

— сбалансированное 257

— сжатое суффиксное 198

—, ссылочная реализация 121, 251

— суффиксное 196

— упорядоченное 250

—, число вершин 122, 142

— — листьев 122

десятичная дробь, период 20

— запись, печать 17, 20, 141

— — рекурсивная 119

— —, чтение 92

детерминизация конечного
автомата 195

динамическое программирование
135, 137

— —, кратчайшие пути 146

диофантово уравнение 12, 14

дополнение регулярного
множества 196

дополняющий путь 164, 166, 168,
169

Евклида алгоритм 12, 13

— — двоичный 13

жулик на пособии 31

задача NP-полная 70

— о рюкзаке 70, 140

игра Гейла 216

— крестики-нолики 215

— мат с неподвижным королём
228

— ним 210

—, ретроспективный анализ 226

— с нулевой суммой 212

— с полной информацией 209

—, цена 211

индуктивная функция 38

индуктивное расширение 39

исток 159

источник 194
калькулятор стековый 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

Лев(К, t) 306

ЛевКонт(К → U) 294

ЛевКонт(К → U, t) 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

Напр(К → V) 288

Нач(Х) 276, 287

начало слова 179

неассоциативное произведение
139

недетерминированный конечный
автомат 194

неориентированный граф 130

неравенство Крафта-

Макмиллана 230–233
нетерминал 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

— k-го по порядку 88, 133, 256

— в глубину 153

— в ширину 114, 152

— двоичный 33

— кратчайшего пути 146

— минимума 84

— образца 185, 187, 189

— одного из слов 190

— подслова 177, 181, 184, 185, 187

— представителя большинства 88

Посл(Х) 276

Послед(Х) 287

последовательности монотонные,
перечисление 125

последовательность, содержащая
все слова длины n 108

постфиксная запись 144

потенциал 151

поток 157–159

— через разрез 161

потомок вершины 121

права авторские 4

предпоток 163

приведение 293

приоритетная очередь 115
программа сжатия информации
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

сортировка $n \log n$ 73

— деревом 75, 115

— квадратичная 72

—, нижняя оценка сложности 82

— слиянием 73, 80

— топологическая 128, 155

— Хоара (быстрая) 80, 132

— — нерекурсивная 143

— цифровая 83

—, число сравнений 82

Сост($S$) 297

составные символы, замена 90

сочетаний число 57, 136

сылки суффиксные 200

стек 96

—, два в массиве 100

— отложенных заданий 141

—, реализация в массиве 97

—, ссылочная реализация 100
стековый калькулятор 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

Гасфилд (Gusfield, 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önig, 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, С.) 311

Липский (Lipski, W.) 311

Лисовский, Анджей 141

Макмиллан (McMillan, В.) 230, 232

Матиясевич, Ю. В. 4, 21, 181

Мотвани (Motvani, R.) 311

Мур (Moore, Ronald W.) 224

Нивергельт (Nievergelt, J.) 267, 311

Пападимитриу (Papadimitriou, С.) 311

Паскаль (Pascal, В.) 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
Хопкрофт (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