Публикация первой части ( habrahabr.ru/post/274603 ) вызвала довольно обширную и интересную дискуссию по различным аспектам языка применения ПРОЛОГ.
Цель была – показать опытным, и не очень, программистам, что ничего сложного в Прологе нет, и каждый может его применять в работе.
Почему-то не было вопросов непосредственно по тексту публикации. Буду думать, что там все понятно.
Приступим к рассмотрению более практических аспектов программирования на языке Пролог.
В этом разделе рассмотрим основные аспекты реализации на языке ПРОЛОГ трансляции контекстно-свободных языков на примере арифметических выражений.
Как известно, PROLOG возник из атрибутных грамматик. Поэтому синтаксический анализ – первое и естественное применение этого языка.
В отличие от такого средства, как регулярные выражения, на PROLOG легко писать трансляторы для более сложных — контекстно-свободных языков.
Для транслятора необходимо иметь лексический анализатор, синтаксический анализатор и генератор объектного кода.
1.Лексический анализ
Лексический анализатор на входе имеет строку символов, на выходе — список лексических единиц. Рассмотрим лексический анализатор для арифметических выражений.
Исходный предикат lexr/2 выполняет преобразование строки символов в список кодов символов, удаление пробелов (delb/2), с последующим переходом к lexr1/2, который рекурсивно просматривает входной список, выделяя из него лексические единицы — служебные символы и целые числа — последовательности цифр.
Предикат lexr1/2 завершает работу при исчерпании входного списка символов.
Предикат term/4 из входного списка символов выделяет очередную лексическую единицу Hs, которая записывается в начало выходного списка вызывающего предиката. Четвертый аргумент — оставшийся список, который будет обработан на следующем шаге рекурсии. Второй аргумент — служебный, для накопления списка цифр целого числа. В начале устанавливаем его в [].
Предикат term/4 состоит из четырех процедур для четырех ситуаций, которые могут возникнуть при просмотре входного списка.
Если в голове списка находится служебный символ, заносим его в выходной список, предварительно преобразовав его в строку. Это при условии, что рабочая переменная содержит пустой список.
Если же очередной элемент списка — служебный символ, но в рабочей переменной есть значения, накопленный список цифр из второго аргумента преобразуем в строку и заносим в выходной список. При этом служебный символ заносится в выходной список для повторного рассмотрения на следующем рекурсивном шаге.
Если очередной символ — цифра, то она заносится в конец второго аргумента — служебного списка и рекурсия продолжается.
Четвертая процедура включается при исчерпании входного списка при поиске очередной цифры числа. Исчерпание списка означает завершение просмотра целого числа.
Сервисные предикаты spec/1, digit/1 обеспечивают проверку кода символа на соответствие служебному символу или цифре.
Предикат member/2 выполняет проверку вхождения элемента в список.
Предикат append/3 выполняет соединение двух списков.
Надо отметить, что предикат lexr/2 реализует детерминированные вычисления — без бэктрекинга, поскольку лексический анализ не требует возвратов.
При возникновении бэктрекинга, он может выдавать неправильный результат.
Для исключения бэктрекинга, который может взывать внешняя процедура, в конце lexr/2 вставлена операция отсечения -"!", которая отключает возможность бэктрекинга предиката после его завершения.
2.DCG – грамматика
Все учебники по ПРОЛОГу пишут про DCG – Definite Clause Grammar и описывают это как магическое средство для построения синтаксического анализатора, с рассуждениями про разностные списки и декларативную семантику.
По моему мнению, DCG – просто удобный оператор для сокращения записи при описании грамматик.
ПРОЛОГ сам по себе так устроен, что в нем можно, прямо описав грамматику, получить синтаксический анализатор, точнее говоря, его основу.
Грамматика простого арифметического выражения.
Ex = :: Sterm | Sterm AdSign Ex
Sterm = :: AdSign Term | Term
Term =:: Factor | Factor MuSign Term1
Term1 = :: Term | Term MuSign Term1
Factor =:: ( Ex) | Number
AdSign =:: ‘+’ | ‘-‘
MuSign =:: ‘*’ | ‘/’
Можно переписать это непосредственно в виде предложений DCG.
На вход надо подать список лексем.
e:-
A=[12,’-‘,98,’*’,’(‘,19,’+’,34,’*’,’(‘,200,’-‘,23,’)’,’)’, ],
ex(A,[]).
Если использовать лексический анализатор, входную строку можно ввести с устройства:
es:-
read_line(0,S),
lexr(S,L),
ex(L,[]).
Давайте посмотрим, как это работает. Есть такой встроенный предикат expand_term/2, который показывает, как система обрабатывает DCG – предложение.
Если набрать
expand_term((a--> b,c,d),L).
то получим:
L = a(A,B):-b(A,C),c(C,D),d(D,B)
Если набрать этот же предикат для терминального правила
expand_term((a--> [‘+’]),L).
то получим:
L= a([‘+’|T],T)
Терминальное правило хорошо иллюстрирует процессы, происходящие при выполнении грамматического разбора на ПРОЛОГе – каждое применение правила вычитает из входного списка нужные символы, удовлетворяющие этому правилу. В случае терминального символа, он должен находиться в голове текущего списка, «хвост» списка передается дальше.
При вызове первого, входного, правила грамматики, второй аргумент доложен быть пустым списком, чтобы была рассмотрена вся входная строка до конца.
Очевидно, что всякое правило в формате DCG легко переписать в виде основного типа предложений ПРОЛОГа – для нетерминальных правил надо добавить два аргумента в каждый вызов и заголовок, а для терминального правила – просто подставить константу в заголовок.
Отсюда ясно, что «магия» простоты реализации синтаксического анализа основана не на свойствах DCG – операторов, а на собственной природе языка ПРОЛОГ. DCG полезно тем, что освобождает от необходимости вставлять в каждый вызов две переменные и следить за правильным именованием входного и выходного списка каждого аргумента.
Конечно, пользы от такой программы немного, поскольку в качестве результата Вы получите только «Yes» или «No».
Получить синтаксическое дерево выражения также нетрудно – достаточно добавить соответствующие аргументы. Но в этом случае надо учесть приоритет операций.
3. Синтаксический анализ
Добавив один аргумент в каждое правило, получим на выходе синтаксическое дерево выражения. Здесь нам не понадобится прямая или обратная польская запись, поскольку синтаксическое дерево будет представлено непосредственно, в виде вложенных списков.
Для вызова такой программы надо указывать три параметра
Результат синтаксического анализа в приведенном примере будет иметь вид:
[-,10,[-,3,[+,5,4]]]
Рекурсивный предикат calc/2 выполняет вычисление значения арифметического выражения по его синтаксическому дереву.
Для данного примера результат будет – «16». Однако он оказывается неверным, должно быть «6»! Действительно – синтаксическое дерево построено неправильно – оно соответствует выполнению операций справа налево. Поскольку арифметические операции левоассоциативны, получен неверный результат.
Грамматика, которая годилась для проверки правильности арифметического выражения, была построена без учета ассоциативности операций.
Правило
ex([S,R1,R2]) --> sterm(R1), adsign(S),ex1(R2).
надо заменить на правило вида
ex([S,R1,R2]) --> ex(R1), adsign(S),term(R2).
Однако такое правило содержит левую рекурсию и будет зацикливаться. Что делать? Выход из положения такой – «раздробить» рекурсивный вызов на составные части, тогда уже рекурсия не будет левой – входной аргумент изменится!
Для данной грамматики синтаксическое дерево нашего примера будет иметь вид
[+,[-,[-,10,3],5],4]
а полученное значение будет равно «6».
4.Непосредственное вычисление
Синтаксическое дерево разбора выражения может быть использовано для генерации объектного кода путем рекурсивного просмотра процедурой, аналогичной вышеприведенной calc/2.
В тех случаях, когда требуется только вычисление арифметического выражения, можно не строить дерево, а выполнять вычисление в ходе синтаксического анализа.
В приведенной программе можно заметить фигурные скобки. Такие скобки используются в случае применения «обычных» предикатов ПРОЛОГа, т.е. для них не надо выполнять добавление двух аргументов.
На основе такого подхода можно строить трансляторы различных контекстно-свободных языков, в том числе, HTML, XML.
В третьей части рассмотрим применение Пролога для построения одного типа интеллектуальных систем — экспертных систем.
Цель была – показать опытным, и не очень, программистам, что ничего сложного в Прологе нет, и каждый может его применять в работе.
Почему-то не было вопросов непосредственно по тексту публикации. Буду думать, что там все понятно.
Приступим к рассмотрению более практических аспектов программирования на языке Пролог.
В этом разделе рассмотрим основные аспекты реализации на языке ПРОЛОГ трансляции контекстно-свободных языков на примере арифметических выражений.
Как известно, PROLOG возник из атрибутных грамматик. Поэтому синтаксический анализ – первое и естественное применение этого языка.
В отличие от такого средства, как регулярные выражения, на PROLOG легко писать трансляторы для более сложных — контекстно-свободных языков.
Для транслятора необходимо иметь лексический анализатор, синтаксический анализатор и генератор объектного кода.
1.Лексический анализ
Лексический анализатор на входе имеет строку символов, на выходе — список лексических единиц. Рассмотрим лексический анализатор для арифметических выражений.
Исходный предикат lexr/2 выполняет преобразование строки символов в список кодов символов, удаление пробелов (delb/2), с последующим переходом к lexr1/2, который рекурсивно просматривает входной список, выделяя из него лексические единицы — служебные символы и целые числа — последовательности цифр.
Предикат lexr1/2 завершает работу при исчерпании входного списка символов.
Предикат term/4 из входного списка символов выделяет очередную лексическую единицу Hs, которая записывается в начало выходного списка вызывающего предиката. Четвертый аргумент — оставшийся список, который будет обработан на следующем шаге рекурсии. Второй аргумент — служебный, для накопления списка цифр целого числа. В начале устанавливаем его в [].
Предикат term/4 состоит из четырех процедур для четырех ситуаций, которые могут возникнуть при просмотре входного списка.
Если в голове списка находится служебный символ, заносим его в выходной список, предварительно преобразовав его в строку. Это при условии, что рабочая переменная содержит пустой список.
Если же очередной элемент списка — служебный символ, но в рабочей переменной есть значения, накопленный список цифр из второго аргумента преобразуем в строку и заносим в выходной список. При этом служебный символ заносится в выходной список для повторного рассмотрения на следующем рекурсивном шаге.
Если очередной символ — цифра, то она заносится в конец второго аргумента — служебного списка и рекурсия продолжается.
Четвертая процедура включается при исчерпании входного списка при поиске очередной цифры числа. Исчерпание списка означает завершение просмотра целого числа.
Сервисные предикаты spec/1, digit/1 обеспечивают проверку кода символа на соответствие служебному символу или цифре.
Предикат member/2 выполняет проверку вхождения элемента в список.
Предикат append/3 выполняет соединение двух списков.
lexr(S,R):- list_text(L,S), delb(L,L1),lexr1(L1,R),!.
lexr1(L,[Hs|T1]):-
term(L,[],Hs,L1),
lexr1(L1,T1).
lexr1([],[]).
term([H|T],[],Hs,T):- spec(H),list_text([H],Hs).
term([H|T],L,I,[H|T]):-
L\=[],
spec(H),
list_text(L,Ls),
int_text(I,Ls).
term([H|T],L,R,Lr):-
digit(H),
append(L,[H],L1),
term(T,L1,R,Lr).
term([],L,I,[]):-
L\=[],
list_text(L,Ls),
int_text(I,Ls).
delb([32|T],L):-delb(T,L).
delb([H|T],[H|T1]):-delb(T,T1).
delb([],[]).
spec(H):-member(H,"+-*/()").
digit(H):- H>47, H<58.
append([H|T],L,[H|L2]):-append(T,L,L2).
append([],L,L).
member(H,[H|T]).
member(H,[H1|T]):-H\=H1,member(H,T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
lr:-
A = $(10-237*65+3/837467)-(342-678)$,
lexr(A,L),
write(A),nl,
write(L),nl.
Надо отметить, что предикат lexr/2 реализует детерминированные вычисления — без бэктрекинга, поскольку лексический анализ не требует возвратов.
При возникновении бэктрекинга, он может выдавать неправильный результат.
Для исключения бэктрекинга, который может взывать внешняя процедура, в конце lexr/2 вставлена операция отсечения -"!", которая отключает возможность бэктрекинга предиката после его завершения.
2.DCG – грамматика
Все учебники по ПРОЛОГу пишут про DCG – Definite Clause Grammar и описывают это как магическое средство для построения синтаксического анализатора, с рассуждениями про разностные списки и декларативную семантику.
По моему мнению, DCG – просто удобный оператор для сокращения записи при описании грамматик.
ПРОЛОГ сам по себе так устроен, что в нем можно, прямо описав грамматику, получить синтаксический анализатор, точнее говоря, его основу.
Грамматика простого арифметического выражения.
Ex = :: Sterm | Sterm AdSign Ex
Sterm = :: AdSign Term | Term
Term =:: Factor | Factor MuSign Term1
Term1 = :: Term | Term MuSign Term1
Factor =:: ( Ex) | Number
AdSign =:: ‘+’ | ‘-‘
MuSign =:: ‘*’ | ‘/’
Можно переписать это непосредственно в виде предложений DCG.
ex --> sterm.
ex --> sterm, adsign,ex.
sterm --> adsign, term.
sterm --> term.
term --> factor.
term --> factor,musign,term1.
term1 --> term.
term1 --> term, musign, term1.
factor --> [N],{number(N)}.
factor --> lb,ex,rb.
adsign --> ['+']. adsign --> ['-'].
musign --> ['*']. musign --> ['/'].
lb --> ['(']. rb --> [')'].
На вход надо подать список лексем.
e:-
A=[12,’-‘,98,’*’,’(‘,19,’+’,34,’*’,’(‘,200,’-‘,23,’)’,’)’, ],
ex(A,[]).
Если использовать лексический анализатор, входную строку можно ввести с устройства:
es:-
read_line(0,S),
lexr(S,L),
ex(L,[]).
Давайте посмотрим, как это работает. Есть такой встроенный предикат expand_term/2, который показывает, как система обрабатывает DCG – предложение.
Если набрать
expand_term((a--> b,c,d),L).
то получим:
L = a(A,B):-b(A,C),c(C,D),d(D,B)
Если набрать этот же предикат для терминального правила
expand_term((a--> [‘+’]),L).
то получим:
L= a([‘+’|T],T)
Терминальное правило хорошо иллюстрирует процессы, происходящие при выполнении грамматического разбора на ПРОЛОГе – каждое применение правила вычитает из входного списка нужные символы, удовлетворяющие этому правилу. В случае терминального символа, он должен находиться в голове текущего списка, «хвост» списка передается дальше.
При вызове первого, входного, правила грамматики, второй аргумент доложен быть пустым списком, чтобы была рассмотрена вся входная строка до конца.
Очевидно, что всякое правило в формате DCG легко переписать в виде основного типа предложений ПРОЛОГа – для нетерминальных правил надо добавить два аргумента в каждый вызов и заголовок, а для терминального правила – просто подставить константу в заголовок.
Отсюда ясно, что «магия» простоты реализации синтаксического анализа основана не на свойствах DCG – операторов, а на собственной природе языка ПРОЛОГ. DCG полезно тем, что освобождает от необходимости вставлять в каждый вызов две переменные и следить за правильным именованием входного и выходного списка каждого аргумента.
Конечно, пользы от такой программы немного, поскольку в качестве результата Вы получите только «Yes» или «No».
Получить синтаксическое дерево выражения также нетрудно – достаточно добавить соответствующие аргументы. Но в этом случае надо учесть приоритет операций.
3. Синтаксический анализ
Добавив один аргумент в каждое правило, получим на выходе синтаксическое дерево выражения. Здесь нам не понадобится прямая или обратная польская запись, поскольку синтаксическое дерево будет представлено непосредственно, в виде вложенных списков.
ex(R) --> sterm(R).
ex([S,R1,R2]) --> sterm(R1), adsign(S),ex(R2).
sterm([S,R,[]]) --> adsign(S), term(R).
sterm(R) --> term(R).
term(R) --> factor(R).
term([S,R1,R2]) --> factor(R1),musign(S),term1(R2).
term1(R) --> term(R).
term1([S,R1,R2]) --> term(R1), musign(S), term1(R2).
factor(N) --> [N],{number(N)}.
factor(R) --> lb,ex(R),rb.
adsign('+') --> ['+']. adsign('-') --> ['-'].
musign('*') --> ['*']. musign('/') --> ['/'].
lb --> ['(']. rb --> [')'].
Для вызова такой программы надо указывать три параметра
e3:-
S='10-3-5+4',
lexr(S,L),
ex(R,L,[]),
calc(R,Res),
write(S),nl,
write(R),nl,
write(Res),nl.
Результат синтаксического анализа в приведенном примере будет иметь вид:
[-,10,[-,3,[+,5,4]]]
Рекурсивный предикат calc/2 выполняет вычисление значения арифметического выражения по его синтаксическому дереву.
calc([S,A1,A2],Nr):-calc(A1,N1),calc(A2,N2),calc1(S,N1,N2,Nr),!.
calc(A1,A1):-A1\=[_|_].
calc1(*,N1,N2,Nr):- Nr is N1*N2.
calc1(/,N1,N2,Nr):- Nr is N1/N2.
calc1(+,N1,N2,Nr):- Nr is N1+N2.
calc1(-,N1,N2,Nr):- Nr is N1-N2.
Для данного примера результат будет – «16». Однако он оказывается неверным, должно быть «6»! Действительно – синтаксическое дерево построено неправильно – оно соответствует выполнению операций справа налево. Поскольку арифметические операции левоассоциативны, получен неверный результат.
Грамматика, которая годилась для проверки правильности арифметического выражения, была построена без учета ассоциативности операций.
Правило
ex([S,R1,R2]) --> sterm(R1), adsign(S),ex1(R2).
надо заменить на правило вида
ex([S,R1,R2]) --> ex(R1), adsign(S),term(R2).
Однако такое правило содержит левую рекурсию и будет зацикливаться. Что делать? Выход из положения такой – «раздробить» рекурсивный вызов на составные части, тогда уже рекурсия не будет левой – входной аргумент изменится!
ex(E)-->eterm(E).
ex([S,E1,E2])-->sterm(E1),sn(S),eterm(E2).
sterm(E)-->eterm(E).
sterm([S,E1,E2])-->eterm(E1),sn(S),eterm(E2).
sterm([S2,[S1,E1,E2],E3])--> eterm(E1),sn(S1),sterm(E2),sn(S2),eterm(E3).
eterm(E)-->fct(E).
eterm([S2,[S1,E1,E2],E3])--> fct(E1),sn2(S1),eterm(E2),sn2(S2),fct(E3).
eterm([S,E1,E2])-->fct(E1),sn2(S),fct(E2).
sn2(*)-->[*]. sn2(/)-->[/]. sn2(div)-->[div]. sn2(mod)-->[mod]. sn2(and)-->[and].
fct(E)-->number(E).
fct(E)-->lb,ex(E),rb.
fct(E)-->snot,fct(E).
number(X)-->[X],{number(X)}.
lb-->['('].
rb-->[')'].
sg(+)-->[+].
sg(-)-->[-].
sn(E)-->sg(E).
Для данной грамматики синтаксическое дерево нашего примера будет иметь вид
[+,[-,[-,10,3],5],4]
а полученное значение будет равно «6».
4.Непосредственное вычисление
Синтаксическое дерево разбора выражения может быть использовано для генерации объектного кода путем рекурсивного просмотра процедурой, аналогичной вышеприведенной calc/2.
В тех случаях, когда требуется только вычисление арифметического выражения, можно не строить дерево, а выполнять вычисление в ходе синтаксического анализа.
ex(E)-->eterm(E).
ex(R)-->sterm(E1),sn(S),eterm(E2),{clc([S,E1,E2],R)}.
sterm(E)-->eterm(E).
sterm(R)-->eterm(E1),sn(S),eterm(E2),{clc([S,E1,E2],R)}.
sterm(R)-->eterm(E1),sn(S1),sterm(E2),sn(S2),eterm(E3),{clc([S1,E1,E2],N),
clc([S2,N,E3],R)}.
eterm(E)-->fct(E).
eterm(R)-->fct(E1),sn2(S1),eterm(E2),sn2(S2),fct(E3),{clc([S1,E1,E2],N),
clc([S2,N,E3],R)}.
eterm(R)-->fct(E1),sn2(S),fct(E2),{clc([S,E1,E2],R)}.
sn2(*)-->[*]. sn2(/)-->[/]. sn2(div)-->[div]. sn2(mod)-->[mod]. sn2(and)-->[and].
fct(E)-->number(E).
fct(E)-->lb,ex(E),rb.
number(X)-->[X],{number(X)}.
lb-->['('].
rb-->[')'].
sg(+)-->[+].
sg(-)-->[-].
sn(E)-->sg(E).
clc(A1,A1):-A1\=[_|_].
clc([*,N1,N2],Nr):- Nr is N1*N2.
clc([/,N1,N2],Nr):- Nr is N1/N2.
clc([+,N1,N2],Nr):- Nr is N1+N2.
clc([-,N1,N2],Nr):- Nr is N1-N2.
В приведенной программе можно заметить фигурные скобки. Такие скобки используются в случае применения «обычных» предикатов ПРОЛОГа, т.е. для них не надо выполнять добавление двух аргументов.
На основе такого подхода можно строить трансляторы различных контекстно-свободных языков, в том числе, HTML, XML.
В третьей части рассмотрим применение Пролога для построения одного типа интеллектуальных систем — экспертных систем.