Жанр: Учеба
Программирование в теоремах и задачах
...; массив diff содержит правиль-
| | | ные значения для этого поддерева; возможно нарушение
| | | сбалансированности в v}
| | | balance (v, d1); d := c + d1;
| | end;
| end;
end;
Легко проверить, что значение d может быть равно только 0 или 1
(но не -1): если c = 0, то diff [v] = 0 и балансировка не производится.
Программа удаления строится аналогично. Ее основной фрагмент
таков:
{инвариант: стек содержит путь к изменившемуся поддереву,
высота которого изменилась по сравнению с высотой в
исходном дереве на d (=0 или -1); это поддерево
сбалансировано; значения diff для его вершин правильны;
в остальном дереве все осталось как было -
в частности, значения diff}
while (d "" 0) and ..стек непуст do begin
| {d = -1}
| ..взять из стека пару в "v, direct"
| if direct = l 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;
| {c = изменение высоты поддерева с корнем в v по срав-
| нению с исходным деревом; массив diff содержит
| правильные значения для этого поддерева;
| возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1
(но не -2): если c = -1, то diff [v] = 0 и балансировка не производится.
Отметим также, что наличие стека делает излишними переменные
father и direction (их роль теперь играет вершина стека).
12.2.6. Доказать, что при добавлении элемента
(а) второй из трех случаев балансировки (см. рисунок выше)
невозможен;
(б) полная балансировка требует не более одного вращения
(после чего все дерево становится сбалансированным),
в то время как при удалении элемента может понадобиться
много вращений.
Замечание. Мы старались записать программы добавления и
удаления так, чтобы они были как можно более похожими друг на
друга. Используя специфику каждой из них, можно многое упростить.
Существуют и другие способы представления множеств, гарантирующие
число действий порядка log n на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого
множества. Этот элемент служил границей между левым и правым
поддеревом. Будем теперь хранить в вершине k "= 1 элементов множества
(число k может меняться от вершины к вершине, а также при
добавлении и удалении новых элементов, см. далее). Эти k элементов
служат разделителями для k+1 поддерева. Пусть фиксировано
некоторое число n "= 1. Будем рассматривать деревья, обладающие
такими свойствами:
(1) Каждая вершина содержит от n до 2n элементов (за исключением
корня, который может содержать любое число элементов от 0
до 2n).
(2) Вершина с k элементами либо имеет k+1 сына, либо не
имеет сыновей вообще (такие вершины называются листьями).
(3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он
попадает, неполон (т.е. содержит менее 2n элементов), то нет
проблем. Если он полон, то 2n+1 элемент (все элементы листа и
новый элемент) разбиваем на два листа по n элементов и разделяющий
их серединный элемент. Этот серединный элемент надо добавить
в вершину предыдущего уровня. Это возможно, если в ней менее
2n элементов. Если и она полна, то ее разбивают на две, выделяют
серединный элемент и т.д. Если в конце концов мы захотим
добавить элемент в корень, а он окажется полным, то корень расщепляется
на две вершины, а высота дерева увеличивается на 1.
Удаление элемента. Удаление элемента, находящемся не в листе,
сводится к удалению непосредственно следующего за ним, который
находится в листе. Поэтому достаточно научиться удалять элемент
из листа. Если лист при этом становится неполным, то его
можно пополнить за счет соседнего листа - если только и он не
имеет минимально возможный размер n. Если же оба листа имеют
размер n, то на них вместе 2n элементов, вместе с разделителем -
2n+1. После удаления одного элемента остается 2n элементов - как
раз на один лист. Если при этом вершина предыдущего уровня становится
меньше нормы, процесс повторяется и т.д.
12.2.7. Реализовать описанную схему хранения множеств, убедившись,
что она также позволяет обойтись C*log(n) действий для
операций включения, исключения и проверки принадлежности.
12.2.8. Можно определять сбалансированность дерева иначе:
требовать, чтобы для каждой вершины ее левое и правое поддеревья
имели не слишком сильно отличающиеся количества вершин. (Преимущество
такого определения состоит в том, что при вращениях изменяется
сбалансированность только в одной вершине.) Реализовать
на основе этой идеи способ хранения множеств, гарантирующий
оценку в C*log(n) действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие и малые
вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)
Глава 13. Контекстно-свободные грамматики.
13.1. Контекстно-свободные грамматики. Общий алгоритм раз-
бора.
Чтобы определить то, что называют контекстно-свободной
грамматикой (КС-грамматикой), надо:
(а) указать конечное множество A, называемое алфавитом; его
элементы называют символами; конечные последовательности символов
называют словами (в данном алфавите);
(б) разделить все символы алфавита A на две группы: терминальные
("окончательные") и нетерминальные ("промежуточные");
(в) выбрать среди нетерминальных символов один, называемый
начальным;
(г) указать конечное число правил грамматики, каждое из которых
должно иметь вид
K -" 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 -"
(в последнем правиле справа стоит пустое слово).
Примеры выводимых слов:
(пустое слово)
()
([])
()[([])]
[()[]()[]]
Примеры невыводимых слов:
(
)(
(]
([)]
Эта грамматика встречалась в разделе 00 (где выводимость в ней
проверялась с помощью стека).
Пример 2. Другая грамматика, порождающая тот же язык:
Алфавит: ( ) [ ] T E
Правила:
E -"
E -" TE
T -" (E)
T -" [E]
Начальным символом во всех приводимых далее примерах будем считать
символ, стоящий в левой части первого правила (в данном
случае это символ T), не оговаривая этого особо.
Для каждого нетерминального символа можно рассмотреть множество
всех слов из терминальных символов, которые из него выводятся
(аналогично тому, как это сделано для начального символа в
определении выводимости в грамматике). Каждое правило грамматики
можно рассматривать как свойство этих множеств. Покажем это на
примере только что приведенной грамматики. Пусть SetT и SetE -
множества слов (из скобок), выводимых из нетерминалов T и E соответственно.
Тогда правилам грамматики соответствуют такие
свойства:
E -" SetE содержит пустое слово
E -" TE если слово A принадлежит SetT,
слово B принадлежит
SetE, то слово AB принадлежит SetE
T -" [E] если A принадлежит
SetE, то слово [A] принадлежит SetT
T -" (E) если A принадлежит
SetE, то слово (A) принадлежит SetT
Сформулированные свойства множеств SetE, SetT не определяют эти
множества однозначно (например, они остаются верными, если в качестве
SetE и SetT взять множество всех слов). Однако можно доказать,
что множества, задаваемые грамматикой, являются минимальными
среди удовлетворяющих этим условиям.
13.1.1. Сформулируйте точно и докажите это утверждение для
произвольной контекстно-свободной грамматики.
13.1.2. Постройте грамматику, в которой выводимы слова
(а) 00..0011..11 (число нулей равно числу единиц);
(б) 00..0011..11 (число нулей вдвое больше числа единиц);
(в) 00..0011..11 (число нулей больше числа единиц);
(и только они).
13.1.3. Доказать, что не существует КС-грамматики, в которой
были бы выводимы слова вида 00..0011..1122..22, в которых
числа нулей, единиц и двоек равны, и только они.
Указание. Докажите следующую лемму о произвольной КС-грамматике:
для любого достаточно длинного слова F, выводимого в
этой грамматике, существует такое его представление в виде
ABCDE, что любое слово вида AB..BCD..DE, где B и D повторены
одинаковое число раз, также выводимо в этой грамматике. (Это
можно установить, найдя нетерминальный символ, оказывающийся
своим собственным "наследником" в процессе вывода.)
Нетерминальный символ можно рассматривать как "родовое имя"
для выводимых из него слов. В следующем примере для наглядности
в качестве нетерминальных символов использованы фрагменты
русских слов, заключенные в угловые скобки. (С точки зрения
грамматики каждое такое слово - один символ!)
Пример 3. Алфавит:
терминалы: + * ( ) x
нетерминалы: "выр", "оствыр", "слаг", "остслаг", "множ"
правила:
"выр" -" "слаг" "оствыр"
"оствыр" -" + "выр"
"оствыр" -"
"слаг" -" "множ" "остслаг"
"остслаг" -" * "слаг"
"остслаг" -"
"множ" -" x
"множ" -" ( "выр" )
Согласно этой грамматике, выражение ("выр") - это последовательность
слагаемых ("слаг"), разделенных плюсами, слагаемое -
это последовательность множителей ("множ"), разделенных звездочками
(знаками умножения), а множитель - это либо буква x, либо
выражение в скобках.
13.1.4. Приведите пример другой грамматики, задающей тот же
язык.
Ответ. Вот один из вариантов:
"выр" -" "выр" + "выр"
"выр" -" "выр" * "выр"
"выр" -" x
"выр" -" ( "выр" )
Эта грамматика хоть и проще, но в некоторых отношениях хуже, о
чем мы еще будем говорить.
13.1.5. Дана произвольная КС-грамматика. Построить алгоритм
проверки принадлежности задаваемому ей языку, работающий полиномиальное
время (т.е. число действий не превосходит полинома от
длины проверяемого слова; полином может зависеть от грамматики).
Решение. Заметим, что требование полиномиальности исключает
возможность решения, основанном на переборе всех возможных выводов.
Тем не менее полиномиальный алгоритм существует. Поскольку
практического значения он не имеет (используемые на практике
КС-грамматики обладают дополнительными свойствами, позволяющими
строить более эффективные алгоритмы), мы изложим лишь общую схему
решения.
(1) Пусть в грамматике есть нетерминалы K1,...,Kn. Построим
новую грамматику с нетерминалами K1',...,Kn' так, чтобы выполнялось
такое свойство: из Ki' выводятся (в новой грамматике) те же
слова, что из Ki в старой, за исключением пустого слова, которое
не выводится.
Чтобы выполнить такое преобразование грамматики, надо выяснить,
из каких нетерминалов исходной грамматики выводится пустое
слово, а затем каждое правило заменить на совокупность правил,
получающихся, если в правой части опустить какие-либо из нетерминалов,
из которых выводится пустое слово, а у остальных поставить
штрихи. Например, если в исходной грамматике было правило
K -" L M N,
причем из L и N выводится пустое слово, а из M нет, то это правило
надо заменить на правила
K'-" L'M'N'
K'-" M'N'
K'-" L'M'
K'-" M'
(2) Итак, мы свели дело к грамматике, где ни из одного нетерминала
не выводится пустое слово. Теперь устраним "циклы" вида
K -" L
L -" M
M -" N
N -" K
(в правой части каждого правила один символ, и эти символы образуют
цикл произвольной длины): это легко сделать, отождествив
все входящие в цикл нетерминалы.
(3) Теперь проверка принадлежности какого-либо слова языку,
порожденному грамматикой, может выполняться так: для каждого
подслова проверяемого слова и для каждого нетерминала выясняем,
порождается ли это подслово этим нетерминалом. При этом подслова
проверяются в порядке возрастания длин, а нетерминалы - в таком
порядке, чтобы при наличии правила K -" L нетерминал L проверялся
раньше нетерминала K. (Это возможно в силу отсутствия циклов.)
Поясним этот процесс на примере.
Пусть в грамматике есть правила
K -" L
K -" M N L
и других правил, содержащих K в левой части, нет. Мы хотим узнать,
выводится ли данное слово A из нетерминала K. Это будет
так в одном из случаев: (1) если A выводится из L; (2) если A
можно разбить на непустые слова B, C, D, для которых B выводится
из M, C выводится из N, а D выводится из L. Вся эта информация
уже есть (слова B, C, D короче A, а L рассмотрен до K).
Легко видеть, что число действий этого алгоритма полиномиально.
Степень полинома зависит от числа нетерминалов в правых
частях правил и может быть понижена, если грамматику преобразовать
к форме, в которой правая часть каждого правила содержит 1
или 2 нетерминала (это легко сделать, вводя новые нетерминалы:
например, правило K -" LMK можно заменить на K -" LN и N -" MK,
где N - новый нетерминал).
13.1.6. Рассмотрим грамматику с единственным нетерминалом
K, нетерминалами 1, 2, 3 и правилами
K -" 0
K -" 1 K
K -" 2 K K
K -" 3 K K K
Как проверить выводимость слова в этой грамматике, читая слово
слева направо? (Число действий при прочтении одной буквы должно
быть ограничено.)
Решение. Хранится целая переменная n, инвариант: слово выводимо
"-" непрочитанная часть представляет собой конкатенацию
(соединение) n выводимых слов.
13.1.7. Тот же вопрос для грамматики
K -" 0
K -" K 1
K -" K K 2
K -" K K K 3
13.2. Метод рекурсивного спуска.
В отличие от алгоритма предыдущего раздела (представляющего
чисто теоретический интерес), алгоритмы на основе рекурсивного
спуска часто используются на практике. Этот метод применим, однако,
далеко не ко всем грамматикам. Мы обсудим необходимые ограничения
позднее.
Идея метода рекурсивного спуска такова. Для каждого нетерминала
K мы строим процедуру ReadK, которая - в применении к любому
входному слову x - делает две вещи:
(1) находит наибольшее начало z слова x, которое может быть
началом выводимого из K слова;
(2) сообщает, является ли найденное слово z выводимым из K.
Прежде чем описывать этот метод более подробно, договоримся
о том, как процедуры получают сведения о входном слове и как сообщают
о результатах своей работы. Мы предполагаем, что буквы
входного слова поступают к ним по одной, т.е. имеется граница,
отделяющая "прочитанную" часть от "непрочитанной". Будем считать,
что есть функция (без параметров)
Next: Symbol
дающая первый непрочитанный символ. Ее значениями могут быть
терминальные символы, а также специальный символ EOI (End Of
Input - конец входа), означающий, что все слово уже прочитано.
Вызов этой функции, естественно, не сдвигает границы между прочитанной
и непрочитанной частью - для этого есть процедура Move,
которая сдвигает границу на один символ. (Она применима, если
Next "" EOI.) Пусть, наконец, имеется булевская переменная b.
Теперь мы можем сформулировать наши требования к процедуре
ReadK. Они состоят в следующем:
(1) ReadK прочитывает из оставшейся части слова максимальное
начало A, являющееся началом некоторого слова, выводимого
из K;
(2) значение b становится истинным или ложным в зависимости
от того, является ли A выводимым из K или лишь невыводимым началом
выводимого (из K) слова.
Для удобства введем такую терминологию: выводимое из K слово
будем называть K-словом, а любое начало любого выводимого из
K слова - K-началом. Требования (1) и (2) вместе будем выражать
словами "ReadK корректна для K".
Начнем с рассмотрения частного случая. Пусть правило
K -" L M
является единственным правилом грамматики, содержащим K в левой
части, пусть L, M - нетерминалы и ReadL, ReadM - корректные (для
них) процедуры.
Рассмотрим такую процедуру:
procedure ReadK;
begin
| ReadL;
| if b then begin
| | ReadM;
| end;
end;
13.2.1. Привести пример, когда эта процедура будет некорректной
для K.
Ответ. Пусть из L выводится любое слово вида 00..00, а из M
выводится лишь слово 01. Тогда из K выводится слово 00001, но
процедура ReadK этого не заметит.
Укажем достаточноые условия корректности процедуры ReadK.
Для этого нам понадобятся некоторые обозначения. Пусть фиксированы
КС-грамматика и некоторый нетерминал N этой грамматики.
Рассмотрим N-слово A, которое имеет собственное начало B, также
являющееся N-словом (если такие есть). Для любой пары таких слов
A и B рассмотрим терминальный символ, идущий в A непосредственно
за B. Множество всех таких терминалов обозначим Посл(N). (Если
никакое N-слово не является собственным началом другого N-слова,
то множество Посл(N) пусто.)
13.2.2. Указать (а) Посл(E) для примера 1; (б) Посл(E) и
Посл(T) для примера 2; (в) Посл("слаг") и Посл("множ") для примера
3.
Ответ. (а) Посл(e) = { [, ( }. (б) Посл(e) = { [, ( };
Посл(t) пусто (никакое t-слово не является началом другого). (в)
Посл("слаг") = {*}; Посл("множ") пусто.
Кроме того, для каждого нетерминала N обозначим через Нач(N)
множество всех терминалов, являющихся первыми буквами непустых
N-слов. Это обозначение - вместе с предыдущим - позволит дать
достаточное условие корректности процедуры ReadK в описанной выше
ситуации.
13.2.3. Доказать, что если Посл (L) не пересекается с
Нач(M) и множество всех M-слов непусто, то ReadK корректна.
Решение. Рассмотрим два случая. (1) Пусть после ReadL значение
переменной b ложно. В этом случае ReadM читает со входа
максимальное M-начало A, не являющееся M-словом. Оно является
K-началом (здесь важно, что множество L-слов непусто.). Будет ли
оно максимальным K-началом среди начал входа? Если нет, то A является
началом слова BC, где B есть L-слово, C есть M-начало и
BC - более длинное начало входа, чем A. Если B длиннее A, то A -
не максимальное начало входа, являющееся L-началом, что противоречит
корректности ReadL. Если B = A, то A было бы L-словом, а
это не так. Значит, B короче A, C непусто и первый символ слова
C следует в A за последним символом слова B, т.е. Посл(L) пересекается
с Нач(M). Противоречие. Итак, A максимально. Из сказанного
следует также, что A не является K-словом. Корректность
процедуры ReadK в этом случае проверена.
(2) Пусть после ReadL значение переменной b истинно. Тогда
прочитанное процедурой ReadK начало входа имеет вид AB, где A
есть L-слово, а B есть M-начало. Тем самым AB есть K-начало.
Проверим его максимальность. Пусть C есть большее K-начало. Тогда
либо C есть L-начало (что невозможно, так как A было максимальным
L-началом), либо C = A'B', где A' - L-слово, B' - M-начало.
Если A' короче A, то B' непусто и начинается с символа,
принадлежащего и Нач(M), и Посл(L), что невозможно. Если A'
длиннее A, то это противоречит тому, что A было максимальным.
Итак, A' = A. Но в этом случае B' есть продолжение B, что противоречит
корректности ReadM. Итак, AB - максимальное K-начало.
Остается проверить правильность выдаваемого процедурой ReadK
значения переменной b. Если оно истинно, то это очевидно. Если
оно ложно, то B не есть M-слово, и надо проверить, что AB - не
K-слово. В самом деле, если бы выполнялось AB = A'B', где A' -
L-слово, B' - M-слово, то A' не может быть длиннее A (ReadL читает
максимальное слово), A' не может быть равно A (тогда B'
равно B и не является M-словом) и A' не может быть короче A
(тогда первый символ B' принадлежит и Нач(M), и Посл(L)). Задача
решена.
Перейдем теперь к другому частному случаю. Пусть в КС-грамматике
есть правила
K -" L
K -" M
K -" N
и других правил с левой частью K нет.
13.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),то пустое слово
является наибольшим началом входа, являющимся K-началом. Если
Next принадлежит одному (и, следовательно, только одному) из
этих множеств, то максимальное начало входа, являющееся K-началом,
непусто и читается соответствующей процедурой.
13.2.5. Используя сказанное, составьте процедуру распознавания
выражений для грамматики (уже рассматривавшейся в примере
3):
"выр" -" "слаг" "оствыр"
"оствыр" -" + "выр"
"оствыр" -"
"слаг" -" "множ" "остслаг"
"остслаг" -" * "слаг"
"остслаг" -"
"множ" -" x
"множ" -" ( "выр" )
Решение. Эта грамматика не полностью подпадает под рассмотренные
частные случаи: в правых частях есть комбинации терминалов
и нетерминалов
+ "выр"
и группы из трех символов
( "выр" )
В грамматике есть также несколько правил с одной левой частью и
с правыми частями разного рода, например
"оствыр" -" + "выр"
"оствыр" -"
Эти ограничения не являются принципиальными. Так, правило типа
K -" L M N
можно было бы заменить на два правила K -" LQ и Q -" MN, терминальные
символы в правой части - на нетерминалы (с едиственным
правилом замены на соответствующие терминалы). Несколько правил
с одной левой частью и разнородными правыми также можно свести к
уже разобранному случаю: например,
K -" L M N
K -" P Q
K -"
можно заменить на правила
K -" K1
K -" K2
K -" K3
K1 -" L M N
K2 -" P Q
K3 -"
Но мы не будем этого делать - а сразу же запишем то, что получится,
если подставить описания процедур для новых терминальных
символов в места их использования. Например, для правила
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
| | ReadB;
| | 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;
Читая приведенную далее программу, полезно иметь в виду соответствие
между русскими и английскими словами:
ВЫРажение EXPRession
ОСТаток ВЫРажения REST of EXPRession
СЛАГаемое ADDitive term
ОСТаток СЛАГаемого REST of ADDitive term
МНОЖитель MULTiplier
procedure ReadSymb (c: Symbol);
| b := (Next = c);
| if b then begin Move; end;
end;
procedure ReadExpr;
| ReadAdd;
| if b then begin ReadRestExpr; end;
end;
procedure ReadRestExpr;
| if Next = '+' then begin
| | ReadSymb ('+');
| | if b then begin ReadExpr; end;
| end else begin
| | b := true;
| end;
end;
procedure ReadAdd;
| ReadMult;
| 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 ReadMult;
| 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) пусты, но написанная по
нашим канонам процедура
procedure ReadK;
begin
| ReadK;
| if b then begin
| | ReadK;
| end;
end;
не заканчивает работы.)
В даннном случае процедуры ReadRestExpr, ReadRestAdd,
ReadMult либо завершаются, либо уменьшают длину непрочитанной
части входа. Поскольку любой цикл вызовов включает одну из них,
то зацикливание невозможно. Задача решена.
13.2.6. Пуст
...Закладка в соц.сетях
