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.