Scriptsprache Kontrollstrukturen Postfix Notation

  • VB.NET

Es gibt 19 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Scriptsprache Kontrollstrukturen Postfix Notation

    Heyho,

    Ich arbeite zur zeit an einer wirklich klein gedachten Scriptsprache, die im wesentlichen Variablen verwalten soll und ein paar Kontrollstrukturen bieten soll (If-Abfrage, For-Schleife, evt. While Schleife). Die einzelnen Tokens werden bereits richtig aufgetrennt und auch typisiert.

    Beispiel:

    Quellcode

    1. if(number=2)
    2. OUTPUT('number equals 2')
    3. end
    5. =>
    6. if ( number = 2 )
    7. OUTPUT( 'number equals 2' )
    8. end


    Für den Interpreter am Schluss muss ich die Tokens in eine Art Postfix-Notation bringen ähnlich wie bei einem Term-Parser. Die Frage, die mich interessiert, ist wie ich die Kontrollstrukturen sinnvoll in die Notation umkehren kann, selbst wenn diese eventuell geschachtelt werden. Um die Schachtelung zu behandeln würde ich eine Dictonary anlegen, dass die Anfangszeile der Kontrollstruktur und das Ende beinhaltet (der Zeilenindex). Jedoch habe ich bisher keine Idee wie ich das Dictionary dann sinnvoll in den Algo einbauen kann.

    Danke für eure Ideen/Vorschläge.

    8-) faxe1008 8-)

    In Deinem Beispiel unterscheiden sich die beiden Gruppen nur durch Leerzeichen. :/
    Definiere

    faxe1008 schrieb:

    die Notation umkehren
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    RodFromGermany schrieb:

    In Deinem Beispiel unterscheiden sich die beiden Gruppen nur durch Leerzeichen. :/

    Das sind die einzelnen Tokens. Tokens definieren sich als Bestandteile eines Ausdrucks, denen ein Typ zugewiesen wird. Im oberen Fall wären das Kontrollstrukturen, Identifier bzw. Variablennamen, Stringliterale, Operatoren und Klammern. Gemäß der Definition: de.wikipedia.org/wiki/Token_(%C3%9Cbersetzerbau) handelt es sich bei der "Aufteilung" des Terms die ich vorgenommen habe um Tokens.

    Mit Notation umkehren meine ich ähnlich wie beim ShuntingYard-Algorithmus die Infix-Notation zu einer Art Postfix-Notation umzukehren, so dass die Klammern entfallen und der Interpreter sich Zeile um Zeile, Token für Token entlang hangeln kann und einen Befehl nach dem anderen durchführt. Wenn jemand sonst eine verwertbarre Idee hat, wie mit den vorliegenden Tokens umgegangen werden kann, darf sie gerne hier rein stellen ;)

    8-) faxe1008 8-)

    faxe1008 schrieb:

    zu einer Art Postfix-Notation umzukehren
    Also so was wie Umgekehrte polnische Notation?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Da es anscheinend niemand weiß bzw. denkt dass sowas wie die Postfix-Notation geeignet ist um die Tokens für den Interpreter besser einlesbar zu machen muss es eine andere Alternative geben. Ich hatte mir gedacht, dass ich jede Zeile durchsuche, ob sie einen Operator oder eine mathematische Funktion enthält, den entsprechenden Teil aus der Zeile dann mit nem Parser ausrechnen, dann zurück in die Zeile schieben und den Interpreter drüber jagen.

    Beispiel:

    Quellcode

    1. if(2+3*2=9-3)
    2. irgendwas
    3. end
    5. => 2+3*2=9-3 herausschneiden und an Parser übergeben
    6. => Als Resultat eine 1 als True zurückschieben
    8. if(1)
    9. irgendwas
    10. end


    Doch irgendwie sehe ich dabei erhebliche Performance-Probleme wenn es dann beispielsweise um if-abfragen innerhalb einer For-Schleife gehen würde. Daher stellt sich mir, bevor ich weiter arbeite die Frage wie ich einen sauberen performanten Interpreter schreiben kann der ebenfalls mathematische Ausdrücke berechnen kann, die im Script auftauchen. Ich bin dankbar für jede Idee :)

    8-) faxe1008 8-)

    @Artentus Die Schachtelung von Funktionen ist nicht das Problem, sondern viel eher, dass ich keine Ahnung habe wie ich geschachtelte Blöcke unmissverständlich für den Interpreter in Postfix schreiben kann.

    Quellcode

    1. if(2-1=1)
    2. if(2>1)
    4. end
    5. end


    Bei sowas habe ich keine Idee wie das in Postfix auszusehen hat.

    8-) faxe1008 8-)

    Was wäre dann dein Vorschlag? Den Interpreter stur Zeile für Zeile durcharbeiten lassen, ohne eine "Vereinfachung" durch den Algorhytmus? Die Frage ist dann allerdings wie ich mit mathematischen Ausdrücken umgehe, wenn ich nicht nen Mischmasch aus Parser und Interpreter bastele.

    8-) faxe1008 8-)

    Abfragen und Schleifen gibts ja auch eigentlich nicht in dieser Form. Am einfachsten wir es wohl sein, wenn du vor dem Interpretieren etwas Vorarbeit leistest und diese Konstrukte in ihre jeweiligen Lowlevel-Äquivalente übersetzt. Der Interpreter muss dann nur noch mit Jumps umgehen können, alles andere (grundlegende Arithmetik und Logik) musst du ja so oder so implementieren.

    Danke Artentus daran arbeite ich momentan. Ich bin gerdae dabei ein Dictionary für die Jump-Marks zu erstellen, sprich wie der Interpreter bei if() Abfragen springen soll.

    Quellcode

    1. 0:if()
    2. 1:if()
    3. 2:end
    4. 3:end


    Das Dictionary soll so aussehen, dass ein Eintrag die Zeilennummer beinhaltet in der das If-steht und die Value des Eintrags ist das das kommunizierende end.

    Quellcode

    1. =>Dictionary({
    2. 0,3
    3. 1,2
    4. })


    So sollte es dann aussehen.

    Problem ist nur, dass der Algorithmus den ich mir dazu überlegt habe irgendeinen Fehler aufweist, den ich nicht finde. Hier mal die Theorie dahinter:
    IfGoBack=0

    Quellcode

    1. 0: if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    3. 1:if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    5. 2:end IfGoBack=0+1=1 IfConditions(IfConditions.count-IfGoBack).Value=currentline
    7. 3:end IfGoBack=1+1=2 IfConditions(IfConditions.count-IfGoBack).Value=currentline
    9. 4:if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    11. 5:end IfGoBack=0+1=1 IfConditions(IfConditions.count-IfGoBack).Value=currentline


    Mit diesem Beispiel funktioniert es auch tadellos, allerdings hat der Algo damit Schwierigkeiten:

    Quellcode

    1. 0:if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    2. 1:if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    3. 2:end IfGoBack=0+1=1 IfConditions(IfConditions.count-IfGoBack).Value=currentline
    4. 3:if() IfGoBack=0 IfConditions.add(currentline,Nothing)
    5. 4:end IfGoBack=0+1=1 IfConditions(IfConditions.count-IfGoBack).Value=currentline
    6. 5:end IfGoBack=1+1=2 IfConditions(IfConditions.count-IfGoBack).Value=currentline


    Beim letzten End würde der Fehler auftreten, dass IfConditions(1).Value auf currentline gesetzt wird, was aber nicht stimmt, denn IfConditions(1).Value ist ja bereits beschrieben.
    Wenn der Algo optimal läuft sollte es so aussehen:
    Dicitionary({
    0,5
    1,2
    3,4
    })

    In dem obigen Fall würde das Dicitonary so aussehen:
    Dicitionary({
    0,
    1,5
    3,4
    })


    Kann jemand von euch den Fehler finden, oder weiß jemand einen Algorithmus der mit obigen Beispielen zurechtkommt?

    8-) faxe1008 8-)

    Also ein if braucht eigentlich keine Jump-Mark, nur das entsprechende End (und das else, falls es eines gibt). Es muss auch nicht gespeichert werden, welche Jump-Marks zu irgend nem if gehören.
    In Assembler gibt es eine Reihe von Jumps, für dich interessant ist aber wohl nur eine. Da du in deinem Fall keine Register hast, ist die am leichtesten als intern definierte Funktion eingebaut. Ein Aufruf könnte z.B. so aussehen: JMP(a, "x:end")
    Dabei ist a eine boolsche Variable (kann auch eine vom Precompiler eingefügte Konstante sein) und x die Zeilennummer des Jump-Marks. Die Jump-Mark wird irgend wie vom Precompiler hinterlegt (wie du das genau machst liegt bei dir), die interne Funktion JMP springt dann mit der Ausführung dort hin, falls a war ist.
    Da es sich um eine ganz normal geparste Funktion handelt, kann anstelle von ​a ein beliebig komplexer Ausdruck stehen. Anders ausgedrückt, die Bedingung der if-Abfrage kann da 1 zu 1 drinstehen.
    Der einzige Part, der hier also zu beachten ist, ist, dass die interne Funktion JMP mehr Kontrolle über deine Runtime braucht als jede im Script definierte Funktion. Sie muss nämlich die Ausführung beeinflussen können. Da alle internen Funktionen ja aber in der Sprache des Interpreters implementiert sein sollten (also hier VB.Net), sollte das machbar sein.

    Je nachdem, wie mans nimmt.
    Der Precompiler muss in der Tat wissen, welches end zu welchem if gehört, damit die korrekte JUMP-Mark eingetragen werden kann. Steht die aber erstmal da drin muss der Interpreter nur noch da hinspringen, zu was die mal gehört hat ist da dann ganz uninteressant.

    Ich denke, das lässt sich am einfachsten auf einem Blatt Papier als Flow-Diagramm lösen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RFG: Kannst du mal das obige Beispiel als Flow-Diagramm reinschreiben? Kann mir gerade nicht wirklich was darunter vorstellen.

    Wo ich gerade darüber nachdenke ist, die Sache mit nem Stack zu lösen, der für die If-Tokens noch die Zeilennummer mitspeichert. Bei jedem End würde dann das vorhergie if vom stack mitsammt Zeilennummer geholt werden.

    8-) faxe1008 8-)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „faxe1008“ ()

    faxe1008 schrieb:

    reinschreiben
    nicht schreiben, sondern malen.
    Die Pfeile, von wo er nach wo gehen soll. das ist bei einfachen Zeilen obsolete, bei Verzweigungen jedoch aufschlussreich.
    Etwa so:

    Für solch gibt es doch regelrecht "CAD"-Programme (der Name fällt mir gerade nicht ein).
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook