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; // возвращаем значение Выражения
}
}
Программа выглядит неплохо. Это почти тривиальная транскрипция грамматики. Она довольно проста: сначала считываем Выражение, а затем проверяем, следует ли за ним символ + или –, и в случае положительного ответа считываем Терм.