Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

11.5. РЕКУРСИЯ ПРИ ОБРАБОТКЕ СИМВОЛЬНОЙ ИНФОРМАЦИИ

685

В рамках приведенных соглашений представленное рекурсивное определе-

ние в точности соответствует рекуррентному соотношению: проверка усло-

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

Read

(S)

отрезает первый символ и запоминает его,

REV

обращает остаток строки

(и, разумеется, печатает полученную строку), а

Write (S)

дописывает запо-

мненный символ.

Если для решения данной задачи попытаться составить итеративную про-

грамму, то, по-видимому, придется предусмотреть запоминание читаемых

входных символов в специальной области памяти (массив, список и др.), ко-

торую программист будет вынужден отводить явно. Эта ситуация возникает,

поскольку поставленная задача является рекурсивной по существу (см. со-

поставление рекурсивной и итеративной схем).

Пример 11.5.1. Задача, для которой рекурсия позволяет описать алгоритм

решения достаточно просто.

Пусть обрабатываемая последовательность символов (текст)содержит не-

которое количество парных символов, называемых открывающими и закры-

вающими скобками. Текст считается сбалансированным по скобкам в следу-

ющих случаях:

1) текст не содержит скобочных символов (в том числе, пустой текст);

2) если тексты

сбалансированы, то сбалансирован текст, составлен-

ный из

, за которым помещается

;

3) если текст

сбалансирован, то сбалансирован текст, образованный из

путем обрамления его парными открывающей и закрывающей скобками;

4) других сбалансированных текстов нет.

Заметим, что это определение есть просто словесно записанное рекуррент-

ное соотношение.Если “(”и “)”,“[”и “]”,“<”и “>”—пары соответствующих

открывающих и закрывающих скобок, то сбалансированы тексты

“()”,

“asd(ill0)[q]”,

“(ро+i<l><[]>(123))”,

“([<()>])([])”,

а тексты

