Непейвода Н.Н., Скопин И.Н. Основания программирования
Подождите немного. Документ загружается.
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
695
В соответствии с новой грамматикой процесс распознавания того, явля-
ется ли входная строка выражением, задается с помощью комплекта логиче-
ских функций:
E
,
M
,
T
и
I
. Они выясняют, распознается ли некоторая часть
строки как выражение (
E
), простое выражение (
M
), терм (
T
) и имя перемен-
ной (
I
), и тогда вырабатывают значение true, а в противном случае — false.
Для наглядности программы этих функций поименованы также, как прави-
ла грамматики. Они составляются систематическим переписыванием пра-
вил, при котором понятия, появляющиеся в правиле, превращаются в вызовы
соответствующих им функций, а обрамленные фигурными скобками части
оформляются как циклы.
Обработка символов, из которых строится выражение (букв, знаков “+”,
“-”, “*”, “/”, скобок), задается как сравнение этих символов с значением ли-
теры из входного потока. Это значение поставляется специальной процеду-
рой
Scan
, которая записывает его в глобальную переменную
S
. В предста-
вленной ниже программе
Scan
осуществляет чтение литеры из файла вво-
да и печатает пробел под очередным читаемым символом (чтобы в случае
ошибки можно было бы отметить этот символ в вводимой строке). Как пра-
вило, подобные действия сопровождаются другими дополнительными вычи-
слениями лексического характера,например,распечаткой читаемой последо-
вательности символов, удалением незначащих пробелов и др. Тем самым в
программе синтаксического анализа выделяется часть, отвечающая за прове-
дение лексических вычислений, главная цель которых — выработка лексем
(в предлагаемой программе это значения переменной
S
), передаваемых для
выполнения собственно синтаксических вычислений без избыточной инфор-
мации. Обучаемому предлагается модифицировать программу с тем, чтобы
указанные выше дополнительные лексические вычисления осуществлялись.
Переменная
S
и процедура
Scan
включены в комплект подпрограмм син-
таксического распознавания.
Последнее предварительное замечания касается использования в програм-
ме конструкции #13 языка
Turbo Pascal
. Она обозначает символьное значе-
ние, которое нельзя представить графически, в данном случае это символ пе-
рехода на новую строку, который позволяет узнавать, действительно ли вся
входная последовательность прочитана.
Программа 11.6.1
program PARSER;
var S : Char;
696
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
function E : Boolean; forward;
function M : Boolean; forward;
function T : Boolean; forward;
function I : Boolean; forward;
procedure Scan;
begin
Read ( S ); Write (’ ’);
end; Scan
function E : Boolean;
var f : Boolean;
begin
if M
then begin
f := true;
while f and ((S = ’+’) or (S = ’-’)) do
begin
Scan; f := E
end;
E := f;
end
else E := false
end; {E}
function M : Boolean;
var f : Boolean;
begin
if T
then begin
f := true;
while f and ((S = ’*’) or (S = ’/’)) do
begin
Scan; f := M
end;
M := f;
end
else M := FALSE
end; {M}
function T : Boolean;
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
697
begin
if I
then T := true
else if (S = ’(’)
then begin
Scan;
if E
then if S = ’)’
then begin Scan; T := true
end
else T := false
end
else T:= false
end; {T}
function I : Boolean;
var f : Boolean;
begin
f := S in [’a’..’z’];
while S in [’a’..’z’] do Scan;
I := f
end; {I}
begin {
Начало программы
PARSER }
Scan;
if E and ( S = #13 )
then begin Writeln; Writeln (’OK’) end
else begin Writeln (’^’); Writeln (’ERR’) end
end.
Предлагаемая программа демонстрирует опосредованную рекурсивность под-
программ: функция
T
непосредственно себя не вызывает, но за счет того, что
в ней употребляется вызов функции
E
, она является рекурсивной (
E
может
вызвать
M
, которая, в свою очередь, может вызвать
T
). Особой является опо-
средованная рекурсия, когда отсутствуют явные рекурсивные вызовы в двух
и более подпрограммах, а рекурсия образуется лишь за счет динамической
последовательности вызовов подпрограмм:
procedure P;
698
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
begin
... Q; ...
end;
procedure Q;
begin
... P; ...
end;
В таких случаях говорят о взаимной рекурсивности подпрограмм.
Опосредованная, а тем более, взаимная рекурсия — это ситуация, тре-
бующая обязательного употребления в программах предописаний процедур
и функций. Их отсутствие нарушало бы основополагающий принцип языка
Pascal
, согласно которому все, что используется в программе, должно быть
ранее (по тексту) описано. Роль такого необходимого описания процедуры
или функции играет заголовок,за которым следует служебное слово forward:
function E : Boolean; forward;
В программе распознавателя обязательно предописание только для функ-
ции
E
, т. к., расположив остальные подпрограммы в соответствующем по-
рядке, можно добиться выполнения отмеченного принципа. Дополнитель-
ные предописания здесь служат иной цели: они дают возможность такого
порядка подпрограмм, который лучше соответствует восприятию (в той по-
следовательности, в которой заданы правила грамматики). Еще одна роль
предописаний связана с методологическим принципом разделения уровней
определения программных единиц и их использования: при употреблении
подпрограмм, имеющих предописания легче абстрагироваться от того, как
они реализуют требуемые действия, сосредоточивая внимание на том, что
они должны делать.
Приведенная программа — иллюстративный пример распознавателя. В
практических случаях,например,в трансляторах,синтаксический анализ обыч-
но устроен существенно сложнее. Намек на такое усложнение был предста-
влен, когда говорилось о лексических вычислениях (процедура
Scan
). Сле-
дует добавить, что целью синтаксического анализа, как правило, является не
только распознавание принадлежности строки языку, но и выполнение дру-
гих, более содержательных действий.
8
8
Одно из таких действий — выдача осмысленного сообщения об ошибке в случае не-
правильного выражения, другое — составление по ходу анализа таблиц идентификаторов,
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
699
11.6.3. Обратная польская запись выражений: понятие,алгоритмы вы-
числения и построения
В качестве еще одной иллюстрации рекурсивной обработки строк при
трансляции предлагается программа, строящая по строке-выражению так на-
зываемую обратную польскую запись (ПОЛИЗ)данного выражения.ПОЛИЗ —
это такая запись выражения, при которой каждое бинарное подвыражение
<левый операнд> <знак операции> <правый операнд>
заменяется на
<левый операнд> <правый операнд> <знак операции>
.
Например, выражение
a+b*(c/e-d)
представляется как
abce/d-*+
. Для упро-
щенной грамматики выражений
E
→
M { + E |- E }* ( 1 )
M
→
T { * M |/ M }* ( 2 )
T
→
I |( E ) ( 3 )
I
→
{ a |b |c |...|z }+ ( 4 )
грамматику ПОЛИЗ можно определить, просто преобразовав правые части
правил ( 1 ), ( 2 ) и ( 3 ):
M { + E |- E }*
=⇒
M { E + |E - }* ( 1’ )
T { * M |/ M }*
=⇒
T { M * |M / }* ( 2’ )
I |( E )
=⇒
I |E . ( 3’ )
Часть строки, распознаваемая как имя переменной (правило (4)) перено-
сится в ПОЛИЗ неизменной.
Нетрудно заметить, что ПОЛИЗ есть просто другое представление струк-
туры выражения по сравнению с исходным его видом. Как мы скоро уви-
дим, оно великолепно согласуется с вычислением-интерпретацией, причем
именно так, как того требует определение семантики абстрактным вычисли-
телем, заданным на структуре синтаксического домино. Таким образом, ПО-
ЛИЗ вполне можно рассматривать в качестве одной из форм задания абстракт-
ного синтаксиса (при этом, разумеется, надо еще задавать атрибуты элемен-
тов структуры, например, подобно тому, как мы это делали с синтаксическим
домино).
блоков, операторов и вообще накопление вспомогательной информации для последующей
трансляции и отладки программы.
700
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
Употребление обратной польской записи выражений в качестве внутрен-
него представления в транслирующих программах позволяет избежать ско-
бок и приоритетов операций. Но, пожалуй, более важно то, что ПОЛИЗ хо-
рошо согласуется с выполнением вычислений на стеке. Соответствующий
алгоритм можно представить следующей схемой:
Открыть пустой стек;
Установить чтение ПОЛИЗ на начало;
Прочитать два символа из ПОЛИЗ, сохраняя их в стеке;
{
в стеке находятся два операнда, прочитанные из ПОЛИЗ,
очередной символ из ПОЛИЗ — операнд или знак операции
}
пока не все символы ПОЛИЗ прочитаны цикл
начало
Прочитать символ из ПОЛИЗ; если прочитанный символ — операнд
то Поместить прочитанный символ в стек
иначе {
прочитанный символ — знак операции
}
начало
Вычислить бинарное выражение с операндами из стека
и с операцией, определяемой прочитанным символом;
Поместить результат вычисления в стек;
{
два верхних элемента стека заменяются
на результат вычисления операции
}
Прочитать символ из ПОЛИЗ
конец
конец
Существенным условием работоспособности данного алгоритма являет-
ся предположение о корректности польской записи.Это предположение впол-
не оправдано, поскольку в практически важных случаях ПОЛИЗ строится по
обычной записи выражения, а в ходе такого построения проверка корректно-
сти возможна и весьма целесообразна. Для учебных целей может потребо-
ваться программа, которая не связана с обсуждаемым ограничением. Обуча-
емым предлагается записать приведенный алгоритм на
Pascal
либо
C/C++
, а
также модифицировать его с учетом возможной некорректности польской за-
писи. Следует сравнить два варианта программы. Полезно также попытаться
сделать алгоритм более эффективным за счет других его улучшений. Кроме
того, предлагается трансформировать данную итеративную схему в рекур-
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
701
сивную. Какие структуры данных при этой трансформации окажутся избы-
точными и почему?
В таблице 11.2 представлены примеры выражений в обычной записи и их
перевод в ПОЛИЗ, а также последовательности состояний вычислений вы-
ражения по его польской записи, соответствующие приведенному алгорит-
му. Состояния вычислений показаны в виде двух частей: содержимое стека и
непрочитанного остатка ПОЛИЗ. Промежуточные результаты вычислений в
стеке обозначаются как
R
и
R1
. Несущественные для понимания состояния
заменены многоточием.
Предлагаемая ниже программа перевода обычной записи выражения в
ПОЛИЗ составляется путем простого дополнения программы распознавате-
ля необходимыми структурами данных и действиями.
Дополнительные структуры данных — это глобальная переменная стро-
кового типа
R
, предназначенная для накопления ПОЛИЗ выражения, и ло-
кальные переменные
op
символьного типа в функциях
E
и
M
, в которых со-
храняется знак соответствующей операции до тех пор,пока он не станет нуж-
ным для переноса в
R
(т. е. до завершения обработки второго операнда ка-
ждого из бинарных подвыражений).
Дополнительные действия — это наращивание
R
, запоминание знаков
операций в op. Уместно отметить, что такое запоминание есть неявная орга-
низация стека, которая осуществляется посредством рекурсивных вызовов.
Кроме него к дополнительным действиям также относится результирующий
вывод ПОЛИЗ вводимого выражения,который задается,если выражение ока-
зывается корректным.
С учетом сделанных замечаний программа
POLIS
, приводимая ниже, не
нуждается в дополнительных пояснениях.
Программа 11.6.2
program POLIS;
var S : Char;
R : String;
function E : Boolean; forward;
function M : Boolean; forward;
function T : Boolean; forward;
function I : Boolean; forward;
procedure Scan;
702
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
Выражение ПОЛИЗ Состояния вычислений:
стек остаток ПОЛИЗ
a a a
a +
b ab + a b +
a
b +
R
ac * ( a - b
) ac a b - * ... ac a b - *
ac
R *
R
( a - b ) * ( c + d
) a b - c d - * ... a b - c d + *
R c d + *
R
R1 *
R
a+(b+(c+(d+e)*f)*g)*h a b c d e + f * + g * + h * + ... a b c d e + f * + g * + h * +
a b c
R f * + g * + h * +
a b c R
f * + g * + h * +
a b c
R + g * + h * +
... a b R
g * + h * +
... a R
h * +
a
R +
R
(((a+b)*c+d)*e+f)*g+h a b + c * d + ... R c* d +e * f + g *h+
e * f + g * h
+ R c * d + e * f + g *h+
R d + e * f + g * h +
... R
f + g * h +
... R
g * h +
R h +
R
a-(b-(c-(d
-(e-f)))) a b c d e f - - - - - ... a b c d e f - - - - -
a b c d
R - - - -
a b c
R - - -
a b
R - -
a
R -
R
Таблица 11.2. Обычная и обратная польская записи выражений, вычисления
по обратной польская записи.
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
703
begin
Read ( S ); Write (’ ’);
end; {Scan}
function E : Boolean;
var f : Boolean;
op: char;
begin
if M
then begin
f := TRUE;
while f and ((S = ’+’) or (S = ’-’)) do
begin
op := S;
Scan; f := E;
R := R + op + ’ ’
end;
E := f;
end
else E := FALSE
end; {E}
function M : Boolean;
var f : Boolean;
op: char;
begin
if T
then begin
f := TRUE;
while f and ((S = ’*’) or (S = ’/’)) do
begin
op := S;
Scan; f := M;
R := R + op + ’ ’
end;
M := f;
end
else M := FALSE
704
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
end; {M}
function T : Boolean;
begin
if I
then T := TRUE
else if (S = ’(’)
then begin
Scan;
if E
then if S = ’)’
then begin Scan; T := TRUE
end
else T := FALSE
end
else T:= FALSE
end; {T}
function I : Boolean;
var f : Boolean;
begin
f := S in [’a’..’z’];
while S in [’a’..’z’] do
begin
R := R + S;
Scan;
end;
if f
then R := R + ’ ’;
I := f
end; {I}
begin {
Начало программы
POLIS }
Writeln( ’Введите выражение’ );
R := ”;
Scan;
if E and ( S = #13 )
then