Wie kann ich dieses DCG in Prolog erstellen?

Question

Ich möchte ein DCG, die Sprachen wie diese erstellen erhalten akzeptiert:

• c
• bbbcbbb
• bbacbba
• ABACABA
• aababacaababa

Wie Sie dieses Mittel sehen dass es eine bestimmte Reihenfolge von a und b gibt, dann eine c und dann wieder die exakt gleiche Reihenfolge wie vor der c. Wenn diese Bedingungen nicht erfüllt werden, wird es fehlschlagen.

Ich bin zur Zeit hier mit meinem Ansatz (Arbeiten, sondern erkennt auch falsche Wörter)

s --> x, s, x. 
s --> [c]. 
x --> [a]. 
x --> [b]. 

Kann jemand von euch mir helfen, was ich ändern muss? Ich weiß nicht, wie ich weitermachen soll. Danke vielmals.

Answer 1

Ein DCG ist wirklich nur ein Prolog-Programm, vorverarbeitet mit versteckten Argumenten, die eine Differenzliste implementieren. Wir können immer unsere eigenen Parameter hinzufügen und Pattern Matching verwenden. Dann

s --> ab(X), [c], ab(X). 
ab([a|T]) --> [a], ab(T). 
ab([b|T]) --> [b], ab(T). 
ab([]) --> []. 

?- atom_chars(aababacaababa,Cs),phrase(s, Cs). 
Cs = [a, a, b, a, b, a, c, a, a|...] 

Answer 2

Die Sprache, die Sie beschreiben, ist weder regulär noch kontextfrei. Sie müssen also auf die Prolog-Erweiterungen zurückgreifen, die in DCGs angeboten werden. Es gibt einige Idiome Sie vielleicht gewöhnungs:

% any sequence 

seq([]) --> 
    []. 
seq([E|Es]) --> 
    [E], 
    seq(Es). 

Mit dieser nicht-Terminal, könnten wir eine Sequenz beschreiben, die wiederholt wird, und durch ein Zeichen getrennt:

rep(Seq, Sep) --> 
    seq(Seq), 
    [Sep], 
    seq(Seq). 

Dies ergibt sich eindeutig zu allgemein ist. Sie wollten nur ab und c. Sie können nun weitere Anforderungen hinzu:

rep(Seq, Sep) --> 
    seq(Seq), 
    {phrase(abs,Seq)}, 
    [Sep], 
    seq(Seq). 

abs --> [] | ("a"|"b"), abs. 

So jetzt:

s --> 
    rep(_,c). 

Die Alternative zu "hard-Code" die Grammatik ist, wie @CapelliC gezeigt hat. Die Verwendung von seq//1 macht den Ansatz etwas flexibler.

Es ist sehr bequem, doppelte Anführungszeichen für die Liste der Zeichen zu verwenden. Siehe this answer, um die Verwendung von Anführungszeichen zur Darstellung einer Liste von Zeichen zu ermöglichen.