Программирование. Принципы и практика использования C++ Исправленное издание

double primary    // реализует числа и скобки

6.5.2. Выражения

Сначала напишем функцию expression. Грамматическое правило Выражение выглядит следующим образом:

Выражение:

  Терм

  Выражение '+' Терм

  Выражение '–' Терм

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

6.5.2.1. Выражения: первая попытка

Посмотрев на правило Выражение '+' Терм, сначала попытаемся вызвать функцию expression, поищем операцию + (и –), а затем вызовем функцию term.

double expression

{

  double left = expression;  // считываем и вычисляем Выражение

  Token t = get_token;       // получаем следующую лексему

  switch (t.kind) {            // определяем вид лексемы

  case '+':

    return left + term;      // считываем и вычисляем Терм,

                               // затем выполняем сложение

  case '–':

    return left – term;      // считываем и вычисляем Терм,

                               // затем выполняем вычитание

  default:

    return left;               // возвращаем значение Выражения

  }

}

Программа выглядит неплохо. Это почти тривиальная транскрипция грамматики. Она довольно проста: сначала считываем Выражение, а затем проверяем, следует ли за ним символ + или –, и в случае положительного ответа считываем Терм.

К сожалению, на самом деле этот программный код содержит мало смысла. Как узнать, где кончается выражение, чтобы искать символ + или –? Напомним, что наша программа считывает символы слева направо и не может заглянуть вперед, чтобы узнать, нет ли там символа +. Фактически данный вариант функции expression никогда не продвинется дальше своей первой строки: функция expression начинает работу с вызова функции expression, которая, в свою очередь, начинается с вызова функции expression, и так до бесконечности. Этот процесс называется бесконечной рекурсией, но на самом деле он довольно быстро заканчивается, исчерпав память компьютера. Термин рекурсия используется для описания процесса, который выполняется, когда функция вызывает саму себя. Не любая рекурсия является бесконечной; рекурсия является очень полезным методом программирования (см. раздел 8.5.8).

6.5.2.2. Выражения: вторая попытка

Итак, что же мы делаем? Каждый Терм является Выражением, но не любое Выражение является Термом; иначе говоря, можно начать поиск с Терма и переходить к поиску полного Выражения, только обнаружив символ + или –. Рассмотрим пример.

double expression

{

  double left = Term;        // считываем и вычисляем Терм

  Token t = get_token;       // получаем следующую лексему

  switch (t.kind) {            // определяем вид лексемы

  case '+':

    return left + expression; // считываем и вычисляем

                                // Выражение, затем

                                // выполняем сложение

  case '–':

    return left – expression; // считываем и вычисляем

                                // Выражение, затем

                                // выполняем вычитание

  default:

    return left;                // возвращаем значение Терма

  }

}