“((”,

686

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

“([)]”,

“asd((ill0)[q]”,

“(ро+i<l><[]>(123)”,

“)(”

не сбалансированы.

Требуется написать программу,проверяющую сбалансированность по скоб-

кам вводимой последовательности символов.

Решение этой задачи, когда имеется только одна пара соответствующих

скобок, для определенности “(” и “)”, очень просто:

Программа 11.5.2

count := 0;

while not Eof and ( count >= 0 ) do

begin

Read ( S );

if S = ’(’

then count := count + 1

else if S = ’)’

then count := count - 1

end;

if count = 0

then Write (’OK’)

else Write (’ERR’);

Здесь

count

— счетчик скобок, который увеличивается, когда во входном по-

токе встречается открывающая скобка, и уменьшается, когда встречается за-

крывающая скобка. Цикл просмотра входного потока прекращается при об-

наружении лишней закрывающей скобки (

count

в этом случае оказывается

отрицательным) или по исчерпанию вводимых символов. Дополнительная

проверка того, что при исчерпании ввода число открывающих и закрыва-

ющих скобок совпадает, т. е.

count = 0

, завершает алгоритм. (Прежде чем

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

стоятельно преобразовать этот алгоритм в рекурсивную подпрограмму.)

По-видимому, это самый лучший алгоритм, когда имеется единственная

пара скобок. Однако непосредственно перенести его на случаи с двумя и бо-

лее парами скобок не удается. Причина тому — невозможность без использо-

вания дополнительной памяти отследить правильность чередования скобок,

11.5. РЕКУРСИЯ ПРИ ОБРАБОТКЕ СИМВОЛЬНОЙ ИНФОРМАЦИИ

687

к примеру, “

[(])

”. Каждая парная открывающая скобка требует, чтобы провер-

ка баланса для фрагмента текста, обрамленного ею слева и соответствующей

закрывающей скобкой справа, осуществлялся заново. Правила составления

сбалансированных текстов таковы, что позволяют говорить об экземплярах

процессов такой проверки, которые

a) отвечают за обработку содержимого скобок, и

b) подчиняются стековой дисциплине.

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

подпрограммой, для определенности логической функцией, каждый процесс

экземпляр которой порождается при появлении открывающей скобки (одно-

го из предусмотренных видов) и выполняет обработку текста до появления

во входном потоке соответствующей закрывающей скобки или обнаружения

дисбаланса. Если вид закрывающей скобки совпадает с видом открывающей

скобки, породившей процесс, то происходит завершение процесса с выраба-

тыванием значения true, а если нет или входной поток завершается прежде,

чем встречается требуемая закрывающая скобка, то процесс завершается со

значением false.

Эти соображения положены в основу алгоритма, представленного ниже.

В дополнение к ним при составлении программы используется следующее

наблюдение. Содержательные действия обсуждаемой программы связаны с

реакцией на появление во входном потоке только скобочных символов и об-

наружением конца вводимой последовательности. Поэтому разумно преду-

смотреть фильтрацию ввода, выделяя и передавая для обработки основной

функции только скобки и специальный символ, отмечающий конец текста.

В последующей программе такая фильтрация осуществляется процедурой

Scan

Требуемое для обработки значение процедура

Scan

передает через пере-

менную

. Еще одна глобальная переменная, используемая в программе, —

,предназначенная для индикации выявления дисбаланса.В глобальном кон-

тексте программы представлено также описание констант:

const Etxt = ’*’; {

для определенности

}

bs1 = ’(’; es1 = ’)’;

bs2 = ’[’; es2 = ’]’;

bs3 = ’<’; es3 = ’>’;

688

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

смысл которых очевиден. Вполне удовлетворительный вариант подпрограм-

мы, проверяющей фрагмент текста, может быть задан функцией

Balans

function Balans ( Q : Char ) : Boolean;

begin

Scan;

case S of

Etxt : Balans := TRUE;

bs1, bs2, bs3 : Balans := Balans ( S );

es1 : Balans := Q = bs1;

{

это лучше, чем

}

{if Q = bs1 then Balans := TRUE}

{else Balans := FALSE }

es2 : Balans := Q = bs2;

es3 : Balans := Q = bs3;

end

end; {Balans}

Однако в этой подпрограмме имеется некоторая избыточность действий,

связанная с проверкой

Q = bsI

, (I = 1, 2, 3): до этого уже проверялось, что

значение

равно

bsI

(второй вариант оператора case). За счет того, что через

параметр функции можно передавать код не открывающей, а закрывающей

скобки, можно избавиться от этой избыточности:

function Balans ( Q : Char ) : Boolean;

begin

Scan;

case S of

Etxt : Balans := true;

bs1 : Balans := Balans ( es1 );

bs2 : Balans := Balans ( es2 );

bs3 : Balans := Balans ( es3 );

es1, es2, es3 : Balans := S = Q;

end

end; {Balans}

Окончательно программа, предлагаемая в качестве решения задачи, вы-

глядит следующим образом:

11.5. РЕКУРСИЯ ПРИ ОБРАБОТКЕ СИМВОЛЬНОЙ ИНФОРМАЦИИ

689

Программа 11.5.3

program BalansTest;

const Etxt = ’*’; {

для определенности

}

bs1 = ’(’; es1 = ’)’;

bs2 = ’[’; es2 = ’]’;

bs3 = ’<’; es3 = ’>’;

var S : char;

P : Boolean;

procedure Scan;

begin

if Eof

then S := Etxt

else repeat

Read ( S );

until Eof or

( S in [ bs1, bs2, bs3, es1, es2, es3 ] );

if Eof then S := Etxt

end; {Scan}

function Balans ( Q : char ) : Boolean;

begin

Scan;

case S of

Etxt : Balans := TRUE;

bs1 : Balans := Balans ( es1 );

bs2 : Balans := Balans ( es2 );

bs3 : Balans := Balans ( es3 );

es1, es2, es3 : Balans := S = Q;

end

end; {Balans}

begin

P := true;

while not Eof and P do P := Balans ( S );

if P then Write (’OK’)

else Write (’ERR’);

end.

Уместно обратить внимание на то, что в данной программе не потребовалось

690

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

использовать какие бы то ни было счетчики (аналогичные

Count

из предыду-

щего алгоритма). Их роль, очевидно, играют рекурсивные вызовы функции

Balans

, точнее, соответствующие экземпляры функции для каждой открыва-

ющей скобки.

Для того, чтобы увидеть, насколько трудозатраты, красота и модифици-

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

от стиля), сравните полученное решение с программой 13.1.2, написанной

в сентенциальном стиле.

Конец примера 11.5.1.

Рекурсия в обработке символьной информации занимает очень важное

место. Достаточно сказать, что задача синтаксического анализа, решаемая

при разработке любого транслятора, является рекурсивной по существу. Де-

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

помощи так называемых контекстно-свободных грамматик, языки которых

требуют для своего распознавания использовать автоматы с магазинной па-

мятью (т. е. со стеком, в котором запоминаются состояния автомата, другая

информация, управляющая вычислительным процессом). В дальнейшем мы

этой задаче уделим особое внимание (см. п. 11.6 и следующий за ним).

§ 11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ

11.6.1. Синтаксический распознаватель простых выражений

Рекурсивная по своей природе структура программных текстов в их кон-

кретно-синтаксическом и абстрактно-синтаксическом представлениях наво-

дит на мысль о том, что при трансляции могут продуктивно применяться

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

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

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

тельный и эффективный метод рекурсивного спуска. В последующих далее

главах мы еще не раз будем обращаться к алгоритмам трансляции, чтобы

выделить другие методы и сопоставить их с рекурсивным спуском. Базовой

иллюстрацией для дальнейшего рассмотрения методов служат упрощенные

арифметические выражения, для которых строятся следующие программы:

a) синтаксический анализатор: проверяет тот факт, что вводимая последо-

вательность символов принадлежит языку арифметических выражений с

точки зрения его конкретного синтаксиса;

11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ

691

b) конструктор абстрактного синтаксиса: переводит конкретно-синтакси-

ческое представление строки в форму дерева, которое можно интерпрети-

ровать как ее абстрактно-синтаксическое представление;

c) интерпретатор дерева абстрактного синтаксиса: вычисляет выраже-

ние.

Упрощенные выражения описываются следующей контекстно-свободной грам-

матикой:

<M> “-” <E> ( 1 )

<T> “/” <M> ( 2 )

“(” <E> “)” ( 3 )

<L> <I> ( 4 )

<L> ::= “a”

“b”

“c”

...

“z” ( 5 )

Эта грамматика записана в нотации из § 2.1, но для краткости мы дали

однобуквенные обозначения нетерминальным символам:

<E>

— выражение

(определяемое понятие);

<M>

— простое выражение,

<T>

— терм,

<I>

— имя

переменной,

<L>

— буква. Символы, из которых строится выражение — бу-

квы латинского алфавита (правило 5, в котором для краткости варианты по-

рождения недостающих букв заменены многоточием), знаки сложения и вы-

читания

“+”

“-”

(правило 1), знаки умножения и деления

“*”

“/”

(правило 2),

скобки

“(”

“)”

(правило 3). Правило 4 служит для задания способа формиро-

вания имени из букв (имя может состоять из любого положительного числа

букв). В дальнейшем, употребляя терминальные и нетерминальные симво-

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

вызывает двусмысленности.

Понятно, что грамматика задает рекуррентное соотношение, определя-

ющее структуру простых выражений. Это соотношение играет ту же роль,

что и словесное описание структуры строк в задаче про баланс скобок: оно

будет использовано для непосредственного построения алгоритма анализа.

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

ний иллюстрируется примерами, которые приведены в таблице 11.1. В левой

колонке таблицы записаны выражения, а в правой — их вывод-порождение

в виде цепочки строк, выводимых одна из другой путем применения правил

и их вариантов. Единичное, так называемое непосредственное порождение

обозначается с помощью “⇒”, которое для пояснения обычно индексирует-

ся парой чисел: номер правила и номер варианта (через точку). Если такой

692

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

индекс для понимания не представляет интереса, то он опускается. В некото-

рых примерах ряд непосредственных промежуточных порождений, не прин-

ципиальных для понимания, опускается. Эта ситуация отмечается символом

“*” после “⇒”.

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

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

мой программе для распознавания принадлежности строк к языку, задавае-

мому грамматикой, основывается на методе рекурсивного спуска. Суть мето-

да состоит в моделировании вывода анализируемой строки путем выдвиже-

ния и проверки гипотез о применении в ходе вывода тех или иных правил.Ка-

ждому правилу грамматики сопоставляется (рекурсивная) подпрограмма —

процедура или функция, которая способна распознавать свойство выводи-

мости части входной строки из данного правила. Эти подпрограммы орга-

низуют синхронное перемещение по правым частям правил грамматики и

входному потоку символов. В ходе такого перемещения возможно либо срав-

нение входного символа с символом из правила, либо проверка гипотезы о

выводимости очередной части строки из некоторого (нового,не являющегося

текущим) правила. В первом случае, когда сравнение успешно, происходит

продвижению по входной строке слева направо, а когда оно не успешно —

отвержение текущей гипотезы и возврат к подпрограмме правила, которая

вызвала исполняемую в данный момент подпрограмму.

Для произвольной грамматики метод рекурсивного спуска требует, во-

обще говоря, возвратов анализа к уже прочитанной части строки. Но, если

