А. Григорьев - О чём не пишут в книгах по Delphi

В предыдущем примере выражение сначала от начала до конца просматривается лексическим анализатором и переводится в иную форму (список лексем). Затем этот список обрабатывается синтаксическим анализатором. Таким образом, калькулятор получается двухпроходным, хотя из синтаксиса и семантики выражения необходимость нескольких проходов не вытекает. Попробуем переделать его так, чтобы он стал однопроходным.

В некоторых языках многопроходность — обязательное требование к реализации компилятора. Например, в языке C++ реализацию функций класса можно вставлять в само описание класса. При этом внутри этих функций можно обращаться к тем полям и функциям класса, которые объявлены ниже. Таким образом, откомпилировать подобный код может только компилятор как минимум с двумя проходами, чтобы на первом проходе можно было найти все поля класса, а на втором — откомпилировать функции класса.

В предыдущей реализации калькулятора синтаксический анализатор работал с лексическим через процедуру Nextи свойство Lexeme: процедура Nextпередвигала текущую позицию в списке лексем, а свойство Lexemeдавало доступ к текущей лексеме. Легко видеть, что при таком алгоритме лексическому анализатору нет необходимости хранить полный список лексем, достаточно помнить текущую, а при вызове Nextанализировать очередную часть строки, выделяя из нее следующую лексему и делая ее текущей. Таким образом, синтаксический и лексический анализаторы будут работать по очереди, обрабатывая каждый по одной лексеме.

В реализации лексического анализатора требуются следующие изменения. Во-первых, теперь конструктор не запускает полный цикл лексического анализа, а только сохраняет переданную строку и выделяет из нее первую лексему. Во-вторых, выражение и позиция в выражении теперь должны сохраняться между вызовами методов лексического анализатора и поэтому становятся полями этого класса. В-третьих, метод Nextтеперь выполняет выделение очередной лексемы, которую помещает в специально созданное для этого поле, а свойство Lexemeвозвращает указатель на это поле, а не на элемент списка. Остальные функции лексического анализатора изменились только в том отношении, что теперь выражение и указатель на позицию в строке получают не через параметры, а напрямую обращаются к соответствующим полям.

Пример однопроходного калькулятора с лексическим анализатором находится на компакт-диске в папке SinglePassSample. В листинге 4.14 показан код той части нового варианта класса TLexicalAnalyzer, которую понадобилось изменить, чтобы обеспечить однопроходность.

type

TLexicalAnalyzer = class

private

// Выражение для вычисления

FExpr: string;

// Текущая позиция

FP: Integer;

// Текущая лексема

FCurrLexeme: TLexeme;

function GetLexeme: PLexeme;

procedure SkipWhiteSpace;

procedure ExtractLexeme;

procedure PutLexeme(LexemeType: TLexemeType; Pos: Integer; const Lexeme: string);

procedure Number;

procedure Word;

public

constructor Create(const Expr: string);

procedure Next;

property Lexeme: PLexeme read GetLexeme;

end;

constructor TLexicalAnalyzer.Create(const Expr: string);

begin

inherited Create;

FP := 1;

FExpr := Expr;

Next;

end;

// Получение указателя на текущую лексему

function TLexicalAnalyzer.GetLexeme: PLexeme;

begin

Result := @FCurrLexeme;

end;

// Получение следующей лексемы

procedure TLexicalAnalyzer.Next;

begin

if FP <= Length(FExpr) then

begin

SkipWhiteSpace;

ExtractLexeme;

end

else PutLexeme(ltEnd, FP, '');

end;

// Замещение текущей лексемы новой лексемой

procedure TLexicalAnalyzer.PutLexeme(LexemeType: TLexemeType; Pos: Integer; const Lexeme: string);

begin

FCurrLexeme.LexemeType := LexemeType;

FCurrLexeme.Pos := Pos;

FCurrLexeme.Lexeme := Lexeme;

end;

Теперь класс TLexicalAnalyzerхранит не список лексем, а только одну текущую лексему, а функция PutLexemeне добавляет лексему в список, а изменяет значение текущей лексемы. Функция Nextвместо простого изменения индекса выделяет очередную лексему, т.е. выполняет одну итерацию цикла лексического анализа. Функции SkipWhiteSpace, ExtractLexemeи т.п. избавились от параметров, через которые передавалось выражение и позиция, потому что теперь выражение и позиция хранятся в полях класса.

Синтаксический анализатор при этом остается без изменений, т.к. интерфейс лексического анализатора не изменился.

Чтобы не реализовывать дважды одну и ту же грамматику, введем в наш синтаксис еще одну возможность — поддержку функций с несколькими аргументами. Конкретно — функцию с двумя аргументами Log(а, x), возвращающей логарифм xпо основанию a, а также функцию Mean, которая принимает произвольное число аргументов и возвращает их среднее. Для этого правила, связанные с функциями, переопределим так:

::= '(' { } ')'

::= 'sin' | 'cos' | 'ln' | 'log' | 'mean'

Отдельного комментария требует символ , разделяющий аргументы в функции. В Delphi, как и во многих других языках программирования, таким разделителем служит запятая. Но наша грамматика определена так, что запятая, в принципе, может служить разделителем целой и дробной части числа. Как уже говорилось, в этом случае может возникнуть неоднозначность в выражениях типа f(1,5)— это вызов функции fто ли с одним аргументом 1.5, то ли с двумя аргументами 1 и 5. Чтобы избежать подобных неоднозначностей, в нашей грамматике разделителем аргументов будет символ, выбранный разделителем элементов списка (в русской локализации Windows это точка с запятой). Для корректной работы программы следите, чтобы на вашем компьютере разделители элементов списка, а также целой и дробной частей не оказались одинаковыми.

Особенность нашего нового синтаксиса в том, что он допускает любое число аргументов для любой функции, т.е., например, выражение sin(0, 1, 2, 4)синтаксически корректно (при условии, что разделителем элементов списка является запятая), хотя смысла это выражение не имеет. Можно было бы ввести отдельные синтаксические правила для функций с одним аргументом, с двумя аргументами и с произвольным числом аргументов, но такой подход встречается редко, т.к. обычно намного проще осуществить проверку на этапе семантического анализа (т.е. в нашем случае — при вычислении функции).

Для реализации новых синтаксических и семантических правил в код вносятся следующие изменения. Во-первых, появляются новые лексемы ltLog, ltMeanи ltListSeparator, а соответствующие методы лексического анализатора модифицируются так, чтобы распознавать их. Во-вторых, модифицируется функция Func— она сначала вычисляет все аргументы, переданные функции, а потом проверяет, является ли количество аргументов допустимым, и если да, вычисляет требуемую функцию.