за 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. Пусть в грамматике имеются два правила с нетерми-
иналом K в левой части, имеющих вид
K -> LK
K ->
по которым K-слово представляет собой конечную последова-
тельность L-слов, причем множества Посл(L) и Нач(K) (в данном
случае равное Нач(L)) не пересекаются. Используя корректную для
L процедуру ReadL, написать корректную для K процедуру ReadK, не
используя рекурсии. Предполагается, что пустое слово не выводимо
из L.
Решение. По нашим правилам следовало бы написать
procedure ReadK;
begin
| if (Next принадлежит Нач (L)) then begin
| | ReadL;
| | if b then begin ReadK; end;
| end else begin
| | b := true;
| end;
end;
завершение работы гарантируется тем, что пустое слово не выводи-
мо из L (и, следовательно, перед рекурсивным вызовом длина неп-
рочитанной части уменьшается).
Эта рекурсивная процедура эквивалентна нерекурсивной:
procedure ReadK;
begin
| b := true;
| while b and (Next принадлежит Нач (L)) do begin
| | ReadL;
| end;
end;
Формально можно проверить эту эквивалентность так. Завершаемость
в обоих случаях ясна. Достаточно проверить поэтому, что тело ре-
курсивной процедуры эквивалентно нерекурсивной в предположении,
что ее рекурсивный вызов эквивалентен вызову нерекурсивной про-
цедуры. Подставим:
if (Next принадлежит Нач (K)) 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
истинно). Вторую команду можно перенести в начало:
b := true;
if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end;
Теперь внутренний if можно выкинуть (если b ложно, цикл while
все равно не выполняется) и добавить в условие внешнего if усло-
вие b (которое все равно истинно).
b := true;
if b and (Next принадлежит Нач (L)) then begin
| ReadL;
| while b and (Next принадлежит Нач (A)) do begin
| | ReadL;
| end;
end;
что эквивалентно приведенной выше нерекурсивной процедуре (из
которой вынесена первая итерация цикла).
13.2.7. Доказать корректность приведенной выше нерекурсив-
ной программы непосредственно, без ссылок на рекурсивную.
Решение. Рассмотрим наибольшее начало входа, являющееся
K-началом. Оно представляется в виде конкатенации (последова-
тельного приписывания) нескольких непустых L-слов и, возможно,
одного непустого L-начала, не являющегося L-словом. Инвариант
цикла: прочитано несколько из них; b <=> (последнее прочитанное
