Программирование — страница 22 из 57

“Программирование — это понимание”.

Кристен Нюгорд (Kristen Nygaard)

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

6.1. Задача

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

• Иллюстрирует методы проектирования и программирования.

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

• Не требует слишком большого количества новых языковых конструкций.

• Достаточно сложная и требует размышлений над ее проектированием.

• Допускает много вариантов решения.

• Решает понятную задачу.

• Решает задачу, которая заслуживает решения.

• Имеет решение, которое достаточно невелико, чтобы его можно было просто и ясно описать и понять.

Мы выбрали следующую задачу: “Поручить компьютеру выполнить простые арифметические операции, введенные пользователем”. Иначе говоря, мы хотим создать простой калькулятор. Совершенно очевидно, что такие программы полезны; каждый настольный компьютер поставляется с такой программой, и вы можете даже купить карманный калькулятор, который выполняет только такие программы.

Например, если вы введете строку

2+3.1*4

то программа должна ответить

14.4

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

6.2. Размышления над задачей

С чего начать? Просто немного подумайте о задаче и о том, как ее можно решить. Сначала поразмышляйте о том, что должна делать программа и как вы хотели бы с ней взаимодействовать. Затем подумайте о том, как написать такую программу. Попытайтесь написать краткое изложение идеи, лежащей в основе решения, и найдите изъяны в своей первой идее. По возможности обсудите задачу и способы ее решения со своими друзьями. Объяснение идеи своим друзьям удивительным образом позволяет понять ее недостатки и способы ее создания; бумага (или компьютер) не разговаривает с вами и обычно не соответствует вашим предположениям. В принципе проектирование — это коллективная деятельность.

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

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

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

6.2.1. Стадии разработки программы

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

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

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

• Реализация. Записываем код, отлаживаем его и тестируем, для того чтобы убедиться, что программа делает то, что нужно.

6.2.2. Стратегия

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

• Какая задача должна быть решена? Для того чтобы ответить на этот вопрос, необходимо прежде всего попытаться уточнить, что вы пытаетесь сделать. Как правило, для этого формулируют описание задачи, т.е. пытаются понять, в чем заключается ее суть. На этом этапе вы должны встать на точку зрения пользователя (а не программиста); иначе говоря, должны задавать вопросы о том, что должна делать программа, а не о том, как она будет это делать. Спросите: “Что эта программа может сделать для меня?” и “Как бы я хотел взаимодействовать с этой программой?” Помните, большинство из нас являются опытными пользователями компьютеров.

• Ясна ли постановка задачи? Для реальных задач на этот вопрос никогда нельзя ответить положительно. Даже студенческое упражнение бывает трудно сформулировать достаточно точно и конкретно. Поэтому попытайтесь уточнить постановку задачи. Было бы обидно решить неправильно поставленную задачу. Другая ловушка состоит в том, что вы можете поставить слишком много вопросов. Пытаясь понять, что вы хотите, легко увлечься и стать претенциозным. Почти всегда лучше задавать поменьше вопросов, чтобы программу было легче описать, понять, использовать и (возможно) реализовать. Убедившись, что этот подход работает, можно создать более изощренную “версию 2.0”, основанную на вашем опыте.

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

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

• Знаете ли вы, какие инструменты, библиотеки и тому подобные ресурсы вам могут понадобиться? Ответ почти всегда положительный. Даже на самых ранних этапах изучения языка программирования в вашем распоряжении есть небольшие фрагменты стандартной библиотеки С++. Позднее вы узнаете больше об этой библиотеке и способах ее эффективного использования. Вам понадобятся графика и библиотеки графического интерфейса пользователя, а также библиотеки для работы с матрицами и т.п. Получив небольшой опыт, вы сможете найти тысячи таких библиотек в веб. Помните: не стоит изобретать колесо, разрабатывая программное обеспечение для решения реальных задач. Однако при обучении программированию все обстоит в точности наоборот: ученик должен заново изобрести колесо, чтобы увидеть, как оно действует. Время, которое вы сэкономите, используя хорошую библиотеку, можно посвятить разработке других частей программы или отдыху. Как понять, что та или иная библиотека подходит для решения вашей задачи и имеет достаточно высокое качество? Это трудная проблема. Можно поспрашивать у коллег, в дискуссионных группах по интересам или попытаться поэкспериментировать с библиотекой на небольших примерах, прежде чем подключать ее к вашему проекту.

• Проанализируйте части решения, которые описаны отдельно (и, возможно, используются в разных местах программы или даже в других программах). Для этого требуется опыт, поэтому в данной книге мы приводим много примеров. Мы уже использовали векторы (класс vector), строки (класс string), а также потоки ввода и вывода (cin и cout). Эта глава содержит первые завершенные примеры проектирования, реализации и использования программы, содержащей типы, определенные пользователем (Token и Token_stream). В главах 8 и 13–15 представлено много других примеров вместе с принципами их проектирования. Пока рассмотрим аналогию: если бы вы конструировали автомобиль, то начали бы с идентификации его составных частей, например колес, двигателя, сидений, дверных ручек и т.д. Современный автомобиль состоит из десятков тысяч таких компонентов. Реальная программа в этом отношении не отличается от автомобиля за исключением того, что состоит из фрагментов кода. Мы же не пытаемся создавать автомобили непосредственно из исходного сырья, т.е. из стали, пластика и дерева. Поэтому и программы не следует конструировать непосредственно из выражений, инструкций и типов, предусмотренных в языке. Проектирование и реализация составных компонентов является основной темой нашей книги и проектирования программного обеспечения вообще (пользовательские типы описаны в главе 9, иерархии классов — в главе 14, а обобщенные типы — в главе 20).

• Создавайте небольшие и ограниченные версии программы, решающие ключевые части вашей задачи. Начиная работу, мы редко хорошо понимаем задачу. Мы часто так думаем (разве мы не знаем, что такое калькулятор), но на самом деле это не так. Только сочетание размышлений над задачей (анализ) и экспериментирования (проектирование и реализация) дает нам солидное понимание того, что требуется для создания хорошей программы. Итак, пишите небольшие и ограниченные версии, чтобы достичь следующих целей.

• Выявить свое понимание идеи и требуемые инструменты.

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

 Иногда такая ограниченная первоначальная версия называется прототипом (prototype). Если первая версия не работает или работает очень плохо (что вполне вероятно), отбросьте ее и создайте другую. Повторяйте этот процесс до тех пор, пока не достигнете желаемого. Не барахтайтесь в путанице; со временем она будет лишь возрастать.

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

6.3. Назад к калькулятору!

Как мы хотим взаимодействовать с калькулятором? Это просто: мы знаем, как использовать потоки cin и cout, но графические пользовательские интерфейсы (GUI) будут рассмотрены лишь в главе 16, поэтому остановимся на клавиатуре и консольном окне. Введя выражение с помощью клавиатуры, мы вычисляем его и выводим результат на экран. Рассмотрим пример.

Выражение: 2+2
Результат: 4
Выражение: 2+2*3
Результат: 8
Выражение: 2+3–25/5
Результат: 0

Эти выражения, т.е. 2+2 и 2+2*3, должны быть введены пользователем; все остальное сделает программа. Для приглашения к вводу мы используем слово “Выражение: ”. Мы могли бы выбрать фразу “Пожалуйста, введите выражение и символ перехода на новую строку”, но этот вариант выглядит слишком многословным и бессмысленным. С другой стороны, такие короткие приглашения, как >, выглядят чересчур загадочно. Анализировать такие варианты использования на ранней стадии проектирования программы весьма важно. Это позволяет сформулировать очень практичное определение того, что программа должна делать как минимум.

Обсуждая проектирование и анализ, мы будем называть такие примеры прецедентами использования (use cases). Впервые сталкиваясь с разработкой калькулятора, большинство людей сразу приходят к следующей логике программы:

read_a_line
calculate // выполните работу
write_result

Этот набросок, конечно, не программа; он называется псевдокодом (pseudo code). Псевдокоды обычно используются на ранних этапах проектирования, когда еще не совсем ясно, какой смысл мы вкладываем в обозначения. Например, является ли слово “calculate” вызовом функции? Если да, то каковы его аргументы? Для ответа на этот вопрос просто еще не настало время.

6.3.1. Первое приближение

На этом этапе мы действительно еще не готовы написать программу, имитирующую функции калькулятора. Мы просто мало думали об этом, но размышления — трудная работа, а, как большинство программистов, мы стремимся сразу писать какой-то код. Итак, попробуем написать простую программу-калькулятор и посмотрим, к чему это приведет. Первое приближение может выглядеть примерно так:

