Простой калькулятор

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

Таким образом, наш калькулятор будет распознавать и вычислять цепочки чисел, между которыми стоят знаки операции, которые над этими числами выполняются. В вырожденном случае выражение может состоять из одного числа и, соответственно, не содержать ни одного знака операции. Опишем эти правила с помощью БНФ, используя ранее определённый символ <Number>.

Для написания калькулятора нам понадобятся две новых функции - IsOperator, которая проверяет, является ли следующий символ оператором, и Expr, которая получает на входе строку, анализирует её в соответствии с указанными правилам и вычисляет результат. Кроме того, функция IsNumber сама по себе нам тоже больше не нужна - мы создадим на её основе функцию Number, которая получает на входе строку и номер позиции, начиная с которой в этой строке должно быть расположено число, проверяет, так ли это, и возвращает это число. Кроме того, функция Number должна перемещать указатель на следующий после числа символ строки, чтобы функция Expr, вызвавшая Number, могла узнать, с какого символа продолжать анализ. Если последовательность символов не является корректным числом, функция Number возбуждает исключение ESyntaxError, определённое специально для указания на ошибку в записи выражения.

Сама по себе задача преобразования строки в вещественное число достаточно сложна, и чтобы не отвлекаться на её решение, мы будем использовать функцию StrToFloat из модуля SysUtils. Когда функция Number выделит из строки последовательность символов, являющуюся числом, эта последовательность передаётся функции StrToFloat, и преобразованием занимается она. Здесь надо учесть два момента. Во-первых, в нашей грамматике разделителем целой и дробной части является точка, а StrToFloat использует системные настройки, т.е. разделителем может быть и запятая. Чтобы обойти эту проблему, слегка изменим синтаксис и будем сравнивать аргумент функции IsSeparator не с символом ".", а с DecimalSeparator (таким образом, наш калькулятор тоже станет чувствителен к системным настройкам). Во-вторых, не всякое выражение, соответствующее нашей грамматике, будет допустимым числом с точки зрения StrToFloat, т.к. эта функция учитывает диапазон типа Extended. Например, синтаксически верное выражение "2e5000" даст исключение EConvertError, т.к. это число выходит за пределы этого диапазона. Но пока мы остаёмся в рамках типа Extended, мы вынуждены мириться с этим.
Новые функции выглядят следующим образом:

Код приведён практически без комментариев, т.к. он очень простой, и все моменты, заслуживающие упоминания, мы уже разобрали в тексте. В прилагаемом архиве находится программа SimpleCalcSample, которая демонстрирует работу нашего калькулятора. Калькулятор выполняет действия над числами слева направо, без учёта приоритета операций, т.е. вычисление выражения "2+2*2" даст 8.

Грамматика выражения является простой для разбора, т.к. разбор выражения идёт слева направо, и для соотнесения очередной части строки с тем или иным нетерминальным символом на любом этапе анализа достаточно знать только следующий символ. Такие грамматики называются LR(1)-грамматиками (в более общем случае требуется не один символ, а одна лексема). Класс этих грамматик исследован Кнутом.

Грамматика Паскаля не относится к классу LR(1)-грамматик из-за уже упоминавшейся проблемы отнесения else к тому или иному if. Чтобы решить эту проблему, приходится вводить два нетерминальных символа - завершённой формы оператора if (с else) и незавершённой (без else). Таким образом, встретив в тексте программы лексему "if", синтаксический анализатор не может сразу отнести её к одному из этих символов, пока не продвинется вперёд и не натолкнётся на наличие или отсутствие else. А так как оператор if может быть оператором в циклах for, while или в операторе with, для них также приходится вводить завершённую и незавершённую форму. Именно из-за этой проблемы Вирт (разработчик Паскаля) в своих более поздних языках отказался от идеи составного оператора и модифицировал синтаксис таким образом, чтобы проблема else не возникала.

Другим достоинством нашей простой грамматики является её однозначность. Любая синтаксически верная строка не допускает неоднозначной трактовки. Неоднозначность могла бы возникнуть, например, если бы какая-то операция обозначалась символом ".". Тогда было бы непонятно, должно ли выражение "1.5" трактоваться как число "одна целая пять десятых" или как выполнение операции над числами 1 и 5. Этот пример выглядит несколько надуманным, но неоднозначные грамматики, тем не менее, иногда встречаются на практике. Например, если запятая служит для отделения дробной части числа от целой и для разделения значений в списке параметров функций, то выражение "f(1,5)" может, с одной стороны, трактоваться как вызов функции f с одним аргументом 1.5, а с другой - как вызов её с двумя аргументами 1 и 5. Правила решения неоднозначных ситуаций не описываются в виде БНФ, их приходится объяснять "на словах", что затрудняет разбор соответствующих выражений. Другой пример неоднозначной грамматики - грамматика языков C/C++. В них оператор инкремента, записывающийся как "++", имеет две формы записи - префиксную (перед увеличиваемой переменной) и постфиксную (после переменной). Кроме того, этот оператор возвращает значение, поэтому его можно использовать в выражениях. Синтаксически допустимо, например, выражение "a+++b", но грамматика не даёт ответа, следует ли это трактовать как "(a++)+b" или как "a+(++b)". Кроме того, т.к. существует операция "унарный плюс", возможно и третье толкование - "a+(+(+b))".

Учёт приоритета операторов

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

Для примера рассмотрим выражение "2*4+3*8/6". Наш синтаксис должен как-то отразить то, что аргументами операции сложения в данном случае являются не числа 4 и 5, а "2*4" и "3*8/6". В общем случае это означает, что выражение - это последовательность из одного или нескольких слагаемых, между которыми стоят знаки "+" или "-". А слагаемые - это, в свою очередь, последовательности из одного или нескольких чисел, разделённых знаками "*" и "/". А теперь запишем то же самое на языке БНФ:

Определение символа <Operator1> совпадает с определением введённого ранее символа <Sign>. Но использовать <Sign> в определении <Expr> было бы неправильно, т.к., в принципе, в выражении могут существовать и другие операции, имеющие тот же приоритет (как, например, операции арифметического или и арифметического исключающего или в Delphi), и тогда определение <Operator1> будет расширено. Но это не должно затронуть определение символа <Number>, в которое входит <Sign>.

Чтобы приспособить калькулятор к новым правилам, нужно заменить функцию Operator на Operator1 и Operator2, добавить функцию Term и внести изменения в Expr. Функция Number остаётся без изменения. Обновлённая часть калькулятора выглядит следующим образом.

Если вы разобрались с предыдущими примерами, приведённый здесь код будет вам понятен. Некоторых комментариев требует только функция Term. Она выделяет, начиная с заданного символа, ту часть строки, которая соответствует определению <Term>. Вызвавшая её функция Expr должна продолжить разбор выражения со следующего за этой подстрокой символа, поэтому функция Term, как и Number, имеет параметр-переменную P, которая на входе содержит номер первого символа слагаемого, а на выходе - номер первого после этого слагаемого символа.

Пример калькулятора, учитывающего приоритет операций, содержится в архиве под именем PrecedenceCalcSample. Поэкспериментировав с ним, легко убедиться, что теперь вычисление "2+2*2" даёт правильное значение 6.

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

Выражения со скобками

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

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

В этих определениях появилась рекурсия, т.к. в определении <Expr> используется (через <Term>) символ <Factor>, а в определении <Factor> - <Expr>. Соответственно, при реализации такой грамматики будут использоваться рекурсивные функции.

Наша грамматика не учитывает, что перед скобками может стоять знак унарной операции "+" или "-", хотя общепринятые правила записи выражений вполне допускают выражения типа "3*-(2+4)". Поэтому, прежде чем приступить к реализации нового калькулятора, введём правила, допускающие такой синтаксис. Можно было бы модифицировать определение <Factor> таким образом:

Однако такой подход страдает отсутствием общности. В дальнейшем мы усложним наш синтаксис, введя другие типы множителей - функции, переменные. Перед каждым из них, в принципе, может стоять знак унарной операции, поэтому логичнее определить синтаксис таким образом, чтобы унарная операция допускалась вообще перед любым множителем. В этом случае можно будет слегка упростить определение <Number>, т.к. знак "+" или "-" в начале числа можно будет трактовать не как часть числа, а как унарный оператор, стоящий перед множителем, представленным в виде числовой константы.
С учётом этого новая грамматика запишется следующим образом:

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

Мы видим, что грамматика стала "более рекурсивной", т.е. в определении символа <Factor> используется он сам. Соответственно, функция Factor будет вызывать саму себя.

Символ <UnaryOp>, определение которого совпадает с определениями <Operator1> и <Sign>, мы делаем независимым нетерминальным символом по тем же причинам, что и ранее: в принципе, синтаксис может допускать унарные операции (как, например, not в Delphi), которые не являются ни знаками, ни допустимыми бинарными операциями.

Побочным эффектом нашей грамматики стало то, что, например, "-5" воспринимается как множитель, а потому перед ним допустимо поставить унарный оператор, т.е. выражение "--5" также является корректным множителем и трактуется как "-(-5)". А перед "--5", в свою очередь, можно поставить ещё один унарный оператор. И так - до бесконечности. Это может показаться не совсем правильным, но, тем не менее, такая грамматика широко используется. Легко, например, убедиться, что компилятор Delphi считает допустимым выражение "2+-+-2", трактуя его как "2+(-(+(-2)))".
Нижеследующий код иллюстрирует реализацию данной грамматики.

По сравнению с предыдущим примером функция Term осталась такой же с точностью до замены вызовов Number на вызовы новой функции Factor. Функция Factor выделяет подстроку, отвечающую отдельному множителю. Множители, напомним, могут быть трёх типов: число, выражение в скобках, множитель с унарным оператором. Различить их можно по первому символу подстроки. Функция Factor распознаёт тип множителя и вызывает соответствующую функцию для его вычисления.

Функция Expr теперь может применяться не только к выражению в целом, но и к отдельной подстроке. Поэтому она, как и все остальные функции, теперь имеет параметр-переменную P, через который передаётся начало и конец этой подстроки. Из функции убрана проверка того, что в результате её использования строка проанализирована полностью, т.к теперь допустим анализ части строки.

Функция Expr в своём новом виде стала не очень удобна для конечного пользователя, поэтому была описана ещё одна функция - Calculate. Это вспомогательная функция, которая избавляет пользователя от вникания в детали "внутренней кухни" калькулятора, т.е. использования переменной P и проверки того, что строка проанализирована до конца.

Пример калькулятора со скобками находится в архиве под названием BracketsCalcSample. Анализируя его код, можно заметить, что по сравнению с предыдущим примером незначительно изменена функция Number - из неё в соответствии с новой грамматикой убрана проверка знака в начале выражения.