ASCII-Parser. Wie, wo, was?



  • Hallo,
    und zwar bin ich gezwungen, früher oder später einen Parser für ASCII-Textdateien zu schreiben. All die Jahre über habe ich das immer "von Hand" gemacht, sprich std::string::find und co kg. Allerdings geht mir das ziemlich auf'n Sack und leserlich ist das am Ende dann auch nicht mehr wirklich, auch wenn es gut funktioniert. Deswegen wollte ich heute mal fragen, wie ihr eure Texte zu parset.

    Ich würde das Parsing gerne mal von Boost::Regex oder Boost::Spirit übernehmen lassen, allerdings wurde mir immer gesagt dass diese Libs nicht für soetwas verwendet werden sollten. Da frage ich mich, wieso das so ist und wofür die dann sonst gedacht sind?

    Ich hoffe mir kann einer helfen, danke im voraus.



  • Was sind denn das für Textdateien?
    Wenn es um irgendwelche Daten geht, dann hat man üblicherweise eine entsprechendes Format, wie XML oder JSON, für welche es gute Parser gibt.

    Abgesehen von kurzen Hacks oder einfachen init Dateien benutze ich keine normale Textdateien und brauche somit keinen Parser dafür (für was auch? Gibt ja keine Struktur).



  • Ja schon, klar gibt es Parser für die bekannteren und oft verwendeten Textformate, aber ich meine beispielsweise OBJ-Dateien oder einfache Spieledateien.



  • aber ich meine beispielsweise OBJ-Dateien oder einfache Spieledateien.

    Würde mich auch mal interessieren.

    Von Haskell kommend bin ich den Luxus von Parser Combinators gewohnt (z.B. Parsec), die das schreiben von Parsern echt extrem einfach machen. Ich habe es bisher aber nicht geschafft etwas ähnliches in C++ umzusetzen. Boost.Spirit geht da schon in die richtige Richtung.

    In C++ scheint die Antwort zu sein, entweder einen Parser Generator zu bemühen oder eine fertige Library für ein bestimmtes Format (z.B. Assimp, wenn man OBJ laden will) zu benutzen.



  • Was willst du denn genau parsen?
    Für das Extrahieren von Informationen aus HTML-Dateien habe ich eine einfache Parserklasse, die außer verschiedene Variationen von find und parse(Until), sowie push/pop für die aktuelle Position nicht viel können muss. So ziemlich alle anderen Formen von Text, die mir normalerweise unterkommen, haben irgendwelche Trennzeichen (Leerzeichen, Kommas, Tabs, '=' (.ini-Dateien), '&' (z.B. URL-Parameter)) und können dadurch recht bequem mit split+lexical_cast verarbeitet werden.

    aber ich meine beispielsweise OBJ-Dateien oder einfache Spieledateien.

    Spieledaten legt man üblicherweise bis auf Ausnahmen (etwa Konfigurationsdateien) binär ab. Da Textdateien zu benutzen macht die Sache unnötig kompliziert und schadet den Ladezeiten.
    Ich vermute, mit OBJ-Dateien meinst du das da:
    http://en.wikipedia.org/wiki/Wavefront_.obj_file
    Scheint auch wieder sehr sympathisch zu sein, alles sauber durch Zeilenumbrüche, Leerzeichen, Kommas, Slashes, usw. getrennt.



  • Athar schrieb:

    Spieledaten legt man üblicherweise bis auf Ausnahmen (etwa Konfigurationsdateien) binär ab. Da Textdateien zu benutzen macht die Sache unnötig kompliziert und schadet den Ladezeiten.

    Na ja, das mag ab einer gewissen Größe stimmen, aber bei den meisten Hobbyspielen ist das völlig egal. Zudem man dann ja eh noch einen Parser braucht, wenn man die von Maya & co ausgespuckten Dateien in das Spieleigene Format bringen will.

    @Kóyaánasqatsi
    Ich mache das normalerweise so, dass ich eine generische, mit Iteratoren arbeitende Parserklasse habe, die Strings (bzw. Ranges, geht schneller), ints und floats parsen kann. Darüber setze ich dann die eigentlichen Loader für verschiedene Formate auf. Das ist jetzt nicht das abstrakteste template-gehax0re, aber es geht recht schnell und ist einfach zu implementieren. Für .obj und ähnliche Formate reicht es jedenfalls locker. (Für sehr große Dateien ungeeignet, da man jede Datei in einem Block in den Ram läd. Aber wer hat schon 500 MB große Models / Maps.)



  • Das Problem ist einfach dass es kein Patentrezept für Parser gibt. Ich denke mal das StringStream die einfachste Alternative ist?!



  • Kóyaánasqatsi schrieb:

    Das Problem ist einfach dass es kein Patentrezept für Parser gibt. Ich denke mal das StringStream die einfachste Alternative ist?!

    warum nicht gleich einen std::ifstream, was ja auch 'nur' ein std::istream ist. Ich behaupte mal, dass für 95% aller Leseaufgaben das locker ausreicht.
    Das 'lese-alles-in-einen-String-und-fummele-es-mit-Stringfunktionen-auseinander" ist einer der verbreitetsten Anfängerfehler und resultiert letztlich nur aus der Unkenntnis darüber was std::istream alles kann.
    Das Lesen von int und float ist wirklich ein Witz, dafür brauch man keinen speziellen Parser.

    Aber im Grunde ist das alles Kaffeesatz lesen, wenn nicht bekannt ist, was hier eigentlich gelesen/geparst werden soll. Gib uns doch mal ein Beispiel für eine einfache Spieledatei im Textformat. Was meinst Du mit OBJ-Dateien?

    Gruß
    Werner



  • Werner Salomon schrieb:

    Was meinst Du mit OBJ-Dateien?

    Er meint Wavefront Object: http://en.wikipedia.org/wiki/Wavefront_.obj_file

    Nehmen wir mal die Grundfunktionalität. Es sollen folgende Informationen eingelesen werden:

    std::vector<float> vertices;
    std::vector<float> normals;
    std::vector<float> texture_coords;
    std::vector<unsigned short> vertex_faces;
    std::vector<unsigned short> normal_faces;
    std::vector<unsigned short> texture_faces;
    

    Ich wäre sehr an einem schnellen und eleganten Parser für dieses Format interessiert. (Meiner ist halt schnell, aber nicht unbedingt sehr elegant.)

    Edit: Als Testdatei könnte so etwas herhalten: http://www.3drender.com/challenges/ (Challenge #24: The Cabin, OBJ)



  • cooky451 schrieb:

    Ich wäre sehr an einem schnellen und eleganten Parser für dieses Format interessiert. (Meiner ist halt schnell, aber nicht unbedingt sehr elegant.)

    Edit: Als Testdatei könnte so etwas herhalten: http://www.3drender.com/challenges/ (Challenge #24: The Cabin, OBJ)

    Ich schreibe gleich auch mal einen. Mal sehen wie schnell er ist. Könntest du uns deine Messdaten vlt mitteilen? (Nur das Parsing)



  • cooky451 schrieb:

    Ich wäre sehr an einem schnellen und eleganten Parser für dieses Format interessiert. (Meiner ist halt schnell, aber nicht unbedingt sehr elegant.)

    Edit: Als Testdatei könnte so etwas herhalten: http://www.3drender.com/challenges/ (Challenge #24: The Cabin, OBJ)

    Ich habe Dir hier einen Entwurf angehängt. Das Einlesen stützt sich auf ctest und is_endl ab; die hatte ich schon in einigen Beiträgen hier beschrieben. Für die von Dir angegebene Datei braucht es ca. 15s. Zeitoptimiert ist da gar nichts. Um dies zu tun, muss man zunächst heraus bekommen, welche Aktionen welche Zeit benötigen. Ob das langsam oder elegant ist, musst Du selber beurteilen.
    Falls Du Fragen hast, so nur heraus damit.

    #include "ctest.h" // s. http://www.c-plusplus.net/forum/p1828117#1828117
    #include "is_endl.h" // s. http://www.c-plusplus.net/forum/p1940874#1940874
    #include <fstream>
    #include <limits>
    #include <vector>
    #include <string>
    
    std::istream& skipline( std::istream& in )
    {
        return in.ignore( std::numeric_limits< std::streamsize >::max(), '\n' );
    }
    
    std::istream& comment( std::istream& in )
    {
        while( ctest( in, '#' ) )
            in >>  skipline;
        return in;
    }
    
    struct Vertex
    {
        friend std::istream& operator>>( std::istream& in, Vertex& v )
        {   // Vertex, with (x,y,z[,w]) coordinates, w is optional
            in >> v.m_x >> v.m_y >> v.m_z;
            if( is_endl( in ) )
                v.m_w = 1.0;
            else
                in >> v.m_w;
            return in;
        }
        float m_x, m_y, m_z, m_w;
    };
    struct Texture
    {
        friend std::istream& operator>>( std::istream& in, Texture& t )
        {   // Texture coordinates, in (u,v[,w]) coordinates, w is optional
            in >> t.m_u >>  t.m_v;
            if( is_endl( in ) )
                t.m_w = 0.0; // ??
            else
                in >> t.m_w;
            return in;
        }
        float m_u, m_v, m_w;
    };
    
    struct Normal
    {
        friend std::istream& operator>>( std::istream& in, Normal& n )
        {   // Normals in (x,y,z) form; normals might not be unit
            return in >> n.m_x >> n.m_y >> n.m_z;
        }
        float m_x, m_y, m_z;
    };
    
    struct Face 
    {
        struct Indices
        {
            friend std::istream& operator>>( std::istream& in, Indices& i )
            {   // vi oder vi/vti oder vi/vti/vni oder vi//vni
                i.m_vt = 0;
                i.m_vn = 0;
                if( ctest( in >> i.m_v, '/' ) )
                {
                    if( ctest( in, '/' ) || ctest( in >> i.m_vt, '/' ) )
                        in >> i.m_vn;
                }
                return in;
            }
            std::size_t m_v, m_vt, m_vn;
        };
        friend std::istream& operator>>( std::istream& in, Face& f )
        {
            std::vector< Indices > ii;
            for( Indices i; !is_endl( in ) && !in.eof() && in >> i; )
                ii.push_back( i );
            if( in )
                swap( ii, f.m_indices );
            return in;
        }
        std::vector< Indices > m_indices;
    };
    
    template< typename T >
    void read( std::istream& in, T& coll )
    {
        typename T::value_type x;
        if( in >> x )
            coll.push_back( x );
    }
    
    int main()
    {
        using namespace std;
        vector< Vertex > vertices;
        vector< Normal > normals;
        vector< Texture > texture_coords; 
        vector< Face > faces;
    
        ifstream in("Lighting_Challenge_24_theCabin.obj");
        for( string tok; in >> comment >> tok; )
        {
            if( tok == "v" ) read( in, vertices );
            else if( tok == "vt" ) read( in, texture_coords );
            else if( tok == "vn" ) read( in, normals );
            else if( tok == "f" ) read( in, faces ); 
            else 
                in >> skipline; // nicht unterstützte Einträge
        }
        cout << "fertig " << (in.eof()? "Ok": "Fehler") << endl;
        return 0;
    }
    

    Gruß
    Werner

    @Edit: Bugfix in Manipulator comment; Zeile 15; while statt if



  • Hm..
    Also deine Version braucht bei mir ca. 140 Sekunden. Meine dagegen 1,4 Sekunden. Windows 7, Visual Studio 2010.

    Ich hatte zwar erwartet, dass meine wesentlich schneller sein wird (die Datei wird halt in einem Rutsch ausgelesen und dann erst geparst), aber der Vorsprung scheint mir doch unrealistisch. Kann aber keine Messfehler finden.
    Ich kann meinen Code hier schlecht ganz posten, da das etwas verschachtelter ist in einem großen Projekt, aber die Grundidee sieht so aus:

    Timer<f32> timer;
      auto filebuf = readFile(filename);
      Parser<decltype(filebuf)> parser(filebuf);
      std::vector<f32> vertices;
      std::vector<f32> normals;
      std::vector<f32> texture_coords;
      std::vector<u16> vertex_faces;
      std::vector<i32> normal_faces;
      std::vector<i32> texture_faces;
      while (parser.parseString())
      {
        if (parser.lastString() == "v")
        {
          vertices.push_back(parseFloat(parser));
          vertices.push_back(parseFloat(parser));
          vertices.push_back(parseFloat(parser));
          if (std::isdigit(parser.peek()))
            vertices.push_back(parseFloat(parser));
        }
        else if (parser.lastString() == "vt")
        {
          texture_coords.push_back(parseFloat(parser));
          texture_coords.push_back(parseFloat(parser));
          if (std::isdigit(parser.peek()))
            texture_coords.push_back(parseFloat(parser));
        }
        else if (parser.lastString() == "vn")
        {
          normals.push_back(parseFloat(parser));
          normals.push_back(parseFloat(parser));
          normals.push_back(parseFloat(parser));
        }
        else if (parser.lastString() == "f")
        {
          while (std::isdigit(parser.peek()))
          {
            vertex_faces.push_back(parseInt(parser) - 1);
            if (parser.peek() == '/')
            {
              parser.skipAfter('/');
              if (std::isdigit(parser.peek()))
              {
                texture_faces.push_back(parseInt(parser) - 1);
              }
              if (parser.peek() == '/')
              {
                parser.skipAfter('/');
                normal_faces.push_back(parseInt(parser) - 1);
              }
            }
          }
        }
        else //if (*parser.lastString() == '#')
        {
          parser.skipAfter('\n');
        }
      }
      sys::stdlog << "Time to parse model " << filename << ": " << timer.elapsed() << std::endl;
    

    Der Parser arbeitet intern eigentlich nur mit Iteratoren, die halt über die Daten gehen und sie entsprechend parsen. Die IOStream-Umwandlungen sind leider nicht so schnell, deshalb habe ich das auch selbst geschrieben.
    Falls doch jemand interesse an dem ganzen Code hat, eben bescheid sagen, dann frickel ich das schnell aus dem Projekt raus.


Log in to reply