#include "std_lib_facilities.h"
int main()
{
  cout << "Пожалуйста, введите выражение (допускаются + и –): ";
  int lval = 0;
  int rval;
  char op;
  int res;
  cin>>lval>>op>>rval; // считываем что-то вроде 1 + 3
  if (op=='+')
    res = lval + rval; // сложение
  else if (op=='–')
    res = lval – rval; // вычитание
  cout << "Результат: " << res << '\n';
  keep_window_open();
  return 0;
}

Иначе говоря, программа считывает пару значений, разделенных оператором, например 2+2, вычисляет результат (в данном случае 4) и выводит его на печать. Здесь переменная, стоящая слева от оператора, обозначена как lval, а переменная, стоящая справа от оператора, — как rval.

Эта программа работает! Ну и что, если программа довольно простая? Очень хорошо получить что-то работающее! Возможно, программирование и компьютерные науки проще, чем о них говорят. Может быть, но не стоит слишком увлекаться ранним успехом. Давайте сделаем кое-что.

1. Несколько упростим код.

2. Добавим операции умножения и деления (например, 2*3).

3. Добавим возможность выполнять несколько операторов (например, 1+2+3).

В частности, известно, что корректность входной информации следует проверять (в нашем варианте мы “забыли” это сделать) и что сравнивать значения с несколькими константами лучше всего с помощью инструкции switch, а не if.

Цепочку операций, например 1+2+3+4, будем выполнять по мере считывания значений; иначе говоря, начнем с 1, потом увидим +2 и добавим 2 к 1 (получим промежуточный результат, равный 3), увидим +3 и добавим 3 к промежуточному результату, равному 3, и т.д.

После нескольких неудачных попыток и исправления синтаксических и логических ошибок получим следующий код:

#include "std_lib_facilities.h"
int main()
{
  cout <<
<< "Пожалуйста, введите выражение (допускаются +, –, * и /): ";
  int lval = 0;
  int rval;
  char op;
  cin>>lval; // считываем самый левый операнд
  if (!cin) error("нет первого операнда");
  while (cin>>op) { // считываем оператор и правый операнд в цикле
    cin>>rval;
    if (!cin) error("нет второго операнда ");
    switch(op) {
    case '+':
      lval += rval; // сложение: lval = lval + rval
      break;
    case '–':
      lval –= rval; // вычитание: lval = lval – rval
      break;
    case '*':
      lval *= rval; // умножение: lval = lval * rval
      break;
    case '/':
      lval /= rval; // деление: lval = lval / rval
      break;
    default: // нет другого оператора: выводим результат
      cout << "Результат: " << lval << '\n';
      keep_window_open();
      return 0;
    }
  }
  error("неверное выражение");
}

Это неплохо, но попытайтесь вычислить выражение 1+2*3, и вы увидите, что результат равен 9, а не 7, как утверждают учителя математики. Аналогично, 1–2*3 равно –3, а не –5, как мы думали. Мы выполняем операции в неправильном порядке: 1+2*3 вычисляется как (1+2)*3, а не 1+(2*3), как обычно. Аналогично, 1–2*3 вычисляется как (1–2)*3, а не 1–(2*3), как обычно. Лентяи! Мы можем считать правило, согласно которому умножение выполняется раньше, чем сложение, устаревшим, но не стоит отменять многовековые правила просто для того, чтобы упростить себе программирование. 

6.3.2. Лексемы

Теперь (каким-то образом) мы должны заранее узнать, содержит ли строка символ * (или /). Если да, то мы должны (каким-то образом) скорректировать порядок выполнения вычислений. К сожалению, пытаясь заглянуть вперед, мы сразу же наталкиваемся на многочисленные препятствия.

1. Выражение не обязательно занимает только одну строку. Рассмотрим пример.

1
+
2

Это выражение до сих пор вычислялось без проблем.

2. Как обнаружить символ * (или /) среди цифр и символов +, –, ( и ) в нескольких строках ввода?

3. Как запомнить, в каком месте стоит символ *?

4. Как вычислить выражение, которое не выполняется слева направо (как 1+2*3). Если бы мы были безоглядными оптимистами, то сначала решили бы задачи 1–3, отложив задачу 4 на более позднее время. Кроме того, нам понадобится помощь. Кто-то ведь должен знать, как считать такие вещи, как числа и операторы, из входного потока и сохранить их так, чтобы с ними было удобно работать. Общепринятый и самый полезный ответ на эти вопросы таков: разложите выражение на лексемы, т.е. сначала считайте символы, а затем объедините их в лексемы (tokens). В этом случае после ввода символов

45+11.5/7

программа должна создать список лексем

45
+
11.5
/
7 

Лексема (token) — это последовательность символов, выражающих нечто, что мы считаем отдельной единицей, например число или оператор. Именно так компилятор языка С++ работает с исходным кодом программы. На самом деле разложение на лексемы часто в том или ином виде применяется при анализе текста. Анализируя примеры выражений на языке С++, можно выделить три вида лексем.

• Литералы с плавающей точкой, определенные в языке C++, например 3.14, 0.274e2 и 42.

• Операторы, например +, –, *, /, %.

• Скобки (, ).

Внешний вид литералов с плавающей точкой может создать проблемы: считать число 12 намного легче, чем 12.3е–3, но калькуляторы обычно выполняют вычисления над числами с плавающей точкой. Аналогично, следует ожидать, что скобки в программе, имитирующей вычисления калькулятора, окажутся весьма полезными.

Как представить такие лексемы в нашей программе? Можно попытаться найти начало (и конец) лексемы, но это может привести к путанице (особенно, если позволить выражениям занимать несколько строк). Кроме того, если хранить числа в виде строки символов, то позднее следует идентифицировать это число по его цифрам; например, если мы видим строку 42 и где-то храним символы 4 и 2, то позднее должны выяснить, что эта строка представляет число 42 (т.е. 4*10+2). Общепринятое решение этой задачи — хранить каждую лексему в виде пары (вид, значение).

Вид идентифицирует лексему как число, оператор или скобку. Для чисел (в нашем примере — только для чисел) в качестве значения используется само число.

Итак, как же выразить идею о паре (вид, значение) в программе? Для этого определим тип Token, представляющий лексемы. Почему? Вспомните, почему мы вообще используем типы: они хранят данные, которые нам нужны, и предоставляют возможность выполнять полезные операции над этими данными. Например, тип int позволяет хранить целые числа и выполнять операции сложения, вычитания, умножения и вычисления остатка, в то время как тип string позволяет хранить последовательности символов и выполнять конкатенацию и доступ к символу по индексу. В языке С++ и его стандартной библиотеке определено много типов, например char, int, double, string, vector и ostream, но не тип Token. На самом деле существует огромное количество типов — тысячи и сотни тысяч, — которые мы хотели бы иметь, но которых нет в языке и в стандартной библиотеке.

Среди наших любимых типов, которых нет в библиотеке, — классы Matrix (см. главу 24), Date (см. главу 9) и целые числа с бесконечной точностью (поищите в веб класс Bignum). Если вы еще раз поразмыслите над этим, то поймете, что язык не может поддерживать десятки тысяч типов: кто их определит, кто их реализует, как их найти и какое толстое руководство по использованию языка при этом получится? Как и большинство современных языков программирования, язык С++ решает эту проблему, позволяя программисту при необходимости определять свои собственные типы (типы, определенные пользователем).

6.3.3. Реализация лексем

Как должна выглядеть лексема в нашей программе? Иначе говоря, как должен выглядеть тип Token? Класс Token должен предусматривать выполнение операторов, например + и –, а также представлять числа, такие как 42 и 3.14. В самой простой реализации нужно придумать, как задать вид лексемы и как хранить числа.

Существует много способов реализации этой идеи в программе на языке С++. Вот ее простейший вариант:

class Token { // очень простой тип, определенный пользователем
public:
  char kind;
  double value;
};

Класс Token — это тип (такой же, как int или char), поэтому его можно использовать для определения переменных и хранения значений. Он состоит из двух частей (членов): kind и value. Ключевое слово class означает “тип, определенный пользователем”; это значит, что он содержит члены (хотя в принципе может их и не содержать). Первый член, kind, имеет тип char и представляет собой символ. С его помощью удобно хранить символы '+' и '*', чтобы представить операции * и +. Рассмотрим пример использования этого типа.

Token t;       // t — объект класса Token
t.kind = '+';  // t представляет операцию +
Token t2;      // t2 — другой объект класса Token
t2.kind = '8'; // цифра 8 означает, что "вид" является числом
t2.value = 3.14;

Для доступа к члену класса используется обозначение имя_объекта.имя_члена. Выражение t.kind читается как “член kind объекта t”, а выражение t2.value — как “член value объекта t2”. Объекты класса Token можно копировать так же, как и переменные типа int.

Token tt = t;    // копирование при инициализации
if (tt.kind != t.kind) error("невозможно!");
t = t2;          // присваивание
cout << t.value; // вывод числа 3.14

Имея класс Token, можно выразить выражение (1.5+4)*11 с помощью семи лексем.

