Doppelte Einträge prüfen

[Desmulator]

HalliHallo,

also es geht sich um folgendes: Ich hab eine Liste von Tokens. Jeder Token hat auf eine ID, die ich an, der den Tokenizer benutzt zurückgebe, wenn das passende Token erkannt wurde. Somit kann der die Daten dann richtig verarbeiten. Logisch?

Allerdings braucht mein Tokenizer für jedes Token eine Priorität. Ein Token mit hoher Priorität wird vor einem Token mit niedriger Priorität erkannt. Beispiel :

Der String soll in Tokens gesplittet werden:

keyword Es gibt zwei Tokens:

Delphi-Quellcode:

Den Key, als feste Zeichenfolge, "keyword".
Die ZeichenRange [k,e,y,w,o,r,d]. Dabei können die Buchstaben in beliebiger Reihenfolge auftreten.

Was wird also nun in dem String erkannt? A: Der Key oder B : Die ZeichenRange? Dafür sind die Proiorities, mit ihrer Hilfe wird das Problem gelöst.

So nun das Problem. Ich will die Tokens, die sich in einer Array befinden, darauf prüfen, ob es keine doppelte ID bzw. Priorität gibt.

Aufbau:

Delphi-Quellcode:

TToken = record
 ID : Cardinal;
 Proiority : Cardinal;
 ...
end;

Tokens : array of TToken;

Meine Idee war es eine art Liste ( set ) mit zu führen und jede Zahl, die nicht bereits in der Liste ist, hinzu zufügen.
Sollte sie jedoch existieren, so wird False zurückgeben.

Delphi-Quellcode:

function TTokenizer.CheckConflict : Boolean;
var
  Index : Cardinal;
  IDs : set of Cardinal;
  Prioritys : set of Cardinal;
begin
  Index := 0;
  repeat
    if Tokens[Index].ID in IDs then begin
      Result := False;
      Exit;
    end;
    Include(IDs, Tokens[Index].ID);
  until Index = Length(Tokens);
  Index := 0;
  repeat
    if Tokens[Index].Priority in Prioritys then begin
      Result := False;
      Exit;
    end;
    Include(Prioritys, Tokens[Index].Priority);
  until Index = Length(Tokens);
end;

Doch dann viel mir noch vor dem ersten kompilieren ein, dass ein Set maximal 255 Einträge haben kann und Cardinal ein bischen mehr ( ca. 4 Mrd. ) hat.

Wie könnte ich das noch machen? Ich versuche bewust zu vermeiden, eine Array mitzuführen , diese immer vollkommen zudurchlaufe und auf den selben eintrag zuprüfen.

Mfg Desmu

[Apollonius]

Ich denke, dass es auch für den weiteren Ablauf empfehlenswert ist, die Liste nach Priorität zu sortieren. Zum Einfügen führst du einfach eine binäre Suche durch und weißt damit dann auch, ob die Priorität schon vorhanden ist.
Damit bliebe noch das Problem mit den IDs. Wie viele Token gibt es denn?

[Desmulator]

Wenn ich dich richtig verstanden habe, soll die Priority von die Position in der Array dargstellt werden?

Nun die Anzahl der Tokens ist Variable, kommt darauf an wie viele Elemente die Sprache hat, die erkannt werden soll.
Desweiteren soll es möglich sein, die ID nicht nach der Reihenfolge vergeben zu können. Die IDs stellen lediglich
einen Erkennungswert für den Benutzer da.

Beispiel:

Delphi-Quellcode:

const
   MyTokenId : Cardinal = 12;

...

if Tokenizer.CurrentToken.Id = MyTokenId then
   //An dieser Stelle ist mein Token aufgetaucht.

Vondaher...

Atm überlege ich, ob ich die Kontrolle der ID's nicht weglassen kann, schließlich kann es ja der Fall sein dass mehrere Tokens den gleichen Bereich abdeken. z.B. Strings können sowohl mit ' als auch " beginnen, in diesem Fall wäre es sinnvoll nur eine ID zu verwänden.

Sollte dies und obriges der Fall sein, hat sich der Konflikttest auch erledigt.

[Apollonius]

Meine Idee war lediglich, das Token-Array nach der Priorität zu sortieren. Das macht das Prüfen auf doppelt vergebene Prioritäten sehr einfach und ist außerdem auch später nützlich, denn du schaust ja erst nach dem Token mit der höchsten Priorität, dann nach dem mit der zweithöchsten und so weiter. Das heißt aber nicht, dass die IDs in irgendeiner Weise mit der Priorität zusammenhängen müssen.

Meine Frage nach der Anzahl der Token stelle ich deshalb, weil du, wenn es nicht zu viele sind, leicht dein Set durch eine TBits-Instanz ersetzen kannst.

[Desmulator]

Ah okay.
Also erst sotieren und dann noch Dopplungen suchen?

Ich hatte den Sotieralgorythmus eh schon implementiert

[Apollonius]

Du kannst beides in einem machen, indem du Insertion Sort verwendest.