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

. Программу, реализующую грамматику, часто называют программой грамматического разбора (parser).

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

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

Что же эти функции должны делать в действительности? Каждая из них должна вызывать другие грамматические функции в соответствии с грамматическим правилом, которое она реализует, а также функцию

, если в правиле упоминается лексема. Например, когда функция пытается следовать правилу (Выражение), она должна вызвать следующие функции:

Что должен возвращать такой грамматический анализатор? Может быть, реальный результат вычислений? Например, для выражения

функция должна была бы возвращать . Теперь понятно! Именно это мы и должны сделать! Поступая таким образом, мы избегаем ответа на один из труднейших вопросов: “Как представить выражение в виде данных, чтобы его можно было вычислить?” Вместо того чтобы хранить представление этого выражения в памяти, мы просто вычисляем его по мере считывания входных данных. Эта простая идея коренным образом изменяет ситуацию! Она позволяет в четыре раза уменьшить размер программы по сравнению с вариантом, в котором функция возвращает что-то сложное для последующего вычисления. Таким образом, мы сэкономим около 80% объема работы.

Функция

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

Сначала напишем функцию

. Грамматическое правило выглядит следующим образом:

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

Посмотрев на правило Выражение '+' Терм, сначала попытаемся вызвать функцию

, поищем операцию (и ), а затем вызовем функцию .