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;

Формально можно проверить эту эквивалентность так. Завершаемость в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной процедуры эквивалентно нерекурсивной в предположении, что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры. Подставим: