>,<.>=,<=,<>

3. >,<.>=,<=,<>

4. and,or

5. =

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

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

В ходе выполнения следующих действий мы из арифметического выражения получаем дерево.

Например: A=5+func(6+C,D,E)/E-4

Рис 2.1. Дерево арифметического выражения.

2.2.1.4 Анализ параметров предикатов

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

По первой лексеме массива можно определить, что это за параметр:

Если это название структуры – то структура,

Если левая квадратная скобка – то список,

Если число или строка – то константа,

Если идентификатор – то переменная.

Если выяснили, что параметром является список или структура, то отправляемся на специальные функции анализа списков или структур, где выделяются отдельные элементы списка или структуры и выясняется их тип.

  2.2.1.5 Проверка типов параметров

На вход поступает объект с параметром и имя типа, с которым сравнивается параметр. На выходе мы должны выдать логическое значение, говорящее может ли параметр хотя бы теоретически относиться к сравниваемому типу.

Если параметром является переменная, то считается, что она может быть любого типа. Числовые, строковые и логические константы могут быть опознаны сразу.

Сложнее дело обстоит со структурами и списками, а также анализом составных типов.

При анализе составного типа необходимо выяснить, относится ли параметр к одному из типов составного типа. Если да, значит необходимо возвратить истину.

Рассматривая структуру, мы должны проверить тип каждого из элементов, составляющих структуру. Если все элементы имеют правильные типы, то возвратить истину.

Список может быть записан двумя способами:

1.          [Элемент1, Элемент2, … , ЭлементN]

2.          [Голова|Хвост]

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

При рассмотрении второго случая необходимо учитывать то, что Голова имеет тип элемента списка, а Хвост – тип списка.

2.3 Работа интерпретатора

Функция работы интерпретатора представляет собой рекурсивную функцию, выполняющую алгоритм бэктрекинга.

Алгоритм бэктрекинга заключается в следующем. Для первого оператора Пролог-программы интерпретатор находит решение, удовлетворяющее этому оператору. Если решение было найдено, то переходим к следующему оператору. На втором операторе, с учетом результатов на предыдущем шаге, программа пытается решение для второго оператора. Если решение было найдено, то программа идет дальше. В противном случае, программа должна вернуться на шаг назад и подобрать другое решение для первого условия, а затем опять попытаться выполнить второе условие. Такой процесс идет до тех пор, пока не будет выполнено последнее условие, и предложение будет объявлено истинным. Или, если программа не сможет больше подобрать решения для первого условия, то все предложение будет объявлено ложным.

Принцип действия интерпретатора основан на рекурсивном вызове функции TPrologProgram.ExecutePredicate, которая выполняет предикат. На вход функции поступает объект TStackNode, в котором содержатся входные параметры, а также номер предложения, с которого необходимо начинать выполнять предикат. Функция ExecutePredicate возвращает логическое значение, указывающее на то, было ли найдено решение для предиката или нет. Входные и выходные параметры предиката хранятся в поле InputParameters.

Последовательность действий, которые выполняет функция ExecutePredicate, выглядит следующим образом:

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

2.    Необходимо найти решение для каждого из условий предложения. Интерпретатор проходит по каждому из условий предложения последовательно.

3.    Перед выполнением условия проверяется, запускается на оно на прямом пути или на обратном. Если на прямом пути, то в дополнительный стек заносится еще один элемент TSubStackNode, в котором содержатся следующие данные: само условие, список имен созданных на данном шаге переменных и список имен переменных свободных до текущего шага. Если условие запускается на обратном пути, то объект TSubStackNode не создается, так как был создан ранее.

4.    Если текущее условие предикат или база данных, то для них необходимо создать новый объект TStackNode и сформировать пакет входных параметров. Затем, если текущее условие база данных, то вызывается функция обработки баз данных ExecuteExtDataPredicate, если условие стандартный предикат, то - ExecuteStandardPredicate, и, если это предикат пользователя то рекурсивно вызывается ExecutePredicate.
Если текущее условие - выражение, то выполняется функция ExecuteArithmeticTerm.

5.    Если после своего выполнения условие вернуло значение False, то запускается механизм обратного прохода. Уничтожается последний элемент TSubStackNode, и программа возвращается к предыдущему условию и пытается найти новое решение для него.

