Заметки о рекурсии - 3. Косвенная рекурсия

Введение

До сих пор, говоря о рекурсии (см. статьи 1 и 2), мы подразумевали, что рекурсивная процедура обращается к самой себе. Например, для вычисления факториала нужно сначала найти факториал меньшего числа; чтобы переложить ханойскую башню, нужно переложить башню из меньшего числа колец, и так далее.
В принципе, ничто не мешает нам обобщить подобный метод на большее число процедур. Например, процедура A вызывает процедуру B, а та, в свою очередь, процедуру A. Такая рекурсия называется косвенной или взаимной, в отличие от авторекурсии, с которой мы уже познакомились ранее.
Разумеется, две взаимно-рекурсивные процедуры это не предел. Вполне можно построить более длинную цепочку взаимной рекурсии: процедура A1 вызывает A2, та, в свою очередь, A3 и так далее; замыкает цепочку процедура AN, которая вызывает A1. Рекурсия налицо.
Допустима ли подобная конструкция с точки зрения ее практической реализации? Разумеется, допустима при условии, что выбранный вами язык программирования поддерживает механизм рекурсии. Как мы уже знаем, для этого необходимо, чтобы формальные параметры процедуры передавались через стек. Немаловажно также, чтобы временные объекты, создаваемые внутри процедуры в ходе ее выполнения, тоже располагались в стеке.
Кроме того, в языках со строгой типизацией зачастую требуется, чтобы имя процедуры, тип и количество ее параметров, а также тип возвращаемого значения (если есть) были определена до ее использования. В случае авторекурсии это требование выполняется автоматически, поскольку к моменту рекурсивного вызова процедуры ее заголовок уже определен. Некоторые затруднения, однако, могут возникнуть в случае взаимной рекурсии:
Код:
// Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

void A(void)
{
B();
}

void B(void)
{
A();
}

int main(int argc, char* argv[])
{
A();
return 0;
}

Как мы видим, процедура A вызывает процедуру B, которая к этому моменту еще не определена. Разумеется, при компиляции этой конструкции возникает ошибка:
Код:
Compiling...
Test.cpp
C:\PROJECTS\Shelek\Recurce\Test\Test.cpp(8) : error C2065: 'B' : undeclared identifier
C:\PROJECTS\Shelek\Recurce\Test\Test.cpp(12) : error C2373: 'B' : redefinition; different type modifiers
Error executing cl.exe.

Test.exe - 2 error(s), 0 warning(s)

Возникает замкнутый круг: одна из процедур неизбежно должна вызвать другую, еще не описанную; перестановка процедур местами ничего не дает, поскольку проблема симметрична. К счастью, разорвать его весьма просто; в частности, для C++ достаточно лишь объявить процедуру B перед вызовом, не описывая ее тело:

Код:
// Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

void B(void); // теперь A знает, как вызвать B
void A(void)
{
B();
}

void B(void)
{
A();
}

В других языках также предусмотрены аналогичные средства решения подобных проблем. Например, в языке Pascal имеется ключевое слово forward, которое указывает, что тело процедуры будет описано позже.
Впрочем, не все языки нуждаются в подобных ухищрениях. Так, Visual Basic превосходно обходится без предварительного описания подпрограмм, а сами подпрограммы могут располагаться в произвольном порядке.
Итак, технические сложности для реализации косвенной рекурсии нами успешно преодолены. Теперь осталось определиться с другим вопросом, не менее важным: о целесообразности ее применения.
Конечно же, мы не будем довольствоваться голословным утверждением, что косвенная рекурсия важна, а попросту приведем пример задачи, которая легко и изящно решается с ее использованием.
Чтобы наши усилия не пропали впустую, постараемся выбрать такую задачу, которая достаточно проста, чтобы на ее примере можно было учиться, не утопая в премудростях задачи, и в то же время достаточно полезна, чтобы найти практическое применение.

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

Нередко в программы, например, имеющие дело с финансами, встраивается простейший калькулятор, позволяющий на лету произвести несложные расчеты. Еще чаще, к сожалению, такого калькулятора в программе не оказывается. Помнится, не так давно на форуме задавали вопрос о том, где можно взять подобную подпрограмму. Мы попытаемся сделать подобный калькулятор своими руками.
Разумеется, написать простейший калькулятор задача весьма расплывчатая. Поскольку нечетко поставленные задачи настоящий бич программистского племени, мы не будем поддаваться искушению сразу же приступить к кодированию, а сначала более основательно поработаем над заданием.
Итак, мы хотим написать подпрограмму, которая получает на входе арифметическое выражение, вычисляет его значение, если это выражение корректно, и возвращает его значение в вызывающую программу.
Такая постановка уже выглядит конкретнее, но тем не менее еще далека от совершенства. Какое выражение мы считаем арифметическим и корректным? Уточняем дальше.
Прежде всего, очевидно, что наш калькулятор должен работать с числами. Для простоты мы ограничимся действительными числами, состоящими из целой и (необязательной) дробной частей. Если дробная часть присутствует, она отделяется от целой части десятичной точкой. Мы намеренно откажемся от экспоненциального представления чисел в виде мантиссы и порядка, поскольку для простейших расчетов, как правило, такое представление избыточно.
Для того, чтобы приносить реальную пользу, наш калькулятор должен уметь производить операции над числами. Мы реализуем четыре действия арифметики: сложение, вычитание, умножение и деление.
На первый взгляд поставленная задача кажется весьма тривиальной. Арифметическое выражение представляется в виде последовательности чисел, отделенных друг от друга знаками арифметических операций. Достаточно считать первое число, затем знак операции, второе число и можно выполнять операцию над считанными числами. Если за вторым числом следует новая операция, она выполняется над предыдущим результатом и следующим числом, и так далее, пока все выражение не будет подсчитано. Обычный цикл, и без рекурсии можно прекрасно обойтись.
Все было бы просто, если бы не одно но: арифметические операции не равнозначны по приоритету. Принято, что умножение и деление имеют приоритет выше, чем сложение и вычитание, и выполняются в первую очередь. Казалось бы, мелочь, но отравляет жизнь писателей программ-калькуляторов изрядно.
Получается, что, наткнувшись на операцию сложения, мы не можем выполнять ее немедленно, а должны заглянуть вперед на одну операцию. Если следующая операция умножение, мы должны отложить текущую операцию, выполнить следующую за ней, а потом вернуться к текущей. И это еще не все, ведь за умножением может следовать еще одно умножение, которое тоже должно быть выполнено прежде. Конечно, задача не из неразрешимых, бывают и посложнее. Но тем не менее изяществом подобный алгоритм не блещет, и удовольствие от разработки такой программы вряд ли получишь. А ведь получившегося монстрика нужно потом еще и протестировать, ибо подобные запутанные программы нередко таят в себе ошибки.
Некоторые разработчики калькуляторов в таких случаях используют тактику страуса: можно спрятать голову в песок и делать вид, что ее не существует. В этом случае пользователи через некоторое время привыкнут к этому недостатку и будут подстраиваться под него, меняя порядок операндов таким образом, чтобы более приоритетные операции оказались впереди низкоприоритетных. Такой прием проходит не всегда, и тогда в дело идет клочок бумаги в качестве стека для записи промежуточных результатов в случае длинных выражений.
Собственно, именно так и работают большинство из виденных мной бухгалтерских калькуляторов (что не удивляет) и изрядная часть инженерных (что уже может быть неприятным сюрпризом). Помнится, много лет назад купленный мной на первом курсе для обсчета экспериментальных результатов калькулятор Texas Instruments изрядно удивил однокурсников, выдав, что 2+2*2=6. Его коллеги советского производства семейства Электроника-ХХ единодушно сходились во мнении, что истинное значение данного выражения 8. Лишь несколько лет спустя их младшие товарищи усвоили-таки приоритет арифметических операций.
Мы не пойдем по этому пути и будем разрабатывать простую, но тем не менее корректную программу, которая не потребует от пользователя каких-либо ухищрений и вывертов. Это значит, что порядок выполнения операций будет определяться общепринятым приоритетом: сначала умножение/деление, затем сложение/вычитание.
Правда, при этом возникает другая проблема: как быть, если низкоприоритетную операцию потребуется выполнить в первую очередь? Традиционно для изменения порядка операций используются скобки. Так, например, запись:
(2+3)*5


означает, что сложение следует выполнить до умножения, и правильный результат такого выражения 25, а не 17, как предписывает приоритет операций.
Итак, очередное уточнение технического задания: программа-калькулятор принимает выражение, составленное из чисел, арифметических операций и скобок, и вычисляет его значение, руководствуясь следующими правилами:

* Часть выражения, заключенная в скобки, имеет приоритет над остальной частью, находящейся вне скобок, и вычисляется раньше нее.
* Скобки могу быть вложенными, при этом приоритет вложенных скобок выше, чем охватывающих.
* Операции умножения/деления имеют приоритет выше, чем операции сложения/вычитания.
* Операции с равным приоритетом выполняются по порядку, слева направо.



Теперь требования к программе полностью прояснены. Однако возникает странное ощущение: сначала была поставлена довольно простая задача, затем она была уточнена до деталей и вся простота куда-то улетучилась. Обычно бывает наоборот: по мере уточнения задачи программисту становится все яснее, как ее реализовать. Но у нас, похоже, не тот случай. Конечно, велик соблазн последовать примеру разработчиков бухгалтерских калькуляторов и не напрягаться самим, переложив проблему на потребителя. Мы ему, впрочем, не поддадимся, а попробуем взглянуть на проблему с другой стороны.

Тот же калькулятор, вид сбоку

Зачастую взгляд на, казалось бы, сложную проблему с другой стороны может привести к простому и элегантному решению. Не является исключением и наш случай.
Рассмотрим выражение вроде

2 * 4 + 9 / 3 - 4 * 5 / 2


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

* 2 * 4 = 8
* 9 / 3 = 3
* 8 (п.1) + 3 (п.2) = 11
* 4 * 5 = 20
* 20 (п.4) / 2 = 10
* 11 (п.3) 10 (п.5) = 1



Нагляднее порядок вычисления данного выражения можно представить в виде графа:


На этом графе в виде бинарного дерева числа, над которыми выполняются арифметические операции, представлены листовыми вершинами. Они соединяются ребрами с узловыми вершинами, которые помечены знаками арифметических операций. Справа от каждого узла находится число, которое представляет собой порядковый номер выполнения операции при вычислении выражения.
Каждый узел фактически представляет собой подвыражение вида левый-операнд операция правый-операнд. Если обе дочерние вершины графа листовые, то есть операнды числа, значение подвыражения определяется в результате выполнения над ними данной операции. Если же хотя бы одна из дочерних вершин узловая, соответствующий операнд сам является подвыражением, которое должно быть вычислено перед вычислением текущего подвыражения. Значение всего выражения можно вычислить, выполнив операцию, которой помечен корневой узел, над его операндами-подвыражениями.
Не правда ли, уже знакомая картина? Чтобы вычислить выражение, нужно вычислить значения левого и правого поддеревьев, а затем выполнить указанную в корне операцию. В свою очередь, каждое поддерево представляет собой уменьшенное подобие исходного (конкретно меньше исходного на 1 уровень). Идеальная задача для применения рекурсии.
Итак, у нас две новости. Первая хорошая, даже очень: чтобы вычислить выражение, достаточно пройтись по дереву, от корня до листьев, и просчитать каждый узел. Задача весьма тривиальная для тех, кто владеет рекурсией (а мы в ней изрядно поднаторели за два предыдущих урока).
А теперь плохая новость. Дерево это за нас никто строить не собирается, придется заняться этим самостоятельно. Все, что пользователь передает на вход нашей программы, это текстовая строка, представляющая выражение в форме, дружественной пользователю (а именно в точности как в примерах из школьного учебника арифметики). Значит, проблема с правильной расстановкой приоритетов операций никуда не делась, мы ее просто до поры отложили в сторону.
Выходит, наша возня с построением дерева вычисления выражений была впустую? Не совсем. Конечно, непосредственного и немедленного решения поставленной задачи мы не получили. Однако, если посмотреть на разобранное выражение повнимательнее, можно заметить, что в отсутствие скобок умножение и деление тяготеют к нижним уровням дерева, в то время как сложение с вычитанием к верхним, ближе к корню (не забываем, что в математике многое поставлено с ног на голову, и даже деревья в ней растут корнями вверх). Это и понятно, ведь при рекурсивной обработке выражения верхние уровни обсчитываются в последнюю очередь. Отсюда важный вывод, который нам очень пригодится впоследствии. Точнее, этих выводов три, но они очень тесно связаны:

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



Данное представление выражения представляется мне куда более простым и логичным, чем 4 правила вычисления выражений, выведенные нами в предыдущей главе. (Разумеется, при этом не делается различие между сложением и вычитанием; точно так же единой операцией считаются умножение и деление). Остаются невыясненными лишь 2 вопроса:

* Если мы сначала перемножаем сомножители, а потом складываем слагаемые, причем тут рекурсия?
* Что делать, если в выражении встретилось подвыражение в скобках?



Отвечать, пожалуй, лучше начну со второго вопроса. Как мы уже выяснили на примере с построением дерева разбора выражения, подвыражение ничем в сущности не отличается от выражения (разве что проще). Поэтому немного подправим третий вывод о структуре выражения:
3'. Сомножитель представляет собой число либо выражение, заключенное в скобки.
Это небольшое с виду дополнение позволяет нам охватить все возможные варианты построения арифметического выражения из чисел, четырех операций арифметики и круглых скобок, позволяющих группировать подвыражения.
Теперь и ответ на первый вопрос становится очевиден. Мы определи выражение через слагаемое, слагаемое через сомножитель, а сомножитель, в свою очередь, через выражение. Круг замкнулся, и теперь мы знаем, что имя ему взаимная рекурсия.
К сожалению, задача все еще не прояснилась настолько, чтобы стал очевиден путь ее решения, хоть мы и полагаем уже, что лежит он через применение взаимной рекурсии. Перед тем, как двигаться дальше, мы должны вновь изменить точку зрения на задачу и посмотреть на нее под другим углом, на этот раз с точки зрения теории формальных языков.

Немного теории

Поставим задачу немного иначе. У нас есть некое выражение, записанное в виде цепочки символов. Мы должны разобрать это выражение и, если оно правильное (смысл этого понятия уточним чуть позже), вычислить его значение.
В такой постановке задача начинает напоминать разработку интерпретатора некоего языка программирования, пусть и несложного. Этот интерпретатор считывает программу, интерпретирует инструкции и, если их синтаксис корректен, выполняет одну за другой, пока программа не окажется выполненной. Тогда правильное выражение такое, которое соответствует синтаксису этого самого языка.
Если мы решаем выбрать такое направление, наша задача разделяется на две, как и при реализации любого другого языка программирования:

* Определить сам язык.
* Разработать его транслятор (в нашем случае интерпретатор).



Если разработка транслятора языка в наше время является уже довольно-таки рутинной задачей, хорошо формализованной и проработанной теоретически, то разработка нетривиального языка задача намного более сложная и творческая. Впрочем, в нашем случае язык очень прост, поэтому муки творчества мы вряд ли успеем испытать. Однако для определения языка по всем правилам все же придется немного потрудиться. Но вначале не обойтись без азов теории формальных языков.

Что такое язык

Рассмотрим множество каких-либо символов, например, кириллический алфавит. Выстраивая их в цепочку один за другим, можно составить слова, а из слов осмысленные предложения русского языка. Любой знающий этот язык способен понять смысл фразы.
Однако далеко не каждое сочетание букв дает русское слово. Если комбинировать буквы хаотически, вероятность его получения не столь велика. Точно так же далеко не каждое сочетание слов дает синтаксически правильное предложение. (В данный момент мы не вдаемся в смысл, который несет это предложение, нас интересует лишь то, насколько формально правильным оно является; семантика отдельный вопрос, которого мы касаться не будем).
Разумеется, в данный момент нас не интересует морфология живых языков, используемых людьми для общения; мы будем рассматривать исключительно формальные языки, в которых предложения строятся по относительно немногочисленным, четко определенным правилам.
Итак, для того, чтобы изъясняться на каком-либо языке, мы должны в первую очередь освоить его алфавит, то есть множество символов, из которых строятся фразы. Эти символы атомарны, то есть не могут быть разделены на какие-либо составные части; например, черточки, составляющие букву А, по отдельности никакого смысла не несут.
Но знание одного алфавита явно недостаточно, поскольку большинство цепочек символов бессмысленно с точки зрения языка. Правила, по которым строятся предложения языка из символов, называются грамматикой.
Итак, язык это подмножество цепочек символов, принадлежащих его алфавиту, или предложений. Предложение принадлежит языку, если оно удовлетворяет правилам грамматики.
Таким образом, чтобы определить свой собственный язык, мы должны определить его алфавит и грамматику. Определить алфавит несложно: достаточно всего лишь перечислить все допустимые символы языка. С грамматикой сложнее: словесное описание нетривиальных грамматических правил может получиться громоздким и невразумительным, поскольку наш человеческий язык плохо приспособлен для подобной задачи.
К счастью, в теории формальных языков имеется строгий и изящный формализм для описания грамматики.

Грамматика

Определение формальной грамматики включает в себя 4 основные части:
G(Vn, Vt, P, S)
Здесь:
G - грамматика;
Vn - множество нетерминальных символов;
Vt - множество терминальных символов;
P - множество правил продукции;
S - начальный символ.
Проясним смысл каждого из этих понятий.
Терминальный символ - это по сути синоним атомарного, то есть символ, который входит в алфавит языка и не подлежит дальнейшему разложению на составные части. Не следует путать символ в понимании формальной грамматики с тем смыслом, который обычно вкладывается в него программистами: это не обязательно литера. Например, ключевое слово begin языка программирования Pascal - это тоже символ, причем терминальный, неделимый на отдельные литеры.
Нетерминальный символ - это вспомогательное понятие, он вводится исключительно для описания неких категорий языка, которые в результате преобразований превращаются в цепочки терминальных. В предложениях языка терминальные символы не встречаются.
Правило продукции - это правило вида N->X, где N - нетерминальный символ, X - последовательность терминальных и нетерминальных символов. (Вообще говоря, есть более общее представление правил продукции, но в данном случае мы будем иметь дело исключительно с контекстно-свободными грамматиками, поэтому такое упрощение вполне допустимо; вдаваться в тонкости классификаций грамматик мы в этой статье не будем, просто примите это примечание к сведению).
Начальный символ - один из нетерминальных символов, который особым образом выделен из всего множества. Именно с него начинается построение предложения данного языка.

Нормальная Форма Бэкуса

Для описания синтаксиса формальных языков (а фактически - правил продукции) великим ученым, внесшим огромный вклад в развитие информатики, Джоном Бэкусом был разработан специальный метаязык, который в его честь был назван Нормальной Формой Бэкуса (БНФ, Backus Normal Form, BNF). Этот метаязык довольно прост. Он содержит небольшое число метасимволов - "<", ">", "|", "::=". (К сожалению, в те времена про WWW еще и слыхом не слыхивали, поэтому Бэкус и не предполагал, какие проблемы вызовет публикация описаний формальных языков посредством HTML, который считает угловые скобки своей собственностью).
Метасимвол "::=" означает "есть по определению". Он отделяет нетерминальный символ (или короче - нетерминал) от его определения.
Угловые скобки заключают в себя нетерминал. Если вы видите конструкцию вида <nonterm>, это значит, что символ nonterm является нетерминалом, и вы наверняка найдете его где-то в левой части одного из правил продукции.
Метасимвол "|" разделяет альтернативные варианты определения нетерминала. Например, определение вида:
<знак-числа> ::= + | -
означает, что в любом месте, где встречается нетерминал "знак-числа", его можно заменить либо плюсом, либо минусом.
Попробуем воспользоваться БНФ и определить с ее помощью какую-нибудь несложную синтаксическую категорию. Например, нам для нашего интерпретатора потребуется работа с действительными числами. Итак:
<number> ::= <unsigned-number> | <sign> <unsigned-number>
Эта конструкция означает, что число может либо не иметь знака вовсе (быть беззнаковым), либо состоять из знака, за которым следует беззнаковое число.
Определить категорию знака числа совсем несложно:
<sign> ::= + | -
Категория "беззнаковое число" посложнее:
<unsigned-number> ::= <int-part> | <int-part> . <fract-part>
Мы определили, что беззнаковое число состоит либо из одной только целой части, либо из целой части, за которой следуют точка и дробная часть. Разумеется, от такого определения немного толку, если не определены нетерминалы, которые мы использовали в его правой части. Продолжаем:
<int-part> ::= <digits>
<fract-part> ::= <digits>
И целую, и дробную часть мы определили как последовательности цифр:
<digits> ::= <digit> | <digit> <digits>
На последнее определение стоит обратить внимание. Если сформулировать его неформальным языком, оно звучит следующим образом: "Последовательность цифр - это либо цифра, либо цифра, за которой следует последовательность цифр". Как видим, и здесь без рекурсии не обошлось...
И напоследок определим, что есть цифра:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Очевидно, что под определение <number> попадают целые и действительные числа, со знаком и без такового, у которых целая часть и дробная (если она есть) содержат как минимум по одной цифре.
Аналогичным образом можно описать практически любую конструкцию формального языка. Правда, описание это лаконичным не назовешь. Если уж такая несложная категория, как действительное число, потребовала 7 определений, то достаточно сложная конструкция может оказаться куда более громоздкой. Однако ради строгости и непротиворечивости БНФ с этим недостатком можно смириться.

Расширенная Форма Бэкуса-Наура

