Интерпретатор языка Пролог (стр. 6 из 15)
2.2.1 Принцип работы предкомпилятора
Предкомпилятор состоит из двух основных частей:
· Лексический анализатор
· Синтаксический анализатор.
Лексический анализатор выполняет разбор текста программы на лексемы. В ходе работы лексического анализатора формируется массив лексем, соответствующих программе.
Синтаксический анализатор на основе массива лексем, полученных от лексического анализатора, формирует объект программы.
2.2.1.1 Работа лексического анализатора
Для удобства работы лексический анализатор склеивает весь текст программы в одну длинную строку. Такое склеивание можно проводить, так как максимальная длина строки в Delphi 4 равна 2 гигабайтам. При склеивании строк, в конце каждой строки ставится пара символов Enter и пробел. Это делается для того, чтобы удобно можно было вычислить положение лексемы в тексте программы.
Лексический анализатор просматривает текст программы символ за символом, пропуская символы, заключенные между фигурными скобками. В ходе просмотра анализатор выделяет цепочку символов, которая похожа на лексему, после чего передает управление анализатору лексем.
Анализатор лексем, получив строку с предполагаемой лексемой, пытается сначала сопоставить ее со стандартными лексемами (арифметические знаки, точка, запятая и т.п.). Если строка не является стандартной лексемой, то далее анализатор лексем пытается найти ее среди предикатов, функций и баз данных. В случае неудачи анализатор проверяется строку, является ли она правильным идентификатором. Если да, то это переменная. Если лексема начинается и кончается кавычками, то это строка. На заключительном этапе проверяется, может ли лексема быть числом.
Если ни одно из условий не было выполнено, то выдается сообщение об ошибке.
На выходе анализатора лексем формируется объект лексемы, в котором хранится тип лексемы, ее строковый вид, а также положение лексемы в тексте программы.
Потом из полученных лексем создается массив.
2.2.1.2 Синтаксический анализатор
На начальном этапе массив лексем разбивается на несколько подмассивов по одному для каждого предиката. При разбиении массива проверяется следующее правило: каждое предложение начинается с имени предиката и заканчивается точкой. Таким образом, выделяются лексемы соответствующие каждому предикату.
Затем работа продолжается с каждым из подмассивов отдельно. Пользуясь вышеописанным правилом, выделяется отдельное предложение и отправляется на синтаксический анализ.
Предложение в Прологе имеет следующий формат:
ИмяПредиката (Параметр1, Параметр2, …) if
Условие1(Параметр11, Параметр12, …),
Условие2(Пераметр21, Параметр22, …),
УсловиеN(ПараметрN1, ПараметрN2, …).
При синтаксическом анализе, во-первых, проверяется заголовок предложения. Проверяется имя предиката и параметры (их количество и тип) и наличие слова “if”. Если в качестве параметра стоит переменная, то считается, что переменная может быть любого типа, а константы подвергаются жесткому контролю.
Из массива лексем предложения выделяются отдельные условия. В этом случае должны быть выполнены следующие требования:
· Все условия разделены запятыми друг от друга;
· Цепочка условий заканчивается точкой;
· Внутри условия все скобки (круглые и квадратные) должны быть закрыты.
Проверка условий делится на три части в зависимости от типа первой лексемы:
· Вызов предиката, если первая лексема - имя предиката;
· Вызов базы данных, если первая лексема - имя базы данных;
· Вычисление арифметического выражения - во всех остальных случаях.
При синтаксическом анализе вызовов предикатов и баз данных выполняется разбор параметров примерно такой же, как при анализе заголовка предложения.
При анализе арифметического выражения строится дерево, соответствующее выражению.
2.2.1.3 Анализ арифметического выражения
Если на вход поступает массив из одного элемента, то немедленно формируется лист арифметического дерева, и программа выходит из функции.
Среди всего массива лексем находится оператор с наинизшим приоритетом, причем операции, которые находятся внутри скобок в рассмотрение не берутся. В Прологе приоритеты операций распределены следующим образом:
1. *,/
2. +,-
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.