Обратите внимание на то, что для простых лексем значение не требуется, поэтому мы не используем член value. Нам нужен символ для обозначения чисел. Мы выбрали символ '8' просто потому, что он явно не оператор и не знак пунктуации. Использование символа '8' для обозначения чисел немного загадочно, но это лишь на первых порах.

Класс Token представляет пример типа, определенного пользователем. Тип, определенный пользователем, может иметь функции-члены (операции), а также данные члены. Существует много причин для определения функций-членов. В данном примере мы описали две функции-члена для того, чтобы инициализация объекта класса Token стала проще.

class Token {
public:
  char kind;     // вид лексемы
  double value;  // для чисел: значение
  Token(char ch) // создает объект класса Token
                 // из переменной типа char
    :kind(ch), value(0) { }
  Token(char ch, double val)   // создает объект класса Token
    :kind(ch), value(val) { }  // из переменных типа
                               // char и double
};

Эти две функции-члена называют конструкторами (constructors). Их имя совпадает с именем типа, и они используются для инициализации (конструирования) объектов класса Token. Рассмотрим пример.

Token t1('+');      // инициализируем t1, так что t1.kind = '+'
Token t2('8',11.5); // инициализируем t2,
                    // так что t2.kind = '8' и t2.value = 11.5

В первом конструкторе фрагмент :kind(ch), value(0) означает “инициализировать член kind значением переменной ch и установить член value равным нулю”. Во втором конструкторе фрагмент :kind(ch), value(val) означает “инициализировать член kind значением переменной ch и установить член value равным переменной val”. В обоих вариантах нам требуется лишь создать объект класса Token, поэтому тело функции ничего не содержит: { }. Специальный синтаксис инициализации (список инициализации членов класса) начинается с двоеточия и используется только в конструкторах.

Обратите внимание на то, что конструктор не возвращает никаких значений, потому что в конструкторе это не предусмотрено. (Подробности изложены в разделах 9.4.2 и 9.7.)

6.3.4. Использование лексем

Итак, похоже, что мы можем завершить нашу программу, имитирующую калькулятор! Однако следует уделить немного времени для планирования. Как использовать класс Token в калькуляторе?

Можно считать входную информацию в вектор объектов Token.

Token get_token(); // считывает объекты класса Token из потока cin
vector tok; // здесь храним объекты класса Token
int main()
{
  while (cin) {
    Token t = get_token();
    tok.push_back(t);
  }
  // ...
}

Теперь можно сначала считать выражение, а вычислить его позднее. Например, для выражения 11*12 получим следующие лексемы:

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

Рассмотрим теперь более сложные выражения. Выражение 1+2*3 состоит из пяти объектов класса Token.

Теперь операцию умножения можно выполнить с помощью простого цикла.

for (int i = 0; i
  if (tok[i].kind=='*') { // мы нашли умножение!
    double d = tok[i–1].value*tok[i+1].value;
    // и что теперь?
  }
}

Да, и что теперь? Что делать с произведением d? Как определить порядок выполнения частичных выражений? Хорошо, символ + предшествует символу *, поэтому мы не можем выполнить операции просто слева направо. Можно попытаться выполнить их справа налево! Этот подход сработает для выражения 1+2*3, но не для выражения 1*2+3. Рассмотрим выражение 1+2*3+4. Это пример “внутренних вычислений”: 1+(2*3)+4. А как обработать скобки? Похоже, мы зашли в тупик. Теперь необходимо вернуться назад, прекратить на время программировать и подумать о том, как считывается и интерпретируется входная строка и как вычисляется арифметическое выражение.

 Первая попытка решить эту задачу (написать программу-калькулятор) оказалась относительно удачной. Это нетипично для первого приближения, которое играет важную роль для понимания задачи. В данном случае это даже позволило нам ввести полезное понятие лексемы, которое представляет собой частный случай широко распространенного понятия пары (имя, значение). Тем не менее всегда следует помнить, что “стихийное” программирование не должно занимать слишком много времени. Необходимо программировать как можно меньше, пока не будет завершен этап анализа (понимание задачи) и проектирования (выявление общей структуры решения).

ПОПРОБУЙТЕ

С другой стороны, почему невозможно найти простое решение этой задачи? Ведь она не выглядит слишком сложной. Такая попытка позволит глубже понять задачу и ее решение. Сразу же определите, что следует сделать. Например, проанализируйте строку 12.5+2. Ее можно разбить на лексемы, понять, что выражение простое, и вычислить ответ. Это может оказаться несколько запутанным, но прямым решением, поэтому, возможно, следовало бы идти в этом направлении! Определите, что следует сделать, если строка содержит операции + и * в выражении 2+3*4? Его также можно вычислить с помощью “грубой силы”. А что делать с более сложным выражением, например 1+2*3/4%5+(6–7*(8))? И как выявлять ошибки, такие как 2+*3 и 2&3? Подумайте об этом, опишите на бумаге возможные решения, используя интересные или типичные арифметические выражения.

6.3.5. Назад к школьной доске!

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

while (not_finished) {
  read_a_line
  calculate // выполняем вычисления
  write_result
}

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

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

1. Если мы введем выражение 45+5/7, то как выделить его отдельные части — 45, +, 5, / и 7? (Выделение лексем!)

2. Как идентифицировать конец ввода выражения? Разумеется, с помощью символа перехода на новую строку! (Слово “разумеется” всегда подозрительно: “разумеется” — это не причина.)

3. Как представить выражение 45+5/7 в виде данных, чтобы потом вычислить его? Прежде чем выполнить сложение, необходимо из цифр 4 и 5 образовать целое число 45 (т.е. вычислить выражение 4*10+5). (Таким образом, выделение лексем — только часть решения.)

4. Как гарантировать, что выражение 45+5/7 вычисляется как 45+(5/7), а не как (45+5)/7?

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

6. Можно ли использовать переменные? Например, можно написать

v=7
m=9
v*m

Хорошая идея, но давайте подождем. Сначала следует понять, как работает программа. Возможно, ответ на шестой вопрос является самым важным. В разделе 7.8 мы увидим, что, ответив “да”, мы практически вдвое увеличим размер программы. Это приведет к удвоенным затратам времени, необходимого для разработки первого приближения. Если вы новичок, то ваши усилия увеличатся даже вчетверо и проект выйдет из-под вашего контроля. Очень важно избегать углубления во всевозможные детали на ранних этапах проекта. Сначала создайте простую версию, реализовав лишь основные функции. Получив работоспособную программу, вы станете более уверенными. Намного проще разрабатывать программу поэтапно, а не сразу всю. Ответив “да” на шестой вопрос, вы столкнетесь с еще одним неприятным эффектом: теперь вам будет сложнее устоять перед соблазном реализовать еще одно “важное свойство”. Как насчет вычисления математических функций? А насчет циклов? Начав накапливать “важные свойства”, трудно остановиться.

С точки зрения программиста вопросы 1, 3 и 4 бессмысленны. Они связаны друг с другом, поскольку, обнаружив число 45 и оператор +, мы должны решить, что с ними делать? Иначе говоря, мы должны решить, как их хранить в программе?

Очевидно, что выделение лексем является частью решения, но только частью.

Как поступает опытный программист? Сложные технические вопросы часто имеют стандартные ответы. Известно, что люди пишут программы-калькуляторы так же давно, как существует ввод символов с клавиатуры, т.е. как минимум пятьдесят лет.

Должен быть стандартный ответ! В такой ситуации опытный программист консультируется с коллегами или изучает научную литературу. Глупо надеяться, что в один прекрасный день вы сможете придумать что-то лучшее, чем то, что было сделано за пятьдесят лет.

6.4. Грамматики

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

45+11.5/7

программа должна создать список лексем

45
+
11.5
/
7

Лексема — это последовательность символов, представляющих собой отдельную единицу языка, например число или оператор.

После создания лексем программа должна обеспечить корректную интерпретацию завершенных выражений. Например, нам известно, что выражение 45+11.5/7 означает 45+(11.5/7), а не (45+11.5)/7, но как объяснить программе, что деление имеет более высокий приоритет, чем сложение? Стандартный ответ — написать грамматику, определяющую синтаксис ввода, а затем программу, реализующую правила этой грамматики. Рассмотрим пример.

// Пример простой грамматики выражений:
Выражение:
  Терм
  Выражение "+" Терм // сложение
  Выражение "–" Терм // вычитание
Терм:
  Первичное выражение
  Терм "*" Первичное выражение // умножение
  Терм "/" Первичное выражение // деление
  Терм "%" Первичное выражение // остаток (деление по модулю)
Первичное выражение:
  Число
  "(" Выражение ")" // группировка
Число:
  литерал_с_плавающей_точкой

Это набор простых правил. Последнее правило читается так: “Число — это литерал с плавающей точкой”. Предыдущее правило утверждает: “Первичное выражение — это Число или скобка, '(', за которой следует Выражение и скобка, ')'”. Правила для Выражения и Терма аналогичны; каждый из них определяется в терминах одного из предыдущих правил.

Как показано в разделе 6.3.2, наши лексемы, позаимствованные из определения языка C++, таковы:

• литерал_с_плавающей_точкой (по правилам языка C++, например, 3.14, 0.274e2 или 42);

• +, –, *, /, % (операторы);

• (, ) (скобки).

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

На первый взгляд грамматика абсолютна бессмысленна. Формальные обозначения всегда выглядят так. Однако следует иметь в виду, что они (как вы скоро убедитесь) весьма элегантны, носят универсальный характер и позволяют формализовать все арифметические вычисления. Вы без проблем можете вычислить выражения 1–2*3, 1+2–3 и 3*2+4/2. Кажется, что эти вычисления “зашиты” в вашем мозге. Однако можете ли вы объяснить, как вы это делаете? Можете ли вы объяснить это достаточно хорошо кому-нибудь, кто таких вычислений никогда не делал? Можете ли вы сделать это для любого сочетания операторов и операндов? Для того чтобы достаточно точно и подробно объяснить все это компьютеру, необходимы обозначения, и грамматика является наиболее мощным и удобным инструментом.

Как читать грамматику? Получив некое входное выражение, мы ищем среди правил совпадения для считанной лексемы, начиная с первого правила Выражение. Считывание потока лексем в соответствии с грамматикой называется синтаксическим разбором (parsing), а программа, выполняющая эту работу, называется синтаксическим анализатором (parser, или syntax analyser). Синтаксический анализатор считывает лексемы слева направо, точно так же, как мы печатаем, а затем читаем слова. Рассмотрим простой пример: 2 — это выражение?