6.    Если все условия были выполнены, то формируются выходные параметры и функция возвращает истину. В противном случае, программа возвращается к пункту 1 и пытается найти еще одно предложение, соответствующее входным данным.

7.    Если были исчерпаны все предложения и ни для одно не было найдено решения, то необходимо возвратить False.

2.3.1 Выполнение обращений к базам данных

Обращение к базе данных происходит с помощью SQL-запросов.

При первом обращении к базе данных создается объект SQL-запроса и сам запрос.

Формат SQL-запроса

SELECT <поле1>,…,<полеN>

FROM <имя базы данных>

WHERE

<поле1>=<значение1> and

<поле2>=<значение2> and

…

<полеN>=<значениеN>

В запросе используются только условия-равенства, так как в Прологе при сопоставлении значении на входе в предикат используется только сравнение.

В список условий помещаются только те поля, значения которых на входе определены.

При первом обращении к базе берется первая запись из запроса.

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

Таким образом, доступ к базе данных осуществляется как обычным предикатам, которые состоят только из предложений-фактов.

2.3.2 Вычисление арифметических выражений

На основе построенного при компиляции дерева арифметического выражения достаточно несложно, используя рекурсию, вычислить выражение.

На вход функции поступает объект с деревом арифметического выражения и объект со списком переменных, созданных ранее программой.

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

Дерево может состоять из одного элемента, если это константа или переменная. На этом шаге рекурсия заканчивается и возвращается значение константы или переменной (если до этого в списке переменных ее не значилось, то создается новая переменная).

2.4 Объекты, используемые компилятором и интерпретатором 2.4.1 Объекты переменных TPrologVariable, TPrologVariables, TPrologVariableList, TPrologVariableStruct

Для преставления переменных всех типов (целые, дробные, строки, логические, списки, структуры) служит класс TPrologVariable. Для определения типа переменной служит поле iType. В поле Data хранится указатель на данные, соответствующие типу. Для простых типов (целые, дробные, строки, логические) – это указатель на соответствующий тип. Конструктор создает переменную без типа. Деструктор автоматически освобождает память для переменной любого типа. Для этого класса опеределены следующие методы:

1.         procedure CreateVariable(DomainType:string; vName:string) - создание переменной типа DomainType с именем vName;

2.         procedure DestroyVariable - уничтожение переменной (эта процедура не является деструктором, так как не уничтожает сам объект, а только освобождает память)

3.         function CreateCopy:TPrologVariable - создание точной копии переменной;

4.         procedure AssignVariable (v:TPrologVariable) - присваивание значения переменной.

Для представления списков введен класс TPrologVariableList, в котором хранится имя типа списка, имя типа элемента списка, тип представления списка (в виде перечисления элементов или «голова-хвост»), а также динамический массив, содержащий объекты TPrologVariable, являющиеся элементами списка.

В структурах (TPrologVariableStruct) аналогично хранится имя типа структуры, массив с типами элементов структуры и динамический массив с элементами структуры.

Следует отметить, что в классе TPrologVariable, могут храниться как переменные, так и константы. У константы поле Name - пустая строка.

Класс TPrologVariables позволяет организовать к пакету переменных:

1.    procedure AddVariable(v:TPrologVariable) - добавление переменной в список переменных;

2.    function AddNewVariable:TPrologVariable - создание и добавление новой переменной в список;

3.    procedure DeleteVariable(n:integer) procedure DeleteVariable(vName:string) procedure DeleteLastVariable - удаление переменной по ее индексу или по имени, либо последнюю переменную в списке;

4.    function VariableByName(vName:string):TPrologVariable - доступ к конкретной переменной по ее имени;

5.    property Variables[ind:integer]:TPrologVariable - свойство, оргназиующее доступ к переменным как к массиву переменных.

2.5.2 Стандартные функции и предикаты

Все стандартные функции и предикаты имеют одинаковые параметры.

Объявление функции выглядит следующим образом:

TStdFunction=function (Args:TPrologVariables):TPrologVariable;

Args – пакет с входными параметрами.

Функция возвращает значение в виде переменной TPrologVariable.

Объявление функции, выполняющая работу предиката:

TStdPredicate=function (VarPacket:TPrologVariables; BackTracking:Boolean):Boolean;

VarPacket – пакет с параметрами к предикату

BackTracking – логическая переменная, которая установлена в True, если предикат был вызван на обратном пути алгоритма бэктрекинга.

Функция возвращает логическое значение, которое должен возвратить предикат после своего выполнения.

2.6 Представление Пролог-программы в виде объектов

Для хранения откомпилированной Пролог-программы используются три класса TPrologTerm, TPredicateClause и TProgramPredicate.

TPrologTerm служит для хранения одного условия внутри предложения. В нем хранится тип условия (выражение, предикат, база данных), позиция условия в тексте Пролог-программы, а также указатель (Data) на объект представляющий данное условие (TSubTermPredicate, TSubTermExtData, TSubTermExpression).

TSubTermPredicate служит для хранения условий-предикатов. В данном классе есть следующие поля:

1.         Name :String - имя предиката;

2.         StandardPredicate :Boolean - True - если предикат стандартный;

3.         Params :TVariablesArray - параметры для вызова предиката;

4.         NoInverse :Boolean - признак наличия или отсутствия инверсии перед вызовом предиката.

TSubTermExtData аналогичен классу TSubTermPredicate за исключением того, что в нем нет поля StandardPredicate.

TSubTermExtData предназначен для представления арифметических выражений. Он представляет собой рекурсивный объект с полями LeftHand и RightHand для представления выражений левой и правой частей выражения. Данный класс содержит следующие поля:

1.         Operation :TExpressionOperation - тип операции;

2.         FuncName :String - имя функции, если Operation=eoFunction;

3.         Operand :TPrologVariable - переменная или константа, если Operation=eoVariable;

4.         LeftHand :TSubTermExpression - левая часть выражения;

5.         RightHand :TSubTermExpression - правая часть выражения

6.         FuncParams :array of TSubTermExpression - параметры функции, если Operation=eoFunction.

TPredicateClause хранит в себе одно предложение. Параметры предложения хранятся в массиве Params, а условия - в Terms.

TProgramPredicate хранит полную информацию о предикате. Объект этого класса используется как на этапе компиляции, так и на этапе интерпретации. Он хранит имя предиката (Name), типы параметров, текст предиката, все лексемы предиката, а также массив с предложениями предиката.

Класс TPrologProgram хранит всю информацию о Пролог-программе:

·            Описания типов (Domains);

·            Описания баз данных (ExtData);

·            Предикаты (TProgramPredicate);

·            Массив со стеком (Stack);

·            Массив с контрольными точками (BreakPoints);

·            Имя запускаемого предиката (StartPredicate);

·            Флаг работы программы (OnTheRun).

2.7 Основные модули

Модуль CompileUnit. В данном модуле определяется класс пролог-программы - TPrologProgram, а также два класса, использующихся при запуске интерпретатора: TStackNode и TSubStackNode. Модуль CompileUnit является ядром интерпретатора.

Модуль ProgramClasses. В данном модуле описываются основные классы, использующиеся в объектах TPrologProgram, TStackNode и TSubStackNode как контейнерные:

–           TLexemRecord - представляет одну лексему, выделенную из текста программы;

–           TPrologVariable - представляет переменную во время выполнения пролог-программы.

–           TPrologVariableList - контейнерный класс, использующийся в TPrologVariable, для представления списков;

–           TPrologVariableStruct - контейнерный класс, использующийся в классе TPrologVariable, для представления структур;

–           TPrologVariables - класс, представляющий собой список переменных TPrologVariable с возможностью доступа к переменной по имени;

–           TSubTermPredicate - класс использующийся в TPrologTerm для представления обычного предикатного условия в предложении;

–           TSubTermExtData - класс использующийся в TPrologTerm для представления предикатного условия вызова базы данных в предложении;

–           TSubTermExpression - класс использующийся в TPrologTerm для представления арифметических выражений в предложении;

–           TPrologTerm - класс использует TSubTermPredicate, TSubTermExtData, TSubTermExpression как контейнерные для представления одного условия в предложении;

–           TPredicateClause - использует массив объекстов TPrologTerm и TPrologVariable для представления одного предложения в программе;

–           TProgramDomain - класс использующийся в TPrologProgram как контейнерный для описания типов;

–           TProgramExtData - класс использующийся в TPrologProgram как контейнерный для описания баз данных;

–           TProgramPredicate - класс использующийся в TPrologProgram как контейнерный для описания предикатов;

–           TPrologFile - класс использующийся в TPrologProgram как контейнерный для описания файлов открытых во время выполнения программы;

Модуль PrologRunTime описывает класс ошибок TRunTimeError, а также все функции и встроенные предикаты Пролога.

MainFormUnit - модуль описания главной формы TMainForm;

ProgFormUnit - модуль описания окна инспектора TProgForm;

DomConstrFormUnit - модуль описания конструктора типов TExtDataForm;

ExtDataFormUnit - модуль описания конструктора баз данных TExtDataForm;

PredicateConstrFormUnit - модуль описания конструктора предикатов TPredicateConstrForm;

EditorFormUnit - модуль описания окна редактора TEditorForm

ConsoleUnit - модуль описания окна консоли TConsole;

ErrorsFormUnit - модуль описания окна ошибок компиляции TErrorsForm;

StackFormUnit - модуль описания окна стека программы TStackForm;

RunTimeDebugFormUnit - модуль описания окна отладки программы TRunTimeDebugForm;

BreakPointsFormUnit - модуль описания окна контрольных точек TBreakPointsForm;

ProjectOptionsFormUnit - модуль описания окна опций проекта.

2.8 Демонстрационная программа по выбору конфигурации компьютера

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

В программе используются две базы данных.

База данных базовых конфигураций ("Configs.db"), в которой содержатся оптимальные конфигурации для каждой из элементарных задач.

Таблица 2.1.

Имя поля	Тип поля	Комментарий
Task	String[33]	Название задачи
Frequency	Integer[4]	Частота процессора
Processor	String[17]	Тип процессора
Memory	Integer[4]	Размер ОЗУ
VideoMemory	Integer[4]	Размер видеопамяти
HDD	Integer[4]	Размер винчестера
MonitorSize	Integer[4]	Диагональ монитора
Addition1Name	String[17]	Название 1-го дополнительного устройства
Addition1Value	String[9]	Характеристика 1-го дополнительного устройства
Addition2Name	String[17]	Название 2-го дополнительного устройства
Addition2Value	String[9]	Характеристика 2-го дополнительного устройства
Addition3Name	String[17]	Название 3-го дополнительного устройства
Addition3Value	String[9]	Характеристика 3-го дополнительного устройства
Addition4Name	String[17]	Название 4-го дополнительного устройства
Addition4Value	String[9]	Характеристика 4-го дополнительного устройства

База приоритетов устройств ("DeviceClass.db"). Используется для разделения устройств по их характеристикам, в том числе и процессоров.

Таблица 2.2.

Имя поля	Тип поля	Комментарий
TypeName	String[17]	Имя класса устройств
SubType	String[33]	Имя отдельного устройства
SubTypeIndex	Real	Характеристика устройства

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

Пара предикатов ReadParameters и _ReadParameters предназначены для ввода списка элементарных задач с клавиатуры в список строк StringList.

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

AddNewAddition добавляет в списки дополнительных устройств новое устройство. Сначала предикат пытается найти устройство среди уже известных. Если оно не найдено, то добавляется новое устройство. Если среди уже известных устройств имеется устройство аналогичного типа, то из двух устройств выбирается устройство с наивысшим классом по базе DeviceClass.

Предикат ChooseConfig проходит по всему списку элементарных задач, поступившему с клавиатуры, постепенно выбирая лучшую конфигурацию. Объемы оперативной памяти, видеопамяти и диагональ монитора выбираются по максимальному значению. Размер винчестера получается сложением размеров винчестеров для каждой элементарной задачи.

Текст демонстрационной программы приведен в приложении.

3 Технологическая часть 3.1 Требования по эксплуатации интерпретатора языка Пролог

Программа интерпретатора языка Пролог предназначена для эксплуатации на персональных вычислительных машинах на базе процессоров семейства Pentium и выше в минимальной конфигурации с 16 Мб оперативной памяти. Для установки программы необходимо:

·           в минимальной конфигурации - 1.5 Мб дискового пространства;

·           в полной конфигурации (с установкой Borland Database Engine) - 10 Мб дискового пространства.

В качестве операционной системы может использоваться Microsoft Windows 95, Windows 98, Windows NT.

3.2 Установка системы

Система поставляется на четырех дискетах размером 3.5" и объемом 1.44 Мб.

Установка программы производится с дискет, путем запуска из операционной системы Windows файла "Setup.exe", находящегося на первой дискете. Далее необходимо действовать согласно указаниям.

При установке программы необходимо указать директорию, в которую будет производиться инсталляция.

В процессе установки программа спросит, устанавливать ли Borland Database Engine на машину или нет. Если BDE уже установлена на компьютер ранее, то повторная установка не требуется.

По завершении процесса установки программа-инталлятор создаст в системном меню раздел с названием "Prolog", а внутри него ярлык на файл "Prolog.exe" с названием "Prolog with databases", ярлык на help-файл и на файл "readme.txt".

3.3 Руководство пользователя программы интерпретатора языка Пролог 3.3.1 Запуск программы

Запуск программы можно произвести несколькими способами.

Нажать кнопку "Пуск", выбрать в меню пункт "Программы", выбрать пункт "Prolog". После того, как раскроется подменю, нажать на строку "Prolog with databases".

Дважды щелкнуть по иконке Пролога на рабочем столе

Воспользоваться "проводником" или другим менеджером файлов.

3.3.2 Перечень функций, реализуемых системой

Программа интерпретатора языка Пролог выполняет следующие функции:

1.         ввод, сохранение и редактирование программы на языке Пролог.

2.         осуществление отладочного режима работы с просмотром вызовов предикатов и значений переменных.

3.         запуск программы на исполнение

4.         возможность приостановки работающей программы на контрольной точке, установленной в тексте программы, или при нажатии кнопки "Пауза".

3.3.3 Редактирование Пролог-программы

После запуска программы вся работа по написанию программы может производиться в интегрированной среде разработчика.

Интегрированная среда разработчика предоставляет разработчику следующие возможности:

1.         создание нового файла программы;

2.         открытие существующего файла программы;

3.         сохранение файла;

4.         сохранение файла под новым именем;

5.         выход из системы;

6.         редактирование файла с использованием буфера обмена;

7.         настройку параметров программы Пролог;

8.         настройку редактора;

9.         запуск программы на исполнение;

10.       временную остановку работы программы;

11.       доступ к файлу справки.

Все эти возможности доступны через пункты меню или через кнопки быстрого доступа.

После запуска программы появляется главное окно, на котором размещены главное меню и основные панели с кнопками быстрого доступа.

Рис 3.1. Вид главного окна.

Программу необходимо в двух окнах: в окне редактора и в окне инспектора.

Инспектор содержит в себе основную информацию о программе: описания типов данных, таблиц баз данных и предикатов.

Рис 3.2. Вид окна инспектора.

Окно инспектора разбито на три части: "Типы", "Внешние данные" и "Предикаты". В случае надобности разделы "Типы" и "Внешние данные" можно временно свернуть, нажав на верхнюю кнопку соответствующей панели.

Для добавления элемента в список типов необходимо нажать на кнопку с изображением плюса. Тогда справа от кнопки появится меню для выбора типа: "Список", "Структура", "Составной тип". Для каждого типа открывается окно конструктора типов, в котором можно редактировать составные элементы типов. При нажатии на кнопку "Ок" тип будет занесен в список типов. Для внесения нового элемента в тип необходимо выбрать его из списка, ввести комментарий (если необходимо) и нажать на кнопку плюс на нижней панели

 

а) б)

Рис. 3.3. Вид окна конструктора типов: а) конструктор списков;

б) конструктор структур

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

Рис. 3.4. Вид окна конструктора баз данных

Ввод предиката производится аналогично вводу нового типа.

Для редактирования элемента любого из списков можно дважды щелкнуть по нужному элементу. Для удаления элемента из списка нужно щелкнуть по нему, а затем нажать на кнопку минус.

При однократном нажатии на элемент с именем предиката текстовый курсор в окне редактора автоматически перейдет к тому месту в программе, где описывается данный предикат.

Текст программы вводится в окне редактора. Это окно состоит из панели инструментов и редактора. На панели инструментов находится кнопки для копирования, вырезания и вставки фрагмента текста, а также кнопка по установки контрольной точки в тексте. Из окна редактора можно мгновенно получить справку о любом стандартном предикате или функции, набрав имя предиката или функции в тексте и нажав кнопку F1.

Рис. 3.5. Вид окна редактора.

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

Shift - стрелки вверх, вниз, вправо, влево, Home, End - выделение области текста для операций;

Ctrl-Insert или Ctrl-C - копировать выделенную область в буфер обмена;

Shift-Insert или Ctrl-V - вставить фрагмент из буфера обмена;

Shift-Del или Ctrl-X - вырезать фрагмент в буфер обмена.

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

Рис. 3.6. Вид окна опций проекта.