Zdroj


% Naprogramujte test zda řetězec odpovídá
% regulárnímu výrazu. Backtrackujte
% přes všechny možnosti ve správném pořadí.

% match(+Pattern, +String)

/* Pro zjednodušení mají vzory následující pravidla:
  - číslo odpovídá znaku s daným kódem,
    tedy například match("abc", "abc") uspěje
  - seznam vzorů odpovídá zřetězení
  - `any(Seznam)` uspěje pokud uspěje
    libovolný vzor ze seznamu (priorita zleva doprava)
  - `rep(N1, N2, Vzor)` odpovídá Vzoru opakovaném
    N1-krát až N2-krát. N2 může bý také `inf`
    a `rep(Vzor)` je zkratka za `rep(0,inf,Vzor)`.
    Preferují se *delší* opakování před kratšími.
  - `ref(Prom, Vzor)` matchuje Vzor
    a odpovídající podřetězec naunifikuje na Prom.

  Plný počet bodů jsou 3, bodování bude zhruba
  odpovídat míře fuknčnosti jednotlivých pravidel.
*/

% Pro lepší čitelnost zavedeme operátorovou syntaxi
:-
	op(180, xfy, ref),	% Var ref Exp
	op(160, fy, rep),	% Digits = rep Digit
	op(140, fy, any),	% Digit = any "0123456789"
	true.


% match(+Pattern, +String)
match(E, Str) :- match(E, Str, []).
% match(+Pattern, +String, -UnmatchedPart)

% character code
match(Ch, [Ch|Rest], Rest) :- integer(Ch).

% list means concatenation
match([], Str, Str).
match([H|T], Str, Rest) :-
	match(H, Str, R1),
	match(T, R1, Rest).

% choice
match(any Lst, Str, Rest) :-
	member(E, Lst),
	match(E, Str, Rest).

% reference
match(Var ref E, Str, Rest) :-
	match(E, Str, Rest),
	append(Var, Rest, Str).

% repeat
match(rep E, Str, Rest) :-	% a shortcut
	match(rep(0, inf, E), Str, Rest).
match(rep(I1, I2, E), Str, Rest) :-	% try longer
	(I2=inf, I2n=inf ; integer(I2), I2>0, I2n is I2-1),
	I1n is max(0,I1-1),
	match(E, Str, Rest1),
	match(rep(I1n, I2n, E), Rest1, Rest).
match(rep(0, _, _E), Str, Str).	% empty repeat

Dotazy


?-	AlNum = "abcdefghijklmnopqrstuvwxyz0123456789",
	AlNums = rep any AlNum,
	Chars = rep any [any AlNum, any "<>/ ."],
	SimpleTag = [
		Chars,
		"<", Tag ref AlNums, ">",
		Chars,
		"</", Tag ref AlNums, ">",
		Chars
	],
	HTML1 = "<h2>nad</h2> <p>od<i><b>ti</b></i><br>radek.</p>",
	match(SimpleTag, HTML1).
...
Tag = [98];
...
Tag = [105];
...
Tag = [112];
...
Tag = [104, 50];
false.

?-	AlNum = "abcdefghijklmnopqrstuvwxyz0123456789",
	AlNums = rep any AlNum,
	Addr = [
		Protocol ref any["http", "ftp"], "://",
		Server ref [ rep [AlNums,"."], AlNums ],
		Port ref rep(0,1,[ ":", any"0123456789" ]),
		Path ref rep ["/",AlNums]
	],
	match(Addr, "http://vcunat.matfyz.cz/vyuka/np").
AlNums = any[...],
Addr = [...],
Server = [118, 99, 117, 110, 97, 116, 46, 109, 97|...],
Port = [],
Path = [47, 118, 121, 117, 107, 97, 47, 110, 112] ;
false.


/* zakladni testy */
?-  match("test","test").
true.
?- match("test","testy").
false.
?- match("testy","test").
false.
/* any */
?- match(any "axbycz","c").
true ;
false.
?- match(any "axbycz","p").
false.
?- match(any ["ab","cd"],"cd").
true.
/* neomezene rep */
?-  match(rep any ["ab","cd"],"").
true.
?- match(rep any ["ab","cd"],"cdab").
true ;
false.
?- match(rep any ["ab","cd"],"abba").
false.
/* omezene rep */
?- match(rep(1,3,"a"),"aaa").
true ;
false.
?- match(rep(1,3,"a"),"aaaa").
false.
?- match(rep(1,3,"a"),"").
false.
?-  match(rep(1,3,"a"),"a").
true ;
false.
/* ref */
?- match(["s", X ref rep "a","e"],"saae").
X = [97, 97] ;
false.