Аналогичный алгоритм возможен и в предыдущих версиях калькулятора: достаточно добавить в конец строки символ, который в ней заведомо не должен был появляться (например,
#1
), и проверять в функции
Expr
или
Calculate
, что разбор выражения остановился именно на этом символе.
Лексический анализ выражения заключается в чередовании вызовов функций
SkipWhiteSpace
и
ExtractLexeme
. Первая из них пропускает все, что может разделять две лексемы, вторая распознает и помещает в список одну лексему.
Обратите внимание, как в лексическом анализаторе реализован метод
Number
.
Рассмотрим выражение "1е*5". В калькуляторе без лексического анализатора функция
Number
, дойдя до символа "*" выдавала исключение, т.к. ожидала увидеть здесь знак "+", или число. Но лексический анализатор не должен брать на себя такую ответственность — поиск синтаксических ошибок. Поэтому в данном случае он должен, дойдя до непонятного символа в конструкции, которую он счел за экспоненту, откатиться назад, выделить из строки лексему "1" и продолжить выделение лексем с символа "е". В результате список лексем будет выглядеть так: "1, "е", "*", "5". И уже синтаксический анализатор должен потом разобраться, допустима ли такая последовательность лексем или нет.
Отметим, что для нашей грамматики непринципиально, зафиксирует ли в таком выражении ошибку лексический или синтаксический анализатор. Но в общем случае может существовать грамматика, в которой такое выражение допустимо, поэтому лексический анализатор должен действовать именно так, т.е. выполнять откат, если попытка выделить число зашла на каком-то этапе в тупик (самый простой пример — наличие в языке бинарного оператора, начинающегося с символа "е" — тогда пользователь сможет написать этот оператор после числа без пробела, и чтобы справиться с такой ситуацией, понадобится откат). Функция
Number
вызывается из
ExtractLexeme
только в том случае, когда в начале лексемы встречается цифра, а с цифры может начинаться только лексема
ltNumber
. Таким образом, сам факт вызова функции
Number
говорит о том, что в строке гарантированно обнаружена подстрока (состоящая, по крайней мере, из одного символа), которая является числом. Функции синтаксического анализатора очень похожи на аналогичные функции из предыдущих примеров, за исключением того, что работают не со строкой, а со списком лексем. Поэтому мы приведем здесь только одну из них — функцию
Term
(листинг 4.13).
Листинг 4.13. Пример функции, использующей лексический анализатор
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
. Но самое радикальное средство повышения производительности — переделка синтаксического анализатора таким образом, чтобы он не вычислял выражение самостоятельно, а формировал машинный код для его вычисления. Однако написание компилятора математических выражений выходит за рамки данной книги.
4.9. Однопроходный калькулятор и функции с несколькими переменными
В предыдущем примере выражение сначала от начала до конца просматривается лексическим анализатором и переводится в иную форму (список лексем). Затем этот список обрабатывается синтаксическим анализатором. Таким образом, калькулятор получается двухпроходным, хотя из синтаксиса и семантики выражения необходимость нескольких проходов не вытекает. Попробуем переделать его так, чтобы он стал однопроходным.
Примечание
В некоторых языках многопроходность — обязательное требование к реализации компилятора. Например, в языке C++ реализацию функций класса можно вставлять в само описание класса. При этом внутри этих функций можно обращаться к тем полям и функциям класса, которые объявлены ниже. Таким образом, откомпилировать подобный код может только компилятор как минимум с двумя проходами, чтобы на первом проходе можно было найти все поля класса, а на втором — откомпилировать функции класса.
В предыдущей реализации калькулятора синтаксический анализатор работал с лексическим через процедуру
Next
и свойство
Lexeme
: процедура
Next
передвигала текущую позицию в списке лексем, а свойство
Lexeme
давало доступ к текущей лексеме. Легко видеть, что при таком алгоритме лексическому анализатору нет необходимости хранить полный список лексем, достаточно помнить текущую, а при вызове
Next
анализировать очередную часть строки, выделяя из нее следующую лексему и делая ее текущей. Таким образом, синтаксический и лексический анализаторы будут работать по очереди, обрабатывая каждый по одной лексеме.
В реализации лексического анализатора требуются следующие изменения. Во-первых, теперь конструктор не запускает полный цикл лексического анализа, а только сохраняет переданную строку и выделяет из нее первую лексему. Во-вторых, выражение и позиция в выражении теперь должны сохраняться между вызовами методов лексического анализатора и поэтому становятся полями этого класса. В-третьих, метод
Next
теперь выполняет выделение очередной лексемы, которую помещает в специально созданное для этого поле, а свойство
Lexeme
возвращает указатель на это поле, а не на элемент списка. Остальные функции лексического анализатора изменились только в том отношении, что теперь выражение и указатель на позицию в строке получают не через параметры, а напрямую обращаются к соответствующим полям.
Пример однопроходного калькулятора с лексическим анализатором находится на компакт-диске в папке
SinglePassSample
. В листинге 4.14 показан код той части нового варианта класса
TLexicalAnalyzer
, которую понадобилось изменить, чтобы обеспечить однопроходность.