Когда БНФ была применена в знаменитом (можно сказать, судьбоносном для информатики) проекте разработки языка Algol-60 (который для программистов является тем же, что и латынь для медиков), руководитель проекта Питер Наур решил избежать громоздкости, дополнив и расширив нотацию новыми элементами. Новая нотация получила название Расширенной Формы Бэкуса-Наура (РБНФ).
Строго говоря, в литературе встречается несколько сходных нотаций, и каждая из них именуется РБНФ. Видимо, нотация окончательно сформировалась не сразу, и промежуточные формы продолжают сосуществовать.
Изменение нотации коснулось следующих аспектов:

* Исчезли метасимволы в виде угловых скобок, теперь нетерминалы выделяются курсивом (за что Науру огромное человеческое спасибо от всех, кто публикует статьи в HTML).
* Добавлены метасимволы в виде квадратных скобок "[" и "]". Элементы, заключенные в квадратные скобки, являются необязатель;ными, т.е. могут быть пропущены.
* Добавлены метасимволы в виде фигурных скобок "{" и "}". Элементы, заключенные в фигурные скобки, могут повторяться произвольное число раз (в том числе ни разу).



Есть варианты РБНФ, в которых метасимвол "::=" заменен простым знаком равенства, но я не считаю эту замену хорошей идеей, поскольку экономия двух литер может привести к путанице, и мы такой вариант использовать не будем.
Разумеется, сами метасимволы также могут встретиться в конструкциях описываемого языка. В этих случаях они берутся в кавычки. Надеюсь, путаницы это не вызовет, тем более что в нашем простейшем примере грамматики они не встретятся.
В заключение следует отметить, что пробелы, разделяющие описания элементов языка, не являются частью конструкций самого языка. Так, в предыдущем примере <digit> <digits> не означает, что цифры в последовательности разделены пробелами.
Итак, посмотрим, что нам дает подобное расширение. Повторим описание той же категории "число" новыми средствами:
number ::= [sign] int-part [.fract-part]
sign ::= + | -
int-part ::= digits
fract-part ::= digits
digits ::= digit {digit}
digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Описание стало явно компактнее и явно проще для чтения.
Конечно, наша обзорная экскурсия в теорию формальных языков была весьма поверхностной. Тем не менее, полученных сведений должно хватить для решения нашей нехитрой задачи.

Синтаксис калькулятора

Сделаем еще одно (на этот раз последнее) уточнение поставленной задачи:
Необходимо разработать интерпретатор арифметических выражений, которые записываются по следующим правилам:

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



Определим входной язык интерпретатора.

Алфавит калькулятора

Алфавит нашего языка незатейлив. Он включает в себя:

* Десятичные цифры "0", "1", "2", "3", "4", "5", "6", "7", "8", "9".
* Разделитель дробной части - десятичную точку ".".
* Знаки арифметических операций - "+", "-", "*", "/".
* Круглые скобки для группировки подвыражений - "(" и ")".



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

Синтаксис калькулятора

Синтаксис можно выразить посредством РБНФ следующим образом:

* expr ::= item { op-add item }
* op-add ::= + | -
* item ::= factor { op-mul factor }
* op-mul ::= * | /
* factor ::= number | ( expr)
* number ::= int-part [ .fract-part ]
* int-part ::= digits
* fract-part ::= digits
* digits ::= digit { digit }
* digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9



Комментарии:

* Выражение представляет собой слагаемое, после которого может быть произвольное количество операций-типа-сложения, за каждой из которых следует слагаемое.
* Операция-типа-сложения может быть сложением либо вычитанием.
* Слагаемое представляет собой сомножитель, после которого может быть произвольное количество операций-типа-умножения, за каждой из которых следует сомножитель.
* Операция-типа-умножения может быть умножением либо делением.
* Сомножитель представляет собой либо число, либо выражение, заключенное в круглые скобки.
* В оставшихся правилах продукции содержится уже хорошо знакомое нам описание категории "число".




Грамматика языка

Теперь в нашем распоряжении есть все 4 части, составляющие полное определение грамматики:

* Терминальные символы перечислены в разделе "Алфавит калькулятора".
* Нетерминальные символы перечислены слева от метасимвола "::=" в разделе "Синтаксис калькулятора".
* Правила продукции перечислены в разделе "Синтаксис калькулятора".
* Начальным символом нашей грамматики является метасимвол "выражение" ("expr").



Мы основательно потрудились, потратив немало сил и времени на детализацию задачи и на ее формальную спецификацию. Собственно, то, чем мы занимались до сих пор, нельзя назвать программированием в общепринятом смысле этого слова. Скорее, это был анализ задачи (пожалуй, чересчур тщательный и детальный для столь скромной задачи, но наша цель сейчас - обучение, а не конечный результат, поэтому подробности здесь не будут лишними).
Однако теперь, приступив к этапу написания самой программы, мы увидим, насколько легко и быстро будет осуществляться кодирование, каким ясным и компактным получится код и, главное, как легко будет при необходимости его модифицировать (например, если возникнет потребность добавить дополнительные функции к нашему калькулятору).
К слову сказать, во многих фирмах, занимающихся промышленным производством софта, само слово программист фактически является синонимом слова кодер и не является ни престижной, ни высокооплачиваемой, поскольку написать код по подробной спецификации - задача немногим сложнее той, что выполняют компиляторы. Зачастую эту работу выполняют люди со средним техническим образованием, и творчества в их труде немногим больше, чем в труде бухгалтера, кропотливо сводящего дебет с кредитом.
Собственно, именно к такой работе мы сейчас и приступим.

Реализация калькулятора

Хотя это и не было упомянуто в нашем кратком обзоре теории формальных языков, здесь уместно было бы упомянуть, что разработанный нами язык относится к 3-му типу по классификации Хомского. Это довольно важно, потому что для синтаксического разбора подобных языков достаточно иметь сканер с предпросмотром на 1 символ вперед. При условии наличия такого сканера разбор предложения языка можно осуществить за один проход без возврата. (Забегая вперед, скажу, что сначала я заготовил впрок именно такой сканер; однако грамматика оказалась столь проста, что даже просмотр на 1 символ вперед оказался избыточным, и я впоследствии удалил эту функцию из интерфейса класса сканера).
Итак, начнем работу с реализации сканера.

Сканер

Итак, наш сканер должен давать нам возможность посимвольно просматривать выражение только вперед, при этом сигнализируя о попытке чтения после конца входной строки. Для выполнения этой задачи создадим заголовочный файл Scanner.h:
Код:
class CScanner
{
private:
const char *m_pCurrent; // буфер для хранения выражения
public:
CScanner(const char *pc);
bool IsEmpty(void) const; // проверка буфера на пустоту
char Current(void) const; // текущий символ буфера
void MoveNext(void); // переход к следующему символу буфера
}; // CScanner
Данный класс включает в себя конструктор, позволяющий при создании сканера привязать его к интерпретируемому выражению, пару функций, позволяющих проверить остаток интерпретируемой строки на пустоту и извлечь текущий символ, и метод, позволяющий продвинуться на один символ вперед.
Реализация класса находится в файле Scanner.cpp. Она столь незатейлива, что вряд ли нуждается в комментариях даже для начинающего программиста:
Код:
#include "Buffer.h"

CScanner::CScanner(const char *pc)
{
m_pCurrent = pc;
}

bool CScanner::IsEmpty(void) const
{
return !(*m_pCurrent);
}

char CScanner::Current(void) const
{
return *m_pCurrent;
}

void CScanner::MoveNext(void)
{
m_pCurrent++;
}
Теперь мы почти готовы к написанию самого интерпретатора. Почти - потому, что нам нужно разобраться еще с одним назойливым, но немаловажным вопросом - обработкой ошибок.

Обработка ошибок

Поскольку практически наверняка пользоваться нашим калькулятором будет конечный пользователь программы, в которую он будет встроен, и поскольку людям свойственно ошибаться, необходимо встроить в наш калькулятор средства для обработки ошибок.
Самое простое решение - это завершать выполнение программы с соответствующей диагностикой. Но такой подход годится лишь для учебной программы, да и то с большой натяжкой. Если наш калькулятор окажется встроен в большой пакет программ для финансовых расчетов и после часа работы программа из-за опечатки при вводе вылетит, выдав на прощание что-то невразумительное вроде неожиданно достигнут конец строки, вряд ли это будет хорошей рекламой нашему софту.
В современных языках программирования есть хорошая альтернатива данному подходу. Если при работе приложения какая-либо подпрограмма обнаруживает ошибку (например, делимое равно нулю), она вызывает исключение. Если вызывающая программа знает, как обрабатывать такую исключительную ситуацию, она перехватывает это исключение и обрабатывает ошибку, например, предлагая пользователю исправить вводимую строку. Если вызывающая программа не собирается обрабатывать исключение, оно передается по стеку вызовов на один уровень выше до тех пор, пока либо на каком-то уровне исключение не будет перехвачено и обработано, либо стек вызовов не будет исчерпан. В последнем случае исполняющая система завершит выполнение программы с соответствующей диагностикой, ибо дальнейшее продолжение работы в такой ситуации бессмысленно.
Такой подход намного конструктивнее. Если наш интерпретатор найдет в выражении символ, недопустимый в данном контексте, будет сгенерировано исключение, которое может быть перехвачено пользовательской программой и обработано.
Для того, чтобы диагностика в случае ошибки была более вразумительной, имеет смысл генерировать не одно исключение на все случаи жизни, а пакет родственных исключений, каждое из которых соответствует определенной проблеме ввода. В этом случае автор программы имеет выбор: ограничиться скупой констатацией факта ошибки или сделать детальную диагностику.
Все исключения калькулятора перечислены в файле Error.h:
Код:
// общая ошибка
class CCalcError
{
public:
CCalcError() {}
~CCalcError() {}
virtual const char * Reason(void) const { return "Calc - Expression calculation error"; }
};

// ожидается конец строки
class CCalcEndOfLineExpErr: public CCalcError
{
private:
char cBadChar;
public:
CCalcEndOfLineExpErr(char c) { cBadChar = c; }
~CCalcEndOfLineExpErr() {}
virtual const char * Reason(void) const { return "Calc - End of line expected"; }
const char BadChar(void) const { return cBadChar; }
};

// ожидается цифра или открывающая круглая скобка
class CCalcDigitOrOpenExpErr: public CCalcError
{
private:
char cBadChar;
public:
CCalcDigitOrOpenExpErr(char c) { cBadChar = c; }
~CCalcDigitOrOpenExpErr() {}
virtual const char * Reason(void) const { return "Calc - Digit or '(' expected"; }
const char BadChar(void) const { return cBadChar; }
};

// ожидается цифра
class CCalcDigitExpErr: public CCalcError
{private:
char cBadChar;
public:
CCalcDigitExpErr(char c) { cBadChar = c; }
~CCalcDigitExpErr() {}
virtual const char * Reason(void) const { return "Calc - Digit expected"; }
const char BadChar(void) const { return cBadChar; }
};

// ожидается открывающая круглая скобка
class CCalcCloseExpErr: public CCalcError
{
private:
char cBadChar;
public:
CCalcCloseExpErr(char c) { cBadChar = c; }
~CCalcCloseExpErr() {}
virtual const char * Reason(void) const { return "Calc - ')' expected"; }
const char BadChar(void) const { return cBadChar; }
};

// буфер строки пуст
class CCalcBufEmptyErr: public CCalcError
{public:
CCalcBufEmptyErr() {}
~CCalcBufEmptyErr() {}
virtual const char * Reason(void) const {return "Calc - Buffer is empty"; }
};

// деление на нуль
class CCalcDivByZeroErr: public CCalcError
{public:
CCalcDivByZeroErr() {}
~CCalcDivByZeroErr() {}
virtual const char * Reason(void) const {return "Calc - Division by zero"; }
};
Обратите внимание, что все классы исключения, кроме CCalcError, являются производными от CCalcError. Это позволяет программе, которая не желает вдаваться в тонкости ошибки, обрабатывать это исключение, общее для всех ошибок. Кроме того, можно поставить перехват этого исключения после перехватчиков всех дочерних ошибок; это может оказаться полезным в случае, если вы забудете перехватить какую-либо из них. Хоть в этом случае вызывающая программа не сможет получить детальную информацию об ошибке, тем не менее аварийного завершения не произойдет.
Все классы исключений имеют виртуальную функцию Reason, которая возвращает текстовое описание причины ошибки. Кроме того, в тех случаях, когда это уместно, исключение возвращает также символ BadChar, который представляет тот самый символ, который оказался причиной данной ошибки.
Теперь, закончив со вспомогательными классами, можно приступать к написанию самого интерпретатора.

Интерпретатор

Интерфейс интерпретатора незатейлив - он представляет собой единственную функцию, которая получает при вызове сканер, в который заряжена строка с исходным выражением. Эта функция возвращает результат типа double, который является результатом вычисления выражения (разумеется, при условии, что выражение корректно, точнее - соответствует описанной нами грамматике; в противном случае возникает одно из исключений, описанных в Error.h).
Содержимое Calc.h:
Код:
/*Программа-калькулятор*/
#include "Scanner.h"

extern double GetValue(CScanner &b); // возвращает значение выражения
Реализация интерпретатора (Calc.cpp):
Код:
#include <ctype.h>
#include "Calc.h"
#include "Error.h"

// вспомогательная функция - преобразование литеры в число
int CharToInt(const char c)
{
// проверяем, является ли литера цифрой
if (!isdigit(c)) // если нет, вызываем исключение
throw CCalcDigitExpErr(c);
// цифра - вычисляем значение
return (c - '0');
} // CharToInt

// обработка числа
double GetNumber(CScanner &b)
{
// проверяем, не пуст ли буфер
if (b.IsEmpty())
throw CCalcBufEmptyErr();
// проверяем, является ли текущая литера цифрой
if (!isdigit(b.Current()))
throw CCalcDigitExpErr(b.Current());
// все в порядке - как и ожидалось, в буфере число
double resultValue = 0.0;
// считываем целую часть числа
while (isdigit(b.Current()))
{
resultValue *= 10.0;
resultValue += CharToInt(b.Current());
b.MoveNext();
} // while
// проверяем наличие необязательной дробной части
if (b.Current() == '.')
{
// пропускаем десятичную точку
b.MoveNext();
// считываем дробную часть
// сначала убедимся, что после точки следует цифра
if (!isdigit(b.Current()))
throw CCalcDigitExpErr(b.Current());
double step = 1.0;
while (isdigit(b.Current()))
{
step /= 10.0;
resultValue += step * CharToInt(b.Current());
b.MoveNext();
} // while
} // if
// возвращаем значение считанного числа
return resultValue;
} // GetNumber

