Интерактивный интерпретатор

result:=1

5. Вычисление угла треугольника по трем сторонам.

angle [a,b,c]

#вычисляет угол треугольника со сторонами

#a, b и c между сторонами a и b (в градусах)

if ~isnum[a]|~isnum[b]|~isnum[c]

println "Invalid arguments"

error

endif

if (a<=0)|(b<=0)|(c<=0)

println "Not a triangle"

error

endif

cos_alpha:=(a*a+b*b-c*c)/(2*a*b)

if (cos_alpha>=1)|(cos_alpha<=-1)

println "Not a triangle"

error

endif

alpha:=arccos[cos_alpha]

result:=alpha*180/pi[]

Проектирование и реализация программы-интерпретатора

Для реализации интерпретатора было решено использовать платформу Microsoft .NET v.1.1 и язык программирования C#. Это связано с тем, что платформа .NET обеспечивает достаточно высокую производительность (быстродействие) приложений при значительном увеличении скорости разработки. Последнее обеспечивается за счет наличия удобных визуальных средств разработки, обширной и мощной стандартной библиотеки классов, использования автоматической сборки мусора, когда память из-под более неиспользуемых объектов освобождается автоматически. Язык C# же является основным языком платформы .NET, позволяющим полностью использовать все преимущества технологии Microsoft .NET, он имеет весьма гибкий синтаксис, позволяющий реализовывать достаточно сложные алгоритмы сравнительно небольшими, но легко читаемыми фрагментами кода.

В программе можно выделить две основные группы классов, две подсистемы, ответственные за логику работы интерпретатора и графический интерфейс пользователя соответственно. Поскольку первая подсистема содержит значительно большее число классов, чем вторая, было решено расположить ее в отдельном пространстве имен logic, вложенном в корневое пространство имен проекта. Классы, ответственные за графический интерфейс пользователя, расположены непосредственно в корневом пространстве имен проекта. Кроме того, в пространстве имен logic имеется два вложенных пространства имен - operators и vartypes, соответствующие двум основным иерархиям наследования в проекте - операторам программы и типам данных. Корневое пространство имен имеет имя interpr. Диаграмма пакетов проекта изображена на рис. 1.

Роль посредника между пользовательским интерфейсом и подсистемой, реализующей логику работы интерпретатора, выполняет класс Facade (фасад). Он также ответственен за создание отдельного потока для выполнения команд пользователя (вводимых с консоли). Выполнять их в том же потоке, что и обрабатывать сообщения пользовательского интерфейса нельзя так как в этом случае зациклившуюся пользовательскую функцию будет невозможно прервать. Многие методы класса Facade сводятся к простому вызову методов других классов из пространства имен logic. Этот класс в дальнейшем будет рассмотрен более подробно.

Для обработки ошибок применяется механизм структурной обработки исключений. При этом используются следующие классы пользовательских исключений (для ошибок в классах пространства имен interpr.logic):

· CalcException - ошибка по вине пользователя (синтаксическая или в вычислениях);

· SyntaxErrorException - синтаксическая ошибка, обнаруживаемая во время «компиляции», т. е. при загрузки функции или преобразования введенной команды во внутренний формат. Унаследован от CalcException;

· LineSyntaxException - синтаксическая ошибка в конкретном операторе функции. Содержит информацию об месте обнаружения (имя функции, строка).

· OtherException - ошибки, связанные с некорректной работой интерпретатора не по вине пользователя. Класс используется для отладочных целей. При нормальной работе такое исключение никогда не должно генерироваться.

· LinkedListException - ошибка в методах класса LinkedList. Унаследован от класса OtherException.

· NamespaceSerializationException - унаследован непосредственно от System.Exception. Такое исключение - генерируется если пространство имен консоли не может быть успешно восстановлено.

Соответствующая диаграмма классов изображена на рис. 2.

