// Выделение из строки подстроки, соответствующей
// определению <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)).
4.5. Учет приоритета операторов
Следующим нашим шагом станет модификация калькулятора таким образом, чтобы он учитывал приоритет операций, т. е. чтобы умножение и деление выполнялись раньше сложения и умножения.
Дня примера рассмотрим выражение "2*4+3*8/6". Наш синтаксис должен как-то отразить то, что аргументами операции сложения в данном случае являются не числа 4 и 3, а "2*4" и "3*8/6". В общем случае это означает, что выражение — это последовательность из одного или нескольких слагаемых, между которыми стоят знаки "+" или "-". А слагаемые — это, в свою очередь, последовательности из одного или нескольких чисел, разделенных знаками "*" и "/". А теперь запишем то же самое на языке БНФ (листинг 4.4).
Листинг 4.4. Грамматика выражения с учетом приоритета операций
<Expr> ::= <Term> {<Operator1> <Term>}
<Term> ::= <Number> {<Operator2> <Number>}
<Operator1> ::= '+' | '-'
<Operator2> ::= '*' | '/'
Примечание
Определение символа <Operator1> совпадает с определением введенного ранее символа <Sign>. Но использовать <Sign> в определении <Expr> было бы неправильно, т.к., в принципе, в выражении могут существовать и другие операции, имеющие тот же приоритет (как, например, операции арифметического или и арифметического исключающего или в Delphi"), и тогда определение <Operator1> будет расширено. Но это не должно затронуть определение символа <Number>, в которое входит <Sign>.
Чтобы приспособить калькулятор к новым правилам, нужно заменить функцию Operator на Operator1 и Operator2, добавить функцию Term (слагаемое) и внести изменения в Expr. Функция Number остается без изменения. Обновленная часть калькулятора выглядит следующим образом (листинг 4.5).
Листинг 4.5. Реализация калькулятора с учетом приоритета операций
// Проверка символа на соответствие <Operator1>
function IsOperator1(Ch: Char): Boolean;
begin
Result := Ch in ['+', '-'];
end;
// Проверка символа на соответствие <Operator2>
function IsOperator2(Ch: Char): Boolean;
begin
Result := Ch in ['*', '/'];
end;
// Выделение подстроки, соответствующей <Term>,
// и ее вычисление
function Term(const S: string; var P: Integer): Extended;
var
OpSymb: Char;
begin
Result := Number(S,P);
while (P <= Length(S)) and IsOperator2(S[P]) do
begin
OpSymb := S[P];
Inc(P);
case OpSymb of
'*': Result := Result * Number(S, P);
'/': Result := Result / Number(S, P);
end;
end;
// Проверка строки на соответствие <Expr>
// и вычисление выражения
function Expr(const S: string): Extended;
var
P: Integer;
OpSymb: Char;
begin
P := 1;
Result := Term(S, P);
while (P <= Length(S)) and IsOperator1(S[P]) do
begin
OpSymb := S[P];
Inc(P);
