Полноценный калькулятор
Последняя версия нашего калькулятора может считать сложные выражения, но для практического использования этого мало. В этом разделе мы научим наш калькулятор использовать функции и переменные. Также будет введена операция возведения в степень, обозначающаяся значком "^".
Имена переменных и функций - это идентификаторы. Идентификатор определяется по общепринятым правилам: он должен начинаться с буквы латинского алфавита или символа "_", следующие символы должны быть буквами, цифрами или "_". Таким образом, грамматика идентификатора выглядит так:
Код:
<Letter> ::= 'A' | ... | 'Z' | 'a' | ... | 'z' | '_'
<Identifier> ::= <Letter> {<Letter> | <digit>}
Следствием этой грамматики является то, что отдельно взятый символ "_" является корректным идентификатором. И хотя это может на первый взгляд показаться абсурдным, тем не менее, именно таковы общепринятые правила. Легко убедиться, что, например, Delphi допускает объявление переменных с именем "_".
В нашей грамматике переменной будет называться отдельно стоящий идентификатор, функцией - идентификатор, после которого в скобках записан аргумент, в качестве которого может выступать любое допустимое выражение (для простоты мы будем рассматривать только функции с одним аргументом, т.к. обобщение грамматики на большее число аргументов очевидно). Другими словами, определение будет выглядеть так:
Код:
<Variable> ::= <Identifier>
<Function> ::= <Identifier> '(' <Expr> ')'
Из приведённых определений видно, что грамматика, использующая их, не относится к классу LR(1)-грамматик, т.к. обнаружив в выражении идентификатор, анализатор не может сразу решить, является ли этот идентификатор переменной или именем функции, это выяснится только при проверки следующего символа - скобка это или нет. Тем не менее, реализация такой грамматики достаточно проста, и это не будет доставлять нам существенных неудобств.
Переменные и функции, так же, как и выражения, заключённые в скобки, выступают в роли множителей. Соответственно, их появление в грамматике учитывается расширением смысла символа <Factor>.
Код:
<Factor> ::= <UnaryOp> <Factor> |
<Variable> |
<Function> |
<Number> |
'(' <Expr> ')'
Теперь рассмотрим свойства оператора возведения в степень. Во-первых, его приоритет выше, чем у операций сложения и деления, т.е. выражение "a*b^c" трактуется как "a*(b^c)", а "a^b*c" - как "(a^b)*c". Во-вторых, он правоассоциативен, т.е. "a^b^c" означает "a^(b^c)", а не "(a^b)^c". В-третьих, его приоритет выше, чем приоритет унарных операций, т.е. "-a^b" означает "-(a^b)", а не "(-a)^b". Тем не менее, "a^-b" означает "a^(-b)".
Таким образом, мы видим, что показателем степени может быть любой отдельно взятый множитель, а основанием - число, переменная, функция или выражение в скобках, т.е. любой множитель, за исключением начинающегося с унарного оператора. Запишем это в виде БНФ.
Код:
<Factor> ::= <UnaryOp> <Factor> | <Base> ['^' <Factor>]
<Base> ::= <Variable> | <Function> | <Number> | '(' <Expr> ')'
Правая ассоциативность также заложена в этих определениях. Рассмотрим, как будет разбираться выражение "a^b^c". Сначала функция Factor (через вызов функции Base) выделит и вычислит множитель "a", а потом вызовет саму себя для вычисления остатка "b^c". Таким образом, а будет возведено в степень b^c, как это и требуют правила правой ассоциативности.
Вообще, вопросы правой и левой ассоциативности операторов, которые мы здесь опустили, оказывают влияние на то, как определяется грамматика языка. Более подробно об этом написано в [1].
Так как определения символов <Expr> и <Term> в нашей новой грамматике не изменились, не изменятся и соответствующие функции. Для реализации нового синтаксиса нам потребуется изменить функцию Factor и ввести новые функции Base, Identifier и Func (будем использовать такое сокращение, т.к. function в Delphi является зарезервированным словом). Идентификаторы будем полагать нечувствительными к регистру символов.
Для простоты обойдёмся тремя функциями: sin, cos и ln. Увеличение количества функций, допустимых в выражении - простая техническая задача, не представляющая особого интереса.
Если у нас появились переменные, то мы должны как-то хранить их значения, чтобы при вычислении выражения использовать их. В нашем примере мы будем хранить их в TStrings, получая доступ через свойство Values. С точки зрения производительности этот способ - один из самых худших, поэтому при создании реального калькулятора лучше придумать что-нибудь другое. Мы здесь будем использовать этот способ исключительно из соображений наглядности.
PHP код:
// Вычисление функции, имя которой передаётся через FuncName
function Func(const FuncName,S:string;var P:Integer):Extended;
var Arg:Extended;
begin
// Вычисляем аргумент
Arg:=Expr(S,P);
// Сравниваем имя функции с одним из допустимых
if AnsiCompareText(FuncName,'sin')=0 then
Result:=Sin(Arg)
else if AnsiCompareText(FuncName,'cos')=0 then
Result:=Cos(Arg)
else if AnsiCompareText(FuncName,'ln')=0 then
Result:=Ln(Arg)
else
raise ESyntaxError.Create('Неизвестная функция '+FuncName)
end;
// Выделение из строки идентификатора и определение,
// является ли он переменной или функцией
function Identifier(const S:string;var P:Integer):Extended;
var InitP:Integer;
IDStr,VarValue:string;
begin
// Запоминаем начало идентификатора
InitP:=P;
// Первый символ был проверен ещё в функции Base.
// Сразу переходим к следующему
Inc(P);
while (P<=Length(S)) and (S[P] in ['A'..'Z','a'..'z','_','0'..'9']) do
Inc(P);
// Выделяем идентификатор из строки
IDStr:=Copy(S,InitP,P-InitP);
// Если за ним стоит открывающая скобка - это функция
if (P<=Length(S)) and (S[P]='(') then
begin
Inc(P);
Result:=Func(IDStr,S,P);
// Проверяем, что скобка закрыта
if (P>Length(S)) or (S[P]<>')') then
raise ESyntaxError.Create('Ожидается ")" в позиции '+IntToStr(P));
Inc(P)
end
// если скобки нет - переменная
else
begin
VarValue:=Form1.ListBoxVars.Items.Values[IDStr];
if VarValue='' then
raise ESyntaxError.Create('Необъявленная переменная '+IDStr+
' в позиции '+IntToStr(P))
else
Result:=StrToFloat(VarValue)
end
end;
// Выделение подстроки, соответствующей ,
// и её вычисление
function Base(const S:string;var P:Integer):Extended;
begin
if P>Length(S) then
raise ESyntaxError.Create('Неожиданный конец строки');
// По первому символу подстроки определяем,
// какое это основание
case S[P] of
'(': // выражение в скобках
begin
Inc(P);
Result:=Expr(S,P);
// Проверяем, что скобка закрыта
if (P>Length(S)) or (S[P]<>')') then
raise ESyntaxError.Create('Ожидается ")" в позиции '+IntToStr(P));
Inc(P)
end;
'0'..'9': // Числовая константа
Result:=Number(S,P);
'A'..'Z','a'..'z','_': // Идентификатор (переменная или функция)
Result:=Identifier(S,P)
else
raise ESyntaxError.Create('Некорректный символ в позиции '+IntToStr(P))
end
end;
// Выделение подстроки, соответствующей ,
// и её вычисление
function Factor(const S:string;var P:Integer):Extended;
begin
if P>Length(S) then
raise ESyntaxError.Create('Неожиданный конец строки');
// По первому символу подстроки определяем,
// какой это множитель
case S[P] of
'+': // унарный "+"
begin
Inc(P);
Result:=Factor(S,P)
end;
'-': // унарный "-"
begin
Inc(P);
Result:=-Factor(S,P)
end
else
begin
Result:=Base(S,P);
if (P<=Length(S)) and (S[P]='^') then
begin
Inc(P);
Result:=Power(Result,Factor(S,P))
end
end
end
end;
Пример калькулятора называется FullCalcSample. Его интерфейс содержит новые элементы, с помощью которых пользователь может задавать значения переменных. В левой нижней части окна находится список переменных с их значениями (при запуске программы этот список пустой). Правее находятся поля ввода "Имя переменной" и "Значение переменной", а так же кнопка "Установить". В первое поле следует ввести имя переменной, во второе - её значение. При нажатии на кнопку "Установить" переменная будет внесена в список, а если переменная с таким именем уже есть в списке, то её значение будет обновлено. Все переменные, которые есть в списке, могут использоваться в выражении. Если требуемая переменная в списке не найдена, попытка вычислить выражение приводит к ошибке.
Заметим, что символ <Factor> можно было бы определить несколько иначе:
Код:
<Factor> ::= [<UnaryOp>] <Base> ['^' <Factor>]
В нашем случае, когда есть только два унарных оператора, такой синтаксис реализовать было бы проще (пример реализации такого синтаксиса дан в программе FullCalcSample в виде комментария). При этом исчезла бы возможность ставить несколько знаков унарных операций подряд. В общем случае такой подход неверен, т.к. при большем количестве унарных операций эта возможность может пригодиться, да и выглядит она естественно. Поэтому в качестве основного был выбран несколько более сложный, но дающий больше возможностей вариант.
Калькулятор с лексическим анализатором
Прежде чем двигаться дальше, рассмотрим недостатки последней версии нашего калькулятора. Во-первых, бросается в глаза некоторое дублирование функций. Действительно, с одной стороны, выделением числа из подстроки занимается функция Number, но в функции Base также содержится проверка первого символа числа. Функция Identifier также частично дублируется функцией Base.
Второй недостаток - нельзя вставлять разделители, облегчающие чтение выражения. Например, строка "2 + 2" не является допустимым выражением - следует писать "2+2", без пробелов. Если же попытаться учесть возможность вставки пробелов, придётся в разные функции писать много однотипного рутинного кода, который существенно усложнит восприятие программы.
Третий недостаток - сложность введения новых операторов, которые обозначаются не одним символом, а несколькими, например: ">=", "and", "div". Если посмотреть функции Expr и Term, которые придётся в этом случае переделывать, видно, что переделка будет достаточно сложна.
Решить все эти проблемы позволяет лексический анализатор, который выделяет из строки все лексемы, пропуская пробелы и иные разделители, и определяет тип каждой лексемы, не заботясь о том, насколько уместно появление данной лексемы в данном месте выражения. А после лексического анализа начинает работать анализатор синтаксический, который будет иметь дело не с отдельными символами строки, а с целыми лексемами.
В качестве примера рассмотрим реализацию следующей грамматики.
Код:
<Expr> ::= <MathExpr> [<Comparison> <MathExpr>]
<Comparison> ::= '=' | '>' | '<' | '>=' | '<=' | '<>'
<MathExpr> ::= <Term> {<Operator1> <Term>}
<Operator1> ::= '+' | '-' | 'or' | 'xor'
<Term> ::= <Factor> {<Operator2> <Factor>}
<Operator2> ::= '*' | '/' | 'div' | 'mod' | 'and'
<Factor> ::= <UnaryOp> <Factor> | <Base> ['^' <Factor>]
<UnaryOp> ::= '+' | '-' | 'not'
<Base> ::= <Variable> | <Function> | <Number> | '(' <MathExpr> ')'
<Function> ::= <FuncName> '(' <MathExpr> ')'
<FuncName> ::= 'sin' | 'cos' | 'ln'
<Variable> ::= <Letter> {<Letter> | <digit>}
<Letter> ::= 'A' | ... | 'Z' | 'a' | ... | 'z' | '_'
<digit> ::= '0' | ... | '9'
<Number> ::= <digit> {<digit>} ['.' <digit> {<digit>}]
[('E' | 'e') ['+' | '-'] <digit> {<digit>}]
Эта грамматика на первый взгляд может показаться существенно более сложной, чем всё, что мы реализовывали ранее, но это не так: просто здесь приведены определения всех без исключения символов. Определение символа <Number> несколько изменено, но это касается только формы его представления - синтаксис числа остался без изменения. То, что раньше называлось <Expr>, теперь называется <MathExpr>, а выражение <Expr> состоит из одного <MathExpr>, с которым, возможно, сравнивается другое <MathExpr>. Семантика <Expr> такова: если в выражении присутствует только обязательная часть, результатом будет число, которое получилось в результате вычисления <MathExpr>. Если же имеется необязательное сравнение с другим <MathExpr>, то результатом будет "True" или "False" в зависимости от результатов сравнения.
В новой грамматике также расширен набор операторов. Операторы or, xor, and и not являются арифметическими, т.е. применяются к числовым, а не к логическим выражениям. Все операторы, которые применимы только к целым числам (т.е. вышеперечисленные, а также div и mod), игнорируют дробную часть своих аргументов.
Лексический анализатор должен выделять из строки следующие лексемы:
- Все знаки операций, которые используются в определении символов <Comparison>, <Operator1>, <Operator2>, <UnaryOp>, а также символ "^".
- Открывающую и закрывающую скобки.
- Имена функций.
- Идентификаторы (т.е. переменные).
- Числовые константы.
Напомним, что лексический анализатор не должен определять допустимость появления лексемы в данном месте строки. Он просто сканирует строку, выделяет из неё последовательности символов, распознаваемые как отдельные лексемы, и сохраняет информацию о них в специальном списке, которым потом пользуется синтаксический анализатор. Так, например, встретив цифру, лексический анализатор выделяет числовую константу. Встретив букву, он выделяет последовательность буквенно-цифровых символов. Затем сравнивает эту последовательность с одним из зарезервированных слов ("and", "div" и т.п.) и распознаёт лексему соответственно как идентификатор (переменную) или как зарезервированное слово. При этом выяснение, объявлена ли такая переменная, также не входит в обязанности лексического анализатора - это потом сделает синтаксический анализатор.
Из нашей грамматики следует, что имена функций являются зарезервированными словами, т.е. объявить переменные с именами "sin", "cos" и "ln", в отличие от предыдущего примера, нельзя. Это само по себе не упрощает и не усложняет задачу (просто при использовании в качестве имён функций зарезервированных слов эти имена распознаёт лексический анализатор, а при использовании идентификаторов - синтаксический).
Отдельные лексемы выделяются по следующему алгоритму: сначала, начиная с текущей позиции, пропускаются все разделители - пробелы и символы перевода строки. Затем по первому символу определяется лексема - знак, слово (которое потом может оказаться зарезервированным словом или идентификатором) или число. Дальше лексический анализатор выбирает из строки все символы до тех пор, пока они удовлетворяют правилам записи соответствующей лексемы. Следующая лексема ищется с позиции, идущей непосредственно за предыдущей лексемой.
В зависимости от типа лексем разделители между ними могут быть обязательными или необязательными. Например, в выражении "2+3" разделители между лексемами "2", "+" и "5" не нужны, потому что они могут быть отделены друг от друга и без этого. А вот в выражении "6 div 3" разделитель между "div" и "3" необходим, потому что в противном случае эти лексемы будут восприняты как идентификатор "div3". А вот разделитель между "6" и "div" не обязателен, т.к. "6div" не является допустимым идентификатором, и анализатор сможет отделить эти лексемы друг от друга и без разделителя. Вообще, если подстрока, получающаяся в результате слияния двух лексем, может быть целиком интерпретирована как какая-либо другая лексема, разделитель между ними необходим, в противном случае - необязателен. Разделитель внутри отдельной лексемы не допускается (т.е. подстрока "a 1" будет интерпретироваться как последовательность лексем "a" и "1", а не как лексема "a1").
Чтобы продемонстрировать возможности лексического анализатора, добавим поддержку комментариев. Комментарий - это последовательность символов, начинающаяся с "{" и заканчивающаяся "}", которая может содержать внутри себя любые символы, кроме "}". Комментарий считается разделителем, он допустим в любом месте, где допустимо появление других разделителей, т.е. в начале и в конце строки и между лексемами.
Пример калькулятора с лексическим анализатором находится в архиве и называется LexicalSample. Мы не будем приводить в тексте статьи выдержки кода, ограничимся только рассмотрением общих принципов его работы.
Лексический анализатор на входе получает строку, на выходе он должен дать список структур, каждая из которых описывает одну лексему. В нашем примере эти структуры выглядят следующим образом:
Код:
TLexeme=record
LexemeType:TLexemeType;
Pos:Integer;
Lexeme:string
end;