Можно выделить несколько групп классов в пространстве имен interpr.logic - классы, ответственные за вычисление выражений, за выполнение пользовательских функций, за преобразование текста команд и пользовательских функций во внутренний формат («компиляцию» текста программы), классы, участвующие в организации интерактивной работы интерпретатора. Эти группы классов, равно как и подсистема графического интерфейса пользователя, будут рассмотрены ниже. В пространстве имен interpr.logic также имеется один класс вспомогательного назначения - LinkedList. Он представляет двухсвязный список. В нем имеются методы и свойства добавления и чтения элементов в начале и конце списка, определения числа элементов списка. При этом, при попытке чтения из пустого списка, генерируется исключениеLinkedListException. Метод GetIterator(), существующий в двух перегруженных версиях (для первого элемента списка и для заданного индекса), возвращает объект вложенного класса LinkedList.Iterator, который представляет собой итератор, позволяющий читать элементы списка, перемещаясь по нему от начала к концу, а также двигаться в обратном направлении. Элемент списка представляется объектом частного вложенного класса Link, содержащего три поля с видимостью internal - одно для хранения значения элемента списка и два для ссылок на предыдущий и следующий элементы.

Следует также отметить интерфейс interpr.logic.IConsole, представляющий нечто, что может быть использовано для вывода текста. Он имеет два метода - void Print(string str) и void PrintLn(string str), назначение которых понятно из названия.

Основные классы пространства имен interpr.logic показаны на диаграмме на рис. 3.

Рис. 3.

Классы пространства имен interpr.logic.

Внутреннее представление и выполнение программы.

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

Обычная математическая запись арифметических выражений представляет собой так называемую инфиксную запись, в которой знаки операций располагаются между операндами. При этом для уточнения порядка вычисления операций используются приоритеты операций и круглые скобки. Такая форма записи удобна для человека, но неудобна для ЭВМ. Поэтому часто используют так называемую постфиксную или обратную польскую запись. В этом случае знак операции записываются после всех ее операндов, а вычисление производится по довольно простому алгоритму: выражение в ОПЗ последовательно просматриваем слева направо. Если встречаем операнд, то заносим его в стек, если же встречаем операцию, то выбираем ее операнды из стека, выполняем операцию и заносим результат в стек. В начале вычисления выражения стек пуст. Если выражение записано корректно, то при выполнении каждой операции число элементов стека будет не меньше числа ее операндов, и в конце процесса в стеке останется ровно одно значение - результат вычисления выражения. Особенностью ОПЗ является отсутствие необходимости в использовании скобок.

Например, выражение a+(b*c-d)/e в ОПЗ имеет вид abc*d-e/+. Применим к нему описанный выше алгоритм вычисления.

1. Заносим в стек a.

2. Заносим в стек b.

3. Заносим в стек c.

Состояние стека на этот момент: a, b, c - вершина.

4. Извлекаем из стека операнды операции умножения - b и c и заносим в стек результат.

Стек: a, b*c.

5. Заносим в стек d.

Стек: a, b*c, d.

6. Извлекаем из стека операнды, производим вычитание, заносим в стек результат.

Стек: a, b*c-d.

7. Заносим в стек e.

Стек: a, b*c-d, e.

8. Извлекаем из стека операнды, производим деление, заносим в стек результат.

Стек: a, (b*c-d)/e.

9. Извлекаем из стека операнды, производим сложение, заносим в стек результат.

Итого получаем в стеке a+(b*c-d)/e, что и требовалось.

Для представления выражений в интерпретаторе используется класс Expression. Он содержит обратную польскую запись выражения в виде связанного списка (однонаправленного). Звено этого списка, равно как и стека, используемого при вычислении выражения, представляется объектом вложенного класса Expression.Element, содержащим ссылки на следующее звено и на объект, реализующий интерфейс IComputable, который содержит один метод logic.vartypes.VarBase Compute() - получить значение. Вычисление значения выражения по рассмотренном выше алгоритму производится в методе VarBase Expression.Calculate(). Строка, содержащая запись выражения, обрабатывается в конструкторе этого класса. Интерфейс IComputable реализован тремя классами:

· VarBase - абстрактный класс, представляющий значение любого типа данных;

· VarName - представляет переменную по ее имени;

· Call - представляет вызов операции либо функции.

