1:- module(expr, [expr/2, expr/3, expr/4, expr/5, expr/6]).    2% expr : a  module for handy parsing on regular expressions.
    3%       2006-2011
    4%	2013 September
    5%	@author  Kuniaki Mukai
    6%
    7%	expr(?E:term, +A:list, @B:list) is nondet.
    8%       True if d-lists A-B is an instance of E.
    9%
   10%	expr(?E:term, -X:list, @Y:list, +A:list, @B:list) is nondet.
   11%       True if both d-lists A-B and X-Y denote a same list
   12%	which is an instance of E, where the symbol P-Q denotes
   13%	the list D such that append(D, Q, P) holds.
   14
   15% 1. Regular expressions.
   16% 1.1  Basic regular expressons.
   17%	[....] 		(Prolog list, may be a variable)
   18%	dot		( . )
   19%	dot([...])	( [...] )
   20%	out([...])	( [^...] )
   21%	*(E)		(Kleene's star)
   22%	+(E)		(Kleene's star without adding null)
   23%	E + E0		(binary concatenation)
   24%	E^N		( E + E +...+ E (N times) )
   25%	?(E)		(E or null)
   26%	char(L)		(char_type in L)
   27%	code(L)		(code_type in L)
   28%	skip		(skip to the end)
   29%	nil		(the list is nil)
   30%	rest		(to feed the rest of the list)
   31%	E | E0		(disjunction, union)
   32%	E & E0		(conjunction, intersection)
   33%	\+ E		(complement of E)
   34%
   35% 1.2	special
   36%	@(A)		(phrase(A))   (deleted)
   37%
   38% 2. A query terminates for Kleene's closures *(E) of
   39%	a regular expression E if E is proper, where E is proper
   40%	if the null list is not an instance of E.  The user is responsible
   41%	for making sure that his  Kleene's closures are proper.
   42%
   43% 3. For the Kleene closure *(E) of E, the parser works
   44%	in a greedy way in finding strings that matches *(E).
   45%
   46% 4. Very simple, short and straightforward implementation in DCG.
   47%
   48% expr/2.  for compatibility)
   49expr	--> [].
   50expr	--> [_], expr.
   51
   52% expr/3,4,5.  for compatibility)
   53expr(E)		--> kleene(E, min).
   54expr(E, X)	--> kleene(E, min, X, []).
   55expr(E, X, Y)	--> kleene(E, min, X, Y).
   56expr(E, M, X, Y)	--> kleene(E, M, X, Y).
   57
   58% Sample queries:
   59
   60% ?- expr:kleene(X, min, [a,b,c], R).
   61% ?- expr:kleene(X, max, [a,b,c], R).
   62% ?- expr:kleene( *(dot), max, [a,b,c], R).
   63% ?- expr:kleene( (X + X + X),min, [a,b,c,a,b,c,a,b,c], R).
   64% ?- expr:kleene( (X + X + X),max, [a,b,c,a,b,c,a,b,c], R).
   65% ?- expr:kleene( (X + X)^2, min,[a,a,a,a,a,a], R).
   66% ?- expr:kleene( (X + X)^2, max,[a,a,a,a,a,a], R).
   67% ?- expr:kleene( (X + X)^2, max,[a,a,a,a,a,a], R).
   68% ?- expr:kleene( (*([a])) + X + [c] + (*([c])), min,[a,a,b,b,c,c], R).
   69% ?- expr:kleene( (*([a])) + X + [c] + (*([c])), max,[a,a,b,b,c,c], R).
   70% ?- expr:kleene( (+([a,a])) + X + (+([c,c])), min, [a,a,b,c,c], R).
   71% ?- expr:kleene( (+([a,a])) + X + (+([c,c])), max, [a,a,b,c,c], R).
   72% ?- expr:kleene( (+dot) + (+dot), min, [a,b,c,d], R).
   73% ?- expr:kleene( (+dot) + (+dot), max, [a,b,c,d], R).
   74% ?- expr:kleene( &(*([a]), *([b])), min, [a,b], R).
   75% ?- expr:kleene( &(*([a]), *([b])), max, [a,b], R).
   76% ?- expr:kleene( *([a]) + (*(dot)), min, [a,a,a,d,e,f], R).
   77% ?- expr:kleene( *([a]) + (*(dot)), max, [a,a,a,d,e,f], R).
   78
   79% kleene/4
   80kleene([], min)		--> [].
   81kleene([C|R], min)	--> !, [C], kleene(R, min).
   82kleene([C|R], max)	--> [C], kleene(R, max).
   83kleene([], max)		--> !, [].
   84kleene(X+Y, M)		--> kleene(X, M), kleene(Y, M).
   85kleene(dot, _)		--> [_].
   86kleene(dot(L), _)	--> [C], {kleene_dot(C,L)}.
   87kleene(out(L), _)	--> [C], {\+kleene_dot(C,L)}.
   88kleene(*(E), M)		--> kleene_star(E, M). % E must be proper.
   89kleene(+(E), M)		--> kleene(E, M), kleene_star(E, M).
   90kleene(?(E), M)		--> kleene(E, M); [].
   91kleene(E^N, M)		--> kleene_repeat(N,E, M).
   92kleene(char(L), _)	--> [C], {char_type(C,L)}.
   93kleene(code(L), _)	--> [C], {code_type(C,L)}.
   94kleene((E|E0), M)	--> kleene(E, M); kleene(E0, M).
   95kleene(\+(E), M)	-->  \+ kleene(E, M).
   96kleene(&(E,E0), M, A,B) :-  kleene(E,M,A,B), kleene(E0,M,A,B).
   97kleene(nil,_,[],[]).
   98kleene(rest,_,_,[]).
   99kleene(min(E), _)	--> kleene(E, min).
  100kleene(max(E), _)	--> kleene(E, max).
  101
  102%
  103kleene_star(E, min)	--> !, ([]; kleene(E, min), kleene_star(E, min)).
  104kleene_star(E, _)	--> ( kleene(E, max), kleene_star(E, max) ; [] ).
  105
  106% kleene/6
  107kleene([], min, X,X)	--> [].
  108kleene([C|R],min,[C|X],Y) --> !, [C], kleene(R,min,X,Y).
  109kleene([C|R],max,[C|X],Y) --> [C], kleene(R,min,X,Y).
  110kleene([], max, X, X)	--> !, [].
  111kleene(E+E0,M,X,Y)	--> kleene(E,M,X,X0), kleene(E0,M,X0,Y).
  112kleene(*(E),M,X,Y)	--> kleene_star(E,M,X,Y).
  113kleene(+(E),M,X,Y)	--> kleene(E,M,X,X0), kleene_star(E,M,X0,Y).
  114kleene(dot,_,[C|X],X)	--> [C].
  115kleene(dot(L),_,[C|X],X)	--> [C], {kleene_dot(C,L)}.
  116kleene(out(L),_,[C|X],X)	--> [C], {\+kleene_dot(C,L)}.
  117kleene(code(L),_,[C|X],X)	--> [C], {code_type(C,L)}.
  118kleene(char(L),_,[C|X],X)	--> [C], {char_type(C,L)}.
  119kleene(E^N,M,X,Y)		--> kleene_repeat(N,E,M,X,Y).
  120kleene(?(E),M,X,Y)	--> kleene(E,M,X,Y); { X = Y }.
  121kleene((E|E0),M,X,Y)	--> kleene(E,M,X,Y); kleene(E0,M,X,Y).
  122kleene(\+(E),M,X,Y)	--> \+ kleene(E, M,X,Y).
  123kleene(max(L),_,X, Y)	--> kleene(L,max,X,Y).
  124kleene(min(L),_,X,Y)	--> kleene(L,min,X,Y).
  125kleene(&(E,E0),M,X,Y,A,B) :- kleene(E,M,X,Y,A,B), kleene(E0,M,X,Y,A,B).
  126kleene(nil,_,X,X,[],[]).
  127kleene(rest,_,A,B,X,[])   :- append(X, B, A).
  128
  129%
  130kleene_star(_, min, X, X) --> [].
  131kleene_star(E, min, X, Y) --> !, kleene(E, min, X, X0),
  132	{compound(X)},
  133	kleene_star(E, min, X0,Y).
  134kleene_star(E, max, X, Y) --> kleene(E, max, X, X0),
  135	{compound(X)},
  136	kleene_star(E, max, X0,Y).
  137kleene_star(_,max,X,X) --> [].
  138
  139%  compare for code/char type
  140kleene_dot(A,[A|_])	:- !.
  141kleene_dot(A,[B-C|_])	:- B @=< A, A @=< C, !.
  142kleene_dot(A,[_|L])	:- kleene_dot(A,L).
  143
  144%
  145kleene_repeat(0,_,_)	--> [].
  146kleene_repeat(N,E,M)	--> {N>0}, kleene(E, M),
  147	{N1 is N-1},
  148	kleene_repeat(N1,E,M).
  149
  150%
  151kleene_repeat(0,_,_,X,X)--> [].
  152kleene_repeat(N,E,M,X,Y)--> {N>0}, !,
  153	kleene(E,M,X,X0),
  154	{N1 is N-1},
  155	kleene_repeat(N1,E,M,X0,Y)