Procedure ReadK;
Begin
| ReadK;
| if b then begin
| | ReadK;
| end;
End;
Не заканчивает работы.)
В даннном случае процедуры ReadRestExpr, ReadRestAdd, ReadMult либо завершаются, либо уменьшают длину непрочитанной части входа. Поскольку любой цикл вызовов включает одну из них, то зацикливание невозможно. Задача решена.
Пусть в грамматике имеются два правила с нетермииналом 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;
Формально можно проверить эту эквивалентность так. Завершаемость в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной процедуры эквивалентно нерекурсивной в предположении, что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры. Подставим:
Дата добавления: 2015-10-05; просмотров: 647;