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

cvPV (pointer to value) - конвертация указателя в значение;

cvPA (pointer to address) - конвертация указателя в адрес;

cvAV (address to value) - конвертация адреса в значение.

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

И последние замечания по поводу возможной реализации интерпретатора.

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

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

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

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

Пишутся интерпретаторы обычно на языках высокого уровня. И особенно полезными являются здесь принципы объектно-ориентированного программирования. Однако зачастую эффективнее бывает технология, при которой сначала создается макетный интерпретатор, реализованный, скажем, на Прологе. Макетный интерпретатор является полигоном для отладки структуры языка, он, естественно, прост, но малоэффективен с точки зрения скорости интерпретации. Тем не менее, Пролог для отладки структуры языка - незаменимое средство. Интерпретатор языка, среднего между Бейсиком и Паскалем, можно написать за 2-3 дня, и занимать он будет 400-500 строк (личный рекорд автора - это интерпретатор языка, в котором есть циклы, условные операторы, операторные скобки и полная арифметика с набором математических функций, который был написан за два вечера и занимал чуть более 400 строк). После отладки структуры языка можно браться за реализацию интерпретатора и на более эффективных с вычислительной точки зрения языках.

18. Компиляторы компиляторов

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

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

Для этого потребуется некоторое описание двух наших грамматик - грамматики для сканера и грамматики для реализации синтаксического анализатора. Это описание вполне можно хранить в некотором файле. И тогда мы получим своего рода специальный входной язык - язык описания компилятора.

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

А дальше разработчику все равно необходимо будет самостоятельно добавлять семантические процедуры. С семантикой без него все равно ни один КК не справится. И еще пара замечаний.

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

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

И последнее. Познакомиться с описанием одного из наиболее почтенных КК можно в замечательной книге Кернигана и Пайка (см. библиографию). Описанный там КК YACC (Yet Another C Compiler - еще один компилятор С или Yet Another Compiler Compiler - еще один компилятор компиляторов) представляет весьма мощный инструмент, хотя использование его - занятие весьма утомительное. На самом же деле пользоваться надо своим собственным инструментарием. КК - это один из немногих продуктов, ценность которого определяется его "эксклюзивностью". Ведь не случайно создание по-настоящему эффективных компиляторов определяется квалификацией разработчиков, их опытом и, вообще говоря, уровнем их «школы». Потому до сих пор велика конкуренция на рынке компиляторов и трансляторов, эффективность которых у одних производителей заметно отличается от того, что делают другие. Кстати, зачастую бывает и так, что у одного и того же производителя компиляторы для разных языков получаются совсем разного качества.

19. Приложение. Введение в пролог

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

Пролог - это достаточно "древний" язык. Он был создан в 1973 Алэном Колмеро во Франции, в Марсельском университете. Особенно популярен Пролог в Европе и в Японии. В 1981 г., анонсируя проект создания ЭВМ пятого поколения, японцы выбрали именно Пролог в качестве базового языка программирования. Пролог считается одним из языков искусственного интеллекта. Его название происходит от аббревиатуры PROgramming in LOGic (ПРОграммирование ЛОГики) - ПРОЛОГ. Действительно, основа языка Пролог - математическая логика. Пролог знаменует собой важный этап в эволюции языков программирования: движение от языков низкого уровня, пользуясь которыми программисты описывают, как что-либо следует делать (традиционные процедурно-ориентированные), к языкам высокого уровня, в которых указывается, что необходимо делать (декларативные языки).

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

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

19.1 Описание взаимоотношений между объектами

Как уже говорилось, Пролог создан для того, чтобы описывать взаимоотношения между объектами. В этом смысле Пролог можно назвать реляционным языком. "Реляционность" Пролога является значительно более мощной и развитой по сравнению с реляционными языками, используемыми для работы с базами данных. Именно поэтому зачастую Пролог используется для создания СУБД, в которых применяются сверхсложные запросы и процедуры поиска.

Пусть у нас есть несколько объектов. Обозначим их именами a, b, c, d, e и f. Рассмотрим отношение типа "родитель" между этими объектами:

Отношения в Прологе определяются в общем случае заданием имени отношения и n-ки объектов, для которых это отношение выполняется.

На Прологе эта схема будет представлена следующей программой из 6 предложений (фактов):

родитель(a, c).

родитель(b, c).

родитель(b, d).

родитель(c, e).

родитель(c, f).

родитель(f, g).

Аргументы отношения могут быть атомами (конкретными объектами или константами) или переменными - абстрактными объектами.

Здесь объекты a, b, c, d, e, f - это атомы (константы). Обратите внимание на то, что они записываются строчными буквами. Константы на Прологе бывают символьного типа, строкового типа, а также константы - числа. В данном случае мы имеем дело именно с символьными константами. Как обычно, константа - это то, что имеет неизменное значение.

родитель - это бинарное отношение (отношение второго порядка). С тем же успехом можно было бы дополнить нашу схему, добавив отношения первого порядка. Например:

женщина (a).

мужчина (b).

мужчина (c).

и т.д.

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

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

Синтаксис постановки вопроса на языке Пролог выглядит так:

? утверждение

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

Например:

? - родитель (a, c)

Да

? - родитель (a,e)

Нет

и т.п.

Можно задавать и вопросы вида:

?- родитель(a, X)

X = c

Да

?- родитель(X, c)

X = a

X = b

Да

?- родитель(X, Y)

X=aY=c

X=bY=c

X=bY=d

X=cY=e

X=cY=f

X=fY=g

Да

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

19.2 Составные вопросы

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

Некто X является родителем родителя Z, если этот X - родитель некоторого Y, а этот Y является родителем для Z. Это утверждение может быть записано в виде логического выражения, представляющего коньюнкцию. В Прологе операция И обозначается ключевым словом and либо запятой:

родитель(X,Y) and родитель (Y,Z)

Найдем родителя и "деда" объекта g:

Тогда наш вопрос может выглядеть так:

?- родитель(X,Y), родитель(Y, g)

Реакция системы на этот вопрос будет заключаться в выдаче значений переменных X и Y:

X = c

Y = f

Обратите внимание на то, что наш вопрос мог быть записан и в таком виде:

?- родитель(Y, g), родитель(X,Y)

Результат будет тем же самым, однако, как это будет видно далее, эффективность поиска в этом случае будет выше.

19.3 Правила

Введем отношение "отпрыск". Можно изобразить аналогичную вышеприведенной схему отношений и ввести еще 6 предложений-фактов. Однако значительно элегантнее определить отношение "отпрыск" (отношение, противоположное отношению "родитель") следующим образом:

С точки зрения формальной логики понятие "отпрыск" можно определить так:

Для любых X и Y Y является отпрыском X, если X - родитель Y.

На Прологе это будет записано в виде следующего предложения:

отпрыск(Y,X) :- родитель(X,Y).

Подобные предложения называются правилами. Правило имеет условную часть (посылку - антецедент) и часть вывода (заключение - консеквент). Если в привычном виде правило записывается как

Если (антецедент) То (консеквент),

то в Прологе правило выглядит иначе - сначала записывается заключение, а затем посылка:

ЗаключениеifПосылка

Посылка в Прологе называется телом правила, а заключение - головой правила.

(Голова)if(Тело)

Например, отношение родитель_родителя может быть представлено в виде правила

родитель_родителя(X,Z) :- родитель(X,Y), родитель(Y,Z).

А отношение "сестра" может быть определено так:

сестра(X,Y) :-

родитель(Z,X),

родитель(Z,Y),

женщина(X).

19.4 Пролог с математической точки зрения

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

Для примера рассмотрим известный силлогизм Аристотеля:

Все люди смертны. Сократ-человек. Следовательно, Сократ смертен

Более формально:

(Все люди смертны = Для любого X: X - человек => X смертен)

Х: Х - человекХ - смертен

Сократ - человек

Сократ смертен

На Прологе это будет выглядеть так:

смертен(X) :- человек(X).

человек(сократ).

?- смертен(сократ)

Да

19.5 Формализм языка пролог

Итак, подытожим вышеизложенное. С формальной точки зрения Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой. Предложения Пролога состоят из головы и тела. Тело - список целей, разделенных запятыми. Запятые обозначают операцию конъюнкции.

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

Факты содержат утверждения, которые всегда истинны. Факт - это предложение, у которого тело пустое.

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

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

19.6 Переменные

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

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

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

19.7 Механизм поиска решения

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

Сопоставление термов. Все объекты данных в Прологе синтаксически представляют собой термы. Термы сопоставимы, если:

они идентичны;

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

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

19.8 Рекурсивные правила

В Прологе нет циклов. Все итерационные процедуры осуществляются с помощью рекурсии. Кроме того, рекурсия играет, естественно, и самостоятельную роль. Например, можно определить отношение "предок" (предок в самом общем смысле) следующим образом:

предок(X,Z) :- родитель(X,Z).

предок(X,Z) :- родитель(X,Y), предок(Y,Z).

Повторение. Организовать циклические вычисления можно с помощью простого предиката repeat:

repeat.

repeat :- repeat.

Первое правило всегда истинно. Оно необходимо для создания точки возврата, когда сработает рекурсивный repeat. Следовательно, нам достаточно заставить систему перейти к альтернативному варианту, и мы тогда получим бесконечный цикл. Например, предикат echo будет запрашивать пользователя ввод строки, выводить ее на экран. И продолжаться это будет до тех пор, пока пользователь не введет строку "quit":

echo:-repeat,

write("Введите строку (quit-выход)"),

readln(S),

S="quit".

Дело в том, что в последней строке происходит сравнение введенной строки со строкой "quit". Если строки не совпадают, то система вернется к предыдущей альтернативной точке. Таковой является предикат repeat (недаром их у нас два варианта). Система пробует очередной вариант его выполнения и тем самым попадает в бесконечную рекурсию - в бесконечный цикл. А вот если строки совпадут, то тогда выполнение предиката echo будет считаться успешным.

Приведем еще один пример применения рекурсивного правила. Следующий предикат вычисляет сумму ряда:

sum(1,1).

sum(N,Summ) :-

N>0,

Next = N-1,

sum(Next,Sum2),

Summ = N+Sum2.

19.9 Списки

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

Очень характерно, как определяет списки сам Пролог. В Прологе список - это структура, состоящая из головы и хвоста. Голова - это один элемент. Хвост - это список. Список может и не содержать элементов. Тогда он называется пустым списком. Правила определения списка могут выглядеть так:

Список []

Список Голова, Хвост

Голова элемент

Хвост Список

Список задается перечислением его элементов, заключенным в квадратные скобки. Разделение списка на голову и хвост происходит указанием специального разделителя - символа '|'.

Примеры списков:

[1,3,8,1,6], [a, b, ec ], ["абв", "где", "жз"]

При этом в списке [1,3,8,1,6] голова - это элемент 1, а хвост - это список [3,8,1,6]:

[ 1| 3 , 8 , 1 , 6 ]

головахвост

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

print_list([]) :- !.

print_list([H|Tail]) :-

write(H),

print_list (Tail).

Другим примером может служить замечательный предикат append. Это - удивительный предикат. Он столь же прост, сколько и универсален. Если разобраться, как он работает, то можно считать, что вы как минимум наполовину знаете устройство Пролога. Выглядит он весьма просто:

append([],L,L).

append([H|A],B,[H|C]) :- append(A,B,C).

Этот предикат может конкатенировать (сцеплять) два списка, он может проверять, составляет ли конкатенация пары списков третий, он может даже разделять список на все возможные пары его составляющих. Именно это и делается в приведенной ниже программе, которая выводит на экран все возможные разбиения списка:

goal

s([1,2,3,4]).

clauses

append([],L,L).

append([H|A],B,[H|C]) :- append(A,B,C).

print_list([]) :- !.

print_list([H|Tail]) :- write(H), print_list (Tail).

s(S) :- append(L1,L2,S),

print_list(L1),

print_list(L2),

fail.

s(_) :- !.

О том, что такое ! и fail, будет сказано ниже.

19.10 Управление поиском

Откат после неудачи. Предикат fail всегда заканчивается неудачей. Вместо него можно было бы использовать какое-нибудь априорно ложное утверждение (например, 1=2), однако с ним программа выглядит элегантнее. Следующий предикат выводит на экран все имеющиеся имена.

show_all :-

name(X),

fail.

name("Петров").

name("Иванов").

name("Сидоров").

Если бы не fail, то выполнение предиката закончилось бы выводом одного-единственного имени. Правило выдачи на экран “эха”, использующее уже знакомый repeat, но уже в бесконечном цикле, выглядит так:

echo:-

repeat,

readln(S),

write(S),

fail.

Здесь fail служит для того, чтобы реализовать откат после неудачи. Еще раз отметим, что откат происходит к repeat, т.к. в нем существует как минимум две возможности реализации repeat. Это правило порождает бесконечное число точек возврата.

Отсечение. Иногда бывает необходимо ограничить круг поиска, т.е. заставить систему "забыть" о существовании альтернативных вариантов - точек возврата. Фактически речь идет о задаче отсечения ненужных результатов. Этой цели служит предикат cut или '!' (в Прологе вообще любят все сокращать - вместо and - запятая, вместо cut - восклицательный знак, вместо or - точка с запятой ';'). Пользоваться этим предикатом нужно очень осторожно. А лучше стараться не пользоваться вовсе (во всяком случае без крайней необходимости). Этот предикат всегда истинен. Он отсекает все точки возврата, находящиеся до него (иными словами, этот предикат очищает стек точек возвратов).

Примеры использования предиката cut:

show_somebody :-

name(X),

make_cut(X),

!.

make_cut(X) :- X="anonymous".

echo :-

repeat,

readln(S),

write(S),

check(X), !.

check(S) :- S="stop".

check(_) :- fail.

19.11 Примеры программ

Изучение и понимание языков немыслимо без практики и уж тем белее без примеров. Несмотря на ограниченность объема и чрезмерную «лаконичность» изложения основ Пролога, тем не менее будет весьма полезно ознакомиться с решением двух классических Прологовских задач. Кроме того, в конце будет приведен ряд некоторых полезных предикатов, иллюстрирующих логику решения задач.

19.11.1 Программа поиска всех циклов в графе

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

% Программа поиска всех циклов в графе

domains

ilist = integer *

predicates

% Ребро графа

a(integer,integer)

% Поиск пути из FROM в TO. RES - результат,

% OLDWAY - уже пройденный путь.

way2(integer,integer,ilist,ilist) % (FROM, TO, RES, OLDWAY)

% Печать списка

print_list(ilist)

% Проверка принадлежности элемента списку

isin(integer,ilist)

% Поиск всех циклов

findallcirc

goal

findallcirc,

write("\nDone.").

clauses

findallcirc :-

way2(FROM,FROM,W,[]), write(FROM,": "), print_list(W), fail.

findallcirc :- !.

isin(E,[E|_]).

isin(E,[_|Tail]) :- isin(E,Tail).

print_list([]) :- nl.

print_list([H|Tail]) :- write(H," "), print_list(Tail).

way2(X,Y,[Y],OLDWAY) :-

a(X,Y),

not(isin(Y,OLDWAY)).

way2(X,Y,[Z|W2],OLDWAY) :-

a(X,Z),

not(isin(Z,OLDWAY)),

way2(Z,Y,W2,[Z|OLDWAY]).

% Описание ребер графа

a(1,2). a(1,5). a(2,3). a(3,4). a(2,5).

a(4,1). a(5,4). a(3,6). a(6,2).

19.11.2 Анализатор арифметических выражений

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

% Очень простой анализатор арифметических выражений.

% Занимается сканированием строки символов и формированием

% польской формы записи исходного выражения.

DOMAINS

strlist = string*

PREDICATES

% Сканер. На входе - строка, на выходе - поток лексем

scanstr(string,strlist)

% Синтаксический анализатор. На входе - поток лексем (список),

% на выходе - польская форма записи

recognize(strlist,strlist)

% Служебные и вспомогательные предикаты

printlist(strlist)

a2(strlist,strlist,strlist)

a3(strlist,strlist,strlist,strlist)

% Грамматика. Второй аргумент - это фрагмент сформированной

%с помощью правила польской формы

E(strlist,strlist)

T(strlist,strlist)

F(strlist,strlist)

% Проверка того, является ли список именем. Проверяется именно

% список, а не элемент. Это нужно для большей общности.

isitname(strlist)

GOAL

%%% Входная строка

INPUTSTR="b+ c/(d -e)",

%%% Сканирование

scanstr(INPUTSTR,STRLEXEMS),

write("\nПоток лексем:\n"),

printlist(STRLEXEMS), nl,

%%% Распознавание и формирование польской формы

recognize(STRLEXEMS,POLAND),

write("\nПольская форма:\n"),

printlist(POLAND),

write("\nГотово.\n").

CLAUSES

%%% ------------------- Сканер

scanstr("",[]).

scanstr(S,[Token|TLrest]) :-

fronttoken(S,Token,Rest),

scanstr(Rest,TLrest).

%%% ------------------- Вспомогательные предикаты

a2([],L,L).

a2([H|A],B,[H|C]) :- a2(A,B,C).

a3(L1,L2,L3,L) :- a2(L1,LX,L), a2(L2,L3,LX).

printlist([]).

printlist([H|Tail]) :- write(H," "), printlist(Tail).

isitname([N|[]]) :- isname(N).

%%% ------------------- Основной предикат

recognize(L,PF) :- E(L,PF).

%%% ------------------- Синтаксические правила

% E->E+T

E(L,A) :- a3(L1,["+"],L3,L),

E(L1,A1), T(L3,A2), a3(A1,A2,["+"],A).

% E->E-T

E(L,A) :- a3(L1,["-"],L3,L), E(L1,A1), T(L3,A2),

a3(A1,A2,["-"],A).

% E->T

E(L,A) :- T(L,A).

% T->T*F

T(L,A) :- a3(L1,["*"],L3,L), T(L1,A1),

F(L3,A2), a3(A1,A2,["*"],A).

% T->T/F

T(L,A) :- a3(L1,["/"],L3,L), T(L1,A1), F(L3,A2),

a3(A1,A2,["/"],A).

% T->F

T(L,A) :- F(L,A).

% F->name

F(L,L) :- isitname(L).

% F->(E)

F(L,A) :- a3(["("],L1,[")"],L), E(L1,A).

19.11.3 Некоторые полезные предикаты

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

• Определение минимума и максимума двух чисел
• Обратите внимание на использование предиката отсечения. Он необходим для ликвидации возможной точки возврата.
• min2(A,B,A) :- A < B, !.
• min2(_,B,B).
• max2(A,B,A) :- A > B, !.
• max2(_,B,B).
• Определение принадлежности элемента списку
• member(X,[X|_]) :- !.
• member(X,[_|T]) :- member(X,T).
• Выборка элемента списка по его индексу
• index([X|_],1,X) :- !.
• index([_|L],N,X) :- N>1, N1=N-1, index(L,N1,X).
• Вычисление длины списка
• list_len([], 0).
• list_len ([_|T], N) :-
• list_len (T, N2),
• N = N2+1.
• Вычисление суммы элементов списка (а заодно и его длины)
• sum_list([], 0, 0).
• sum_list([H|T], SUM, NUMBER) :-
• sum_list(T, SUM1, NUMBER1),
• SUM = H+SUM1,
• NUMBER = NUMBER1+1.
• Инверсия списка
• reverse(X,Y) :- reverse1([],X,Y).
• reverse1(Y,[],Y).
• reverse1(X1,[U|X2],Y) :- reverse1([U|X1],X2,Y).
• Вычисление максимального элемента списка
• max_in([X],X):- !.
• max_in([H|T],H):- max_in(T,R), R<H, !.
• max_in([H|T],R):- max_in(T,R), H<=R.
• То же, но с использованием предиката max2
• max_in2([A],A).
• max_in2 ([H|T],M) :- max_in2 (T,M1), max2(H,M1,M).
• Удаление элемента из списка
• delete(_,[],[]).
• delete(X,[X|Y],Y):- !.
• delete(X,[A|Y],[A|Z]):- delete(X,Y,Z).

Библиографический список

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. Том 1. М.: Мир, 1978. -616с.

2. Ахо А., Моника С. Лам М., Рави Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. - Вильямс, 2003. - 768 с.

3. Грис Д. Конструирование компиляторов для цифровых вычислительных машин /Пер.с англ. -М.: Мир, 1975.

4. Донован Дж. Системное программирование /Пер.с англ. -М.: Мир, 1975. -540с.

5. Ин Ц., Соломон Д. Использование Турбо-пролога. -М.: Мир, 1993.

6. Керниган Б.В., Пайк Р. UNIX - универсальная среда программирования /Пер.с англ. Березко, Иващенко. Под ред. М.И.Белякова -М.: Финансы и статистика, 1992. -304 с.

7. Марселлус Д. Программирование экспертных систем на Турбо-прологе. -М.: Финансы и статистика, 1994, -254с.

8. Хантер Р. Проектирование и конструирование компиляторов. -М.: Финансы и статистика, 1984.

• Размещено на Allbest.ru

...