грамматика удовлетворяет некоторым условиям, то возможен безвозвратный

анализ. Приведенная грамматика не удовлетворяет этим условиям.

Мы специально выбрали такое представление грамматики, которое тре-

бует преобразования, приспосабливающего ее к безвозвратной схеме анали-

за, чтобы продемонстрировать достаточно типичный метод. Ради этого мы

даже пожертвовали соответствием конкретного синтаксиса правилам вычи-

слений выражений. К слову сказать, представленное ниже преобразование

вернет новой грамматике это полезное свойство.

При модификации грамматики варианты правил переписываются в ви-

де так называемых регулярных выражений, которые образуются из исход-

Обсуждение вопросов, связанных с преобразованием сложно структурированных данных

см. в главе, посвященной сентенциальным методам.

11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ

693

Выражение Вывод-порождение выражения

a E ⇒

1.1

M ⇒

2.1

T ⇒

3.1

I ⇒

4.1

L ⇒

5.1

b E ⇒

1.1

M ⇒

2.1

T ⇒

3.1

I ⇒

4.1

L ⇒

5.2

a +

b E ⇒

1.2

M + E ⇒

2.1

T + E ⇒

3.1

I + E ⇒

4.1

L + E ⇒

5.1

a + E

⇒

1.1

a + M ⇒

2.1

a + T ⇒

3.1

a + I ⇒

4.1

a + L ⇒

5.2

a + b

ac * ( a - b

) E ⇒

1.1

M ⇒

2.2

T * M ⇒

3.1

I * M ⇒

4.2

LI * M ⇒

5.1

aI * M

⇒

5.3

ac * M ⇒

2.1

ac * T ⇒

3.2

ac * (E) ⇒

1.3

ac * (M-E) ⇒

∗

ac * (a - E) ⇒ ac * (a - M) ⇒

∗

ac * (a - b)

( a - b ) *

( c + d )

E ⇒

1.1

M ⇒

2.2

T * M ⇒

3.2

( E ) * M ⇒

∗

( a - b ) * M ⇒

∗

( a

- b) * ( c + d

)

ac *

bd E ⇒

1.1

M ⇒

2.2

T * M

{В предыдущих примерах для очередного порождения

использовалось самое левое из понятий строки; сей-

час демонстрируется возможность продолжать вывод из

любого понятия, имеющегося в строке (в данном слу-

чае это

, второе понятие, из которого получено

Поскольку грамматика выражения контекстно-свобод-

ная, результат вывода не зависит от выбора правил.}

⇒

3.1

T * I ⇒

4.2

Т * LI ⇒

5.2

T * bI ⇒

∗

ac * bd

Таблица 11.1. Примеры вывода выражений

694

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

ной грамматики путем объединения вариантов. Эта модификация приводит

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

входном потоке по первому символу: ситуация, когда первый символ соот-

ветствует грамматике, а последующие нет, гарантирует, что входная строка

не принадлежит языку.

Регулярные выражения задаются в следующей нотации:

• в фигурные скобки “{” и “}” заключаются объединяемые части вари-

антов;

• внутри фигурных скобок возможно использование символа “|” со ста-

рым смыслом (он указывает на возможность вариантов выбора поро-

ждения);

• если непосредственно после фигурных скобок употреблен символ “+”

или “*”, то это означает, что возможно повторение обрамленной фи-

гурными скобками части строки. Символ “*” указывает на необязатель-

ность обрамленной фигурными скобками части — повторение нуль и

более раз, а символ “+” на то, что эта часть в порождении должна по-

явиться по крайней мере один раз.

Данная нотация регулярных выражений более традиционна для теоретиче-

ских рассмотрений регулярных выражений,чем та,что использовалась в § 2.1.

В новой редакции грамматика упрощенных арифметических выражений вы-

глядит следующим образом:

E ::= M { + E

- E }* ( 1 )

M ::= T { * M

/ M }* ( 2 )

T ::= I

( E ) ( 3 )

I ::= { a

...

z }+ ( 4 )

Первое правило состоит в том, что

(выражение) есть

(простое выра-

жение), за которым, быть может, следуют “

+ E

” или “

- E

”, повторенные нуль

и более раз. Аналогично, второе правило читается:

есть

(терм), за ко-

торым, быть может, следуют “

* E

” или “

/ E

”, повторенные нуль и более раз.

Определение терма (правило 3) не изменилось. Четвертое и пятое правило

объединены. Теперь

(имя переменной) есть буква, повторенная один и бо-

лее раз.

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