RegEx Parser написан на прологе - PullRequest
Новая
       7

RegEx Parser написан на прологе

8 голосов
/ 22 января 2011

Я уже несколько часов бьюсь головой об стену по этой задаче. Мы должны разобрать регулярное выражение с Прологом. По большей части предикаты у меня работают, но есть несколько регулярных выражений и строковых комбинаций, которые заставляют их исчерпывать пространство стека в SWI-Prolog. Вот пример с двумя комбинациями строк Regex, одна из которых работает, а другая нет: 

star(star(char(a))), []
star(star(char(a))), [a]

Первый работает, а второй выходит из стека.

Вот предикаты, которые я использую: 

re_match(epsilon, []).
re_match(char(Letter), [Letter]).
re_match(star(_), []).
re_match(seq(Rx1, Rx2), List) :- append(List1, List2, List),  re_match(Rx2, List2),  re_match(Rx1, List1).
re_match(alt(Rx1, Rx2), List) :- re_match(Rx1, List); re_match(Rx2, List).
re_match(star(Rx), List) :- append(List1, List2, List), re_match(Rx, List1), re_match(star(Rx), List2).

Я не уверен, какие изменения мне нужно внести, чтобы заставить его работать, но я не уверен, что еще делать.

Кроме того, изменение List: - добавление (List1, List2, List) к [H | T] не оценивается как true для одного из примеров.

Ответы [ 2 ]

7 голосов
/ 22 января 2011

Рассмотрите возможность использования записи DCG для лучшей читабельности и упрощения рассуждений о свойствах завершения: 

:- op(100, xf, *).

rexp(eps)      --> [].
rexp([T])      --> [T].
rexp(_*)       --> [].
rexp(R*)       --> rexp(R), rexp(R*).
rexp(s(R1,R2)) --> rexp(R1), rexp(R2).
rexp((R1|R2))    --> ( rexp(R1) ; rexp(R2) ).

Пример использования length / 2 для создания все более длинных списков для создания строк, которые соответствуют регулярному выражению: 

?- length(Ls, _), phrase(rexp(s(([a]|[b]),[c]*)), Ls).
Ls = [a] ;
Ls = [b] ;
Ls = [a, c] ;
Ls = [b, c] ;
Ls = [a, c, c] ;
etc.
6 голосов
/ 22 января 2011

У меня нет доступа к SWI Prolog сейчас, но вот предположение:

Попробуйте изменить 

re_match(star(Rx), List) :- append(List1, List2, List),
                            re_match(Rx, List1),
                            re_match(star(Rx), List2).

до 

re_match(star(Rx), List) :- append([H|List1], List2, List),
                            re_match(Rx, [H|List1]),
                            re_match(star(Rx), List2).

, чтобы заставить re_match "съесть что-нибудь", когда оно повторяется в конструкции звезды.

...