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

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;                // возвращаем значение Терма

  }

}

Этот программный код действительно — более или менее — работает. Мы включим его в окончательный вариант программы для грамматического разбора правильных выражений и отбраковки неправильных. Он позволяет правильно вычислить большинство выражений. Например, выражение 1+2 считывается как Терм (имеющий значение 1), за которым следует символ +, а за ним — Выражение (которое оказывается Термом, имеющим значение 2). В итоге получаем ответ, равный 3. Аналогично, выражение 1+2+3 дает ответ 6. Можно было бы много говорить о том, что эта программа делает хорошо, но мы сразу поставим вопрос ребром: а чему равно выражение 1–2–3? Функция expression() считает число 1 как Терм, затем переходит к считыванию 2–3 как Выражения (состоящего их Терма 2, за которым следует Выражение 3). Таким образом, из 1 будет вычтено значение выражения 2–3. Иначе говоря, программа вычисляет выражение 1–(2–3). Оно равно 2. Однако мы еще со школьной скамьи знаем, что выражение 1–2–3 означает (1–2)–3 и, следовательно, равно –4.

Что же мы сделали неправильно с точки зрения программирования? Этот вопрос следует задавать себе каждый раз, когда обнаружите ошибку. Именно так мы можем избежать повторения одних и тех же ошибок. По существу, мы просто просмотрели программный код и угадали правильное решение. Это редко срабатывает! Мы должны понять, как работает программа, и объяснить, почему она работает правильно.

Анализ ошибок — часто лучший способ найти правильное решение. В данном случае функция expression() сначала искала Терм, а затем, если за Термом следовал символ + или –, искала Выражение. На самом деле функция реализовала немного другую грамматику.

Выражение:

  Терм

  Терм '+' Выражение // сложение

  Терм '–' Выражение // вычитание

Отличие от нашей грамматики заключается именно в том, что выражение 1–2–3 должно трактоваться как Выражение 1–2, за которым следует символ – и Терм 3, а на самом деле функция интерпретирует выражение 1–2–3 как Терм 1, за которым следует символ – и Выражение 2–3. Иначе говоря, мы хотели, чтобы выражение 1–2–3 было эквивалентно (1–2)–3 , а не 1–(2–3).

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

Обратите внимание на то, что мы могли бы определить выражение 1–2–3 как 1–(2–3), а не (1–2)–3 и вообще избежать этой дискуссии. Довольно часто самые трудные программистские проблемы возникают тогда, когда мы работаем с привычными для людей правилами, которые изобрели задолго до компьютеров.

6.5.2.3. Выражения: третья попытка (удачная)

Итак, что теперь? Еще раз взгляните на грамматику (правильная грамматика приведена в разделе 6.5.2): любое Выражение начинается с Терма, за которым может следовать символ + или –. Следовательно, мы должны найти Терм, проверить, следует ли за ним символ + или –, и делать это, пока символы “плюс” и “минус” не закончатся. Рассмотрим пример.

double expression()

{

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

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

  while (t.kind=='+' || t.kind=='–') { // ищем + или –

    if (t.kind == '+')

      left += term();       // вычисляем Терм и добавляем его

    else

      left –= term();       // вычисляем Терм и вычитаем его

    t = get_token();

  }

  return left;              // финал: символов + и – нет; возвращаем ответ

}