Публикация первой части ( 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(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, что отключает возможность возврата предиката после его завершения.
2.DCG – грамматика Во всех учебниках PROLOG написано о DCG - Определенная грамматика предложений и описывается как волшебный инструмент для построения синтаксического анализатора с обсуждением списков различий и декларативной семантики.
На мой взгляд, DCG — это просто удобный оператор для сокращения обозначений при описании грамматик.
Сам ПРОЛОГ построен таким образом, что, непосредственно описав грамматику, можно получить парсер, точнее, его основу.
Грамматика простого арифметического выражения.
Пример = :: Стерм | Стерм AdSign Ex
Sterm = :: Термин AdSign | Срок
Срок =::Фактор | Фактор MuSign Term1
Термин1 = ::Срок | Срок действия MuSign Срок1
Коэффициент =:: (Ex) | Число
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 --> [')'].
Входные данные должны быть списком токенов.
е:- A=[12,'-',98,'*','(',19,'+',34,'*','(',200,'-',23,')',')' , ], ex(А,[]).
Если вы используете лексический анализатор, входную строку можно ввести с устройства: эс:- read_line(0,S), лекср(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= а([’+’|Т],Т) Терминальное правило хорошо иллюстрирует процессы, происходящие при выполнении разбора грамматики в PROLOG — каждое применение правила вычитает из входного списка необходимые символы, удовлетворяющие этому правилу.
В случае терминального символа он должен находиться в начале текущего списка; «хвост» списка передается дальше.
При вызове первого, входного, грамматического правила второй аргумент должен быть пустым списком, чтобы вся входная строка считалась до конца.
Очевидно, что любое правило в формате DCG можно легко переписать как оператор PROLOG базового типа — для нетерминальных правил нужно добавлять по два аргумента в каждый вызов и заголовок, а для терминального правила нужно просто подставить константу в заголовок.
Отсюда ясно, что «волшебство» простоты синтаксического анализа основано не на свойствах операторов DCG, а на собственной природе языка PROLOG. DCG полезен, поскольку устраняет необходимость вставлять две переменные в каждый вызов и гарантирует, что список входных и выходных данных каждого аргумента назван правильно.
Пользы от такой программы, конечно, немного, так как в результате вы получите только «Да» или «Нет».
Получить синтаксическое дерево выражения также несложно — достаточно добавить соответствующие аргументы.
Но в этом случае необходимо учитывать приоритет операций.
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. В третьей части мы рассмотрим использование Пролога для построения одного типа интеллектуальных систем — экспертных систем.
Теги: #Пролог #программирование #лексический анализ #синтаксический анализ #перевод #синтаксический анализ #программирование #Пролог
-
Как Настроить Компьютер Для Игр
19 Oct, 24 -
Два Странных Обновления Из Вконтакте
19 Oct, 24 -
Радио-Т №48. Бобук И Умпутун
19 Oct, 24
