C# Einfachen Parser "from Scratch"



  • Hallöchen,
    ich verzweifle gerade daran einen "einfachen" Parser in C# zu schreiben.
    Ich möchte eine Art Tree als Resultat aus einem String erzeugen (bzw Datei).
    Beispiel:
    - Dokument
    - Element
    - Daten
    - /Daten
    - /Element
    - ...
    - /Dokument

    Dabei möchte ich das von Grund auf implementieren (also kein RegEx). Dh auch keine XML Libaries oä nutzen.
    Ich habe am Ende auch andere Tags als XML zB beginnt ein Element mit $ oder % usw, je nach Funktion des Elements.
    Habt ihr vlt gute Ideen oder Vorschläge wie so eine Implementierung möglichst effizient und vlt kompakt ist? Habe mir den Code von verschiedenen Parsern durchgelesen (zb https://limpet.net/mbrubeck/2014/08/11/toy-layout-engine-2.html), aber leider nix richtig brauchbares gefunden, weil es entweder viel zu aufwendig und komplex ist für mein vorhaben oder mit RegEx implementiert ist. Das Resultat soll dann formatiert in eine Datei geschrieben werden.



  • - Dokument 
    - Element 
    - Daten 
    - /Daten 
    - /Element 
    - ... 
    - /Dokument
    

    und Poste mal den exakten String den du parsen möchtest
    nutze Code-Tags dann bleibt deine Formatierung erhalten

    sind die Zeilen mit NewLine abgeschlossen?
    Was bedeutet '-' ?
    was bedeutet '/' ?
    was bedeutet Element/Daten/Dokument usw.
    allgemein: was ist deine Syntax

    ich verstehe jetzt dein Problem nicht - für Regex ist das viel zu trivial
    Einfach zeichenweise durch den String laufe, Zuständen merken, in Baum einordnen oder mit was kämpfst du?



  • Erstmal vielen Dank für die Rückmeldung.

    Mein Problem liegt im gezeigten Aufbau.

    $ Dokumentenkopf
        % Wichtiges Element
            & Erster Datensatz &
            & Zweiter Datensatz &
        %
        % Naechstes Element
            & Erster Datensatz &
            & Zweiter Datensatz &
        %
    $
    

    Denn wenn ich einfach nur durch den String loope und die passenden kürzel ersetzte, kann es passieren, dass der Dokumentenkopf zB in einem Element drin ist. Dh ich brauche so eine Art Schutz, dass nur Tags verwendet werden dürfen, die im aktuellen Kontext Sinn machen.



  • mach dich mit der Post-Vorschau vertraut - deine code-Tags ist irgendwie falsch

    Denn wenn ich einfach nur durch den String loope und die passenden kürzel ersetzte...

    Parsen wird durch Ersetzen nie einfacher - du musst durchlaufen und dir deinen Zustand merken und entsprechend die Daten verarbeiten - dann passiert dein Problem nicht

    ich verstehe aber noch nicht wie & und % einen Baum Formen sollen
    - woher kommt das Format - und was passiert wenn & oder % im Inhalt eines Datensatzes, Dokumentkopf oder wichtigem Element vorkommen

    Poste man einen Beispiel-String - mit deinen ganzen Problempunkten (also auch Dokument unter Element usw.) und dazu einen passend eingerückten Baum als Ergebnis

    Achtung: ich bin schon im Muss-dir-alles-aus-der-Nase-ziehen-Modus - bitte vollständige Beispiele mit Problemstellen, Ergebnisse, Bedenken posten - nicht nur so Happen-Sätze

    bitte mit Code-Tags (einfach markieren und auf Code klicken) und
    in der Vorschau prüfen ob das auch richtig rauskommt - dann erst posten



  • $ Soll einfach nur ein Dokument signalisieren. Davon kann es mehrere in einer Datei geben.
    % Ist einfach nur ein "Container" für andere Container / Daten.
    & signalisiert, dass Daten folgen.
    In ein % darf kein $ und in ein $ kein &. & Darf generell nur auf % folgen.
    Das gleiche Symbol schließt den Bereich wieder.
    Ziel des Parsers ist dieses Format in andere Umwandeln zu können (zb XML, ...).
    Mein C# Projekt beinhaltet schon Klassen für alle Formate wie XML, .. und die passenden Symbole. Jetzt will ich im Prinzip am Ende einen Baum haben, der wieder gelesen wird und dann für andere Formate genutzt werden kann (wie oben beschrieben)

    Hier mal runtergebrochen:

    $ Dialog.cfg
        % Description 
            % Localization 
                & None &
                & Missing &
                & Read &
                & Write &
            %
            % Style
                & Default &
                & Custom &
            %
        %
        % Addons
            & Default &
        %
    $
    $ ... (Nächstes Dokument)
    

    Das mit dem Code Tag will nicht. Ka warum. Hab alle durchprobiert. Deshalb jetzt die Version mit Unterstrichen.



  • das "cs" in Code bedeutet C# Syntax - warum machst du das?
    bei mir und allen anderen hier funktioniert es doch auch

    $ Dialog.cfg 
      % Description 
        % Localization 
          & None & 
          & Missing & 
          & Read & 
          & Write & 
        % 
        % Style 
          & Default & 
          & Custom & 
        % 
      % 
      % Addons 
        & Default & 
      % 
    $ 
    $ ... (Nächstes Dokument)
    

    d.h. 2 Leerzeichen sind eine Tiefe im Baum?
    das mit dem $ & % sind also so eine Art Typ Information?



  • Das code="cs" steht da, weil ich wie gesagt alles ausprobiert habe, nix hat funktioniert.
    Die Tiefe wird durch die Einbettung in das vorherige Element erreicht. Dh % BLA1 gefolgt von % BLA2 & DATA & %%. Damit liegt BLA1 oben und DATA unten.
    Genau, die Symbole sollen die Art des Elements bestimmen (ähnlich bei HTML / XML).
    Mir geht es dabei mehr um eine "allgemeine" Lösung. Dh ich will später auch neue Element einfach hinzufügen können.
    Ich probiere es mal so einfach wie es geht zu beschreiben:
    Das Wurzel Element ist das Dokument. Dieses kann X Elemente enthalten, die wiederum X Elemente enthalten können. Jedes Element kann X Daten enthalten.



  • also

    1. ein "leeres" $ % & bedeutet Scope-Ende

    2. warum am Ende von Daten nochmal ein &?

    3. enthält dein String jetzt Newlines oder nicht?

    also

    "$ Dialog.cfg% Description% Localization& None &" soll zu
    

    oder

    "    $ Dialog.cfg          % Description        % Localization& None &   "
    

    oder

    $ Dialog.cfg 
      % Description 
        % Localization 
          & None &
    

    soll zu

    dokument:Dialog.cfg 
      container:Description 
        container:Localization 
          daten:None
    


  • Ich denke da haste mich mit dem Baum falsch verstanden:
    Der Baum soll nur "intern" so aussehen. Dh als verkette Klassenobjekte.
    Also: Einlesen -> Baumstruktur (als Idee, vlt ist auch Liste besser ka) -> XML / ...
    Die Datei enthält new Lines und das & ist wichtig weil man ja auch hinter die Daten nen neues Element machen kann. Also % Element 1 & Daten & % Element 2 %%



  • Dadurch dass du das selbe Zeichen für Start und Ende von Containern verwendest machst du es dir unnötig kompliziert.
    Kann man natürlich parsen, ist aber mehr Aufwand als wenn du ein anderes Zeichen bzw. eine Zeichensequenz wie \% oder !% verwenden würdest.
    (Die einfachste Variante wäre wohl einen generischen End-Tag zu verwenden, der IMMER ein End-Tag ist. "~" vielleicht oder ";". Konnt drauf an welche Zeichen du im Text "entbehren" kannst.)

    Alternativ, auch sehr einfach zu parsen wäre es wenn du ALLE Spezialsachen über zwei Zeichen lange Escape Sequenzen machst. z.B.
    \D = start document
    \C = start container
    \V = start value
    \. = end document/container/value
    \\ = \

    Über die verschiedenen Klammer-Paare ginge natürlich auch gut.
    Also

    { mydoc.xxx
       [ description
           (value 1)
           (value 2)
           (value 3)
           [ sub container (value) () ]
           [ value-less sub container ]
       ]
       [ whatever ]
    }
    { nextdoc.xxx
    ...
    ...
    

    Beispiel für das Problem:
    $ Dialog.cfg % Description % Localization ...
    Wie soll der Parser beim 2. % wissen dass es ein Start-Tag und kein End-Tag ist? Klar, man könnte sagen Container dürfen nicht leer sein. Das "fixt" dieses Beispiel, aber das selbe Problem hast du beim "öffnen" des nächsten Untercontainers von "Description".

    Lösung: du musst "nach vorne schauen" und gucken was das nächste nicht-Whitespace Zeichen ist. Ist es eines deiner "Steuerzeichen", dann ist es ein Endtag. Ist es was anderes (z.B. ein Buchstabe), dann ist es ein Starttag.

    Geht aber auch nur wenn man Definiert dass der Titel von Containern nicht leer sein darf.
    => Alles doof.
    => Ändere deine Syntax.



  • TrippleC schrieb:

    Die Datei enthält new Lines und das & ist wichtig weil man ja auch hinter die Daten nen neues Element machen kann. Also % Element 1 & Daten & % Element 2 %%

    Die Frage ist: haben die Line-Breaks ne syntaktische Bedeutung?
    Wenn ja, dann kannst du zeilenweise parsen. Das vereinfacht die Sachen natürlich etwas.

    (Die Regel dass Containernamen nicht leer sein dürfen braucht man allerdings trotzdem.)

    Allerdings: wenn du ne halbwegs performante und einfache Implementierung möchtest, dann wäre es günstig wenn die Line-Breaks keine syntaktische Bedeutung hätten UND die Bedeutung eines Tags immer ohne "vorausschauen" klar ist (siehe mein Beitrag von gerade eben).



  • von TrippleC

    Ich denke da haste mich mit dem Baum falsch verstanden:
    Der Baum soll nur "intern" so aussehen. Dh als verkette Klassenobjekte.

    das letzte Beispiel soll eine Objekt-Hierarchie darstellen

    von hustbaer

    Die Frage ist: haben die Line-Breaks ne syntaktische Bedeutung?

    die Frage kommt jetzt das 4. mal - langsam solltest du die mal beantworten

    von hustbaer

    => Ändere deine Syntax.

    ich finde die Syntax auch unnötig kompliziert - und du hast immer noch nicht beantwortet ob die jetzt von dir kommt oder eine Vorgabe ist?

    aber egal wie man es dreht und wendet ist mir IMMER noch nicht klar was dein Implementationsproblem damit ist?



  • Hallo,

    TrippleC schrieb:

    Das mit dem Code Tag will nicht. Ka warum. Hab alle durchprobiert. Deshalb jetzt die Version mit Unterstrichen.

    Du mußt das Häkchen bei "BBCode in diesem Beitrag deaktivieren" entfernen.
    Am besten "BBCode immer aktivieren:" in deinem Profil auf "Ja" stellen.



  • @hustbaer Danke für die Antwort.
    Die new Lines sind enthalten aber haben keine Bedeutung. Ich dachte das wird aus dem Baum klar, weil ich ja mit dem selben Symbol wieder abschließe und es deshalb keine bedeutung hat was da noch dazwischen kommt (also new Line, Tab, etc).
    @Gast3 du hast nie (zumindest finde ich es nicht) die Frage gestellt ob die Syntax von mir ist oder nicht. Aber um es zu beantworten: Die ist von mir.
    Meine Probleme hat hustbaer ganz gut beschrieben. Woher weis ich das % mit % schließt? Wie kann ich daraus ne Baum Struktur implementieren die bestimmte Elemente (wie vorher beschrieben) zu lässt und manche nicht.
    Um das oben genannte Beispiel zu nennen & Daten & darf nicht in $ Dokument $ und $ Dokument $ nicht in % Element % / & Daten &, etc.



  • @Gast3 du hast nie (zumindest finde ich es nicht) die Frage gestellt ob die Syntax von mir ist oder nicht.

    im zweiten Post von mir "woher kommt das Format"

    Woher weis ich das % mit % schließt? Wie kann ich daraus ne Baum Struktur implementieren die bestimmte Elemente (wie vorher beschrieben) zu lässt und manche nicht.

    hustbaer hat dir doch schon Tips gegeben wie du deine Syntax ändern könntest um solche Problem nicht zu haben und mit einer einfachen Statemachine(enum) machst du das parsen

    nur so ein Tip - nur das Zeichen, ohne Kontext zu behandeln wird nicht reichen



  • Als weiterer Tipp: erstell dir mal eine BNF bzw. einfacher eine EBNF, dann erkennst du, ob du dafür einen einfachen Parser schreiben kannst (Stichwort: Rekursiver Abstieg bzw. besser ist die englische Seite Recursive Descent Parser).

    Mit meinem Programm Extended Backus-Naur-Form (EBNF)-Parser kannst du dann auch überprüfen, ob die Beispieldaten zur EBNF passen.



  • TrippleC schrieb:

    Meine Probleme hat hustbaer ganz gut beschrieben. Woher weis ich das % mit % schließt? Wie kann ich daraus ne Baum Struktur implementieren die bestimmte Elemente (wie vorher beschrieben) zu lässt und manche nicht.

    Idealerweise indem du die Syntax anpasst. Ohne Anpassung ist der Parser viel komplizierter. Also natürlich immer noch ein Kindergeburtstag im Vergleich zu z.B. einem C++ Parser. Aber halt viel komplizierter als er sein müsste.

    TrippleC schrieb:

    Um das oben genannte Beispiel zu nennen & Daten & darf nicht in $ Dokument $ und $ Dokument $ nicht in % Element % / & Daten &, etc.

    Wenn du die Syntax anpasst, dann ist der Teil mit "was darf was enthalten" relativ easy. Kann ich dir dann zeigen. Bzw. wenn ich heute Abend nochmal dran denke und Lust&Laune habe dann zeig ich dir ne relativ einfache Variante mit von mir angepasster Syntax.

    Bzw. wenn du es selbst probieren willst...

    class Document
    {
        // Parses a document file. The file is made up of a series Document definitions with optional white spaces before/between/after the Document definition(s).
        public static List<Document> ParseDocumentFile(string fileContents)
        {
            int offset = 0;
            int length = fileContents.Length;
    
            var docs = new List<Document>();
            while (offset < length)
            {
                if (Char.IsWhiteSpace(fileContents[offset]))
                    offset++;
                else // Everything that isn't a white space MUST be the start of a document definition
                    docs.Add(Parse(fileContents, ref offset));
            }
    
            return docs;
        }
    
        // Parses the text in source, starting from offset, into a new Document and returns it.
        // When calling, source[offset] must be the first character of a document start tag.
        // When returning, offset has been adjusted so that source[offset] is the next character AFTER the end tag of the document.
        public static Document Parse(string source, ref int offset)
        {
            if (source[offset] != '$')
                throw new Exception("syntax error");
            offset++;
    
            // ...
        }
    }
    
    class Container
    {
        // Similar to Document.Parse
        public static Container Parse(string source, ref int offset)
        {
            // ...
        }
    }
    
    class DataItem
    {
        // Similar to Document.Parse
        public static DataItem Parse(string source, ref int offset)
        {
            // ...
        }
    }
    

    Ergänze die fehlenden Properties der Klassen und implementiere die drei Parse Funktionen.



  • @hustbaer @Gast3 @Th69 Erst mal vielen Dank für eure Bemühungen.

    @hustbaer der erste Teil sieht meinem ersten Versuch sehr ähnlich.
    Ich überleg mir auch grad die Syntax anzupassen, obwohl mein eigentlicher Versuch und Grundgedanke war, dass mit gleichen Anfangs- und Endsymbolen zu implementieren.



  • Ich würde die Variante mit gleichen Anfangs- und End-Symbolen als universell schlechter ansehen. Also nicht nur schwieriger zu implementieren, sondern auch blöder zu verwenden, blöder zu erklären etc.

    Also wozu sich den Mehraufwand antun, für etwas was universell schlechter ist als die einfacher zu implementierende Lösung?


Log in to reply