2012-09-25 11 views
6

Ich versuche Regular Expression Matching zu tun. Ich habe alle Funktionen ausgeschrieben, aber sie funktionieren nicht so wie sie sollten. Von dem, was ich sagen kann, hat es ein Problem, wenn ich versuche, eine Liste zu vergleichen.
Zum Beispiel "re_contains (a, a)." gibt wahr (offensichtlich), ebenso wie "re_contains (union (a, b), a)".Regulärer Ausdruck Matching Prolog

Aber sobald ich es eine Liste mache, scheitert es. "re_contains (seq (a, b), [a, b])." gibt false zurück. Append sollte alle möglichen Kombinationen durchlaufen, um die Übereinstimmung zu finden, aber keine dieser Funktionen funktioniert ordnungsgemäß. Das bringt mich dazu, dass ich vielleicht einen Basisfall vermisse. Aber ich denke "re_contains (X, L): - X == L." sollte sich darum kümmern. Ich muss hier etwas Wichtiges übersehen.

Hier ist mein Code:

re_contains(empty, []). 

re_contains(X, L) :- 
    X == L. 

re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

re_contains(union(X, _), L) :- 
    re_contains(X, L). 

re_contains(union(_, Y), L) :- 
    re_contains(Y, L). 

re_contains(kleene(X), L) :- 
    append([Car|L1], L2, L), 
    re_contains(X, [Car|L1]), 
    re_contains(kleene(X), L2). 

re_contains(kleene(_),[]). 

Antwort

5

append/3 wird geteilt L, und beide L1 und L2 werden Listen sein.

Ich würde versuchen, re_contains(X, L) :- X == L. mit re_contains(X, [X]).

Nach dem Wechsel zu ersetzen, wird re_contains(a,a). scheitern.

Sie stellen die Sequenz auf verschiedene Arten dar, und Ihr Matcher bietet nicht beides. Tatsächlich sind die einzigen Fälle, die "arbeiten" nicht Sequenzen.

+0

're_contains' funktioniert mit Sequenzen. C.f. 're_contains ([a], [a])'. – false

+0

sicher, aber das OP verwendet keine Listen, um den regulären Ausdruck darzustellen. Ich habe vorgeschlagen, solche Diskrepanzen zu beseitigen. – CapelliC

+0

Die Tatsache, dass es "re_contains (X, L): - X == L." gibt, deutet darauf hin, dass Listen gemeint sind. – false

8

Es gibt mehrere Probleme. Hier sind die offensichtlichsten:

Typisierung. Ihr Prädikat re_contains/2 erwartet eine Liste als zweites Argument. Dass re_contains(a,a). gelingt, ist eher Zufall als Absicht.

Monotonie. Ein weiteres Problem ist, dass re_contains([a],[a]) erfolgreich ist, aber re_contains([X],[a]) schlägt fehl. Oder, um es aus einem anderen Blickwinkel zu sehen: re_contains([X],[a]) schlägt fehl, aber X = a, re_contains([X],[a]) gelingt. Durch das Hinzufügen des Ziels X = a haben wir die Abfrage so spezialisiert, dass die ursprünglich fehlerhafte Abfrage erneut fehlschlagen sollte.

Die Prüfung auf Identität (==/2) sollte durch Gleichheit (=/2) und ersetzt werden, die sicherstellen, dass wir eine Liste haben. Also:

 
re_contains(X, L) :- 
    % X == L. 
    X = L, 
    append(X,_,_). 

Hinweis ist, dass append/3 hier nur verwendet, dass X, um sicherzustellen, ist eine Liste - die tatsächliche Anfügen Funktionalität nicht verwendet wird.

Effizienz. Das dritte Problem betrifft die tatsächliche Art und Weise, wie Sie die Verkettung darstellen. Schauen wir uns nur an die folgende Regel:

 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

Es sei nun angenommen, dass wir hier eine Liste der Länge N haben. Wie viele Antworten sind für das Ziel append(L1, L2, L) möglich? Eigentlich N + 1. Und dies unabhängig von den tatsächlichen Werten.Betrachten wir nun:

?- length(L,1000000), time(re_contains(seq([a],[]),[b|L])). 
% 2,000,005 inferences, 0.886 CPU in 0.890 seconds (100% CPU, 2258604 Lips) 
false. 

re_contains/2 Bedürfnisse hier Zeit proportional zur Länge der Liste. Aber es würde ausreichen, das erste Element zu betrachten, um zu erkennen, dass dies unmöglich ist.

Also das Problem ist die Verwendung von append/3. Es gibt eine einfache Faustregel für Prolog: Wenn Sie zu viel append/3 verwenden, verwenden Sie s — Definite Clause Grammars. Bitte schauen Sie in das Tag für weitere Details — und konsultieren Sie einen einleitenden Prolog Text. Um Ihnen einen Start zu geben, hier ist ein Teil Ihrer Definition:

 
re_contains(RE, L) :- 
    phrase(re(RE), L). 

re([]) --> []. 
re([E]) --> [E]. 
re(seq(X,Y)) --> 
    re(X), 
    re(Y). 

, die nicht mehr die gesamte Liste nicht untersuchen:

 
?- length(L,1000000), time(phrase(re(seq([a],[])),[b|L])). 
% 6 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 127313 Lips) 
false. 

BTW, here ist eine vollständige Definition.

Terminierung/Nicht-Terminierung. In Bezug auf Effizienz ist die Eigenschaft der Kündigung. Im Idealfall endet eine Abfrage, wenn die Menge der Lösungen endlich dargestellt werden kann. Das heißt, durch eine endliche Anzahl von Antworten. OK, das ist das Ideal, nach dem wir streben. Prologs einfacher aber sehr effizienter Ausführungsalgorithmus wird manchmal eine Schleife bilden, wenn eine endliche Anzahl von Antworten möglich gewesen wäre. Das Verständnis des Grundes der Nicht-Kündigung ist manchmal sehr schwierig. Die üblichen Debugging-Strategien – wie Tracen oder Durchlaufen mit einem Debugger – funktionieren nicht, da sie Ihnen viel zu viele Details zeigen. Zum Glück gibt es eine bessere Technik:

Anstatt auf Ihr gesamtes Programm zu schauen, werde ich wieder nur ein sehr kleines Fragment davon betrachten. Dieses Fragment ist ein failure slice (siehe den Link für weitere Details). Es ist viel kleiner, sagt aber eine Menge über das ursprüngliche Programm — vorausgesetzt, dass ein reines, monotones Programm war:

Wenn ein Fehler-Slice nicht beendet wird, dann wird das ursprüngliche Programm nicht beendet.

Wenn wir also eine solche Fehlerscheibe finden, können wir sofort Rückschlüsse auf das gesamte Programm ziehen. Ohne den Rest zu lesen!

Hier ist so eine interessante Ausfall Scheibe:

 
... 
re_contains(X, L) :- false, 
    X = L 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), false, 
    re_contains(X, L1), 
    re_contains(Y, L2). 
re_contains(union(X, _), L) :- false, 
    re_contains(X, L). 
... 

Betrachten wir nun das Ziel re_contains(seq([],[]),L). Idealerweise sollte es genau eine Antwort L = [] und das Ziel beenden sollte. Es koppelt jedoch, da append(L1, L2, L) nicht beendet wird. Vergleichen Sie dies mit der obigen DCG-Lösung, die für phrase(re(seq([],[])),L) endet.

+0

Danke. Mir ist die Prolog-Syntax völlig unbekannt. Ich glaube, ich versuchte mehr von einem C# if-Statement zu machen. –