Вначале рассмотрим классы, представляющие значения различных типов. Все они являются потомками только что названного класса VarBase. Как было сказано выше, в языке существует четыре типа данных - целое число, вещественное число, строка и массив. При этом числовые и строковый типы, в противоположность массиву, называются простыми типами. Для простых значений базовым является абстрактный класс SingleVar. Целый и вещественный типы также особо выделяются как числовые, и для них существует свой базовый абстрактный класс NumVar. Наконец, каждому из четырех типов данных соответствует свой конкретный класс - IntVar, RealVar, StringVar и ArrayVar. Эта иерархия классов находится в пространстве имен interpr.logic.vartypes. Она изображена на диаграмме на рис. 4.

Рис. 4.

Классы пространства имен interpr.logic.vartypes.

Метод Compute() класса VarBase просто возвращает ссылку this. Методы IsArray(), IsSingle(), IsString(), IsNum(), IsInt(), IsReal() позволяют определить тип значения. Они используют оператор RTTI is языка C#. В классе VarBase объявлены абстрактными унаследованные от System.Object методы Clone() и ToString(), что требует обязательного их переопределения у неабстрактных потомков. Абстрактный метод Serialise() сохраняет объект (значение и его тип) в файле. Класс ArrayVar имеет методы для присвоения и получения значений отдельных элементов массива, получения размера массива, выяснения вопроса, определено ли значение элемента массива с заданным индексом. Класс SingleVar определяет абстрактный метод ToBool(), возвращающий логическое значение объекта. В классе NumVar также имеется абстрактный метод ToDouble(), возвращающий значение объекта как вещественное число. Эти классы и их потомки содержат также методы для выполнения над значениями арифметических и логических операций.

В виде объектов классов, производных от VarBase, в выражениях (экземплярах класса Expression), хранятся только константные значения. Переменные же представляются здесь объектами класса VarName, содержащими имя (идентификатор) переменной. Сами же значения переменных хранятся в объектах класса Namespace или производного от него ConsoleNamespace.

Класс Namespace представляет пространство имен (область видимости) пользовательской функции, класс ConsoleNamespace - среды консоли. При работе интерпретатора создается стек пространств имен (областей видимости), на вершине которого находится пространство имен выполняемой в данный момент функции, на дне - среды консоли. Каждый раз при вызове функции создается и добавляется на вершину стека новый объект Namespace, при выходе из функции он уничтожается. Класс Namespace имеет поле, содержащее ссылку на предыдущий элемент стека, у находящегося на дне стека объекта ConsoleNamespace оно всегда содержит нулевой указатель.

Ссылки на вершину и на дно стека пространств имен хранятся в полях класса InterprEnvironment. Доступ к текущему пространству имен осуществляется через его свойство CurrentNamespace. Для этого класса при запуске интерпретатора создается единственный объект, хранящийся в его статическом поле и возвращаемый статическим свойством только для чтения Instance. Таким образом, здесь использован паттерн Singleton. Класс InterprEnvironment выполняет несколько различных функций. Среди них, во-первых, хранение ссылки на объект IConsole, с помощью которого производится вывод. Во-вторых - работа с переменными среды консоли - их сохранение в файле, восстановление из файла (производится во время инициализации объекта при запуске или перезапуске интерпретатора), получение их списка. В-третьих - загрузка и хранение пользовательских функций. Последняя функция будет рассмотрена подробнее ниже.

Последний из классов, реализующих интерфейс IComputable, - класс Call представляет вызов операции, встроенной или пользовательской функции в выражении. Он имеет два поля. Первое из них хранит ссылку на объект класса ArgList, который содержит список операндов. Оно инициализируется методом SetArgList() при каждом выполнении операции или функции. Второе поле содержит ссылку на абстрактный класс Operation, который и представляет операцию или функцию. Этот класс содержит абстрактное свойство только для чтения ReqCount, возвращающее необходимое число операндов (аргументов). К этому свойству обращается свойство класса Call с таким же именем. Второй абстрактный член класса Operation, метод VarBase Perform(ArgList al), выполняет операцию (функцию) над аргументами, содержащимися в объекте ArgList, передаваемыми в качестве параметров. Этот метод возвращает значение, являющееся результатом операции (функции). Никакого аналога типа void не предусмотрено - операция (функция) может не вернуть то или иное значение лишь в случае ошибки. От класса Operation унаследован класс SubName, представляющий пользовательскую функцию по ее имени, и многочисленные классы, представляющие стандартные операции и встроенные функции. Последние являются вложенными в сам класс Operation, притом имеют спецификатор доступа private. Для каждого из них в классе Operation имеется открытое статическое поле только для чтения, инициализирующееся объектом соответствующего типа. Создание других объектов этих вложенных классов невозможно. Здесь также использован паттерн Singleton. Кроме того, можно говорить о применении паттерна Strategy - объект класса Call (контекст) конфигурируется объектом одного из классов, производных от Operation (стратегия), таким образом, для различного поведения (выполнения различных операций и функций) используется один и тот же интерфейс. Диаграмма классов, поясняющая структуру паттерна Strategy применительно к данному случаю, приведена на рис. 5.

Рис. 5.

Использование паттерна Strategy при выполнения операций.

Пользовательскую функцию представляет объект класса Subroutine, содержащий список операторов функции. Этот класс содержит вложенный класс Subroutine.Moment, соответствующий текущей позиции выполнения в функции; его методы позволяют передать управление на следующий оператор либо на оператор с заданным номером, выполнить функцию от начала до конца. Произвольный оператор языка представляется интерфейсом IOperator. Этот интерфейс и все реализующие его классы находятся в пространстве имен interpr.logic.operators.

Интерфейс IOperator имеет два метода. Первый из них, GetKind(), возвращает значение типа перечисления OperatorKind, которое характеризует вид оператора. Второй - void Execute(Subroutine.Moment pos) выполняет оператор. В качестве параметра передается объект Subroutine.Moment, с помощью которого управление в функции передается на нужное место. Нужно отметить, что даже если данный оператор не нарушает линейной последовательности выполнения, то все равно ответственность за переход на следующий оператор лежит на методе Execute() объекта оператора.

Как было сказано выше, ряд операторов может быть использован только в функциях. Соответствующие классы реализуют интерфейс IOperator непосредственно. Другие операторы представляют собой команды, которые могут быть введены в консоли. Общим свойством таких операторов является то, что они не нарушают линейной последовательности выполнения, встретившись в функции. Классы, их представляющие, являются потомками абстрактного класса Command, реализующего интерфейс IOperator. Метод Execute() в классе Command имеет перегруженную версию без параметров, объявленную абстрактной. Версия же из интерфейса, принимающая параметр типа Subroutine.Moment, в этом классе реализована следующим образом: вызывается метод Execute() без параметров, затем управление передается на следующий оператор. В классе Command метод GetKind() возвращает значение OperatorKind.Plain, этот метод здесь не является виртуальным и не переопределяется у потомков.

Рассмотрим теперь отдельные классы, реализующие интерфейс IOperator. Начнем с потомков класса Command.

Во первых, присутствуют две команды, отвечающие за вывод на консоль - print и println. Они представляются классами PrintCommand и PrintLnCommand соответственно. Структура этих классов полностью аналогична. Они содержат поле m_expr, со ссылкой на объект Expression, представляющий выражение, результат вычисления которого должен быть выведен на консоль. В методе Execute() результат вычисления выражения сначала приводится к строке (вызывается метод ToString), затем выводится на консоль вызовом методов объекта InterprNamespace.CurrentConsole.

Команда call реализуется с помощью класса CallCommand, в методе execute() которого просто вычисляется выражение из поля m_expr, результат же вычисления выражения никак не используется.

Конструкторы этих трех классов принимают один параметр типа Expression.

Класс EmptyCommand, представляющий пустую команду (пустая строка либо строка комментария), содержит лишь пустые конструктор без параметров и метод Execute().

Класс ClearCommand содержит поле типа string, в котором хранится имя удаляемой переменной. В методе execute() вызывается метод Remove объекта текущего пространства имен.