1. Выражение должно быть Термом или заканчиваться Термом. Этот Терм должен быть Первичным выражением или заканчиваться Первичным выражением. Это Первичное выражение должно начинаться с открывающей скобки, (, или быть Числом. Очевидно, что 2 — не открывающая скобка, (, а литерал_с_плавающей_точкой, т.е. Число, которое является Первичным выражением.

2. Этому Первичному выражению (Число 2) не предшествует ни символ /, ни *, ни  %, поэтому оно является завершенным Термом (а не выражением, которое заканчивается символом /, * или %).

3. Этому Терму (Первичное выражение 2) не предшествует ни символ +, ни –, поэтому оно является завершенным Выражением (а не выражением, которое заканчивается символами + или –).

Итак, в соответствии с нашей грамматикой 2 — это выражение. Этот просмотр грамматики можно описать так.

Этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Повторяя этот путь, мы видим, что 2 — это выражение, поскольку 2 — это литерал_с_плавающей_точкой, который является Числом, которое является Первичным выражением, которое является Термом, который является Выражением.

Попробуем проделать более сложное упражнение: 2+3 — это Выражение? Естественно, большинство рассуждений совпадает с рассуждениями для числа 2.

1. Выражение должно быть Термом или заканчиваться Термом, который должен быть Первичным выражением или заканчиваться Первичным выражением, а Первичное выражение должно начинаться с открывающей скобки, (, или быть Числом. Очевидно, что 2 является не открывающей скобкой, (, а литералом_с_плавающей_точкой, который является Числом, которое является Первичным выражением.

2. Этому Первичному выражению (Число 2) не предшествует ни символ /, ни *, ни %, поэтому оно является завершенным Термом (а не выражением, которое заканчивается символом /, * или %).

3. За этим Термом (Числом 2) следует символ +, поэтому он является окончанием первой части Выражения, и мы должны поискать Терм, который следует за символом +. Точно так же мы приходим к выводу, что 2 и 3 — это Термы. Поскольку за Термом 3 не следует ни символ +, ни –, он является завершенным Термом (а не первой частью Выражения, содержащего символ + или -). Следовательно, 2+3 соответствует правилу Выражение+Term и является Выражением.

Снова проиллюстрируем эти рассуждения графически (для простоты останавливая разбор на правиле для литерала_с_плавающей_точкой).

Этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Повторяя его, мы видим, что 2+3 — это Выражение, так как 2 — это Терм, который является Выражением, 3 — это Терм, а Выражение, за которым следует символ + и Терм, является Выражением.

Действительная причина, по которой мы так интересуемся грамматиками, заключается в том, что с их помощью можно решить проблему корректного грамматического разбора выражений, содержащих символы + и *, такие как 45+11.5*7. Однако заставить компьютер анализировать правила так, как это сделали мы, очень трудно. Поэтому пропустим промежуточные этапы, которые проделали для выражений 2 и 2+3. Очевидно, что 45, 11.5 и 7 являются литералами_с_ плавающей_точкой, которые являются Числами, которые являются Первичными выражениями, так что можем игнорировать все остальные правила.

1. 45 — это Выражение, за которым следует символ +, поэтому следует искать Терм, чтобы применить правило Выражение+Терм.

2. 11.5 — это Терм, за которым следует символ *, поэтому следует искать Первичное выражение, чтобы применить правило Терм*Первичное выражение.

3. 7 — это первичное выражение, поэтому 11.5*7 — это Терм в соответствии с правилом Терм*Первичное выражение. Теперь можем убедиться, что 45+11.5*7 — это Выражение в соответствии с правилом Выражение+Терм. В частности, это Выражение, которое сначала выполняет умножение 11.5*7, а затем сложение 45+11.5*7 так, будто мы написали выражение 45+(11.5*7).

Еще раз проиллюстрируем эти рассуждения графически (как и ранее, для простоты останавливая разбор на правиле для литерала_с_плавающей_точкой).

Как и прежде, этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Обратите внимание на то, что правило Терм*Первичное выражение гарантирует, что 11.5 умножается на 7, а не добавляется к 45.

Эта логика может показаться запутанной, но многие люди читают грамматики, и простые грамматики несложно понять. Тем не менее мы не собираемся учить вас вычислять выражение 2+2 или 45+11.5*7. Очевидно, вы это и так знаете. Мы лишь стараемся выяснить, как выполняет эти вычисления компьютер. Разумеется, для того чтобы выполнять такие вычисления, людям грамматики не нужны, а вот компьютерам они очень хорошо подходят. Компьютер быстро и правильно применяет правила грамматики. Точные правила — вот что нужно компьютеру.

6.4.1. Отступление: грамматика английского языка

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

Предложение:
  Имя существительное Глагол   // например, C++ rules
  Предложение Союз Предложение // например, Birds fly but
                               // fish swim

Союз:
 "and"
 "or"
 "but"

Имя существительное:
 "birds"
 "fish"
 "C++"

Глагол:
 "rules"
 "fly"
 "swim"

Предложение состоит из частей речи (например, имен существительных, глаголов и союзов). В соответствии с этими правилами предложение можно разложить на слова — имена существительные, глаголы и т.д. Эта простая грамматика также включает в себя семантически бессмысленные предложения, такие как “C++ fly and birds rules,” но решение этой проблемы выходит далеко за рамки рассмотрения нашей книги.

Многие читатели наверняка уже изучали такие правила в средней школе при изучении иностранных языков. Эти правила носят фундаментальный характер. В их основе лежат серьезные неврологические аргументы, утверждающие, что эти правила каким-то образом “встроены” в наш мозг!

Рассмотрим дерево грамматического разбора простого предложения на английском языке.

Сложности еще не закончились. Если вы не уверены, что все правильно поняли, то вернитесь и перечитайте раздел 6.4 с самого начала. Возможно, при втором чтении вы поймете, о чем идет речь!

6.4.2. Запись грамматики

Как выбираются грамматические правила для разбора указанных выше выражений? Самым честным ответом является “опыт”. Способ, который мы применили, просто повторяет способ, с помощью которого люди обычно записывают грамматики. Однако запись грамматики совершенно очевидна: нам необходимо лишь сделать следующее.

 1. Отличать правило от лексемы.

2. Записывать правила одно за другим (последовательно).

3. Выражать альтернативные варианты (разветвление).

4. Выражать повторяющиеся варианты (повторение).

5. Распознавать начальное правило.

В разных учебниках и системах грамматического разбора используются разные соглашения и терминология. Например, иногда лексемы называют терминалами (terminals), а правила — нетерминалами (non-terminals), или продукциями (productions). Мы просто заключаем лексемы в двойные кавычки и начинаем с первого правила. Альтернативы выражаются с помощью линий. Рассмотрим пример.

Список:
  "{"Последовательность"}"
Последовательность:
  Элемент
  Элемент "," Последовательность
Элемент:
  "A"
  "B"

Итак, Последовательность — это Элемент или Элемент, за которым следует разделяющая запятая и другая Последовательность. Элемент — это либо буква A, либо B. Список — это Последовательность в фигурных скобках. Можно сгенерировать следующие Списки (как?):

{A}
{B}
{A,B}
{A,A,A,A,B}

Однако то, что перечислено ниже, списком не является (почему?):

{}
A
{A,A,A,A,B
{A,A,C,A,B}
{A B C}
{A,A,A,A,B,}

Этим правилам вас в детском садике не учили, и в вашем мозге они не “встроены”, но понять их не сложно. Примеры их использования для выражения синтаксических идей можно найти в разделах 7.4 и 7.8.1.

6.5. Превращение грамматики в программу

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

6.5.1. Реализация грамматических правил

Для реализации калькулятора нам нужны четыре функции: одна — для считывания лексем и по одной для каждого грамматического правила.

get_token()  // считывает символы и составляет лексемы
             // использует поток cin
expression() // реализует операции + и –
             // вызывает функции term() и get_token()
term()       // реализует операции *, / и %
             // вызывает функции primary() и get_token()
primary()    // реализует числа и скобки
             // вызывает функции expression() и get_token()

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

Что же эти функции должны делать в действительности? Каждая из них должна вызывать другие грамматические функции в соответствии с грамматическим правилом, которое она реализует, а также функцию get_token(), если в правиле упоминается лексема. Например, когда функция primary() пытается следовать правилу (Выражение), она должна вызвать следующие функции:

get_token()  // чтобы обработать скобки ( и )
expression() // чтобы обработать Выражение

Что должен возвращать такой грамматический анализатор? Может быть, реальный результат вычислений? Например, для выражения 2+3 функция expression() должна была бы возвращать 5. Теперь понятно! Именно это мы и должны сделать! Поступая таким образом, мы избегаем ответа на один из труднейших вопросов: “Как представить выражение 45+5/7 в виде данных, чтобы его можно было вычислить?” Вместо того чтобы хранить представление этого выражения в памяти, мы просто вычисляем его по мере считывания входных данных. Эта простая идея коренным образом изменяет ситуацию! Она позволяет в четыре раза уменьшить размер программы по сравнению с вариантом, в котором функция expression() возвращает что-то сложное для последующего вычисления. Таким образом, мы сэкономим около 80% объема работы.

Функция get_token() стоит особняком: поскольку она обрабатывает лексемы, а не выражения, она не может возвращать значения подвыражений. Например, + и ( — это не выражения. Таким образом, функция get_token() должна возвращать объект класса Token.

// функции, подчиняющиеся грамматическим правилам
Token get_token()   // считывает символы и составляет лексемы
double expression() // реализует операции + и –
double term()       // реализует операции *, / и %
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;                // возвращаем значение Терма
  }
}

Этот программный код действительно — более или менее — работает. Мы включим его в окончательный вариант программы для грамматического разбора правильных выражений и отбраковки неправильных. Он позволяет правильно вычислить большинство выражений. Например, выражение 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.

 Итак, мы написали превосходную программу, которая выполняет вычисления неправильно. Это опасно. Это особенно опасно, поскольку во многих случаях программа дает правильный ответ. Например, выражение 1+2+3 будет вычислено правильно (6), так как 1+(2+3) эквивалентно (1+2)+3.

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

Анализ ошибок — часто лучший способ найти правильное решение. В данном случае функция 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;              // финал: символов + и – нет; возвращаем ответ
}

Этот вариант немного сложнее: мы ввели цикл для поиска символов +и –. Кроме того, дважды повторили проверку символов + и –, а также дважды вызвали функцию get_token(). Поскольку это запутывает логику кода, просто продублируем проверку символов + и –.

double expression()
{
  double left = term();  // считываем и вычисляем Терм
  Token t = get_token(); // получаем следующую лексему
  while(true) {
    switch(t.kind) {
    case '+':
      left += term();    // вычисляем Терм и добавляем его
      t = get_token();
      break;
    case '–':
      left –= term();    // вычисляем Терм и вычитаем его
      t = get_token();
      break;
    default:
      return left;       // финал: символов + и – нет;
                         // возвращаем ответ
    }
  }
}

Обратите внимание на то, что — за исключением цикла — этот вариант напоминает первый (см. раздел 6.5.2.1). Мы просто удалили вызов функции expression() в функции expression() и заменили его циклом. Другими словами, перевели Выражение в грамматическом правиле в цикл поиска Терма, за которым следует символ + или –.

6.5.3. Термы

Грамматическое правило для Терма очень похоже на правило для Выражения.

Терм:
  Первичное выражение
  Терм '*' Первичное выражение
  Терм '/' Первичное выражение
  Терм '%' Первичное выражение

Следовательно, программный код также должен быть похож на код для Выражения. Вот как выглядит его первый вариант:

double term()
{
  double left = primary();
  Token t = get_token();
  while(true) {
    switch (t.kind) {
    case '*':
      left *= primary();
      t = get_token();
      break;
    case '/':
      left /= primary();
      t = get_token();
      break;
    case '%':
      left %= primary();
      t = get_token();
      break;
    default:
      return left;
    }
  }
}

 К сожалению, этот код не компилируется: операция вычисления остатка (%) для чисел с плавающей точкой не определена. Компилятор вежливо предупредит нас об этом. Когда мы утвердительно ответили на вопрос 5 из раздела 6.3.5 — “Следует ли позволить ввод чисел с плавающей точкой?”, — мы не думали о таких последствиях и просто поддались искушению добавить в программу дополнительные возможности. Вот так всегда! Что же делать? Можно во время выполнения программы проверить, являются ли оба операнда операции % целыми числами, и сообщить об ошибке, если это не так. А можно просто исключить операцию % из возможностей нашего калькулятора. Эту функцию всегда можно добавить позднее (см. раздел 7.5). Исключив операцию %, получим вполне работоспособную функцию: термы правильно распознаются и вычисляются. Однако опытный программист заметит нежелательную деталь, которая делает функцию term() неприемлемой. Что произойдет, если ввести выражение 2/0? На нуль делить нельзя. Если попытаться это сделать, то аппаратное обеспечение компьютера обнаружит это и прекратит выполнение программы, выдав сообщение об ошибке. Неопытный программист обязательно столкнется с этой проблемой. По этой причине лучше провести проверку и выдать подходящее сообщение.

double term()
{
  double left = primary();
  Token t = get_token();
  while(true) {
    switch (t.kind) {
    case '*':
      left *= primary();
      t = get_token();
      break;
    case '/':
    { double d = primary();
      if (d == 0) error("деление на нуль");
      left /= d;
      t = get_token();
    break;
    }
    default:
      return left;
    }
  }
}

Почему мы поместили обработку операции / внутри блока? На этом настоял компилятор. Если мы хотим определить и инициализировать переменные в операторе switch, то должны поместить ее в блоке.

6.5.4. Первичные выражения

Грамматическое правило для первичных выражений также простое.

Первичное выражение:
  Число
  '('Выражение')'

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

double primary()
{
  Token t = get_token();
  switch (t.kind) {
  case '(': // обработка варианта '('выражение')'
    { double d = expression();
    t = get_token();
    if (t.kind != ')') error("')' expected");
    return d;
    }
  case '8':         // используем '8' для представления числа
    return t.value; // возвращаем значение числа
  default:
    error("ожидается первичное выражение");
  }
}

По сравнению с функциями expression() и term() в этом программном коде нет ничего нового. В нем используются те же самые языковые конструкции и методы, и объекты класса Token обрабатываются точно так же.

6.6. Испытание первой версии

Для того чтобы выполнить эти функции калькулятора, необходимо реализовать функции get_token() и main(). Функция main() тривиальна: мы просто вызываем функцию expression() и выводим результат на печать.

int main()
try {
  while (cin)
    cout << expression() << '\n';
  keep_window_open();
}
catch (exception& e) {
  cerr << e.what() << endl;
  keep_window_open ();
  return 1;
}
catch (...) {
  cerr << "exception \n";
  keep_window_open ();
  return 2;
}

Обработка ошибок представляет собой обычный шаблон (см. раздел 5.6.3). Отложим реализацию функции get_token() до раздела 6.8 и протестируем эту первую версию калькулятора.

ПОПРОБУЙТЕ

Первая версия программы, имитирующей работу калькулятора (включая функцию get_token()), содержится в файле calculator00.cpp. Запустите его и испытайте.

Нет ничего удивительного в том, что эта первая версия калькулятора работает не совсем так, как мы ожидали. Мы пожимаем плечами и спрашиваем себя: “Почему?”, или “Почему программа работает так, а не иначе?”, или “Что же она делает?” Введите число 2 и символ перехода на новую строку. Ответа вы не получите! Введите символ перехода на новую строку еще раз, чтобы убедиться, что компьютер не завис. Ответа по-прежнему нет. Введите число 3 и символ перехода на новую строку. Ответа нет! Введите число 4 и символ перехода на новую строку. Ответ равен 2! Теперь экран выглядит так:

2
3
4
2

Введем выражение 5+6. Ответ равен 5, а экран выглядит так:

2
3
4
2
5+6
5

Несмотря на свой опыт, скорее всего, вы будете сильно озадачены. Даже опытный программист будет озадачен таким поведением программы. Что происходит? В этот момент попробуйте выйти из программы. Как это сделать? Мы “забыли” указать в программе команду выхода, но прекращение работы может спровоцировать ошибка, поэтому введите символ х, и программа в ответ выведет на экран фразу Неправильная лексема и закончит работу. Наконец-то хоть что-то работает, как запланировано!

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

while (cin) cout << "= " << expression() << '\n'; // версия 1

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

2 
3 
4 
= 2 
5+6 
= 5 
x 
Неправильная лексема

Странно! Попробуйте понять, почему программа делает это. Мы попробовали еще несколько примеров. Только посмотрите на эту головоломку!

• Почему программа реагирует после ввода символов 2 и 3 и ввода символа перехода на новую строку?

• Почему после ввода числа 4 программа выводит на экран число 2, а не 4?

• Почему при вычислении выражения 5+6 программа выводит число 5, а не 11?

Существует множество способов получить такие загадочные результаты. Некоторые из них мы проверим в следующей главе, а пока просто подумаем. Может ли программа руководствоваться неверной арифметикой? Это крайне маловероятно: значение 4 не может быть равным 2, а 5+6 равно 11, а не 5. Попробуем разобраться, что происходит, когда мы вводим символы 1 2 3 4+5 6+7 8+9 10 11 12 и символ перехода на новую строку.

1 2 3 4+5 6+7 8+9 10 11 12
= 1
= 4
= 6
= 8
= 10

Что? Ни 2, ни 3. Почему число 4 в выводе есть, а числа 9 нет (т.е. 4+5)? Почему среди результатов есть число 6 и нет числа 13 (т.е. 6+7)?

Хорошенько подумайте: программа выводит каждую третью лексему! Может быть, программа “съедает” часть входной информации без вычислений? Похоже на это. Проанализируем функцию expression().

double expression()
{
  double left = term();  // считываем и вычисляем Терм
  Token t = get_token(); // получаем следующую лексему
  while(true) {
    switch(t.kind) {
    case '+':
      left += term();    // вычисляем и добавляем Term
      t = get_token();
      break;
    case '–':
      left –= term();    // вычисляем и вычитаем Терм
      t = get_token();
      break;
    default:
      return left;       // финал: символов + и – нет;
                         // возвращаем ответ
    }
  }
}

Если объект класса Token, возвращаемый функцией get_token(), не равен '+' или '–', выполняем оператор return. Мы не используем этот объект и не храним его в памяти для использования в других функциях. Это не умно. Отбрасывание входной информации без анализа недальновидно. Беглый анализ показывает, что функции term() присущ такой же недостаток. Это объясняет, почему наш калькулятор “съедает” по две лексемы после одной использованной.

Модифицируем функцию expression() так, чтобы она не “съедала” лексемы. Куда поместить следующую лексему (t), если программа никак не использует ее? Можно рассмотреть много сложных схем, но давайте просто перейдем к очевидному ответу (его очевидность станет ясной позднее): поскольку лексема будет использована другой функцией, которая будет считывать ее из потока ввода, давайте вернем лексему обратно в поток ввода, чтобы ее могла считать другая функция! Действительно, мы можем вернуть символ обратно в поток ввода, но это не совсем то, что мы хотим. Мы хотим работать с лексемами, а не возиться с символами. Итак, хотелось бы, чтобы поток ввода работал с лексемам, а мы имели бы возможность записывать в него уже считанные лексемы.

Предположим, в нашем распоряжении есть поток лексем — “Token_stream” — с именем ts. Допустим также, что поток Token_stream имеет функцию-член get(), возвращающую следующую лексему, и функцию-член putback(t), возвращающую лексему t обратно в поток.

Мы реализуем класс Token_stream в разделе 6.8, как только увидим, как его следует использовать. Имея поток Token_stream, можем переписать функцию expression() так, чтобы она записывала неиспользованную лексему обратно в поток Token_stream.

double expression()
{
  double left = term(); // считываем и вычисляем Терм
  Token t = ts.get();   // получаем следующую лексему
                        // из потока лексем
  while(true) {
    switch(t.kind) {
    case '+':
      left += term();   // вычисляем и добавляем Терм
      t = ts.get();
      break;
    case '–':
      left –= term();   // вычисляем и вычитаем Терм
      t = ts.get();
      break;
    default:
      ts.putback(t);    // помещаем объект t обратно
                        // в поток лексем
      return left;      // финал: символов + и – нет;
                        // возвращаем ответ
    }
  }
}

Кроме того, такие же изменения следует внести в функцию term().

double term()
{
  double left = primary();
  Token t = ts.get(); // получаем следующую лексему
                      // из потока лексем
  while(true) {
    switch (t.kind) {
    case '*':
      left *= primary();
      t = ts.get();
      break;
    case '/':
    {
      double d = primary();
      if (d == 0) error("деление на нуль");
      left /= d;
      t = ts.get();
      break;
    }
    default:
      ts.putback(t); // помещаем объект t обратно в поток лексем
      return left;
    }
  }
}

Для последней функции программы грамматического анализа primary() достаточно заменить функцию get_token() функцией ts.get(); функция primary() использует каждую лексему, которую она считывает.

6.7. Испытание второй версии

Итак, мы готовы к испытанию второй версии. Введем число 2 и символ перехода на новую строку. Нет ответа. Попробуйте ввести еще один символ перехода на новую строку, чтобы убедиться, что компьютер не завис. По-прежнему нет ответа. Введите число 3 и символ перехода на новую строку. Ответ равен 2. Попробуйте ввести выражение 2+2 и символ перехода на новую строку. Ответ равен 3. Экран выглядит следующим образом:

2
3
=2
2+2
=3

Хм... Может быть, наша функция putback() и ее использование в функции expression() и term() не решает проблему. Попробуем другой тест.

2 3 4 2+3 2*3
= 2
= 3
= 4
= 5

Да! Это правильные ответы! Но последний ответ (6) пропущен. Проблема следующей лексемы не решена. Однако на этот раз она заключается не в том, что наш программный код “съедает” символы, а в том, что он вообще не получает информации, пока не будет введено следующее выражение. Результат вычисления выражения не выводится на экран немедленно; он откладывается до тех пор, пока программа не увидит первую лексему следующего выражения. К сожалению, программа не видит эту лексему, пока мы не нажмем клавишу

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

Как исправить этот недостаток? Очевидное решение — потребовать немедленно выполнить вывод. Договоримся считать, что каждое выражение завершается точкой с запятой, которая одновременно служит триггером вывода. Кроме того, добавим в программу команду выхода. Для этого подходит символ q (первая буква слова quit (выход)). Функция main() содержит инструкцию

while (cin) cout << "=" << expression() << '\n'; // version 1

Заменим ее более запутанной, но более полезной инструкцией.

double val = 0;
while (cin) {
  Token t = ts.get();
  if (t.kind == 'q') break; // 'q' для выхода
  if (t.kind == ';')        // ';' для команды "печатать немедленно"
    cout << "=" << val << '\n';
  else
    ts.putback(t);
  val = expression();
}

Теперь калькулятор действительно можно использовать. Рассмотрим пример.

2;
= 2
2+3;
= 5
3+4*5;
= 23
q

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

6.8. Потоки лексем

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

Входной информацией для нашего калькулятора является последовательность лексем, как было показано выше на примере выражения (1.5+4)*11 (см. раздел 6.3.3). Нам лишь нужна функция, считывающая символы из стандартного потока cin и вводящая в программу следующую лексему по запросу. Кроме того, мы видели, что наша программа часто считывает слишком много лексем, поэтому необходимо как-то возвращать их обратно, чтобы использовать в дальнейшем. Эта ситуация очень типична. Допустим, мы считываем выражение 1.5+4 слева направо. Как убедиться, что число 1.5 считано полностью, а символ + — нет. Пока мы не увидим символ +, можем считывать число 1.55555. Таким образом, нам нужен поток, порождающий лексему при вызове функции get(), и возможность возвращать лексему обратно в поток при вызове функции putback(). Все сущности в языке С++ имеют тип, поэтому необходимо определить тип Token_stream.

Возможно, вы заметили ключевое слово public в определении класса Token, приведенном в разделе 6.3.3. В том случае для его использования не было очевидных причин. Однако при определении класса Token_stream мы должны применить его и объяснить его предназначение. В языке С++ тип, определенный пользователем, часто состоит из двух частей: открытого интерфейса (помеченного как public:) и реализации деталей типа (помеченной как private:). Идея заключается в том, чтобы отделить то, что пользователю необходимо для удобства, от деталей реализации типа, в которые пользователю вникать не обязательно.

class Token_stream {
public:
  // пользовательский интерфейс
private:
  // детали реализации
  // (скрывается от пользователей класса Token_stream)
};

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

Приступим к разработке типа Token_stream. Что пользователь ждет от него? Очевидно, что нам нужны функции get() и putback() — именно поэтому мы ввели понятие потока лексем. Класс Token_stream должен создавать объекты класса Token из символов, считанных из потока ввода, поэтому нам необходима возможность создавать объекты класса Token_stream, способные считывать данные из потока cin. Таким образом, простейший вариант класса Token_stream выглядит примерно так:

class Token_stream {
public:
  Token_stream();        // создает объект класса Token_stream,
                         // считывающий данные из потока cin
  Token get();           // получает объект класса Token
  void putback(Token t); // возвращает объект класса Token
                         // обратно
private:
                         // детали реализации
};

Это все, что требуется от пользователя для использования объектов класса Token_stream. Опытные программисты могут поинтересоваться, почему поток cin является единственным возможным источником символов, — просто мы решили вводить символы с клавиатуры. Это решение можно пересмотреть в упражнении, приведенном в главе 7.

Почему мы использовали “длинное” имя putback(), а не логичное имя put()? Тем самым мы подчеркнули асимметрию между функциями get() и putback(): мы возвращаем лексему в поток ввода, а не вставляем ее в поток вывода. Кроме того, функция putback() есть в классе istream: непротиворечивость имен — полезное свойство. Это позволяет людям запоминать имена функций и избегать ошибок.

Теперь можем создать класс Token_stream и использовать его.

Token_stream ts;    // объект класса Token_stream с именем ts
Token t = ts.get(); // получаем следующий объект класса Token из
 объекта ts
// ...
ts.putback(t); // возвращает объект t класса Token обратно в объект ts

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

6.8.1. Реализация класса Token_stream

Теперь необходимо реализовать три функции класса Token_stream. Как представить класс Token_stream? Иначе говоря, какие данные необходимо хранить в объекте класса Token_stream, чтобы он мог выполнить свое задание? Необходима память для лексемы, которая будет возвращена обратно в объект класса Token_stream. Для простоты будем считать, что лексемы возвращаются в поток по одной. Этого вполне достаточно для нашей программы (а также для очень многих аналогичных программ). Таким образом, нужна память для одного объекта класса Token и индикатор ее занятости.

class Token_stream {
public:
  Token_stream(); // создает объект класса Token_stream,
                  // считывающий данные из потока cin
  Token get();    // получает объект класса Token
                  // (функция get() определена в разделе 6.8.2)
  void putback(Token t); // возвращает объект класса Token
                         // обратно
private:
  bool full;    // находится ли в буфере объект класса Token?
  Token buffer; // здесь хранится объект класса Token,
                // возвращаемый в поток функцией putback()
};

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

Token_stream::Token_stream()
  :full(false), buffer(0) // в буфере нет ни одного объекта
                          // класса Token
{
}

Определяя функцию-член вне определения самого класса, мы должны указать, какому классу она принадлежит. Для этого используется обозначение имя_класса::имя_функции_члена. В данном случае нам необходимо определить конструктор класса Token_stream. Конструктор — это член класса, имя которого совпадает с именем класса.

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

Члены класса инициализированы в списке инициализации (см. раздел 6.3.3); выражение full(false) устанавливает член класса Token_stream с именем full равным значению false, а выражение buffer(0) инициализирует член buffer пустой лексемой, которую мы специально для этого изобрели. Определение класса Token (см. раздел 6.3.3) утверждает, что каждый объект класса Token должен иметь начальное значение, поэтому мы не можем просто проигнорировать член Token_stream::buffer.

Функция-член putback() возвращает аргументы обратно в буфер объекта класса Token_stream.

void Token_stream::putback(Token t)
{
  buffer = t;  // копируем объект t в буфер
  full = true; // теперь буфер полон
}

Ключевое слово void (означающее “ничто”) означает, что функция putback() не возвращает никакого значения. Если бы мы хотели гарантировать, что эта функция не будет использована дважды без считывания лексем, возвращенных в промежутке между ее вызовами (с помощью функции get()), то нам следовало бы добавить проверку.

void Token_stream::putback(Token t)
{
  if (full) error("putback() в полный буфер");
  buffer = t;  // копируем объект t в буфер
  full = true; // буфер теперь полон
}

Проверка переменной full соответствует проверке предусловия “В буфере нет ни одного объекта класса Token”.

6.8.2. Считывание лексем

Всю реальную работу выполняет функция get(). Если в переменной Token_stream::buffer еще нет ни одного объекта класса Token, то функция get() должна считать символы из потока cin и составить из них объект класса Token.

Token Token_stream::get()
{
  if (full) { // если в буфере есть лексема,
              // удаляем ее оттуда
    full=false;
    return buffer;
  }
  char ch;
  cin >> ch;  // обратите внимание на то, что оператор >>
              // пропускает разделители (пробелы, символы перехода
              // на новую строку, символы табуляции и т.д.)
  switch (ch) {
  case ';': // для печати
  case 'q': // для выхода
  case '(': case ')': case '+': case '–': case '*': case '/':
    return Token(ch); // пусть каждый символ
                      // представляет себя сам
  case '.':
  case '0': case '1': case '2': case '3': case '4':
  case '5': case '6': case '7': case '8': case '9':
    { cin.putback(ch); // возвращаем цифру обратно в поток ввода
      double val;
      cin >> val;      // считываем число с плавающей точкой
      return Token('8',val); // пусть символ '8' означает "число"
    }
  default:
    error("Неправильная лексема");
  }
}

Детально рассмотрим функцию get(). Сначала проверим, есть ли в буфере объект класса Token. Если есть, то мы просто вернем его.

if (full) { // если в буфере есть лексема,
            // удаляем ее оттуда
  full=false;
  return buffer;
}

Только если переменная full равна false (т.е. в буфере нет лексем), нам придется иметь дело с символами. В данном случае считываем символ и соответствующим образом обрабатываем его. Мы распознаем скобки, операторы и числа. Любой другой символ становится причиной вызова функции error(), которая прекращает выполнение программы.

default:
  error("Неправильная лексема");

Функция error() описана в разделе 5.6.3 и находится в заголовочном файле std_lib_facilities.h.

Необходимо решить, как представлять разные виды лексем, т.е. выбрать значения, идентифицирующие вид члена. Для простоты отладки мы решили обозначать скобки и операторы соответствующими им символами.

Это позволяет чрезвычайно просто обрабатывать скобки и операторы.

case '(': case ')': case '+': case '–': case '*': case '/': 
  return Token(ch); // пусть каждый символ представляет себя сам 

Честно говоря, мы “забыли” точку с запятой, ';', для вывода и букву q в первой версии. Мы не будем добавлять их, пока в них не возникнет потребность во второй версии.

6.8.3. Считывание чисел

Осталось обработать числа. На самом деле это не просто. Действительно, как узнать значения числа 123? Хорошо, оно равно 100+20+3. А что вы скажете о числе 12.34? Следует ли принять научную систему обозначения, такую как 12.34е5? Мы могли бы провести часы и дни, решая эту задачу, но, к счастью, это не обязательно. Потоки ввода в языке С++ распознают литералы и сами умеют переводить их в тип double. Все, что нам нужно, — как-то заставить поток cin сделать это в функции get().

case '.':
case '0': case '1': case '2': case '3': case '4': case '5':
case '6': case '7':
case '8': case '9':
  { cin.putback(ch);       // возвращаем цифру в поток ввода
    double val;
    cin >> val;            // считываем число с плавающей точкой
    return Token('8',val); // пусть символ '8' обозначает "число"
  }

Мы в некотором смысле произвольно решили, что символ '8' будет представлять число в классе Token. Как узнать, что на вход поступило число? Хорошо, зная по опыту или изучая справочник по языку С++ (например, в приложении А), можно установить, что числовой литерал должен начинаться с цифры или символа '.' (десятичной точки). Итак, этот факт следует проверить. Далее, мы хотим, чтобы поток cin считывал число, но мы уже считали первый символ (цифру или десятичную точку), поэтому пропуск оставшейся части лексемы приведет к ошибке. Можно попытаться скомбинировать значение первого символа со значением оставшейся части; например, если некто ввел число 123, можем взять число 1, а поток cin считает число 23, и нам останется лишь сложить 100 и 23. Это тривиальный случай.

К счастью (и не случайно), поток cin работает точно так же, как поток Token_stream, в том смысле, что мы можем вернуть в него символ обратно. Итак, вместо того чтобы выполнять сложные арифметические действия, мы возвращаем первый символ обратно в поток cin и позволяем ему считать все число.

 Пожалуйста, обратите внимание на то, как мы снова и снова избегаем сложностей и вместо этого находим простые решения, часто полагаясь на библиотеки. В этом заключается смысл программирования: постоянно искать простые решения. Иногда в шутку говорят: “Хороший программист — ленивый программист”. Это означает, что мы должны быть ленивыми (в хорошем смысле): зачем писать длинную программу, если можно написать короткую?

6.9. Структура программы

Как утверждает пословица, за деревьями трудно увидеть лес. Аналогично, легко потерять смысл программы, просматривая все ее функции, классы и т.д. Давайте рассмотрим программу, пропуская ее детали.

#include "std_lib_facilities.h"

class Token {/* ... */};
class Token_stream {/* ... */};
Token_stream::Token_stream():full(false), buffer(0) {/* ... */
}
void Token_stream::putback(Token t) {/* ... */}
Token Token_stream::get() {/* ... */}
Token_stream ts;     // содержит функции get() и putback()
double expression(); // объявление, позволяющее функции primary()
                     // вызывать функцию expression()
double primary() {/* ... */}    // обрабатывает числа и скобки
double term() {/* ... */}       // обрабатывает операции * и /
double expression() {/* ... */} // обрабатывает операции + и –

int main() {/* ... */} // основной цикл и обработка ошибок

 Порядок следования объявлений важен. Мы не можем использовать имя, пока оно не объявлено, поэтому объект ts должен быть объявлен до того, как будет вызвана функция ts.get(), а функция error() должна быть объявлена до функций грамматического анализа, поскольку они используют ее. В графе вызовов существует интересный цикл: функция expression() вызывает функцию term(), которая вызывает функцию primary(), которая вызывает функцию expression().

Эту ситуацию можно проиллюстрировать графически (удалив вызовы функции error()).

Это значит, что мы не можем просто определить эти три функции: не существует такого порядка их следования, при котором вызываемая функция была бы определена заранее. Таким образом, необходимо объявление, которое не было бы определением. Мы решили объявить “наперед” функции expression().

Работает ли эта программа? Работает, если придать этому слову определенный смысл. Она компилируется, запускается, правильно вычисляет выражения и выдает осмысленные сообщения об ошибках. Но работает ли она так, как мы от нее ожидаем? Не удивительно, что на самом деле она работает не совсем так, как надо. Мы испытали первую версию в разделе 6.6 и удалили серьезные ошибки. Однако вторая версия (см. раздел 6.7) не намного лучше, хотя в этом нет ничего страшного (это было вполне предсказуемо). Программа вполне успешно выполняет свою основную задачу и позволяет проверить основные идеи. В этом смысле она вполне успешна, но как только вы станете работать с ней, получите массу проблем.

ПОПРОБУЙТЕ

Запустите программу, посмотрите, что она делает, и попытайтесь понять, почему она так работает.

Задание

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

1. Откройте файл calculator02buggy.cpp. Скомпилируйте его. Найдите и исправьте несколько ошибок. Этих ошибок в тексте книги нет.

2. Измените символ, кодирующий команду выхода, с q на x.

3. Измените символ, кодирующий команду печати, с ; на =.

4. Добавьте в функцию main() приветствие.

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

5. Усовершенствуйте это приветствие, указав, какие операторы можно выполнить и как вывести данные на экран и выйти из программы.

6. Найдите три логические ошибки, преднамеренно внесенные в файл calculator02buggy.cpp, и удалите их из программы.

Резюме

1. Что означает выражение “Программирование — это понимание”?

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

3. Как разбить задачу на небольшие части?

4. Почему следует начинать с небольшой версии программы?

5. Почему нагромождение возможностей может привести в тупик?

6. Перечислите три основных этапа разработки программного обеспечения.

7. Что такое прецедент использования?

8. Для чего предназначено тестирование?

9. Следуя схеме, лежащей в основе этой главы, опишите разницу между Термом, Выражением, Числом и Первичным выражением.

10. В главе входная информация разделена на компоненты: Термы, Выражения, Первичные выражения и Числа. Сделайте это для арифметического выражения (17+4)/(5–1).

11. Почему в программе нет функции number()?

12. Что такое лексема?

13. Что такое грамматика? Что такое грамматическое правило?

14. Что такое класс? Для чего мы используем классы?

15. Что такое конструктор?

16. Почему в функции expression() в операторе switch по умолчанию предусмотрен возврат лексемы обратно в поток?

17. Что значит “смотреть вперед”?

18. Что делает функция putback() и чем она полезна?

19. Почему операцию вычисления остатка (деление по модулю) % трудно реализовать с помощью функции term()?

20. Для чего используются два члена класс Token?

21. Зачем члены класса разделяются на закрытые и открытые?

22. Что произойдет в классе Token_stream, если в буфере есть лексема и вызвана функция get()?

23. Зачем в оператор switch в функцию get() в классе Token_stream добавлены символы ';' и 'q'?

24. Когда следует начинать тестирование программы?

25. Что такое тип, определенный пользователем? Зачем он нужен?

26. Что такое интерфейс типа, определенного пользователем?

27. Почему следует полагаться на библиотечные коды?

Термины

Упражнения

1. Выполните упражнения из раздела ПОПРОБУЙТЕ, если вы не сделали этого раньше.

2. Добавьте в программу возможность обработки скобок {} и (), чтобы выражение {(4+5)*6}/(3+4) стало корректным.

3. Добавьте оператор вычисления факториала: для его представления используйте знак восклицания, !. Например, выражение 7! означает 7*6*5*4*3*2*1. Присвойте оператору ! более высокий приоритет по сравнению с операторами * и /, т.е. 7*8! должно означать 7*(8!), а не (7*8)!. Начните с модификации грамматики, чтобы учесть оператор с более высоким приоритетом. Для того чтобы учесть стандартное математическое определение факториала, установите выражение 0! равным 1.

4. Определите класс Name_value, хранящий строку и значение. Включите в него конструктор (так же как в классе Token). Повторите упр. 19 из главы 4, чтобы вместо двух векторов использовался вектор vector.

5. Добавьте пункт в английскую грамматику из раздела 6.4.1, чтобы можно было описать предложения вида “The birds fly but the fish swim”.

6. Напишите программу, проверяющую корректность предложений в соответствии с правилами грамматики английского языка из раздела 6.4.1. Будем считать, что каждое предложение заканчивается точкой, ., окруженной пробелами. Например, фраза birds fly but the fish swim. является предложением, а фразы but birds fly but the fish swim (пропущена точка) и birds fly but the fish swim. (перед точкой нет пробела) — нет. Для каждого введенного предложения программа должна просто отвечать “Да” или “Нет”. Подсказка: не возитесь с лексемами, просто считайте строку с помощью оператора >>.

7. Напишите грамматику для описания логических выражений. Логическое выражение напоминает арифметическое за исключением того, что в нем используются не арифметические, а логические операторы: ! (отрицание), ~ (дополнение), & (и), | (или) и ^ (исключающее или). Операторы ! и ~ являются префиксными унарными операторами. Оператор ^ имеет более высокий приоритет, чем оператор | (так же, как оператор * имеет более высокий приоритет, чем оператор +), так что выражение x|y^z означает x|(y^z), а не (x|y)^z. Оператор & имеет более высокий приоритет, чем оператор ^, так что выражение x^y&z означает x^y&z).

8. Повторите упр. 12 из главы 5 (игра “Коровы и быки”), используя четыре буквы, а не четыре цифры.

9. Напишите программу, считывающую цифры и составляющую из них целые числа. Например, число 123 считывается как последовательность символов 1, 2 и 3. Программа должна вывести на экран сообщение: “123 — это 1 сотня, 2 десятки и 3 единицы”. Число должно быть выведено как значение типа int. Обработайте числа, состоящие из одной цифры, двух, трех и четырех цифр. Подсказка: для того чтобы получить число 5 из символа '5', вычтите из него символ '0' , иначе говоря, '5'–'0'==5.

10. Перестановка — это упорядоченное подмножество множества. Например, допустим, что вы хотите подобрать код к сейфу. Существует шестьдесят возможных чисел, а вам необходимо выбрать три числа для комбинации. Для этой комбинации чисел существует P(60,3) перестановок, где количество перестановок определяется по формуле:

где символ ! означает факториал. Например, 4! — это 4*3*2*1. Сочетания напоминают перестановки за исключением того, что в них порядок следования не имеет значения. Например, если вы делаете банановое мороженое и хотите использовать три разных вкуса из пяти, имеющихся в наличии, вам все равно, когда вы используете ваниль — в начале или в конце, вы просто хотите использовать ваниль. Формула для вычисления количества сочетаний имеет следующий вид:

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

Послесловие

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

Глава 7. Завершение программы