/*
А теперь приступаем к первой функции, задействованной
в цепочке взаимной рекурсии.
Поскольку сомножитель может быть выражением, а функция разбора
выражения будет описана позже, в этом месте необходимо включить
предварительное описание функции GetExpr (без реализации), чтобы избежать
ошибки обращения к неопределенной функции при компиляции программы.
*/
double GetExpr(CScanner &b);
{
// обработка сомножителя
double GetFactor(CScanner &b)
{
// сомножитель может быть числом,
if (isdigit(b.Current())) // в этом случае его значение = значению этого числа,
return GetNumber(b);
// либо выражением в скобках, в этом случае его следует вычислить
else if (b.Current() == '(')
{
// пропускаем открывающую скобку
b.MoveNext();
// получаем значение выражения
double resultValue = GetExpr(b);
// проверяем наличие закрывающей скобки
if (b.Current() != ')')
throw CCalcCloseExpErr(b.Current());
// пропускаем закрывающую скобку
b.MoveNext();
// возвращаем значение сомножителя
return resultValue;
} // else if
else // текущий символ - не число и не открывающая скобка
throw CCalcDigitOrOpenExpErr(b.Current());
} // GetFactor

// обработка слагаемого
double GetItem(CScanner &b)
{
// получаем первый сомножитель
double resultValue = GetFactor(b);

// проверяем, следует ли за ним операция типа умножения
while ((b.Current() == '*') || (b.Current() == '/'))
{
// сохраняем литеру операции
char mulOp = b.Current();
b.MoveNext();
// получаем следующий сомножитель
double secondOp = GetFactor(b);
// выполняем операцию типа умножения
if (mulOp == '*')
resultValue *= secondOp;
else if (mulOp == '/')
{
// если операция - деление, следует проверить,
// не равен ли нулю второй операнд
if (secondOp == 0.0)
throw CCalcDivByZeroErr();
// все в порядке - можно делить
resultValue /= secondOp;
} // else if
} // while
return resultValue;
} // GetItem

// обработка выражения
double GetExpr(CScanner &b)
{
// получить первое слагаемое
double resultValue = GetItem(b);
// проверяем, следует ли за ним операция типа сложения
while ((b.Current() == '+') || (b.Current() == '-'))
{
// сохраняем литеру операции
char addOp = b.Current();
b.MoveNext();
// получаем следующее слагаемое
double secondOp = GetItem(b);
// выполняем операцию типа сложения
if (addOp == '+')
resultValue += secondOp;
else if (addOp == '-')
resultValue -= secondOp;
} // while
return resultValue;
} // GetExpr

// единственная функция интерпретатора, видимая вызывающей программе
double GetValue(CScanner &b)
{
// вычисляем выражение, находящееся в сканере
double resultValue = GetExpr(b);
// если по завершении работы сканер не пуст,
// значит, в конце выражения что-то неладно
if (!b.IsEmpty())
throw CCalcEndOfLineExpErr(b.Current());
// все в порядке - нормальное завершение, возвращаем значение выражения
return resultValue;
} // GetValue
Полагаю, что при таком обилии комментариев вопросов по алгоритму работы интерпретаторов возникнуть не должно, поэтому на этом раздел заканчиваю.

Основная программа

Ну и в завершение всего, чтобы испытать новоиспеченный калькулятор в работе, дополним наш проект основной программой, которая позволит вводить строки из стандартного ввода, правильные и не очень, и посмотреть реакцию нашего интерпретатора на них:
Код:
// Cross.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include "Calc.h"
#include "Error.h"

int main(int argc, char* argv[])
{
char buff[80]; // буфер для хранения ввода пользователя
for (;;)
{
printf("Input string:\n");
scanf("%s", buff);
CScanner Buffer(buff);
try
{
// вычислить значение введенного выражения
double resultValue = GetValue(Buffer);
printf("Result is: %10.5f\n", resultValue);
} // try
// обработка ошибок
catch (CCalcEndOfLineExpErr E)
{
printf("ERROR! %s; found: %c\n", E.Reason(), E.BadChar());
} // catch
catch (CCalcDigitOrOpenExpErr E)
{
printf("ERROR! %s; found: %c\n", E.Reason(), E.BadChar());
} // catch
catch (CCalcDigitExpErr E)
{
printf("ERROR! %s; found: %c\n", E.Reason(), E.BadChar());
} // catch
catch (CCalcCloseExpErr E)
{
printf("ERROR! %s; found: %c\n", E.Reason(), E.BadChar());
} // catch
catch (CCalcBufEmptyErr E)
{
printf("ERROR! %s\n", E.Reason());
} // catch
catch (CCalcDivByZeroErr E)
{
printf("ERROR! %s\n", E.Reason());
} // catch
catch (CCalcError E)
{
printf("ERROR! %s\n", E.Reason());
} // catch
} // for
return 0;
} // main

Заключение

Попытка привести сколько-нибудь применимый на практике пример заставила меня помимо собственно косвенной рекурсии упомянуть вскользь еще целый ряд не менее любопытных тем: теорию формальных языков, нотации БНФ и РБНФ, построение транслятора языка, заданного посредством грамматики... Разумеется, в небольшой статье, к тому же посвященной другой теме, обо всем этом можно лишь упомянуть, не более того. Если у вас после прочтения данной статьи возникло желание более серьезно познакомиться с этими вопросами, пишите, ваше мнение я обязательно учту при выборе тематики будущих статей.
Все примеры, приведенные в статье, были разработаны и оттестированы в среде Visual C++ V6.0. Однако в них нет никакой привязки именно к этой версии, поэтому ожидается, что они будут работоспособны в любой среде программирования на C++. Кроме того, очевидно, что приведенный код без особых усилий может быть преобразован в программу на языках Pascal, Visual Basic, C# и др. Главное здесь - сама идея построения программы на базе взаимной рекурсии, позволяющая с легкостью построить гибкую программу для интерпретации входных данных, описанных средствами формальной грамматики.
Разумеется, программа не была доведена до совершенства, поскольку это всего лишь иллюстрация метода, а не самоцель. Например, в представлении числа не предусмотрен знак. Сканер можно было бы снабдить счетчиком символов, чтобы в сообщении об ошибке можно было точно указать место ее возникновения. Да и саму функцию интерпретатора можно было бы сделать членом класса сканера, поскольку объектные языки не позволяют вводить "свободные" функции, не принадлежащие классу.
То же самое относится и к терминологии, которая не была особенно строгой. Так, например, порой термин "символ" употреблялся как в своем значении из теории формальных языков, так и в более привычном для программистов значении в качестве синонима слова "литера". Надеюсь, эти вольности не вызовут у читателя путаницы, поскольку из контекста всегда понятно, какое значение термина имелось в виду.
Все усовершенствования программы вы можете выполнить в качестве самостоятельного упражнения, а я на теме косвенной рекурсии ставлю точку. Как всегда, жду ваших вопросов, замечаний, предложений и т.д. в своем разделе форума.
В очередной раз возьму на себя грех и не приведу список литературы, поскольку никакой литературой при подготовке статьи не пользовался. Если кто-то из читателей все же изъявит желание самостоятельно поглубже ознакомиться с какой-либо из затронутых тем, обращайтесь, попробую помочь, чем смогу.

Alf