Существует много способов заставить компьютер следовать грамматическим правилам. Мы используем простейший из них: напишем функцию для каждого грамматического правила, а для представления лексем применим класс
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).