Ich brauche ein paar Tipps für einen kleinen Parser



  • Ich habe eine Skript-Datei mit Befehlen die ich auf Richtigkeit überprüfen will.
    (Sie wird mit einem simplen Texteditor erstellt.)
    Die Datei ist so aufgebaut, dass jede Zeile einen Befehl enthält.
    Bei jedem Befehl sind mehrere verschiedene Parameterkombinationen möglich deren Reihenfolge eingehalten werden muss.
    Manche Befehle beziehen sich auf den vorherigen Befehl.

    Der aktuelle Befehlssatz umfasst aktuell ca. 15 häufig und nocheinmal ca. 15 selten bzw. nicht verwendete Befehle.
    Jeder Befehl hat im Schnitt zwei bis drei verschiedene Parameterkombinationen, maximal sind es 10 verschiedene Kombinationen.

    Was währe da effektiver?
    Einfach alles in einer Schleife mit if / else if abarbeiten oder sollte ich da eine Zustandsmaschine programmieren wie es "richtige" Parser machen?
    Es geht mir nicht um das Einlesen der Daten ansich, sondern nur um das Überprüfen auf Fehler -> Falsche Parameter oder ungültige Zeichen.

    Kann mir da jemand mit Erfahrung einen Tipp geben?



  • http://www.c-plusplus.net/forum/268247

    das hier ist eine anleitung zum interpreterbau. das braucht man auch zum parserbau.



  • hallo,

    ich hab zu dem thema auch eine frage:
    soll man die skript-datei vollständig in einen speicher laden, und dann parsen, oder soll man die datei zeilenweise einlesen?

    mir kommt nämlich dieses ganze "fgets..." auf die dauer recht lächerlich und unprofessionell vor.



  • Zeilenweise, wann immer möglich. Schneller und speicherschonender.
    Gerade bei sowas wie nem Parser, wo du nicht die ganze Datei einlesen willst nur um dann sagen zu können "Parserfehler in Zeile 1"



  • ok, wie macht es eigentlich der python-parser? liest der das auch zeilenweise?



  • Das, was du willst, ist ein Interpreter/virtuelle Maschine.



  • shitstorm schrieb:

    hallo,

    ich hab zu dem thema auch eine frage:
    soll man die skript-datei vollständig in einen speicher laden, und dann parsen, oder soll man die datei zeilenweise einlesen?

    mir kommt nämlich dieses ganze "fgets..." auf die dauer recht lächerlich und unprofessionell vor.

    Ich würde keins von beiden machen. Ich würde über einen puffernden Stream zeichenweise einlesen und parsen. Wie Du einen Parser schreibst, lernst Du in dem Artikel, der hier bereits verlinkt wurde.

    Danke übrigens für den Link. Ich kannte den Artikel noch nicht und finde ihn sehr interessant.



  • Bernd_d_B schrieb:

    Einfach alles in einer Schleife mit if / else if abarbeiten oder sollte ich da eine Zustandsmaschine programmieren wie es "richtige" Parser machen?

    Das Überprüfen der Syntax ist im Wesentlichen dasselbe und damit gleich schwierig wie das "richtige" Parsen, also wird es wohl kaum eine Abkürzung geben.



  • (monty) python schrieb:

    ok, wie macht es eigentlich der python-parser? liest der das auch zeilenweise?

    knivil schrieb:

    Das, was du willst, ist ein Interpreter/virtuelle Maschine.

    ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

    ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.



  • (monty) python schrieb:

    ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

    ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.

    Ich gehe davon aus, dass der python-parser weder noch tut. Er wird wie bei Parsern üblich zeichenweise lesen. Und wenn da eine puffernde Schicht dazwischen ist, dann ist das sehr effizient.



  • tntnet schrieb:

    (monty) python schrieb:

    ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

    ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.

    Ich gehe davon aus, dass der python-parser weder noch tut. Er wird wie bei Parsern üblich zeichenweise lesen. Und wenn da eine puffernde Schicht dazwischen ist, dann ist das sehr effizient.

    also pures fgets()?



  • (monty) python schrieb:

    tntnet schrieb:

    (monty) python schrieb:

    ne. auch der python-interpreter hat (wie alle anderen interpreter auch) einen parser.

    ich will, wie ich ja gefragt hab, lediglich wissen, ob der python-parser skripte ganz oder zeilenweise liest, bevor sie interpretiert werden.

    Ich gehe davon aus, dass der python-parser weder noch tut. Er wird wie bei Parsern üblich zeichenweise lesen. Und wenn da eine puffernde Schicht dazwischen ist, dann ist das sehr effizient.

    also pures fgets()?

    Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.



  • tntnet schrieb:

    Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.

    warum ZEICHENWEISE? was hat das für einen vorteil?

    keine ahnung, wie du mit einzelnen zeichen irgendwas parsen willst.

    wenn ich die ganze zeile einlese, kann ich mit strcmp arbeiten.



  • vorteil? schrieb:

    tntnet schrieb:

    Eher nicht. In C++ würde ich einen std::ifstream nehmen und std::istream::get(char&) verwenden. In C fgetc. Ich habe ja gesagt: zeichenweise.

    warum ZEICHENWEISE? was hat das für einen vorteil?

    keine ahnung, wie du mit einzelnen zeichen irgendwas parsen willst.

    wenn ich die ganze zeile einlese, kann ich mit strcmp arbeiten.

    Lese mal den Artikel über Parser. Was ist wenn Dein Format gar nicht Zeilenweise organisiert ist? Dann kannst Du mit einer Zeile gar nichts anfangen.

    Ein Zeichen löst im Parser jeweils einen Zustandsübergang aus, der möglicherweise Aktivitäten auslöst. So funktioniert ein Parser halt. Ein Parser, der Zeichenweise verarbeitet, ist letzten Endes leichter zu implementieren, also so ein strcmp-strstr-strtok-usw.-parser, der leider viel zu oft implementiert wird, weil die Leute nicht wissen, wie man Parser baut. Strcmp ist naheliegend aber leider in aller Regel eine schlechte Lösung.



  • ja, in der anleitung wird ja auch ein parser auf der basis von "1 + 2" erklärt.

    in einer richtigen programmier- oder skriptsprache hast du aber tokens, z.b. "int".

    du liest also die ganze zeile
    int var1 = 5;

    jetzt kann ich mit strcmp das allerste wort mit einer reihe von tokens vergleichen.

    wenn du das ganze zeichenweise liest, dann hast du ein 'i'.
    keine ahnung, 'i' kann so ziemlich alles bedeuten.

    der parser in der anleitung ist schon ok, man sollte nur nicht alles "wörtlich" nehmen, weil eben in einer funktion nur einzeichen-tokens (wie z.b. '+' oder '-' usw.) vorkommen. da kann man gerne zeichenweise parsen, das ist da wohl das beste.

    aber wenn du tokens hast, die mehr als ein zeichen haben, bringt das zeichenweise lesen nix.
    ich versteh immernoch nicht ganz, wie genau du z.b. "int" erkennen willst, wenn du immer nur ein zeichen liest.



  • Und was ist, wenn der Code so aussieht:

    int
    var1
    = 5
    ;
    

    ?
    Oder ein xml-parser der so etwas sieht:

    <foo>
    <bar
    ></baz
    
    ></foo
    >
    

    ?

    Dann viel Spaß mit strcmp. Schreib mal einen Parser. Vielleicht verstehst Du dann, wie das geht. Ich habe schon so einige Parser geschrieben und ich finde es weitaus einfacher, zeichenweise zu lesen.

    Wenn der Parser ein 'i' bekommt und er ist im Zustand "lese Datentyp", dann fügt er den bisher gelesenen Datentypfeld ein 'i' hinzu. Und wenn er dann ein 'n' und ein 't' bekommt, dann machst er das gleiche, da der Zustand sich nicht verändert hat. Und wenn er in dem Zustand dann ein Leerzeichen bekommt, dann wechselt er den Zustand in "Variablenname lesen". Kommt dann wieder ein 'i', dann reagiert er eben anders. Er wird nämlich den bisher gelesenen Variablennamen um das 'i' erweitern.

    Na ja - ein wenig vereinfacht, aber im prinzip ist das so. Ich implementiere immer eine Methode "parse(char)", die ein grosses switch(state) statement hat, welches auf die Zustände springt.



  • ok.

    eine frage noch: wie speicherst du variablennamen ab? wahrscheinlich in eine verkettete liste?

    wie überprüfst du, ob du den variablennamen schon kennst? dafür kann man doch strcmp nehmen, oder?



  • Warum muss das physikalische Laden der Datei mit dem Parser gekoppelt sein? Natuerlich muss zeichenweise geparst warden, aber nicht unbedingt eingelesen werden.

    dafür kann man doch strcmp nehmen, oder?

    Warum sollten Namen in einer Liste sein und nicht in einem Prefix-Tree? Warum bist du so fixiert auf strcmp? Warum ueberhaupt C?



  • ok, an so einen präfixbaum hab ich garnicht gedacht.



  • @tntnet:

    machst du das dann in etwa so:

    // "int"
    if( array[i] == 'i')
    {
        if(array[i+1] == 'n')
        {
             if(array[i+2] == 't')
             {
                  printf("'int' gefunden an Position %d\n",i);
             }
        }
    }
    

    so in etwa?


Log in to reply