class="z1" alt="" src="images/_002.png"/> Первая попытка решить эту задачу (написать программу-калькулятор) оказалась относительно удачной. Это нетипично для первого приближения, которое играет важную роль для понимания задачи. В данном случае это даже позволило нам ввести полезное понятие лексемы, которое представляет собой частный случай широко распространенного понятия пары (имя, значение). Тем не менее всегда следует помнить, что “стихийное” программирование не должно занимать слишком много времени. Необходимо программировать как можно меньше, пока не будет завершен этап анализа (понимание задачи) и проектирования (выявление общей структуры решения).
ПОПРОБУЙТЕ
С другой стороны, почему невозможно найти простое решение этой задачи? Ведь она не выглядит слишком сложной. Такая попытка позволит глубже понять задачу и ее решение. Сразу же определите, что следует сделать. Например, проанализируйте строку 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, но как объяснить программе, что деление имеет более высокий приоритет, чем сложение? Стандартный ответ — написать грамматику, определяющую синтаксис ввода, а затем программу, реализующую правила этой грамматики. Рассмотрим пример.
// Пример простой грамматики выражений:
Выражение:
Терм
Выражение "+" Терм // сложение
Выражение "–" Терм // вычитание
Терм:
Первичное выражение
Терм "*" Первичное выражение // умножение
Терм "/" Первичное выражение // деление
Терм "%" Первичное выражение // остаток (деление по модулю)
Первичное выражение:
Число
"(" Выражение ")" // группировка
Число:
литерал_с_плавающей_точкой
Это набор простых правил. Последнее правило читается так: “Число — это литерал с плавающей точкой”. Предыдущее правило утверждает: “Первичное выражение — это Число или скобка, '(', за которой следует Выражение и скобка, ')'”. Правила для Выражения и Терма аналогичны; каждый из них