3. vom istream zum iterator

vom istream zum iterator

  • B

    Hallo zusammen.

    Folgendes Szenario:
    Ich habe einen Scanner(-Generator) geschrieben der dem Konzept von boost::spirit sehr ähnelt. Da ich mit Backtracking arbeite bekommt das generierte Scanner-Objekt als Eingabe zwei beliebige Vorwärts-Iteratoren via Konstruktor. Den Anfang und das Ende. Die Ausgabe der Tokens erfolgt aber durch den Shift-Operator. D.h. ich habe den Operator

    Scanner& operator>>(Scanner& lhs, Token& rhs)

    überladen. Somit stellt mein Scanner-Objekt in gewisser Weise eine Art "Stream" dar.

    Folgendes Problem:
    Wenn ich jetzt aber nur den Scanner in eine Konsolen-Anwendung verpacken möchte, bräuchte ich idealer Weise eine Art Container der als Puffer zwischen istream (z.B. cin) und und Char-Vorwärts-Iteratoren fungiert. D.h. der Container müsste mit einem istream als Parameter erstellt werden. Er Müsste konstante Iteratoren für den Anfang und das Ende des Streams bereitstellen, obwohl das Ende des Streams noch nicht erreicht wurde und der Kontainer ständig befüllt wird. Falls ein Iterator auf eine noch nicht geladene Speicherstelle gesetzt wird, müssten die Daten vom Stream nachgeladen werden. Der Container müsste den gesamten Stream-Inhalt puffern, da die aus dem Scanner resultierenden Token die assoziierten Strings nicht selbst speichern, sondern nur Iteratoren auf den ursprünglichen Text halten.

    Es wird noch schlimmer:
    Als nächstes werde ich einen Parser(-Generator) schreiben. Der soll in der selben Anwendung, aber eventuell in einem anderen Thread arbeiten. Das Problem wird das selbe sein wie jetzt beim Scanner, da der Parser wohl nicht ums Backtracking herum kommen wird. Als Eingabe bekommt er wieder Iteratoren, nur diesmal auf Token statt auf chars. Der Scanner liefert aber nur einen "Token-Stream". Das erweitert die Anforderungen an den oben gewünschten Container aber nur gering. Der Container muss also statt einem istream beliebige Objekte verwenden können auf denen der Operator

    StreamType& operator>>(StreamType& lhs, ObjectType& rhs)

    oder sonst eine ähnliche Funktion definiert ist. Des Weiteren sollte der Vorgang thread-sicher sein, damit Scanner und Parser gleichzeitig arbeiten können.

    Lange Rede kurzer Sinn:
    Ich habe das Gefühl, nicht um einen solchen Container herum zu kommen. Meine Internetrecherchen haben nichts brauchbares ergeben und meine Kenntnisse hinsichtlich der Details der STL usw halten sich in Grenzen. Ich glaube aber auch nicht, dass ich der erste bin, der einen solchen Container benötigt. Falls also jemand einen Rat, einen Hinweis, einen Link oder Implementierungsvorschläge hat wär ich sehr dankbar.

    Mfg, blablub

    0
  • C

    Um über einen Eingabestream zu iterieren, gibt es istream_iterator<> und istreambuf_iterator<> (so, wie ich das verstanden habe, brauchst du letzteres). Um deine Tokensequenz (btw, wie verwaltest du diese Sequenz intern?) abarbeiten zu können, benötigst du vermutlich einen eigenen Iterator.

    PS: Du weißt aber, daß man Vorwärts-Iteratoren nicht zuverlässig kopieren kann? Das könnte Probleme geben beim Backtracking.

    0
  • B

    Erst mal danke für die schnelle Antwort.

    PS: Du weißt aber, daß man Vorwärts-Iteratoren nicht zuverlässig kopieren kann? Das könnte Probleme geben beim Backtracking.

    Nein wusste ich nicht. Da habe ich wohl den Begriff Vorwärts-Iterator falsch verwendet. Was ich ausdrücken wollte, ist das ich nur den Operator Iterator& operator++(Iterator& rhs) verwende. Kopieren muss ich den aber natürlich. Zu Testzwecken kam bis jetzt immer nur ein einfacher const char* zum Einsatz.

    Um über einen Eingabestream zu iterieren, gibt es istream_iterator<> und istreambuf_iterator<> (so, wie ich das verstanden habe, brauchst du letzteres).

    Stimmt, der istreambuf_iterator<> scheint meinen Anforderungen schon sehr nahe zu kommen. Das Problem ist aber, wie du ja schon gesagt hast, dass man istream_iterator<> und istreambuf_iterator<> nicht kopieren kann.
    Kann denn ein streambuf beliebig viele Daten speichern, so dass das kopieren von Iteratoren funktionieren könnte?

    wie verwaltest du diese Sequenz intern?

    Meine Implemetierung hat sich genau in dem Punkt geändert. Vorher hatte ich die Token selbst in nem Vector verwaltet. Jetzt rufe ich eine vorher mit dem Scanner assoziierte Funktion auf und übergebe ihr das jeweils erstellte Token. Der Scanner speichert also keine Token. In dem Sinne bin ich ziemlich flexibel. Es muss halt nur ein Container da hinter der die Daten(Token) speichert und die gewünschten Iteratoren unterstützt.

    Um deine Tokensequenz abarbeiten zu können, benötigst du vermutlich einen eigenen Iterator.

    Genau das möchte ich vermeiden. Aber wenn es sich nicht vermeiden lässt, muss ich wohl doch selbst Hand anlegen...

    0
  • T

    Widersprechen sich denn nicht eigentlich Backtracking und Vorwärtsiteratoren, d.h. ich meine, daß du mindestens einen bidirektionalen Iterator brauchst.
    (denn wie CStoll ja sagte, kann es Problem beim Kopieren von reinen Vorwärtsiteratoren geben, da der Speicher evtl. schon wieder aufgeräumt wurde).

    Und ein Scanner sollte eigentlich kein Backtracking benötigen, sondern sequentiell arbeiten können (oder welche Sprachen hast du im Sinn?).

    Für einen Parser benötigst du dann jedoch Backtracking (für kontextfreie Grammatiken).
    Welche Parser-Techniken willst du denn verwenden? Sagt dir der Begriff "Combinator Parser" etwas?

    Wie willst du denn genau die Thread-Synchronization zwischen Scanner und Parser herstellen? Und bist du dir sicher, daß es nicht einfacher wäre, zuerst den Scanner und danach den Parser in einem Thread abzuarbeiten?
    Denn wenn der Parser mit Backtracking arbeitet, dann mußt du auf jeden Fall alle generierten Tokens im Speicher halten (und den Ursprungstext ja dazu, da du ja - wie du geschrieben hast - nur mit Iteratoren (Zeigern) darauf arbeitest).

    Soll das Programm einfach nur so eine Übung für dich sein oder warum setzt du dann nicht boost::spirit ein?

    P.S. Ich tue so, als ob ich Ahnung davon habe -), da ich vor Jahren für meine Diplomarbeit selber einen Scanner und Parser entwickelt habe (mittels funktionaler Programmierung).

    0
  • C

    blablub schrieb:

    Erst mal danke für die schnelle Antwort.

    PS: Du weißt aber, daß man Vorwärts-Iteratoren nicht zuverlässig kopieren kann? Das könnte Probleme geben beim Backtracking.

    Nein wusste ich nicht. Da habe ich wohl den Begriff Vorwärts-Iterator falsch verwendet. Was ich ausdrücken wollte, ist das ich nur den Operator Iterator& operator++(Iterator& rhs) verwende. Kopieren muss ich den aber natürlich. Zu Testzwecken kam bis jetzt immer nur ein einfacher const char* zum Einsatz.

    Dann weißt du es jetzt - von Forward-Iteratoren wird nicht gefordert, daß du die einzelnen Kopien unabhängig voneinander manipulieren kannst (und beim Stream-Iterator ist das ziemlich sicher - der leitet jeden Zugriff direkt an den drunterliegenden Stream weiter, ohne sich um die Position des Lesezeigers zu kümmern). Darum gibt es bei Boost::Spirit auch einen Multipass-Iterator - ein Forward-Iterator mit "sicherer" Kopiersemantik.

    Um über einen Eingabestream zu iterieren, gibt es istream_iterator<> und istreambuf_iterator<> (so, wie ich das verstanden habe, brauchst du letzteres).

    Stimmt, der istreambuf_iterator<> scheint meinen Anforderungen schon sehr nahe zu kommen. Das Problem ist aber, wie du ja schon gesagt hast, dass man istream_iterator<> und istreambuf_iterator<> nicht kopieren kann.
    Kann denn ein streambuf beliebig viele Daten speichern, so dass das kopieren von Iteratoren funktionieren könnte?

    Wie groß der Eingabepuffer ist (wenn er überhaupt Daten zwischenspeichert), hängt vom System ab - da mußt du also vom schlimmsten ausgehen.

    wie verwaltest du diese Sequenz intern?

    Meine Implemetierung hat sich genau in dem Punkt geändert. Vorher hatte ich die Token selbst in nem Vector verwaltet. Jetzt rufe ich eine vorher mit dem Scanner assoziierte Funktion auf und übergebe ihr das jeweils erstellte Token. Der Scanner speichert also keine Token. In dem Sinne bin ich ziemlich flexibel. Es muss halt nur ein Container da hinter der die Daten(Token) speichert und die gewünschten Iteratoren unterstützt.

    Um deine Tokensequenz abarbeiten zu können, benötigst du vermutlich einen eigenen Iterator.

    Genau das möchte ich vermeiden. Aber wenn es sich nicht vermeiden lässt, muss ich wohl doch selbst Hand anlegen...

    Woher soll denn ein vorgegebener Iterator wissen, wie er deine Token-Sequenz verarbeiten soll? Da brauchst du zumindest einen eigenen Adapter, der bei jedem Lesezugriff ein neues Token besorgt (schau dir mal den istream-Iterator als Vorbild an - der arbeitet auf diese Weise (mit dem Eingabeoperator des Streams als "Scanner").

    Edit: Ich tue auch so, als ob ich Ahnung habe 😃 da ich vor Jahren für mein Fachpraktikum intensiver mit Spirit gearbeitet habe (es kam sogar was verwertbares raus).

    0
  • B

    Widersprechen sich denn nicht eigentlich Backtracking und Vorwärtsiteratoren, d.h. ich meine, daß du mindestens einen bidirektionalen Iterator brauchst.

    Also, bidirektional (also mit operator-- und operator++) müssen sie nicht sein. Die alten Iteratoren bleiben ja auf dem Stack. Das hat natürlich den Effekt das es genauso gut bidirektionale Iteratoren sein könnten, da die Daten noch vorhanden sein müssen.

    denn wie CStoll ja sagte, kann es Problem beim Kopieren von reinen Vorwärtsiteratoren geben, da der Speicher evtl. schon wieder aufgeräumt wurde.

    Wie gesagt, ich meinte keine Vorwärtsiteratoren.

    Und ein Scanner sollte eigentlich kein Backtracking benötigen, sondern sequentiell arbeiten können (oder welche Sprachen hast du im Sinn?).

    Es handelt sich um einen Scanner-Generator in dem Sinn, dass ein c++ Ausdruck der regulären Ausdrücken stark ähnelt direkt vom C++Compiler in einen Backtracking-Algorithmus umgewandelt wird. Guck dir boost::spirit an, dann weißt du was ich gemacht hab.

    Für einen Parser benötigst du dann jedoch Backtracking (für kontextfreie Grammatiken).
    Welche Parser-Techniken willst du denn verwenden? Sagt dir der Begriff "Combinator Parser" etwas?

    Nein, vom "Combinator Parser" hab ich noch nichts gehört. was ist denn das?

    Wie willst du denn genau die Thread-Synchronization zwischen Scanner und Parser herstellen? Und bist du dir sicher, daß es nicht einfacher wäre, zuerst den Scanner und danach den Parser in einem Thread abzuarbeiten?
    Denn wenn der Parser mit Backtracking arbeitet, dann mußt du auf jeden Fall alle generierten Tokens im Speicher halten (und den Ursprungstext ja dazu, da du ja - wie du geschrieben hast - nur mit Iteratoren (Zeigern) darauf arbeitest).

    Vielleicht hast du recht. Ich fänd es aber zumindest schön, dass die Token erst vom Scanner produziert werden, wenn der Parser (der sich meinetwegen im selben Tthread wie der Scanner befindet) ein bis jetzt noch nicht gebrauchtes Token anfordert. Natürlich müssen die gespeichert werden. darum gehts ja.

    Soll das Programm einfach nur so eine Übung für dich sein oder warum setzt du dann nicht boost::spirit ein?

    Ja genau. Ich hatte bei den Innereien von boost::spirit nicht durchgeblickt, weil ich keinerlei Erfahrung mit Template-Meta-Programmierung hatte. Jetzt verstehe ich einige Konzepte schon besser. Aber ich hab auch den Ärgeiz meine Übung zu vollenden...

    P.S. Ich tue so, als ob ich Ahnung davon habe -), da ich vor Jahren für meine Diplomarbeit selber einen Scanner und Parser entwickelt habe (mittels funktionaler Programmierung).

    Oh, ja, ich muss auch grad Haskell lernen um einen Parser zu schreiben. Da lobe ich mir doch c++!

    0
  • T

    Bzgl. der Iteratoren solltest du dich nochmal genauer informieren.
    Wenn du willst, daß Iteratoren gültig bleiben, auch wenn du sie kopierst bzw. iterierst, dann benötigst du auf jeden Fall einen konstanten Container und dafür kannst du dann Random-Access-Iteratoren verwenden (dies sind quasi die "stärksten" (editiert!) Iteratoren der gesamten Iterator-Hierarchie).

    Vergleiche dazu:
    std::list: bidirektionale Iteratoren (kopierbar, sofern sich die Liste nicht ändert)
    std::vector: Random-Access Iteratoren (indizierbar und kopierbar, sofern sich der Container nicht ändert)

    Auch wenn es für dich nur ein Übungsprojekt ist, solltest du genau wissen, welche Anforderungen an die Parameter deiner Scanner- und Parserfunktionen gestellt werden.

    Um noch mal auf die Anfangsfrage einzugehen:
    Wenn du einen dynamischen Stream als Container verwendest (der evtl. eine Reallokation intern ausführt) und dazu dann Iteratoren, welche du dann wegen Backtracking kopierst, dann kann das schnell zu Speicherzugriffsfehlern führen (da die Iteratoren nicht mehr gültig wären).
    Bei einem istream kannst du nicht davon ausgehen, daß du auf alte Daten zugreifen kannst, sobald du weiteriterierst hast (sog. Input-Iteratoren).
    Du müßtest also entweder einen Zwischencontainer erstellen und darauf dann einen Random-Acess-Iterator anwenden (Iterator zurücksetzen auf alte Position) oder aber die Anforderungen für deine Scanner-/Parserfunktionen erhöhen.

    Ich will dir nicht den Mut nehmen, sondern ich hoffe, daß du mit den Aussagen von CStoll und mir zu einem guten Design für deine Klassen kommst (anstatt später nochmal das gesamte Design ändern zu müssen).

    0
  • C

    Th schrieb:

    Bzgl. der Iteratoren solltest du dich nochmal genauer informieren.
    Wenn du willst, daß Iteratoren gültig bleiben, auch wenn du sie kopierst bzw. iterierst, dann benötigst du auf jeden Fall einen konstanten Container und dafür kannst du dann Random-Access-Iteratoren verwenden (dies sind quasi die schwächsten Iteratoren der gesamten Iterator-Hierarchie).

    Häh, wie soll man denn das verstehen? Random-Access-Iteratoren sind in ihren Möglichkeiten die mächtigsten Iteratoren (am schwächsten ist ein Output-Iterator).

    0
  • T

    Hi CStoll, hast recht, weiß auch nicht, wieso ich dort "schwächsten" geschrieben habe (ich habe es gerade editert).
    Ich wollte eher darauf hinaus, daß das Kopieren eines Iterators höhere Anforderungen stellt als ein bidirektionaler Operator (mit -- und ++).
    Ich hoffe, das ist wenigstens klar geworden?

    0
  • C

    Selbst das nicht - alle Iteratorentypen ab Forward-Iterator sind zuverlässig kopierbar (in dem Sinn, daß beide Kopien unabhängig über die Daten iterieren können). Nur reine Input- und Output-Iteratoren machen da Probleme.

    0
Anmelden zum Antworten