И, наконец, класс AssignCommand представляет команду присваивания. Он имеет два конструктора, принимающие два или три параметра соответственно, для операторов присваивания значения переменной или элементу массива. В первом из этих параметров содержится имя переменной или массива в левой части оператора присваивания, в остальных - присваиваемое выражение и, во втором случае, индексное выражение. Выражения передаются в их строковой записи, они «компилируются» в объекты класса Expression в конструкторе последнего. Работа с переменными осуществляется с помощью объекта текущего пространства имен, возвращаемого свойством InterprEnvironment.Instance.CurrentNamespace.

К числу классов, представляющих операторы управления последовательностью выполнения, относятся ErrorOperator, ReturnOperator, ForOperator, NextOperator, WhileOperator, LoopOperator, IfOperator, ElseifOperator, ElseOperator, EndifOperator. Для каждого из них имеется свое значение в перечислении OperatorKind, которое и возвращается методом GetKind соответствующего класса.

Метод execute() класса ErrorOperator содержит всего одну строку - генерацию исключения CalcException. Такой же короткий метод выполнения и в классе ReturnOperator - вызывается метод return() объекта Subroutine.Moment pos, который немедленно передает выполнение за конец функции.

Остальные же из рассматриваемых операторов работают в паре с другими операторами - while - с loop, for - с end, if - с elseif, else и endif. Соответствующие классы имеют поля, содержащие номера (позиции) соответствующих парных операторов, и свойства для доступа к ним:

· в классе ForOperator - свойство NextPos - позиция оператора next;

· в классе NextOperator - свойство ForPos - позиция оператора for;

· в классе WhileOperator - свойство LoopPos - позиция оператора loop;

· в классе LoopOperator - свойство WhilePos - позиция оператора while;

· в классах IfOperator, ElseIfOperator и ElseOperator - свойство NextPos - позиция ближайшего снизу соответствующего оператора elseif, else или endif.

Условия и границы циклов там, где они нужны, хранятся в виде объектов типа Expression. Логика выполнения операторов следующая:

· При выполнении оператора while метод Execute() класса WhileOperator вычисляет выражение-условие и, в зависимости от его логического значения, передает управление либо следующему оператору, либо оператору, следующему за оператором loop. Метод Execute() класса LoopOperator передает управление на соответствующий оператор while.

· При выполнении оператора for метод Execute() класса ForOperator вычисляет значения выражений-границ цикла, запоминает значение верхней границы в соответствующем поле класса, затем, если нижняя граница больше верхней границы, передает управление на оператор, следующий за next, иначе - на следующий оператор. При выполнении же оператора next вызывается метод Step() у объекта, представляющего парный оператор for, который увеличивает на единицу переменную-счетчик цикла и, в зависимости от результата сравнения последней с верхней границей цикла, предает управление на оператор, следующий либо за for, либо за next. При этом за все время выполнения цикла метод Execute() класса ForOperator выполняется только один раз.

· При выполнении оператора if метод Execute() класса IfOperator просматривает подряд соответствующие операторы elseif, else и endif до нахождения блока кода, в который следует передать управление. При этом используются свойство NextPos классов IfOperator, ElseOperator, ElseifOperator и метод TestCondition класса ElseifOperator, проверяющий содержащееся в операторе условие. Для определения вида оператора, на который указывает значение свойства NextPos очередного рассматриваемого оператора, у соответствующего объекта вызывается виртуальный метод GetKind.

Диаграмма классов пространства имен interpr.logic.operators приведена на рис. 6.

Рис. 6.

Классы пространства имен interpr.logic.operators.

Пользовательские функции загружаются либо при запуске интерпретатора, либо при сохранении их в редакторе кода. Для хранения загруженных функций используются объекты класса Subroutine. Функция представляется списком операторов (контейнер ArrayList, в котором хранятся объекты типа интерфейса IOperator). Также в классе имеются поля, содержащие общее число операторов, список имен формальных параметров функции и имя функции. Как было сказано выше, в классе Subroutine находится вложенный класс Subroutine.Moment. Он представляет текущую позицию выполнения в функции и в своих полях хранит номер ссылку на объект Subroutine и номер текущего оператора. Его методы работают с частными полями экземпляра класса Subroutine. Поэтому наследование от класса Subroutine становится нежелательным, и он объявлен как sealed.

За хранение загруженных пользовательских функций ответственен класс SubroutinesManager, вложенный (со спецификатором доступа private) в класс InterprEnvironment. Он хранит в двух полях типа System.Collections.ArrayList список загруженных функций, как экземпляров класса Subroutine, и список их имен, соответствие между функцией и ее именем устанавливается по индексу в списках. Singleton-объект класса InterprEnvironment хранит ссылку на один объект класса SubroutinesManager. К его методам обращаются методы класса InterprEnvironment, работающие с пользовательскими функциями, среди которых:

· GetSub(string) - получить объект функции по ее имени;

· LoadSub(string) - загрузить функцию с заданным именем;

· LoadSubs() - загрузить функции из всех файлов в каталоге subroutines;

· UnloadSub(string) - выгрузить функцию с заданным именем.

В выражениях же пользовательские функции представляются объектами класса VarName, которые содержат имя функции, по которому во время выполнения с помощью метода InterprEnvironment.GetSub() поучается соответствующий объект Subroutine. Это связано с тем, что если бы в выражениях в объектах Call хранилась бы ссылка непосредственно на Subroutine, функция, вызывающая другую функцию, не могла бы быть загружена корректно ранее загрузки последней.

Обработка текста программы.

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

Для преобразования строки текста программы в объект, реализующий интерфейс IOperator, используются статические методы класса LineCompiler: Command CompileCommand(string) для команды, введенной с консоли и IOperator CompileOperator(string) для строки функции. Класс LineCompiler не имеет нестатических членов, кроме закрытого конструктора, который, замещая конструктор из базового класса System.Object, не дает возможности создавать экземпляры этого класса. Алгоритм работы обоих названных методов аналогичен. Вначале проверяется наличие в строке лексемы «:=», притом не между двойными кавычками (не в строковой константе). Если она найдена, то данная строка рассматривается как оператор присваивания. Вначале анализируется левая часть оператора присваивания. В зависимости от ее вида, используется нужный конструктор класса AssignCommand - для присваивания значения переменной или элементу массива. Ему в качестве одного из параметров передается часть строки справа от символов «:=», которая разбирается как выражение в конструкторе класса Expression. Если же данный оператор не является оператором присваивания, то из строки выделяется первая лексема, которая последовательно сравнивается с ключевыми словами, с которых начинаются различные операторы (команды). Если совпадений не найдено, то в методе CompileOperator() генерируется исключение SyntaxErrorException - синтаксическая ошибка, в методе же CompileCommand() в этом случае строка рассматривается как сокращенная форма команды println (только выражение). Как только вид оператора определен, оставшаяся часть строки анализируется соответствующим образом. Для многих операторов - if, else if, while, print, println - она рассматривается как одно выражение. При этом на любом из этапов анализа строки при обнаружении ошибки может возникнуть исключение SyntaxErrorException.

Для лексического разбора строки (разбиения на лексемы) используется класс Parser. Каждый его экземпляр используется для разбора одной строки. Класс имеет один конструктор, который принимает один параметр типа string, содержащий обрабатываемую строку. В конструкторе строка подвергается преобразованию - удаляются комментарий, если он присутствует, и лишние пробелы. Класс Parser реализует стандартные интерфейсы System.IEnumerable и System.IEnumerator. Интерфейс IEnumerable представляет объект-список того или иного вида, который допускает последовательный перебор элементов. Он имеет единственный метод IEnumerator GetEnumerator(). Интерфейс IEnumerator представляет объект, который используется для перебора элементов списка. В данном случае эту роль выполняет сам объект класса Parser, поэтому метод GetEnumerator возвращает ссылку this. Этот интерфейс содержит методы MoveNext() - прейти на следующий элемент, Reset() - сброс на начало списка и свойство Current - текущий элемент списка. В данном случае объект Parser рассматривается как список строк-лексем, входящих в состав разбираемой строки. Свойство Current доступно только для чтения и его блок get содержит вызов метода private string GetCurrent(), выделяющего текущую лексему из строки. Строка делится на лексемы следующих видов:

· строковая константа;

· идентификатор;

· число (целое или вещественное, возможно, в экспоненциальной форме);

· служебный символ;

