4.8. Калькулятор с лексическим анализатором
Прежде чем двигаться дальше, рассмотрим недостатки последней версии нашего калькулятора. Во-первых, бросается в глаза некоторое дублирование функций. Действительно, с одной стороны, выделением числа из подстроки занимается функция Number, но в функции Base также содержится проверка первого символа числа. Функция Identifier тоже частично дублируется функцией Base.
Второй недостаток — нельзя вставлять разделители, облегчающие чтение выражения. Например, строка "2 + 2" не является допустимым выражением — следует писать "2+2" (без пробелов). Если же попытаться учесть возможность вставки пробелов, придется в разные функции добавлять много однотипного рутинного кода, который существенно усложнит восприятие программы.
Третий недостаток — сложность введения новых операторов, которые обозначаются не одним символом, а несколькими, например, >=, and, div. Если посмотреть функции Expr и Term, которые придется в этом случае модифицировать, видно, что переделка будет достаточно сложной.
Решить все эти проблемы позволяет лексический анализатор, который выделяет из строки все лексемы, пропуская пробелы и иные разделители, и определяет тип каждой лексемы, не заботясь о том, насколько уместно ее появление в данной позиции выражения. А после лексического анализа начинает работать анализатор синтаксический, который будет иметь дело не с отдельными символами строки, а с целыми лексемами
В качестве примера рассмотрим реализацию следующей грамматики (листинг 4.10).
Листинг 4.10. Грамматика калькулятора с лексическим анализатором
<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>} [<DecimalSeparator> <Digit> {<Digit>}]
(('E' | 'e') ['+' | '-'] <Digit> {<Digit>)]
Примечание
Здесь используется нетерминальный символ <DecimalSeparator>, который мы не определили. Он полагается равным точке или запятой в зависимости от системных настроек.
Эта грамматика на первый взгляд может показаться существенно более сложной, чем все, что мы реализовывали ранее, но это не так: просто здесь приведены определения всех (за исключением <DecimalSeparator>) нетерминальных символов. Определение символа <Number> несколько изменено, но это касается только формы его представления — синтаксис числа остался без изменения. То, что раньше обозначалось как <Expr>, теперь называется <MathExpr>, а выражение <Expr> состоит из одного <MathExpr>, с которым, возможно, сравнивается другое <MathExpr>. Семантика <Expr> такова: если в выражении присутствует только обязательная часть, результатом будет число, которое получилось при вычислении <MathExpr>. Если же имеется необязательное сравнение с другим <MathExpr>, то результатом будет "True" или "False" в зависимости от результатов сравнения.
В новой грамматике также расширен набор операторов. Операторы or, xor, and и not здесь арифметические, т.е. применяются к числовым, а не к логическим выражениям. Все операторы, которые применимы только к целым числам (т.е. вышеперечисленные, а также div и mod), игнорируют дробную часть своих аргументов.
Лексический анализатор должен выделять из строки следующие лексемы:
1. Все знаки операций, которые используются в определении символов <Comparison>, <Operator1>, <Operator2>, <UnaryOp>, а также символ "^".
2. Открывающую и закрывающую скобки.
3. Имена функций.
4. Идентификаторы (т.е. переменные).
5. Числовые константы.
Напомним, что лексический анализатор не должен определять допустимость появления лексемы в данном месте строки. Он просто сканирует строку, выделяет из нее последовательности символов, распознаваемые как отдельные лексемы, и сохраняет информацию о них в специальном списке, которым потом пользуется синтаксический анализатор. Так, например, встретив цифру, лексический анализатор выделяет числовую константу. Встретив букву, он выделяет последовательность буквенно-цифровых символов. Затем сравнивает эту последовательность с одним из зарезервированных слов (and, div и т.п.) и распознает лексему соответственно как идентификатор (переменную) или как зарезервированное слово. При этом выяснение, объявлена ли такая переменная, также не входит в обязанности лексического анализатора — это потом сделает синтаксический анализатор.
Из нашей грамматики следует, что имена функций являются зарезервированными словами, т.е. объявить переменные с именами sin, cos и ln в отличие от предыдущего примера, нельзя. Это само по себе не упрощает и не усложняет задачу, а сделано только в качестве демонстрации возможной альтернативы (просто если именами служат зарезервированные слова, то их распознает лексический анализатор, а если идентификаторы, то синтаксический).
Отдельные лексемы выделяются по следующему алгоритму: сначала, начиная с текущей позиции, пропускаются все разделители — пробелы и символы перевода строки. Затем по первому символу определяется лексема — знак, слово (которое потом может оказаться зарезервированным словом или идентификатором) или число. Дальше лексический анализатор выбирает из строки все символы до тех пор, пока они удовлетворяют правилам записи соответствующей лексемы. Следующая лексема ищется с позиции, идущей непосредственно за предыдущей лексемой.
В зависимости от типа лексем разделители между ними могут быть обязательными или необязательными. Например, в выражении "2+3" разделители между лексемами "2", "+" и "5" не нужны, потому что они могут быть отделены друг от друга и без этого. А в выражении 6 div 3 разделитель между "div" и "3" необходим, потому что в противном случае эти лексемы будут восприняты как идентификатор div3. А вот разделитель между "6" и "div" не обязателен, т.к. 6div не является допустимым идентификатором, и анализатор сможет отделить эти лексемы друг от друга и без разделителя. Вообще, если подстрока, получающаяся в результате слияния двух лексем, может быть целиком интерпретирована как какая-либо другая лексема, разделитель между ними необходим, в противном случае — необязателен. Разделитель внутри отдельной лексемы не допускается (т.е. подстрока "a 1" будет интерпретироваться как последовательность лексем "а" и "1", а не как лексема "а1").
Чтобы продемонстрировать возможности лексического анализатора, добавим поддержку комментариев. Комментарий — это последовательность символов, начинающаяся с "{" и заканчивающаяся "}", которая может содержать внутри себя любые символы, кроме "}". Комментарий считается разделителем, он допустим в любом месте, где возможно появление других разделителей, т.е. в начале и в конце строки и между лексемами.
Пример калькулятора с лексическим анализатором также находится на компакт-диске и называется LexicalSample.
Лексический анализатор на входе получает строку, на выходе он должен дать список структур, каждая из которых описывает одну лексему. В нашем примере эти структуры выглядят следующим образом (листинг 4.11).
Листинг 4.11. Тип TLexeme для хранения информации об одной лексеме
TLexemeType = (
ltEqual, ltLess, ltGreater, ltLessOrEqual,
ltGreaterOrEqual, ltNotEqual, ltPlus, ltMinus,
ltOr, ltXor, ltAsterisk, ltSlash, ltDiv, ltMod,
ltAnd, ltNot, ltCap,
ltLeftBracket, ltRightBracket,
ltSin, ltCos, ltLn,
ltIdentifier, ltNumber, ltEnd);
TLexeme = record
LexemeType: TLexemeType;
Pos: Integer;
Lexeme: string;
end;
LexemeType — поле, содержащее информацию о том, что это за лексема. Тип TLexemeType — это специально определенный перечислимый тип, каждое из значений которого соответствует одному из возможных типов лексемы. Поле Pos хранит номер позиции в строке, начиная с которой идет данная лексема. Это поле нужно только для того, чтобы синтаксический анализатор мог точно указать место ошибки, если встретит недопустимую лексему.
Поле Lexeme хранит саму подстроку, распознанную как лексема. Оно используется, только если тип лексемы равен ltIdentifier или ltNumber. Для остальных типов лексем достаточно информации из поля LexemeType.
Лексический анализатор реализован в виде класса TLexicalAnalyzer. В конструкторе класса выполняется разбор строки и формирование списка лексем. Через этот же класс синтаксический анализатор получает доступ к лексемам: свойство Lexeme возвращает текущую лексему, метод Next позволяет перейти к следующей. Так как наша грамматика предусматривает разбор слева направо, таких примитивных возможностей навигации синтаксическому анализатору вполне хватает. Код анализатора показан в листинге 4.12.
Листинг 4.12. Код лексического анализатора
type
TLexicalAnalyzer = class
private
FLexemeList: TList;
// Номер текущей лексемы в списке
FIndex: Integer;
function GetLexeme: PLexeme;
// Пропуск всего, что является разделителем лексем
procedure SkipWhiteSpace(const S: string; var P: Integer);
// Выделение лексемы, начинающейся с позиции P
procedure ExtractLexeme(const S: string; var P: Integer);
// Помещение лексемы в список
procedure PutLexeme(LexemeType: TLexemeType; Pos: Integer; const Lexeme: string);
// Выделение лексемы-числа
procedure Number(const S: string; var P: Integer);
// Выделение слова и отнесение его к идентификаторам
// или зарезервированным словам
procedure Word(const S: string; var P: Integer);
public
constructor Create(const Expr: string);
destructor Destroy; override;
// Переход к следующей лексеме
procedure Next;
// Указатель на текущую лексему
property Lexeme: PLexeme read GetLexeme;
end;
constructor TLexicalAnalyzer.Create(const Expr: string);
var
P: Integer;
begin
inherited Create;
// Создаем список лексем
FLexemeList := TList.Create;
// И сразу же заполняем его
Р := 1;
while Р <= Length(Expr) do
begin
SkipWhiteSpace(Expr, P);
ExtractLexeme(Expr, P);
end;
// Помещаем в конец списка специальную лексему
PutLexeme(ltEnd, Р, '');
FIndex := 0;
end;
destructor TLexicalAnalyzer.Destroy;
var
I: Integer;
begin
for I := 0 to FLexemeList.Count - 1 do
Dispose(PLexeme(FLexemeList[I]));
FLexemeList.Free;
inherited Destroy;
end;
// Получение указателя на текущую лексему
function TLexicalAnalyzer.GetLexeme: PLexeme;
begin
Result := FLexemeList[FIndex];
end;
// Переход к следующей лексеме
procedure TLexicalAnalyzer.Next;
begin
if FIndex < FLexemeList.Count - 1 then Inc(FIndex);
end;
// Помещение лексемы в список. Параметры метода задают
// одноименные поля типа TLexeme.
procedure TLexicalAnalyzer.PutLexeme(LexemeType: TLexemeType; Pos: Integer; const Lexeme: string);
var
NewLexeme: PLexeme;
begin
New(NewLexeme);
NewLexeme^.LexemeType := LexemeType;
NewLexeme^.Pos := Pos;
NewLexeme^.Lexeme := Lexeme;
FLexemeList.Add(NewLexeme);
end;
// пропускает пробелы, символы табуляции, комментарии и переводы строки,
// которые могут находиться в начале и в конце строки и между лексемами
procedure TLexicalAnalyzer.SkipWhiteSpace(const S: string; var P: Integer);
begin
while (P <= Length(S)) and (S[P] in [' ', #9, #13, #10, '{']) do
if S[P] = '{' then
begin
Inc(P);
while (P <-=Length(S)) and (S[P) <> '}') do Inc(P);
if P > Length(S) then
raise ESyntaxError.Create('Незавершенный комментарий');
Inc(P);
end
else Inc(P);
end;
// Функция выделяет одну лексему и помещает ее в список
procedure TLexicalAnalyzer.ExtractLexeme(const S: string; var P: Integer);
begin
if P > Length(S) then Exit;
case S[P] of
'(': begin
PutLexeme(ltLeftBracket, P, '');
Inc(P);
end;
')': begin
PutLexeme(ltRightBracket, P, '');
Inc(P);
end;
'*': begin
PutLexeme(ltAsterisk, P, '');
Inc(P);
end;
'+': begin
PutLexeme(ltPlus, P, '');
Inc(P);
end;
'-': begin
PutLexeme(ltMinus, P, '');
Inc(P);
end;
'/': begin
PutLexeme(ltSlash, P, '');
Inc(P);
end;
'0'..'9': Number(S, P);
'<':if (P < Length(S)) and (S[P + 1] = '=') then
begin
PutLexeme(ltLessOrEqual, P, '');
Inc(P, 2);
end
else
if (P < Length(S)) and (S[P + 1] = '>') then
begin
PutLexeme(ltNotEqual, P, '');
Inc(P, 2);
end
else
begin
PutLexeme(ltLess, P, '');
Inc(P);
end;
'=': begin
PutLexeme(ltEqual, P, '');
Inc(P);
end;
'>': if (P < Length(S)) and (S[P + 1] = '=') then
begin
PutLexeme(ltGreaterOrEqual, P, '');
Inc(P, 2);
end
else
begin
PutLexeme(ltGreater, P, '');
Inc(P);
end;
'A'..'Z, 'a'..'z', '_': Word(S, P);
'^': begin
PutLexeme(ltCap, P, '');
Inc(P);
end;
else
raise ESyntaxError.Create('Некорректный символ в позиции ' +
IntToStr(Р));
end;
end;
// Выделение лексемы-числа
procedure TLexicalAnalyzer.Number(const S: string; var P: Integer);
var
InitPos, RollbackPos: Integer;
function IsDigit(Ch: Char): Boolean;
begin
Result := Ch in ['0'..'9'];
end;
begin
InitPos := P;
// Выделяем целую часть числа
repeat
Inc(P);
until (P < Length(S)) or not IsDigit(S[P]);
// Проверяем наличие дробной части и выделяем её
if (Р <= Length(S)) and (S[P] = DecimalSeparator) then
begin
Inc(P);
if (Р > Length(S)) or not IsDigit(S[P]) then Dec(P)
else repeat
Inc(P);
until (P > Length(S)) or not IsDigit(S(P));
end;
// Выделяем экспоненту
if (P <= Length(S)) and (UpCase(S[P]) = 'E') then
begin
// Если мы дошли до этого места, значит, от начала строки
// и до сих пор набор символов представляет собой
// синтаксически правильное число без экспоненты.
// Прежде чем начать выделение экспоненты, запоминаем
// текущую позицию, чтобы иметь возможность вернуться к ней
// если экспоненту выделить не удастся.
RollBackPos := P;
Inc(Р);
if Р > Length(S) then P := RollBackPos
else
begin
if S[P] in ['+', '-'] then Inc(P);
if (P > Length(S)) or not IsDigit(S(P)) then P := RollbackPos
else repeat
Inc(P);
until (P > Length(S)) or not IsDigit(S[P]);
end;
end;
PutLexeme(ltNumber, InitPos, Copy(S, InitPos, P- InitPos));
end;
// Выделение слова из строки и проверка его на совпадение
// с зарезервированными словами языка
procedure TLexicalAnalyzer.Word(const S: string; var P: Integer);
var
InitPos: Integer;
ID: string;
begin
InitPos := P;
Inc(P);
while (P <= Length(S)) and
(S[P] in ['0'..'9', 'A'..'Z', 'a'..'z', '_']) do
Inc(P);
ID := Copy(S, InitPos, P - InitPos);
if AnsiCompareText(ID, 'or') = 0 then
PutLexeme(ltOr, InitPos, '')
else if AnsiCompareText(ID, 'xor') = 0 than
PutLexeme(ltXor, InitPos, '')
else if AnsiCompareText(ID, 'div') = 0 then
PutLexeme(ltDiv, InitPos, '')
else if AnsiCompareText(ID, 'mod') = 0 then
PutLexeme(ltMod, InitPos, '')
else if AnsiCompareText(ID, 'and') = 0 then
PutLexeme(ltAnd, InitPos, '')
else if AnsiCompareText(ID, 'not') = 0 then
PutLexeme(ltNot, InitPos, '')
else if AnsiCompareText(ID, 'sin') = 0 then
PutLexeme(ltSin, InitPos, '')
else if AnsiCompareText(ID, 'cos') = 0 then
PutLexeme(ltCos, InitPos, '')
else if AnsiCompareText(ID, 'ln') = 0 then
PutLexeme(ltLn, InitPos, '')
else PutLexeme(ltIdentifier, InitPos, ID);
end;
В конец списка лексем помещается специальная лексема типа ltEnd. В предыдущих примерах приходилось постоянно сравнивать указатель позиции P с длиной строки S, чтобы не допустить выход за пределы диапазона. Если бы не было лексемы ltEnd, точно так же пришлось бы проверять, не вышел ли указатель за пределы списка. Но лексема ltEnd не рассматривается как допустимая ни одной из функций синтаксического анализатора, поэтому, встретив ее, каждая из них возвращает управление вызвавшей ее функции, и заканчивается эта цепочка только на функции Expr. Таким образом, код получается более ясным и компактным.
Примечание
Аналогичный алгоритм возможен и в предыдущих версиях калькулятора: достаточно добавить в конец строки символ, который в ней заведомо не должен был появляться (например, #1), и проверять в функции Expr или Calculate, что разбор выражения остановился именно на этом символе.
Лексический анализ выражения заключается в чередовании вызовов функций SkipWhiteSpace и ExtractLexeme. Первая из них пропускает все, что может разделять две лексемы, вторая распознает и помещает в список одну лексему.
Обратите внимание, как в лексическом анализаторе реализован метод Number. Рассмотрим выражение "1е*5". В калькуляторе без лексического анализатора функция Number, дойдя до символа "*" выдавала исключение, т.к. ожидала увидеть здесь знак "+", или число. Но лексический анализатор не должен брать на себя такую ответственность — поиск синтаксических ошибок. Поэтому в данном случае он должен, дойдя до непонятного символа в конструкции, которую он счел за экспоненту, откатиться назад, выделить из строки лексему "1" и продолжить выделение лексем с символа "е". В результате список лексем будет выглядеть так: "1, "е", "*", "5". И уже синтаксический анализатор должен потом разобраться, допустима ли такая последовательность лексем или нет.
Отметим, что для нашей грамматики непринципиально, зафиксирует ли в таком выражении ошибку лексический или синтаксический анализатор. Но в общем случае может существовать грамматика, в которой такое выражение допустимо, поэтому лексический анализатор должен действовать именно так, т.е. выполнять откат, если попытка выделить число зашла на каком-то этапе в тупик (самый простой пример — наличие в языке бинарного оператора, начинающегося с символа "е" — тогда пользователь сможет написать этот оператор после числа без пробела, и чтобы справиться с такой ситуацией, понадобится откат). Функция Number вызывается из ExtractLexeme только в том случае, когда в начале лексемы встречается цифра, а с цифры может начинаться только лексема ltNumber. Таким образом, сам факт вызова функции Number говорит о том, что в строке гарантированно обнаружена подстрока (состоящая, по крайней мере, из одного символа), которая является числом. Функции синтаксического анализатора очень похожи на аналогичные функции из предыдущих примеров, за исключением того, что работают не со строкой, а со списком лексем. Поэтому мы приведем здесь только одну из них — функцию Term (листинг 4.13).
Листинг 4.13. Пример функции, использующей лексический анализатор
const
Operator2 = (ltAsterisk, ltSlash, ltDiv, ltMod, ltAnd);
function Term(LexicalAnalyzer: TLexicalAnalyzer): Extended;
var
Operator: TLexemeType;
begin
Result := Factor(LexicalAnalyzer);
while LexicalAnalyzer.Lexeme.LexemeType in Operator2 do
begin
Operator := LexicalAnalyzer.Lexeme.LexemeType;
LexicalAnalyzer.Next;
case Operator of
ltAsterisk: Result := Result * Factor(LexicalAnalyzer);
ltSlash: Result := Result / Factor(LexicalAnalyzer);
ltDiv: Result := Trunc(Result) div Trunc(Factor(LexicalAnalyzer));
ltMod: Result := Trunc(Result) mod Trunc(Factor(LexicalAnalyzer));
ltAnd: Result := Trunc(Result) and Trunc(Factor(LexicalAnalyzer));
end;
end;
end;
Если сравнить этот вариант Term с аналогичной функцией из листинга 42, легко заметить их сходство.
Использование лексического анализатора может повысить скорость многократного вычисления одного выражения при разных значениях входящих в него переменных (например, при построении графика функции, ввезенной пользователем). Действительно, лексический анализ в этом случае достаточно выполнить один раз, а потом пользоваться готовым списком. Можно сделать такие операции еще более эффективными, переложив вычисление числовых констант на лексический анализатор. Для этого в структуру TLexeme нужно добавить поле Number типа Extended и модифицировать метод Number таким образом, чтобы он сразу преобразовывал выделенную подстроку в число. Тогда дорогостоящий вызов функции StrToFloat будет перенесен из многократно повторяющейся функции Base в однократно выполняемый метод TLexicalAnalyzer.Number. Но самое радикальное средство повышения производительности — переделка синтаксического анализатора таким образом, чтобы он не вычислял выражение самостоятельно, а формировал машинный код для его вычисления. Однако написание компилятора математических выражений выходит за рамки данной книги.
