О чём не пишут в книгах по Delphi

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

Теперь у нас уже достаточно знаний, чтобы создать простейший калькулятор, т. е. функцию, которая будет на входе принимать выражение, а на выходе, если это выражение корректно, возвращать результат его вычисления. Для начала ограничимся простым калькулятором, который умеет работать только с числовыми константами и знает только четыре действия арифметики. Изменение порядка вычисления операторов с помощью скобок также оставим на потом.
Таким образом, наш калькулятор будет распознавать и вычислять цепочки чисел, между которыми стоят знаки операции, которые над этими числами выполняются. В вырожденном случае выражение может состоять из одного числа и, соответственно, не содержать ни одного знака операции. Опишем эти правила с помощью БНФ и ранее определенного символа <Number>.
<Expr> ::= <Number> {<Operation> <Number>}
<Operation> ::= '+' | '-' | '*' | '/'
Примечание
В нашей грамматике не предусмотрено, что между оператором и его операндами может находиться пробел, т.е. выражение "2 + 2", в отличие от "2+2", не удовлетворяет данной грамматике. В отсутствие лексического анализатора игнорирование пробелов и прочих разделителей (переводов строки, комментариев) является трудоемкой рутинной операцией, поэтому во всех примерах без лексического анализатора мы будем требовать, чтобы выражения не содержали пробелов.
Для написания калькулятора нам понадобятся две новых функции — IsOperator, которая проверяет, является ли следующий символ оператором, и Expr, которая получает на входе строку, анализирует ее в соответствии с указанными правилами и вычисляет результат. Кроме того, функция IsNumber сама по себе нам тоже больше не нужна — мы создадим на ее основе функцию Number, которая получает на входе строку и номер позиции, начиная с которой в этой строке должно быть расположено число, проверяет, так ли это, и возвращает это число. Кроме того, функция Number должна перемещать указатель на следующий после числа символ строки, чтобы функция Expr, вызвавшая Number, могла узнать, с какого символа продолжать анализ. Если последовательность символов не является корректным числом, функция Number возбуждает исключение ESyntaxError, определенное специально для указания на ошибку в записи выражения.
Сама по себе задача преобразования строки в вещественное число достаточно сложна, и чтобы не отвлекаться на ее решение, мы воспользуемся функцией StrToFloat из модуля SysUtils. Когда функция Number выделит из строки последовательность символов, являющуюся числом, эта последовательность передается функции StrToFloat, и преобразованием занимается она. Здесь следует учесть два момента. Во-первых, в нашей грамматике разделителем целой и дробной части является точка, a StrToFloat использует системные настройки, т.е. разделителем может быть и запятая. Чтобы обойти эту проблему, слегка изменим синтаксис и будем сравнивать аргумент функции IsSeparator не с символом ".", а с DecimalSeparator (таким образом, наш калькулятор тоже станет чувствителен к системным настройкам). Во-вторых, не всякое выражение, соответствующее нашей грамматике, будет допустимым числом с точки зрения StrToFloat, т.к. эта функция учитывает диапазон типа Extended. Например, синтаксически верное выражение "2е5000" даст исключение EConvertError, т.к. данное число выходит за пределы этого диапазона. Но пока мы остаемся в рамках типа Extended, мы вынуждены мириться с этим.
Новые функции приведены в листинге 4.3.
Листинг 4.3. Реализация простейшего калькулятора
// Выделение из строки подстроки, соответствующей
// определению <Number>, и вычисление этого числа
// S — строка, из которой выделяется подстрока
// Р — номер позиции в строке, с которой должно
// начинаться число. После завершения работы функции
// этот параметр содержит номер первого после числа
function Number(const S: string; var P: Integer): Extended;
var
 InitPos: Integer;
begin
 // InitPos нам понадобится для выделения подстроки,
 // которая будет передана в StrToFloat
 InitPos := Р;
 if (Р <= Length(S)) and IsSign(S[P]) then Inc(P);
 if (P > Length(S)) or not IsDigit(S[P]) then
  raise ESyntaxError.Create(
   'Ожидается цифра в позиции ' + IntToStr(Р));
 repeat
  Inc(P);
 until (P > Length(S)) or not IsDigit(S[P]);
 if (P <= Length(S)) and IsSeparator(S[P]) then begin
  Inc(P);
  if (P > Length(S)) or not IsDigit(S[P]) then
   raise ESyntaxError.Create(
    'Ожидается цифра в позиции ' + IntToStr(Р));
  repeat
   Inc(P);
  until (P > Length(S)) or not IsDigit(S[P]);
 end;
 if (P <= Length(S)) and IsExponent(S[P]) then
 begin
  Inc(P);
  if Р > Length(S) then
   raise ESyntaxError.Create('Неожиданный конец строки');
  if IsSign(S[P]) then Inc(P);
  if (P > Length(S)) or not IsDigit(S[P]) then
   raise ESyntaxError.Create(
    'Ожидается цифра в позиции ' + IntToStr(Р));
  repeat
   Inc(P);
  until (P > Length(S)) or not IsDigit(S[P]);
 end;
 Result := StrToFloat(Copy(S, InitPos, P - InitPos));
end;

 

// Проверка символа на соответствие <Operator>
function IsOperator(Ch: Char): Boolean;
begin
 Result := Ch in ['+', '-', '*', '/'];
end;

 

// Проверка строки на соответствие <Expr>
// и вычисление выражения
function Expr(const S: string): Extended;
var
 P: Integer;
 OpSymb: Char;
begin
 P := 1;
 Result := Number(S, P);
 while (P <= Length(S)) and IsOperator(S[P]) do
 begin
  OpSymb := S[P];
  Inc(P);
  case OpSymb of
  '+': Result := Result + Number(S, P);
  '-': Result := Result - Number(S, P);
  '*': Result := Result * Number(S, P);
  '/': Result := Result / Number(S, P);
  end;
 end;
 if P <= Length(S) then
  raise ESyntaxError.Create(
   'Heкорректный символ в позиции ' + IntToStr(Р));
end;
Код приведен практически без комментариев, т.к. он очень простой, и все моменты, заслуживающие упоминания, мы уже разобрали в тексте. На прилагаемом компакт-диске находится программа 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++. В них оператор инкремента, записывающийся как "++", имеет две формы записи — префиксную (перед увеличиваемой переменной) и постфиксную (после переменной). Кроме того, этот оператор возвращает значение, поэтому его можно использовать в выражениях. Синтаксически допустимо, например, выражение а+++b, но грамматика не дает ответа, следует ли это трактовать как (а++)+b или как а+(++b). Кроме того, т.к. существует операция "унарный плюс", возможно и третье толкование — а+(+(+b)).
Показать оглавление

Комментариев: 0

Оставить комментарий