· составной служебный символ (`:=', `<=', `>=', `~=', `<>').

Метод GetCurrent() выделяет в строке длинную возможную лексему, начинающуюся с текущей позиции.

Кроме того, класс Parser имеет два открытых статических метода: bool IsID(string) - является ли данная строка корректным идентификатором и bool IsUserID(string) - является ли данная строка корректным идентификатором, не совпадающим с именем какой-либо из встроенных функций.

Преобразование выражений в описанное ранее внутреннее представление производится в конструкторе класса Expression, который имеет две перегруженные версии, принимающие параметры типа string и Parser соответственно. В обеих вызывается private-метод Analyse(), в котором лексемы из строки заносятся в список типа LinkedList (этот класс был рассмотрен выше), который затем передается в качестве параметра другому private-методу OPZ(). В последнем и сосредоточена основная часть алгоритма разбора выражения. Этот алгоритм относится к так называемым восходящим методам синтаксического разбора, в которых дерево разбора строится «снизу вверх». Синтаксический анализ здесь совмещен с семантической обработкой - построением обратной польской записи выражения. Преобразование выражения в ОПЗ производится следующим образом:

· Вначале создается пустой стек операций (объект класса LinkedList).

· Последовательно перебираются лексемы, входящие в разбираемую строку. Если встречается операнд - переменная (идентификатор, после которого нет открывающей квадратной или фигурной скобки) или константа, то он сразу же добавляется к результату, затем, если на вершине стека операндов имеются унарные операции, они выталкиваются в результат.

· Каждая бинарная операция имеет свой приоритет (можно получить в виде числа с помощью private-функции Expression.Priority()).

· Бинарная операция выталкивает из стека в результат операции с большим или равным приоритетом (с вершины стека), затем сама записывается в стек. Для символов `+' и `-' производится проверка, являются они в каждом конкретном случае знаком бинарной операции или унарной - в случае унарной операции перед ее знаком находится открывающая скобка либо другая операция, или операция находится в начале строки.

· Унарная операция сразу записывается в стек.

· Открывающая круглая скобка сразу записывается в стек.

· Закрывающая круглая скобка выталкивает в результат все операции из стека до открывающей скобки, затем скобки уничтожаются, и выталкиваются с вершины стека в результат унарные операции, если они здесь имеются.

· Если после идентификатора в выражении встречается открывающая квадратная скобка, то выделяются списки лексем, из которых состоят выражения-операнды функции (они расположены в квадратных скобках и разделены запятыми; учитывается возможная вложенность вызовов функций), для каждого из них последовательно вызывается рекурсивно метод Analyse1(), при этом в результат дописываются результаты разбора этих выражений, затем, в результат дописывается вызов функции (ее имя - стоящая перед открывающей квадратной скобкой лексема).

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

· После обработки вызова функции или обращения к элементу массива в результат выталкиваются с вершины стека унарные операции, если они присутствуют.

· В конце разбора в результат выталкивается все содержимое стека.

· Константы записываются в результат как объекты классов, представляющих соответствующие типы данных, переменные - как объекты VarName, операции и вызовы функций - как объекты Call.

Рассмотрим пример. Пусть имеется строка (a*c+-b{а+с})/а. Применим описанный алгоритм.

1. Вначале стек операндов и результат пусты.

2. Первая лексема - открывающая круглая скобка. Записываем ее в стек.

Стек: (Результат: <пусто>.

3. Вторая лексема - идентификатор «а». За ним нет открывающей квадратной или фигурной скобки, поэтому записываем его в результат.

4. Стек: (Результат: а

5. Следующая лексема - операция умножения. Записываем ее в стек. На вершине стека нет операций с большим или равным приоритетом, ничего выталкивать не нужно.

6. Стек: (*Результат: а

7. Вторая лексема - идентификатор «с». За ним нет открывающей квадратной или фигурной скобки, поэтому записываем его в результат.

Стек: (*Результат: ас

8. Следующая лексема - знак «+». Перед ним находится идентификатор, поэтому он является знаком операции сложения. Он выталкивает из стека операцию умножения как имеющую более высокий приоритет, затем сам дописывается в стек.

9. Стек: (+ Результат: ас*

10. Следующая лексема - знак «минус». Перед ним нет ни закрывающей скобки ни идентификатора, поэтому он является знаком операции унарный минус (обозначим ее как «_»), записываем ее в стек.

11. Стек: (+_Результат: ас*

12. Следующая лексема - идентификатор b. За ним следует фигурная скобка, поэтому он рассматривается как имя массива. В фигурных скобках находится строка «а+с», которая, будучи преобразованной по рассматриваемому алгоритму, даст в результате «ас+». Допишем это в результат разбора исходного выражения. Затем допишем в результат имя массива («b») и операцию индексации (обозначим ее «{}»). И, наконец, вытолкнем находящуюся на вершине стека операцию унарный минус.

13. Стек: (+Результат: ас*ас+b{}_

14. Следующая (за закрывающей фигурной скобкой) лексема - закрывающая круглая скобка. Она вытолкнет из стека в результат находящуюся перед открывающей скобкой операцию сложения, затем открывающая скобка будет удалена из стека.

Стек; <пусто>Результат: ac*ac+b{}_+

15. Следующая лексема - операция деления. Она дописывается в стек (перед этим стек пуст, ничего выталкивать не нужно).

Стек: /Результат: ac*ac+b{}_+

16. Последняя лексема - идентификатор «а». После него нет никаких скобок, поэтому он сразу же добавляется к результату.

Стек: /Результат: ac*ac+b{}_+a

17. В конце выталкиваем из стека оставшуюся в нем операцию умножения в результат. Итого получаем ac*ac+_b{}+a/, что является обратной польской записью исходного выражения.

При загрузке функции обработка ее текста осуществляется в конструкторе класса Subroutine, который принимает два параметра - имя функции и текст функции (в виде массива строк). При этом отдельно рассматривается первая строка - заголовок функции. Для ее анализа используется private-метод Subroutine.AnalyseHeader(), в котором проверяется соответствие этой строки требуемому формату и извлекается список формальных параметров. Также проверяется соответствие имени функции в заголовке требуемому (первому параметру конструктора). При этом используется объект класса Parser. Затем по очереди подвергаются разбору с помощью метода LineCompiler.CompileOperator() остальные строки, результат «компиляции» каждой из которых добавляется в список операторов функции. При этом используется стек вложенности операторов (применяется объект класса System.Collections.Stack). После обработки каждой строки проверяется тип полученного оператора с помощью метода IOperator.GetType(). Если оператор открывает блок кода (if, elseif, else, while, for), то его номер заносится в стек. Если оператор закрывает блок кода, то из стека извлекается номер парного оператора и присваиваются необходимые значения свойствам NextPos, LoopPos и т. д. соответствующих объектов. Операторы elseif и else рассматриваются одновременно и как закрывающие расположенный выше блок кода, и как открывающие следующий. Нужно отметить, что в первый элемент списка операторов функции (с нулевым индексом) в объекте Subroutine помещается пустой оператор (объект EmptyCommand), благодаря чему каждой строке текста функции соответствует элемент этого списка с индексом, равным номеру этой строки. Основная часть кода конструктора класса Subroutine находится в блоке try, при возникновении исключения SyntaxErrorException в котором генерируется исключение класса LineSyntaxException, объект которого содержит информацию о месте ошибки (имя функции и номер строки).

Графический интерфейс пользователя.

Главной форме приложения, которая изображена на рис. 7, соответствует класс Form1. Основную часть формы занимает компонент ConsoleBox, созданный на основе класса UserControl. Он включает в себя один экземпляр компонента RichTextBox, «растянутый» с помощью свойства Dock на всю доступную площадь. Компонент ConsoleBox представляет собой окно консоли, в которой пользователь вводит команды, и на которую выводятся результаты работы команд. Класс ConsoleBox является единственным классом в окончательной версии проекта, реализующим рассмотренный выше интерфейс IConsole. Важнейшие члены класса ConsoleBox:

· методы Print(string) и PrintLn(string) - реализуют методы интерфейса IConsole, производят вывод текста в окно консоли.

· метод Prompt() - выводит приглашение командной строки (“>>>”) и переводит консоль в режим ожидания команды.

Страницы: 1, 2, 3, 4