4.9. Однопроходный калькулятор и функции с несколькими переменными
В предыдущем примере выражение сначала от начала до конца просматривается лексическим анализатором и переводится в иную форму (список лексем). Затем этот список обрабатывается синтаксическим анализатором. Таким образом, калькулятор получается двухпроходным, хотя из синтаксиса и семантики выражения необходимость нескольких проходов не вытекает. Попробуем переделать его так, чтобы он стал однопроходным.
Примечание
В некоторых языках многопроходность — обязательное требование к реализации компилятора.
Например, в языке C++ реализацию функций класса можно вставлять в само описание класса. При этом внутри этих функций можно обращаться к тем полям и функциям класса, которые объявлены ниже. Таким образом, откомпилировать подобный код может только компилятор как минимум с двумя проходами, чтобы на первом проходе можно было найти все поля класса, а на втором — откомпилировать функции класса.
В предыдущей реализации калькулятора синтаксический анализатор работал с лексическим через процедуру
Next
и свойство
Lexeme
: процедура
Next
передвигала текущую позицию в списке лексем, а свойство
Lexeme
давало доступ к текущей лексеме. Легко видеть, что при таком алгоритме лексическому анализатору нет необходимости хранить полный список лексем, достаточно помнить текущую, а при вызове
Next
анализировать очередную часть строки, выделяя из нее следующую лексему и делая ее текущей. Таким образом, синтаксический и лексический анализаторы будут работать по очереди, обрабатывая каждый по одной лексеме.
В реализации лексического анализатора требуются следующие изменения. Во-первых, теперь конструктор не запускает полный цикл лексического анализа, а только сохраняет переданную строку и выделяет из нее первую лексему. Во-вторых, выражение и позиция в выражении теперь должны сохраняться между вызовами методов лексического анализатора и поэтому становятся полями этого класса. В-третьих, метод
Next
теперь выполняет выделение очередной лексемы, которую помещает в специально созданное для этого поле, а свойство
Lexeme
возвращает указатель на это поле, а не на элемент списка. Остальные функции лексического анализатора изменились только в том отношении, что теперь выражение и указатель на позицию в строке получают не через параметры, а напрямую обращаются к соответствующим полям.
Пример однопроходного калькулятора с лексическим анализатором находится на компакт-диске в папке
SinglePassSample
. В листинге 4.14 показан код той части нового варианта класса
TLexicalAnalyzer
, которую понадобилось изменить, чтобы обеспечить однопроходность.
хранит не список лексем, а только одну текущую лексему, а функция
PutLexeme
не добавляет лексему в список, а изменяет значение текущей лексемы. Функция
Next
вместо простого изменения индекса выделяет очередную лексему, т.е. выполняет одну итерацию цикла лексического анализа. Функции
SkipWhiteSpace
,
ExtractLexeme
и т.п. избавились от параметров, через которые передавалось выражение и позиция, потому что теперь выражение и позиция хранятся в полях класса.
Синтаксический анализатор при этом остается без изменений, т.к. интерфейс лексического анализатора не изменился.
Чтобы не реализовывать дважды одну и ту же грамматику, введем в наш синтаксис еще одну возможность — поддержку функций с несколькими аргументами. Конкретно — функцию с двумя аргументами
Log(а, x)
, возвращающей логарифм
x
по основанию
a
, а также функцию Mean, которая принимает произвольное число аргументов и возвращает их среднее. Для этого правила, связанные с функциями, переопределим так: