Шекет В.І. Конспект лекцій по логічному програмуванню
Подождите немного. Документ загружается.
append([s(likes),l([s(bill),s(mary)])],[s(bill)
,s(sue)],Ans), */
write("First List:",Ans),nl,nl,
/*The trick is to write the list first, than
add the functors *
* append([apple,[[[47],'\1']],[[["This is a
string",b,7, *
* 'w']],bee],['c'],Ans2) */
*
append([l[s("This"),s("is",s("a"),s("list"))]),
s(bee)],
[c('c')],Ans2),
write("Second List :",Ans2),nl.
clauses
/* Concatenate two lists */
append([],L,L).
append([X|L1],L2,[X|L3]):-append(L1,L2,L3).
8.6.Реалізація синтаксичного аналізу за допомогою
списків
Розглянемо задачу синтаксичного аналізу для деякої
примітивної мови програмування паскалеподібного типу.
Розіб'ємо задачу на дві підзадачі: сканування і
синтаксичний аналіз.
Розглянемо програму:
domains
toklist = string*
predicates
tokl(string, toklist)
clauses
tokl(Str, [H | T]):-fronttoken(Str,H,Str1),!,
tokl(Str1,T).
tokl(_,[]).
103
/* Друга частина програми є синтаксичним аналізатором */
domains
program = program(statementlist)
statementlist = statement*
/* визначення типу оператора */
statement =
if_Then_Else(exp,statement,statement);
if_Then(exp,statement);
while(exp,statement);
assign(id,exp)
/* визначення виразу */
exp = plus(exp,exp);
mines(exp,exp);
var(id);
int(integer)
id = string
predicates
s_program(toklist,program)
s_statement(toklist,toklist,statment)
s_statementlist(toklist,toklist,statmentlist)
s_exp(toklist,toklist,exp)
s_exp1(toklist,toklist,exp,exp)
s_exp2(toklist,toklist,exp)
clauses
s_program(List1,program(Statementlist)):-
s_statementlist(List1,List2,Statementlist),
List2=[].
s_statementlist([],[],[]):-!.
s_statementlist([List1,List4,[Statement
Program]):-
s_statement(List1,List2,Statement),
List2 = [";" | List3],
s_statementlist(List3,List4,Program).
104
s_statement(["if"| List1],List7,
if_theh_else(Exp,Statement1,Statement2)):-
s_exp(List1,List2, Exp),
List2 = [ "then" | List3],
s_statement(List3, List4, Statement1),
List4 = ["else" | List5],!,
s_statement(List5, List6, Statement2),
List6 = ["fi" | List7].
s_statement([" if.....
. . .
s_statement([ " do .....
. . .
s_statement([Id | List1], List3,
assign(Id,Exp)):-
isname(Id),
List1 = ["=" | List2],
s_exp(List2,List3,Exp).
s_exp(List1,List3,Exp):-
s_exp2(List1,List2,Exp1),
s_exp1(List2,List3,Exp1,Exp).
s_exp1(["+" | List1],List3,Exp1,Exp):-!,
s_exp2(List1,List2,Exp2),
s_exp1(List2,List3,plus(Exp1,Exp2),
Exp).
s_exp1(["-" ........
s_exp1(List,List,Exp,Exp).
s_exp2([Int | Rest],Rest, int(I)):-
str_int(Int,I),!.
s_exp2([Id | Rest],Rest,var(Id)):-
isname(Id).
105
Предикат tokl є сканером; він аналізує стрічку і
перетворює її в список лексем.
Всі предикати, які починаються з s є предикатами
синтаксичного анализу. В цьому прикладі вхідний текст є
программою на псевдопаскалі. Вона включає оператори: IF
THEN ELSE, IF THEN, DO WHILE і ASSIGNMENT. Для
побудови виразів використовуються дії додавання і
віднімання над змінними і константами цілого типу.
Програма працює наступним чином:
1.Перша фраза сканера, s_program, приймає список лексем і
перевіряє чи може він бути трансформований в список
тверджень.
2.Предикат s_statement приймає той же список лексем і
перевіряє чи зможуть лексеми бути разділені на індивідуальні
твердження, кожне з яких закінчується крапкою з комою.
3.Предикат s_statement перевіряє чи будуть перші лексеми
з списку лексем допустимими твердженнями. Якщо так, тоді
твердження повертається в структуру, а ті лексеми, що
залишились повертаються в s_statement.
а)Чотири фрази s_statement відповідають чотирьом
типам операторів псевдопаскалю. Вони аналізуються послідовно.
б)Потім проводиться порівняння з виразами.
4.Предикати sexp,s_exp1 і s_exp2 працюють аналогічно з
s_statment, але тільки по відношенню до виразів.
Якщо системі побудувати запит:
goal: tokl("b=2;
if b then a=1 else a=2 fi;
do a=a-1 while a ; ", Ans),
s_program(Ans,Res)
тоді вона побудує відповідь:
Ans = ["b", "=",...]
106
Res = program([assign("b", int(2)),
if_then_else(var("b"),
assign("a",int(1))........])
Завдання для практичних робіт
8.1.Визначте два предикати парна довжина (Список) і
непарна довжина (Список), таким чином, щоб вони були
істинними, якщо їх аргументом є список парної або непарної
довжини відповідно.
8.2.Визначте предикат паліндром (Список). Список
називається паліндромом, якщо він читається однаково, як зправа
наліво, так і зліва направо. Наприклад [м,а,д,а,м].
8.3.Визначте відношення переклад(Список1, Список2) для
модифікації списка чисел від 0 до 9 в список відповідних слів.
Наприклад,
переклад ([3,1,7],[три,один,сім])
8.4.Визначте відношення лінеризація (Список1,
ЛінійнийСписок), де ЛінійнийСписок - це той же список, але
“вирівняний” таким чином, що елементи його підсписків
складають один лінійний список.
Наприклад:
goal: лінеризація ([a,d,[c,d],[],[[[e]]],f],L).
L=[a,b,c,d,e,f].
107
9 ТЕХНІКА ПРОГРАМУВАННЯ В ПРОЛОЗІ
В цьому розділі ми розглянемо базові підходи до
реалізації основних типів алгоритмів в Пролозі.
9.1 Принципи побудови експертної системи
Розглянемо наступну задачу. Потрібно реалізувати
експертну систему, яка б визначала тварину, яку мав на увазі
користувач із семи зазначених. Експертна система знайде
тварину за допомогою опитування користувача. Цей приклад
демонструє бектрекінг для перегляду бази даних і показує
ефективне використання предикату not. Типовим діалогом
користувача з експертною системою може бути наступний:
goal: run.
Has it hair?
yes
does it eat meat?
yes
has it a fawn color?
yes
has it dark spots?
yes
Your animal may be a (an) cheetah!
Для програмування діалогу потрібні два кроки. Перший
крок заключається в наповненні бази системи знаннями, а
результуючий - в побудові виведення відповіді. Повна програма
приведена нижче:
database
xpositive(symbol, symbol)
xnegative(symbol,symbol)
predicates
tvaryna_je(symbol)
108
tse_je(symbol)
zapytannia(symbol,symbol,symbol)
pamjataty(symbol,symbol,symbol)
positive(symbol,symbol)
negative(symbol,symbol)
zrozymili_facty
run
clauses
tvaryna_je(cheetah):-tse_je(ssavetc),
tse_je(ssavetc),
positive(maje,tamny_color),
positive(maje,chorni_polosy).
tvaryna_je(tiger):- tse_je(ssavetc),
tse_je(mjasojidna),
positive(maje,tamny_color),
positive(maje,chorni_polosy).
tvaryna_je(zhyrafa):-tse_je(ungulate),
positive(maje,dovga_shyja),
positive(maje,dovgi_nogy),
positive(maje,chorni_polosy).
tvaryna_je(zebra):-tse_je(ungulate),
positive(maje,chorni_polosy).
tvaryna_je(ostrich):-tse_je(ptah),
negative(does,fly),
positive(maje,dovga_shyja),
positive(maje,dovga_shyja),
positive(maje,chornyj_i_bilyj_colir).
tvaryna_je(penguin):-tse_je(ptah),
negative(robyty,litaty),
positive(robyty,plavaty),
109
positive(maje,chornyj_i_bilyj_colir).
tvaryna_je(albatros):-
tse_je(ptah),positive(robyty,litaty_dobre).
tse_je(ssavetc):-positive(maje,sherst).
tse_je(ssavetc):-
positive(robyty,maje_moloko).
tse_je(ptah):-positive(maje,pirja).
tse_je(ptah):-positive(robyty,litaty),
positive(robyty,klade_jajcia).
tse_je(mjasojidna):-
positive(robyty,ijst_mjaso).
tse_je(mjasojidna):-
positive(maje,hostri_zuby),
positive(maje,kihti),
positive(maje,speredi_ochi).
tse_je(ungulate):-tse_je(ssavetc),
positive(maje,kopyta).
tse_je(ungulate):-tse_je(ssavetc),
positive(robyty,zhuvaty_zhujku).
positive(X, Y):-xpositive(X,Y), !.
positive(X, Y):-not(xnegative(X,Y)),
zapytannia(X,Y,yes).
110
negative(X,Y):- xnegative(X,Y), !.
negative(X,Y):- not(xpositive(X,Y)),
zapytannia(X,Y,no).
zapytannia(X,Y,yes):- !,
write(X, " it ", Y,
'\n'),
readln(Reply),
frontchar(Reply, 'y', _),
pamjataty(X, Y, yes).
zapytannia(X,Y,no):- !,
write(X, " it ", Y,
'\n'),
readln(Reply),
frontchar(Reply, 'n', _),
pamjataty (X, Y, no).
pamjataty(X,Y,yes):-assertz(xpositive(X,Y)).
pamjataty(X,Y,no) :-assertz(xnegative(X,Y)).
zrozymili_facty:-
write("\n\nPlease press the space bar to
exit\n"),
retractall(_, dbasedom), readchar(_).
run :-
tvaryna_je(X), !,
write("\nYour animal may be a (an) ",X),
nl, nl, clear_facts.
run :-
write("\nUnable to determine what"),
write("your animal is.\n\n"),
clear_facts.
111
Кожна тварина описується деяким числом характерних
атрибутів, які вона має або ж не має. Вони задаються в
предикатах tvaryna_je і tse_je. Питання, на які
користувачу потрібно відповісти, реалізуються за допомогою
використання предикатів рositive (X,Y) і negative
(X,Y). Але система, між іншим, може задати і питання типу :
Does it have hair?
Отримавши відповідь, система приєднує її до попередньої
інформації для подальшого використання.
Для простоти цей приклад програми буде розглядати
тільки стверджувальні та заперечувальні відповіді. Тому вона
використовує базу даних, яка містить тільки два предикати:
database
xpositive(symbol,symbol)
xnegative(symbol,symbol)
Наприклад, твердження , що тварина не має волосся тоді
може бути задане таким чином:
xnegative(maje,sherst).
Але, попередньо, перед тим , як задавати запитання,
система перевіряє чи відповідь не була відома раніше:
positive(X,Y):-
xpositive(X,Y),!.
positive(X,Y):- not
(xnegative(X,Y)),zapytannia(X,Y,yes).
negative(X,Y):-
xnegative(X,Y),!.
negative(X,Y):- not
(xpositive(X,Y)),zapytannia(X,Y,no).
Відмітимо, що останні правила, які використовуються тут
при визначенні предикатів positive і negative
забезпечують реалізацію тієї ситуації, щоб спростування не
трапилось раніше, ніж пройшло опитування користувача.
112