[Tutorial] Compiler und Virtual Machine

Hier kannst du häufig gestellte Fragen/Antworten und Tutorials lesen und schreiben.
Antworten
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

Ja, das ist am Besten. GetChar() könnte dann #LF, #CR, #LFCR, #CRLF behandeln, Zeilennummer erhöhen, und es
gibt für #LF, #CR, #LFCR, #CRLF immer #LF zurück. Es konvertiert also auch #CR, #CRLF und #LFCR zu #LF -
dann musst Du an anderen Stellen nur auf #LF prüfen.
Oh ja! Ganz tolle Idee, einfach den Look beinhart austauschen an der Quelle und ein anderes Ei ins Nest legen, ein Kuckucksei eben :lol:?
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
Benutzeravatar
Danilo
-= Anfänger =-
Beiträge: 2284
Registriert: 29.08.2004 03:07

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von Danilo »

puretom hat geschrieben:
Ja, das ist am Besten. GetChar() könnte dann #LF, #CR, #LFCR, #CRLF behandeln, Zeilennummer erhöhen, und es
gibt für #LF, #CR, #LFCR, #CRLF immer #LF zurück. Es konvertiert also auch #CR, #CRLF und #LFCR zu #LF -
dann musst Du an anderen Stellen nur auf #LF prüfen.
Oh ja! Ganz tolle Idee, einfach den Look beinhart austauschen an der Quelle und ein anderes Ei ins Nest legen, ein Kuckucksei eben :lol:?
Genau. Ein klassischer Tokenizer mit Enumerationen gibt für #LF, #CR, #LFCR, #CRLF immer Tokens.Eol zurück. In Deinem Falle eben immer #LF.


Was hast Du eigentlich mit Doppelpunkt und Semikolon geplant? Im Moment werden die durch IsWhite() gefiltert, so dass
der folgende Code ohne Fehler kompiliert wird:

Code: Alles auswählen

1::+;1;+::2;;;*;;4:::
Der Code wird wie "1+1+2*4" kompiliert.
cya,
...Danilo
"Ein Genie besteht zu 10% aus Inspiration und zu 90% aus Transpiration" - Max Planck
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

Hi Danilo!

Zu dem ";":

Was habe ich geplan? Hmmm /:-> !!!
So ganz klar ist mir das leider selbst noch nicht, ich habe es einmal bewusst so gelassen, um zunächst für den Lernprozess des Tutoriallesers zu zeigen: technisch brauchen tut man ihn nicht.

Crenshaw macht den ";" als statement delimiter als Option erlaubt, aber nicht zwingend (an sich ja nicht schwer zu machen mit wenigen Änderungen des Parsers und Compilers, ev. zeige ich das mal?).
Ich mag den ";" auch überhaupt nicht, ich bin ein Kind des Basics der 80'er Jahre und finde ihn deswegen optisch wie eine Ohrfeige - Kann auch nicht aus meiner Haut. Deshalb muss er weg :lol: !

Meine Idee war dann, ihn überhaupt einfach rauszufiltern (auch wegen dem Lern-Vorzeigeeffekt, siehe oben), denn technisch ist er für den Compiler unnötig, der kommt ohne ";" auch nicht aus dem Schritt. Sollte ihn dann wer verwenden wollen, dann ist er jederzeit (sogar bis ins Extreme wie du in deinem Beispiel:

Code: Alles auswählen

1::+;1;+::2;;;*;;4:::
zeigst) auf jeden Fall gestattet und macht mir zumindest dabei keine Arbeit beim Programmieren, um ihn extra an passenden Stellen zu erlauben - soll der Programmierer sich eben selbst zügeln oder auch nicht (siehe Ziel der Sprache unten).

Natürlich: Ein Debugger, der Fehler in einer Warnungsliste ausgibt, tut sich leichter, denn den lasse ich (ist jetzt nur so eine Idee von mir) nach einem ";" den Versuch starten, wieder Schritt zu finden.

Da das aber eine Skriptsprache, eventuell sogar nur für den internen Gebrauch eines hypothetischen Game-Entwicklerteams eines Games mit Scriptingmöglichkeit wird (und nach den ersten Lernschritten jeder, der das liest, selber weiterforschen, erweitern, professionalisieren, modernisieren muss) und natürlich keine kommerzielle Hochsprache, kann ich mal fürs Erste damit leben, denn warum sollte ein verantwortungsvoller echter Programmier die Toleranz des Compilers derart auszutzen wie in deinem Beispiel. Wenn er es doch tut, ja und, wenn er will, soll er, tut mir ja nicht weh.

Also abschließend, lange Worte und kurzer Sinn:
  • 1) zunächst hatte ich pädagogische Ziele mit dem Rausfiltern
    2) Ob ich ein Kapitel mache, wo ich das ";" diskutiere? Vielleicht ähnlich wie Crenshaw später, vielleicht.
    3) persönlicher Geschmack und Abneigung gegen ";" an sich
Die Doppelpunkte:

Ich mag Folgendes sehr gern (ähnlich Python und PB)

Code: Alles auswählen

if      (a=1) : print("Zahl ist 1")
else if (a=2) : print("Zahl ist 2")
else if (a=3) : print("Zahl ist 3")
else          : print("Zahl ist ist nix von allem")
Ist wohl eine persönliche Vorliebe von mir (schau dir meine Programme an, da mache ich das auch so)

Zu Enumerations und Tokens:
Genau. Ein klassischer Tokenizer mit Enumerationen gibt für #LF, #CR, #LFCR, #CRLF immer Tokens.Eol zurück.
Würde ich auch gerne irgendwann zeigen (Enumeration und Token-Codes vor dem Parser machen), angedeutet glaube habe ich es in meinen Einleitungen schon: Num, Name, Op, eol, usw., Token-Codes für keywords über eine Map, denn die ist flott, dann nur mehr Token-Zahlen in der Select-Case usw.
Wirth macht es freilich natürlich auch so.
Auch Crenshaw macht das ähnlich mit der Prozedur Scan() in Block().
Aber ich glaube bei dem weiten Feld des Compilerbaus und der unzähligen Möglichkeiten bin ich froh, wenn ich bis zur Virtuellen Maschine und kleinen laufenden Testprogrammen in der Console komme mit meinem Tutorial :cry: .

Ich habe aber beim Lernen erkannt, dass man alles noch VIEL einfacher versteht, wenn ich das für den Beginn in der Select-Case direkt mit Stringvergleichen in Statement() (C-Style Blockenden) oder in Block() (PB-Style Blockenden mit "EndIf" usw.) mache. Je weniger Prozeduren desto besser zum Erlernen des Systems, wie sich die Prozeduren gegenseitig aufrufen, denn diese Art Parser für diese Art Grammatik, die wir hier implementieren, leben von Rekursion.
Wer mal die Grundmethode kann, kriegt dann die anderen Feinheiten so nebenbei dann später selber hin.


LG Puretom

Edit: Lieber Danilo. Ich habe erst jetzt entdeckt, dass du uns einen Expression Parser ein paar Postings zuvor zur Ansicht hochgeladen hast. Vielen Dank dafür! Lg Puretom
(Unter: http://forums.purebasic.com/german/view ... 2&start=30, Verfasst: 28.09.2013 08:30, ca. in der Mitte blauer Link benannt "Expression Parser")
Zuletzt geändert von puretom am 03.10.2013 21:19, insgesamt 4-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

DAS KANN MAN SCHON ERNSTER NEHMEN: BITTE UM BUGBERICHTE, FEEDBACK, LOB, ..., denn das war viel Arbeit


*** KAPITEL 9: TEXT ***


9. Wesentliche Erweiterung des mathematischen Parsers



9.1. Hinzufügen neuer Operatoren: Vergleiche, boolesche Operatoren wie < <= <> = >= > and or xor



9.1.1. Die neue Präzedenztabelle. Eine Diskussion


In diesem Abschnitt möchte ich über die Präzedenz der Logischen Operatoren sprechen:
  • logische Vergleiche (engl. relational operators oder kurz RelOps): =, <, <=, <>, >=, >
  • logische boolesche Verknüpfung: and, or, xor

Von unserer Entscheidung hier hängt viel von dem ab, was man das "look and feel" einer Programmiersprache nennt.


Zur Erinnerung unsere bisherige Toy-C-Präzedenztabelle:

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 ValueFactor()         Negation 
                       bzw. Unäres -|+          
-----------------------------------------------------------
 MulTerm()             * / %                            
-----------------------------------------------------------
 AddExpression()       + -                      niedrigste
-----------------------------------------------------------
Vergleichen wir damit eine (ich habe sie vereinfacht) beliebige Pascal-Präzedenztabelle:

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 ValueFactor()         Negation 
                       bzw. Unäres -|+  
                       Unäres not
-----------------------------------------------------------
 MulTerm()             * / and                          
-----------------------------------------------------------
 AddExpression()       + - or                   
-----------------------------------------------------------
 Relation()            = < <= <> >= >           niedrigste
-----------------------------------------------------------
(Quelle: http://www.freepascal.org/docs-html/ref/refch12.html)

Wir finden "not", "and", "or" und "= < <= <> >= >" neu in dieser Tabelle.

Anmerkung: Ich möchte NICHT die Unterscheidung von C zwischen "=" und "==" übernehmen. Obwohl Toy-C genannt, ist meine Sprache hier näher an Pure Basic als an C. Auch were ich "and" und nicht "&&" und auch "or" verwenden.

Überlegen wir uns, wie mit der Grammatik von Pascal folgende Rechnung gelöst werden würde:

Code: Alles auswählen

if (  a=2 and b<>3   )    <=== Rechnung
if (  a=(2 and b)<>3 )    <=== würde so gelöst
Und das gefällt mir nicht!

Warum ist das so?
Es liegt daran, dass "and" in der Tabelle höherwertiger ist als "=", also wird "and" vor "=" ausgerechnet, genauso wie eben "* / %" vor "+ -".

Ich schlage folgende vorläufige Präzedenztabelle für Toy-C vor:

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 ValueFactor()         Negation 
                       bzw. Unäres -|+  
-----------------------------------------------------------
 MulTerm()             * / %                           
-----------------------------------------------------------
 AddExpression()       + -                  
-----------------------------------------------------------
 Relation()            < <= <> = >= >           
-----------------------------------------------------------
 BoolAnd()             and
-----------------------------------------------------------
 BoolOrXor()           or xor                   niedrigste
-----------------------------------------------------------
Als Vorlage habe ich eine C-Präzedenztabelle gewählt (siehe: http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml) und für meine Zwecke vereinfacht.


Wenn wir jetzt nochmals die Beispiele von oben vergleichen, dann ergibt sich folgende Operatorenreihenfolge:

Code: Alles auswählen

if (  3*4  and  3+5  )
if ( (3*4) and (3+5) )    <=== würde so gelöst
-----------------------------------------------
if (  x<=4  and  y>5  )
if ( (x<=4) and (y>5) )   <=== würde so gelöst
Und das ist für mich schon intuitiver.


Zur Vollständigkeit schauen wir uns noch die Tabelle von Pure Basic (siehe PB-Hilfe -> Variablen, Typen, Operatoren) an, die recht ähnlich ist (bis auf 'not', siehe später):

Code: Alles auswählen

  -----------------+---------------------
  Prioritäts-Level |     Operatoren
  -----------------+---------------------
       8 (hoch)    |      ~, -
       7           |    <<, >>, %, !
       6           |       |, &
       5           |       *, /
       4           |       +, -
       3           | >, >=, <, <=, =, <>
       2           |       Not
       1 (niedrig) |  And, Or, XOr
  -----------------+---------------------
Das war jetzt einfach Strg-C, Strg-V. ;-)


Diese Diskussion über Präzedenzen findet sich auch in Crenshaw und ist sehr interessant, aber leider auf Englisch (http://www.pp4s.co.uk/main/tu-trans-comp-jc-06.html).



9.1.2. Mathematischer Parser, Erweiterung um die Operatoren "< <= <> = >= > and or xor"

Die Erweiterung um diese Operatoren geschieht genau so, wie wir uns das vorstellen.
Jede Präzedenzebene bekommt wieder eine Prozedur zugewiesen.

Hier ein Ausschnitt aus dem Declare-Teil von Modul Parser():

Code: Alles auswählen

    ; --- Mathematischer Parser ---                       
      Declare ValueFactor()          ; holt einen Operanden-Wert, ( ... ), unary -|+
      Declare MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      Declare Relation()             ; logische Vergleiche <, <=, <>, =, >=, >
      Declare BoolAnd()              ; boolesches And 
      Declare BoolOrXor()            ; boolesches Or, Xor 
      Declare Expression()           ; mathematischer Expression Parser 3+4*(4+3)
Wie immer ruft Expression() die niedrigste Präzedenz-Stufe auf, jetzt BoolOrXor() und nicht mehr AddExpression().

Code: Alles auswählen

  Procedure Expression()
      BoolOrXor()
  EndProcedure
Die Prozeduren finden wir im Gesamt-Code, den ich am Ende des Kapitels präsentiere.




9.2. Umbau der Implementation des Unary -|+

Wenn man ein System hat, das man einsetzt, wie hier z.B. eben die Rekursion, dann sollte man dieses System auch konsequent durchziehen. Das sollten wir uns merken.

Während unsere erste "naive" Version des unären + bzw. des unären - bestens und sogar perfekt funktioniert, ist sie eben nicht voll an unser System angepasst.

Bauen wir also unsere Präzedenztabelle nochmals um (und wir werden es noch mehrmals tun ;-) ):

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 NegValueFactor()      Negation 
                       bzw. Unäres -|+  
-----------------------------------------------------------
 MulTerm()             * / %                           
-----------------------------------------------------------
 AddExpression()       + -                  
-----------------------------------------------------------
 Relation()            < <= <> = >= >           
-----------------------------------------------------------
 BoolAnd()             and
-----------------------------------------------------------
 BoolOrXor()           or xor                   niedrigste
-----------------------------------------------------------
Wir fügen in unsere Prozedur-Aufrufkette einfach NegValueFactor() ein:

Code: Alles auswählen

  Procedure NegValueFactor()
      
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary + | unary -
      
    ; Ist ein 'unary -' vor ValueFactor?
      If     Scanner::Token='-'     
          
              Scanner::GetToken()    
              ValueFactor()       ; Aufstieg zu ValueFactor()  
              Code::_Neg()
              
    ; Ist ein 'unary +' vor ValueFactor?
      ElseIf Scanner::Token='+'      
      
              Scanner::GetToken()
              ValueFactor()       ; Aufstieg zu ValueFactor()
                                  
    ; 'normaler' ValueFactor
      Else
      
              ValueFactor()       ; Aufstieg zu ValueFactor()  
          
      EndIf    
          
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu MulTerm()

  EndProcedure
In Wirklichkeit ist das eine ganz einfache und kurze Prozedur, sie wird nur durch meine Kommentare so lang.

Was passiert hier?

Besprechen wir nur den Teil von "unary -", der andere ist identisch:
  • Scanner::GetToken(): Bei einem "unary -" holt der Parser das nächste Token-Lexem-Pärchen
  • ValueFactor(): ruft ValueFactor() auf und kümmert sich um Values
  • Code::_Neg(): kommt von ValueFactor() zurück und hat sich quasi "gemerkt", dass er danach noch negieren muss
Interessant ist, dass diese Ausführung im Prinzip EXAKT dasselbe ist wie unser naiverer Ansatz mit dem Flag negate:
"merken", ob "unary -" war ---> Value holen ---> "neg" ausführen, weil "gemerkt"

Die alte Prozedure ValueFactor() (ohne Kommentare oben/unten):

Code: Alles auswählen

  Procedure ValueFactor()
      
    ; pruefe auf Vorzeichen (unary - | unary +) 
    ; Ja? Überspringe es und setze bei "-" ein Flag
      If     Scanner::Token = '-': Scanner::GetToken(): negate = #True    
      ElseIf Scanner::Token = '+': Scanner::GetToken()                
      EndIf           
    
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token      
      Case '#'  : Code::PushConst(Scanner::Lexem)
      Case 'x'  : Code::PushGlobal(Scanner::Lexem)
      Case '('  : Scanner::GetToken()  ; überspringe "("
                  Expression()         ; ")" wird weiter unten übersprungen
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect
    
    ; Teste Flag "negate"
    ; Ja? Führe "unary -" durch: negiere Value
      If negate = #True
          Code::_Neg()
      EndIf                

    ; holt nächstes Token (=Operator)
    ; überspringe eventuell ")"
      Scanner::GetToken()
    
  EndProcedure
Die neue Prozedure ValueFactor() (ohne Kommentare oben/unten):

Code: Alles auswählen

  Procedure ValueFactor()      
   
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token      
      Case '#'  : Code::PushConst(Scanner::Lexem)
      Case 'x'  : Code::PushGlobal(Scanner::Lexem)
      Case '('  : Scanner::GetToken()  ; überspringe "("
                  Expression()         ; ")" wird weiter unten übersprungen
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect    

    ; holt nächstes Token (=Operator)
    ; überspringe eventuell ")"
      Scanner::GetToken()
    
  EndProcedure
Der Test nach "unary -|+" ist jetzt in NegValueFactor() ausgelagert.
Durch die Aufruflogik der Prozeduren ersparen wir uns auch das Flag negate. Wir kommen ja bereits vom erfolgreichen Test nach "unary -" in ValueFactor() an, also können wir bei Rückkehr automatisch "neg" ausführen.

Natürlich - wir sehen es dann in der Gesamtimplementation im Code-Teil - müssen wir auch wieder einen Declare-Teil und die Aufrufe von MultTerm() von ValueFactor() auf NegValueFactor() ändern, das können wir aber mittlerweile blind (hoffe ich).




9.3. Hinzufügen eines neuen Operators: Potenzieren ^


9.3.1. Erster naiver und falscher Ansatz

Auf jeden Fall fügen wir die Potenz (engl exponentiation oder '2 power to 4') mit einer möglichst hohen Präzedenz ein, wie das auch die Programmiersprache Python tut (siehe wieder einmal: http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml). Die anderen Sprachen erwähne ich gar nicht, denn diese besitzen (wie PB auch!) gar keinen Exponentialoperator.
Wir werden das "^"-Zeichen (Zirkumflex oder engl. caret) verwenden (nebenbei: oben erwähntes Python verwendet übrigens "**").

Präzedenztabelle für die Potenz:

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 NegValueFactor()      Negation 
                       bzw. Unäres -|+  
-----------------------------------------------------------
 Exponentiation()      ^
-----------------------------------------------------------
 MulTerm()             * / %                           
-----------------------------------------------------------
 AddExpression()       + -                  
-----------------------------------------------------------
 Relation()            < <= <> = >= >           
-----------------------------------------------------------
 BoolAnd()             and
-----------------------------------------------------------
 BoolOrXor()           or xor                   niedrigste
-----------------------------------------------------------
Eingefügt haben wir "^" zwischen MulTerm() und NegValueFactor().

Die erste falsche Prozedur Exponentiation():

Code: Alles auswählen

  Procedure Exponentiation_LA() ; *** falsch:  links_assoziativ  ***
                                ;     kann entfernt werden, wenn nicht benötigt
                                
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu NegValueFactor()    
      NegValueFactor()
      
    ; Power-Op in Token/Lexem?
      While Scanner::Token='^'        
        
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu NegValueFactor() 
        ; ====> FALSCH! NUR BEI SELBSTAUFRUF RICHTIG RECHTSASSOZIATIV !!! <==== 
        ; ====> siehe richtige Lösung weiter unten
          NegValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
          Code::_Exp()
      
      Wend            

    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu MulTerm  
      
  EndProcedure
Lassen wir jetzt einmal den Parser mit folgendem Source-Code laufen.

Code: Alles auswählen

-2^-4
XXXXXXXXXXXXXXX
2^3
XXXXXXXXXXXXXXX
2^3*3
XXXXXXXXXXXXXXX
2^3^4             // <==== HIER LIEGT EIN PROBLEM VOR
Unser Compiler macht folgendes .ta-File daraus:

Code: Alles auswählen

        push Const  2
        neg
        push Const  4
        neg
        exp                             <=== PASST
        push Global XXXXXXXXXXXXXXX
        push Const  2
        push Const  3
        exp                             <=== PASST
        push Global XXXXXXXXXXXXXXX
        push Const  2
        push Const  3
        exp                             <=== PASST: "^" höhere Präzedenz als "*"
        push Const  3
        mul                             
        push Global XXXXXXXXXXXXXXX
        push Const  2                   <=== !!!!!! FALSCH FALSCH FALSCH !!!!!!
        push Const  3
        exp
        push Const  4
        exp
Warum passt das nicht? Was verflixt nochmal soll daran jetzt bitte falsch sein?
Es hat doch auch z.B. bei "+,-" bzw. "*,/,%" problemlos funktioniert.



9.3.2. Operatorassoziativität und der Vorschlag einer Lösung

Beantworten wir die oben gestellte Frage.

So wie wir die falsche Prozedur Exponentiation() programmiert haben, löst der Compiler das Ganze folgendermaßen, also genauso wie 2+3+4 oder 2*3*4 usw.:

Code: Alles auswählen

Angabe:                          2^3^4
Lösungsreihenfolge des Parsers: (2^3)^4
Dass er das genauso löste wie 2+3+4 oder 2*3*4 ist auch kein Wunder, ist die Prozedur doch wieder identisch mit denen der anderen Operatoren, also ein leicht varierter (nur bei den Operatoren und den Aufrufen) Klon.

Er rechnet also zuerst 2^3 aus und das Ergebnis nimmt er dann ^4. Bei der Multiplikation, der Addition, bei nahezu allen anderen Operatoren würde das stimmen.

Das Phänomen, das wir gerade kennen lernen und das uns jetzt ärgert, nennt man Operatorassoziativität.
(siehe:http://de.wikipedia.org/wiki/Operatoras ... vit%C3%A4t)

Die meisten Operatoren sind linksassoziativ, d.h. sie werden von links nach rechts gelöst.
Der Exponentialoperator ist aber rechtsassoziativ, d.h. wir müssen ihn von rechts nach links lösen (siehe: http://de.wikipedia.org/wiki/Operatorra ... Operatoren).

Auch in den andauernd von mir zitierten Präzendenztabellen (diese da: http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml) findet sich eine Spalte, die wir bisher wahrscheinlich noch gar nicht bewusst wahrgenommen haben: Sie heißt "Associativity", also Assoziativität.

Ich möchte diese Spalte in den nächsten Präzedenztabellen von Toy-C ebenfalls aufnehmen.

In der Literatur über Compiler habe ich über die Exponentation folgende Aussagen gefunden:
  • Die Exponentation sei wegen ihrer Rechtsassoziativität sehr schwer umzusetzen.
  • Die meisten Programmiersprachen lösen das Problem, indem sie einfach keinen Exponentialoperator einfügen, auch Pure Basic - siehe PB-Hilfe unter Pow() -, Pascal und alle C-Abarten machen das, wenn wir in die Tabelle schauen. Sie nutzen eine Prozedur, die die Exponentialfunktion umsetzt.
    Damit umschifft man das Problem, weil eine Prozedur aufgerufen in einer Prozedur automatisch rechtsassoziativ wird.

    Ein Beispiel in Pure Basic:

    Code: Alles auswählen

    ; =================
; Angabe ist: 2^2^3
; =================
RA = Pow(2,Pow(2,3))   ; richtig rechtsassoziativ : 2^(2^3) ==> 256
LA = Pow(Pow(2,2),3)   ; falsch  linksassoziativ  : (2^2)^3 ==> 64

Debug "richtig rechtsassoziativ : "+Str(RA)
Debug "falsch  linksassoziativ  : "+Str(LA)
    Richtig ergibt das 256. Laut Wikipedia und Assoziativgesetz (http://de.wikipedia.org/wiki/Assoziativ ... Einordnung: gleich oberhalb der Überschrift "Einordnung") ist das die richtige Lösung.
    Würde der Potenzoperator linksassoziativ sein, dann wäre die Lösung 64.
Aufgrund der Aussagen in der Literatur und auch deshalb, weil das Problem auch in Pure Basic mit einer Prozedur gelöst ist, fasste ich den Plan, den Exponentialoperator wegzulassen und später eine Funktion dafür bereitzustellen.
Immerhin macht das C über C++ bis C# mit einer Prozedur bzw. Methode "pow()", auch Pascal kennt diese Prozedur, einzig Python und Lua (http://www.lua.org/pil/3.5.html) machen das unter den mir bekannten Programmiersprachen mit einem eigenen Operator, selbstverständlich mit korrekter Rechtsassoziativität (wieder siehe die schon unzählige Male verlinkte Präzedenztabelle bzw. Lua-Link vorhin).

Also so richtige Schwergewichte, also die Big Boys, "schwindeln" sich mit einer Prozedur aus der Assoziativitätsproblematik, nur Python nicht, also müsste es ja einen Weg geben.

Nach relativ kurzer Überlegung fand ich eine Lösung. Und diese ist so derart einfach wie sexy, dass ich - ich habe oben von einem Vorschlag gesprochen - gar nicht glauben kann, dass sie 1. funktioniert und dass 2. ich sie entdeckt habe.

Aus diesem Grund bitte ich alle, den Parser in allen erdenklichen Lebenslagen zu testen und zu schauen, ob meine Lösung letztlich auch wasserdicht funktioniert (vor allem auch INNERHALB komplizierter mathematischer Ausdrücke mit Klammern und Negationen uvm.).
Ich danke allen Testern aus tiefstem Herzen bereits im Voraus.

Sollten sich Bugs finden, was solls. Die recht häufige Prozedur-Variante können wir immer noch ohne viel Aufwand umsetzen.


Ein Source-Code-Beispiel:

Code: Alles auswählen

2+3+4                     // linksassoziativ: (2+3)+4

XXXXXXXXXXXX
2^2^3                     // rechtsassoziativ: 2^(2^3)
DAS_GLEICHE
2^(2^3)                   // ASM-Code sollte gleich sein: 2^(2^3)

FUNKTIONSTEST_1
25*(2^3^4+(25+3)/2)      /*  testet, ob das Ganze auch eingefügt in einen
                          *  komplizierteren Ausdruck aus der Rekursion herausfindet. 
                          */
                     
FUNKTIONSTEST_2
25+(2^-3^-(4+5*2) *100)  /*  2. Exponent ein Klammerausdruck 
                          *  und einige unnötige Negationen
                          */
Die richtige Variante der Prozedur Exponentation() erzeugt bei mir folgende VM-ASM-Ausgabe (Leerzeilen und Kommentare nachträglich von mir eingefügt):

Code: Alles auswählen

        push Const  2               <=== 2+3+4     // linksassoziativ: (2+3)+4
        push Const  3
        add
        push Const  4
        add
        
        push Global XXXXXXXXXXXX
        push Const  2               <=== 2^2^3     // rechtsassoziativ: 2^(2^3)
        push Const  2
        push Const  3
        exp
        exp
        
        push Global DAS_GLEICHE
        push Const  2               <=== 2^(2^3)   // ASM-Code sollte gleich sein: 2^(2^3)
        push Const  2
        push Const  3
        exp
        exp
        
        push Global FUNKTIONSTEST_1 <=== 25*(2^3^4+(25+3)/2) 
        push Const  25
        push Const  2
        push Const  3
        push Const  4
        exp
        exp
        push Const  25
        push Const  3
        add
        push Const  2
        div
        add
        mul
        
        push Global FUNKTIONSTEST_2 <=== 25+(2^-3^-(4+5*2) *100)
        push Const  25
        push Const  2
        push Const  3
        neg
        push Const  4
        push Const  5
        push Const  2
        mul
        add
        neg
        exp
        exp
        push Const  100
        mul
        add
Die von mir vorgeschlagene richtige Prozedur Exponentiation():

Code: Alles auswählen

  Procedure Exponentiation()    ; *** richtig: rechts_assoziativ ***
    
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu NegValueFactor()    
      NegValueFactor()    
    
    ; Power-Op in Token/Lexem?                                <==== IF statt WHILE
      If Scanner::Token='^'        
         
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Rechtsassoziativ !!! --> Selbstaufruf
        ; ====> BEI SELBSTAUFRUF RICHTIG RECHTSASSOZIATIV !!! <==== ÄNDERUNG HIER         
          Exponentiation()
          
        ; Ausgabe des ASM-Codes des Operators
          Code::_Exp()
      
      EndIf      

    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu MulTerm()  
      
  EndProcedure
Erklärung:
  • Mein Lösungsansatz besteht darin, dass sich die richtige Prozedur Exponentation() immer wieder selbst aufruft - bis zum Ende der Kette der "^"-Operatoren (Beispiel: 2^3^4 +5).
  • Am Ende der "^"-Operatorenkette (also bei '+' im Beispiel) beginnt die Prozedurenaufrufkette wieder rückwärts zu laufen und arbeitet alle "exp"-Befehle bis zum letzten ab.
  • Dadurch wird meiner Meinung nach der Teilausdruck, der aus "^"-Operatoren besteht, rechtsassoziativ.
  • Bitte nicht übersehen, dass ich nicht nur den zweiten Aufruf zur nächsthöheren Prozedur zu einem Selbstaufruf verändert habe, sondern auch die While-Schleife zu einer If-Then-Konstruktion.
  • Wie oben bereits von mir erwähnt, bitte ausgiebig testen.
Ich lasse beide Prozedur-Versionen zum Testen beider Varianten, einmal der richtigen unter dem Prozedurnamen Exponentation() und einmal der falschen unter dem Namen Exponentation_LA() ('_LA' steht für linksassoziativ), im Code-Teil von Kapitel 9.




9.4. Hinzufügen des unären logischen Not


9.4.1. Vorüberlegungen

Die Sache mit dem logischen Not-Operator (nicht zu verwechseln mit dem bitweisen Not-Operator) ist auf den ersten Blick einfach, auf den zweiten schwierig.

Nicht dass seine Umsetzung besonders schwierig wäre, das Wie ist also nicht das Problem an sich, aber die Qual der Entscheidung, wo wir den unären Not-Operator in die Präzedenztabelle einfügen, ist groß.

Verschiedene Sprachen gehen da verschiedene Wege:
  • In Pure Basic finden wir "not" recht weit unten, ebenso in Python.
  • C und Pascal hingegen haben "not" sehr weit oben in der Präzedenztabelle.
Ich würde für mich persönlich (siehe Code-Teil des Kapitels 9) eher die Variante von Pure Basic bevorzugen und das hat seinen Grund (siehe Diskussion nächstes Unterkapitel).



9.4.2. Diskussion: logisches Not und die Operatoren and, or und xor?

Ich folge hier einem Argument von Crenshaw im Kapitel http://www.pp4s.co.uk/main/tu-trans-comp-jc-16.html.

Crenshaw als Naturwissenschaftler weiß, dass man den booleschen Operator "xor" (exlusives Or) auch mit anderen booleschen Operatoren umschreiben kann.

Folgende Schreibweise für die Umschreibung des Xor sei üblich in der Naturwissenschaft, meint er:

Code: Alles auswählen

        a xor b >= (a and not b) or (not a and b)
Wenn wir jetzt erlauben würden, dass "and" eine höhere Präzedenz als "not" hat, dann würde dieser Ausdruck folgendermaßen gelöst:

Code: Alles auswählen

  
        a xor b >= (a and not b) or ( not (a and b) )
                                         ^^^     ^^^
Daraus schließt Crenshaw, dass der Operator "not" eine höhere Präzedenz als "and" und "or/xor" haben muss, eine Bedingung, die in allen mir bekannten Sprachen auch erfüllt ist. Wäre das nicht so, dann kann die obere Umschreibung von "xor" nicht optisch so ausschauen, wir müssten eben die Klammer bei "( not (a and b) )" einfügen und das sei aber, laut Crenshaw, nicht das Aussehen, das ein Wissenschaftler von diesem Ausdruck erwarten würde. Also braucht es eine höhere Präzedenz für "not".

Ich schließe mich ihm an, dass "not" auf jeden Fall höhere Priorität als "and" und "or/xor" haben muss, das ist in den meisten Sprachen der Fall, auch in Pure Basic.

Wenn wir uns an die Präzedenztabelle von Pure Basic erinnern:

Code: Alles auswählen

  -----------------+---------------------
  Prioritäts-Level |     Operatoren
  -----------------+---------------------
       8 (hoch)    |      ~, -
       7           |    <<, >>, %, !
       6           |       |, &
       5           |       *, /
       4           |       +, -
       3           | >, >=, <, <=, =, <>
       2           |       Not
       1 (niedrig) |  And, Or, XOr
  -----------------+---------------------
dann sehen wir aber noch etwas.

"Not" ist hier nämlich von sehr niedriger Präzedenz, wohl richtigerweise noch höher als "and" und "or/xor", aber sonst ganz unten in der Tabelle.



9.4.3. Diskussion: logisches Not und die restlichen Operatoren?

Wie hoch soll die Präzedenz des Not-Operators in Bezug auf die übriggebliebenen Operatoren sein?

Wie es um "and, or, xor" steht, wissen wir ja bereits, denn wir haben uns mit Crenshaw (und den anderen Programmiersprachen) darauf geeinigt, dass "not" auf jeden Fall eine höhere Präzedenz als "and" und "or/xor" haben soll, um die Umschreibung für "xor" korrekt aussehen zu lassen. Damit hätten wir die naturwissenschaftliche bzw. ingenieurswissenschaftliche Mathematik befriedigt bzw. nicht gegen uns aufgebracht.

Aber was ist mit all den anderen?


9.4.3.1. Not-Operator mit sehr hoher Präzedenz (ohne Code)

Präzedenztabelle für not mit sehr hoher Präzedenz:

Code: Alles auswählen

 Prozedur              Operator            Assoziativität   Präzedenz        
-----------------------------------------------------------------------
 ValueFactor()         ( ... )                              höchste
-----------------------------------------------------------------------
 NegValueFactor()      Negation               L *-->
                       bzw. Unäres -|+  
-----------------------------------------------------------------------
 LogNot()              unäres log. not        R <--*
-----------------------------------------------------------------------
 Exponentiation()      ^                      R <--*
-----------------------------------------------------------------------
 MulTerm()             * / %                  L *-->   
-----------------------------------------------------------------------
 AddExpression()       + -                    L *-->
----------------------------------------------------------------------
 Relation()            < <= <> = >= >         L *-->
-----------------------------------------------------------------------
 BoolAnd()             and                    L *-->
-----------------------------------------------------------------------
 BoolOrXor()           or xor                 L *-->        niedrigste
-----------------------------------------------------------------------
Eingefügt habe ich "not" schnell mal zum Testen zwischen Exponentiation() und NegValueFactor() (ich denke, das bekommt mittlerweile jeder selbst auch hin).
Ich folge hier ganz der bereits erwähnten Präzedenztabelle von C (http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml), aber auch in Pascal finden wir "not" ganz weit oben (siehe ebenfalls voriger Link).


Folgen wir diesem Gedanken kurz einmal und überlegen wir uns, wo uns das beim Rechnen hinbringt.

Rechnen wir folgenden Source-Code mit der obigen Präzendenztabelle durch:

Code: Alles auswählen

not a + 5 * 3   // sollte unserer derzeitigen Präzedenztabelle 
                // gemäß so gelöst werden: (not a) + 5*3
VM-ASM im ta.-File zeigt, dass unsere Annahme richtig war:

Code: Alles auswählen

        push Global A
        not
        push Const  5
        push Const  3
        mul
        add
Es geht also "not", was ja so sein muss, wenn wir uns die Präzedenztabelle betrachten, direkt auf den ValueFactor, die restliche Rechnung kommt danach.

Wenn ich hier den ganzen Ausruck "a+5*3" mit "not" versehen will, brauche ich Klammern:

Code: Alles auswählen

not (a + 5 * 3)
In C müsste ich mit Klammern arbeiten, in Pascal ebenfalls, aber eben nicht in Pure Basic zum Beispiel, weil da alle anderen Operatoren (außer "and, or, xor") höherwertig sind als "not".


Ein letztes Source-Code-Beispiel zu diesem Diskussionspunkt:

Code: Alles auswählen

not not not -B + -C
Der Compiler übersetzt in folgendes .ta-File:

Code: Alles auswählen

        push Global B
        neg
        not
        not
        not
        push Global C
        neg
        add
Man sieht auch hier wieder sehr schön, dass "not" hoher Präzedenz immer zuerst auf den (ev. negativen) ValueFactor geht und nicht auf einen größeren (Teil-)ausdruck.

Wenn ich das so haben will, dann werde ich meinen mathematischen Parser genau so programmieren. Die Prozedur LogNot() füge ich genau dort ein.
Ich kann die Prozedur aus dem Code-Teil von Kapitel 9 hernehmen und wie immer nur die Aufrufe davor und in der Prozedur entsprechend anpassen und schon habe ich "not" auf dieser Ebene.
Im Code-Teil ist die Prozedur LogNot() allerdings nicht so weit oben, sondern gleich über "and, or, xor" zu finden, also wie in Pure Basic, weil diesen Compiler ich schreibe und mir diese Präzedenz besser gefällt ;-) .

Und letztlich ist es die Entscheidung des Compiler-Schreibers, wo er sein Not haben will. Das muss jeder für sich selbst entscheiden, denn feste Regeln gibt es hier nicht.



9.4.3.2. Not-Operator mit Präzedenz genau über "and, or, xor" (mit Code)

Ich möchte jetzt hier wieder einmal zur Übersicht den Declare-Teil der Prozeduren des mathematischen Parsers sowie die Präzedenztabelle vorstellen.

Declare-Teil unseres mathematischen Parsers mit einem Not niedrigerer Präzedenz:

Code: Alles auswählen

    ; --- Mathematischer Parser ---                       
      Declare ValueFactor()          ; holt einen Operanden-Wert, ( ... )
      Declare NegValueFactor()       ; unary -|+
      Declare Exponentiation()       ; Potenz: Hoch-Operator: ^ (*rechts assoziativ*)     
      Declare MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      Declare Relation()             ; logische Vergleiche <, <=, <>, =, >=, >
      Declare LogNot()               ; unary logisches Not
      Declare BoolAnd()              ; boolesches And 
      Declare BoolOrXor()               ; boolesches Or, Xor
      Declare Expression()           ; mathematischer Expression Parser 3+4*(4+3)
Präzedenztabelle für not mit niedrigerer Präzedenz:

Code: Alles auswählen

 Prozedur              Operator            Assoziativität   Präzedenz        
-----------------------------------------------------------------------
 ValueFactor()         ( ... )                              höchste
-----------------------------------------------------------------------
 NegValueFactor()      Negation               L *-->
                       bzw. Unäres -|+  
-----------------------------------------------------------------------
 Exponentiation()      ^                      R <--*
-----------------------------------------------------------------------
 MulTerm()             * / %                  L *-->   
-----------------------------------------------------------------------
 AddExpression()       + -                    L *-->
----------------------------------------------------------------------
 Relation()            < <= <> = >= >         L *-->
-----------------------------------------------------------------------
 LogNot()              unäres log. not        R <--*
 -----------------------------------------------------------------------
 BoolAnd()             and                    L *-->
-----------------------------------------------------------------------
 BoolOrXor()           or xor                 L *-->        niedrigste
-----------------------------------------------------------------------
Mit dieser Präzedenzeinstellung geht "not" auf die gesamte Expression und nicht nur auf einen einfachen (ev. negativen) ValueFactor. Der Not-Operator lässt also einen mathematischen Ausdruck VORHER (außer natürlich wie aus der Tabelle ersichtlich "and" und "or/xor".) berechnen und nimmt dessen Ergebnis erst als "not".
Das ist das Verhalten von Pure Basic und auch Python, nicht aber von C oder Pascal, man sieht: Wirklich bindende Regeln gibt es hier nicht.

Am besten ich bringe ein Beispiel:

Code: Alles auswählen

not  a+32*4     // dieser Code müsste folgender
not (a+32*4)    // Reihenfolge entsprechen, also Teil-Expression zuerst
Im .ta-File finden wir (Kommentare und Leerzeichen wie immer von mir):

Code: Alles auswählen

        push Global A    <=== not  a+32*4, Reihenfolge ist not (a+32*4)
        push Const  32
        push Const  4
        mul
        add
        not
        
        push Global A    <=== not (a+32*4)  
        push Const  32   <=== MIT OBEN IDENT, WEIL COMPILER RECHNET
        push Const  4    <=== DURCH PRÄZEDENZ AUTOMATISCH GENAU SO
        mul
        add
        not
Beide Codes sind ident, mit und ohne Klammer, d.h. der Compiler berechnet zuerst den mathematischen Teil-Ausdruck "a+32*4", dessen Operanden mit Operatoren höherer Präzedenz als "not" verbunden sind.

Jetzt können wir in Toy-C intuitiv Folgendes tun:

Code: Alles auswählen

if (not 5+3*4)  // das geht wie in Pure Basic
if (not(5+3*4)) // Klammer dazu nicht notwendig
Zum Verständis hier zum Vergleich denselben Code kompiliert mit dem Parser (voriges Unterkapitel), der ein "not" ganz hoher Präzedenz hat:

Code: Alles auswählen

        push Global A    <=== not a+32*4, also Reihenfolge ist (not a)+32*4 
        not              <=== NOT geht sofort auf den Value  
        push Const  32        
        push Const  4
        mul
        add              
        
        push Global A    <=== not (a+32*4) 
        push Const  32   <=== diese Reihenfolge müssen wir mit einer Klammer erzwingen  
        push Const  4
        mul
        add
        not
Die Operatoren "and, or, xor" haben eine höhere Präzedenz als "not". Also testen wir folgenden Source-Code:

Code: Alles auswählen

(a and not b) or ( not a and b )
XXXXXXXXXXXXXXXXXXXXXX
(a and not b) or ( (not a) and b ) // so (lt. Crenshaw) will es die Naturwissenschaft verstehen
Und unser Compiler schreibt genau das ins .ta-File:

Code: Alles auswählen

        push Global A
        push Global B    <=== BEIDES IDENT, RECHNET ALSO, 
        not              <=== ALS WÄRE DIESE KLAMMER DA
        and
        push Global A
        not
        push Global B
        and
        or
        push Global XXXXXXXXXXXXXXXXXXXXXX
        push Global A
        push Global B    <=== BEIDES IDENT, RECHNET ALSO,  
        not              <=== ALS WÄRE DIESE KLAMMER DA
        and
        push Global A
        not
        push Global B
        and
        or
Heureka!

Hier die fertige Prozedur LogNot() zum Abschluss:

Code: Alles auswählen

  Procedure LogNot()
  
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary not 
    
    ; Ist ein 'unary not' vor ValueFactor?                    <==== IF statt WHILE
      If Scanner::Lexem = "NOT"

        ; vor Aufstieg nächstes Token holen
        ; d.i 'not' ODER ein Value
          Scanner::GetToken()  
            
        ; Selbstaufruf für 'not not not ...'                  <==== VGL. MIT EXPONENTATION()
          LogNot()
            
        ; Ausgabe des ASM-Codes des Operators
          Code::_LogNot()              
             
      Else
      
        ; Aufstieg zu Relation()  
          Relation()
          
      EndIf    
      
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu BoolAnd()

  EndProcedure
Die Prozedur LogNot() hat gewisse Ähnlichkeit mit Exponentation(). Auch hier haben wir einen Selbstaufruf im Code, um mehrere Not-Operatoren hintereinander zu erlauben.



9.4.3.3. Eine noch niedrigere Präzedenz für not?

Was spricht eigentlich gegen eine noch niedrigere Präzedenz?
Außer der oben erwähnten Naturwissenschaft, die ein gewaltiges Gegenargument hat, nichts.

Ich für meinen Teil möchte über niemanden urteilen, der sein "not" noch tiefer in der Präzedenztabelle gibt - das kann jetzt aber wirklich schon jeder, einfach LogNot() über Expression() und vor BoolOrXor() verschieben und Prozeduraufrufe anpassen -, denn das hätte auch durchaus seine Vorteile.

Vergleichen wir hier beide Interpretationsmöglichkeiten, je nach Präzedenz:

Code: Alles auswählen

not a<2 and b>4     /* bei der derzeitigen Einstellung rechnet der Compiler:
                    /*     (not a<2) and (b>4)
                    /*               ^^^-- hier endet "not", weil "and" niedriger  
                    
not (a<2 and b>4)   /* wir hätten vielleicht gewollt, dass "not"
                    /* auf die gesamte Expression geht
                    /*
Hier beide Möglichkeiten als VM-ASM-Code:

Code: Alles auswählen

        push Global A    <=== (not a<2) and (b>4)
        push Const  2
        lt
        not
        push Global B
        push Const  4
        gt
        and
        
        push Global A    <=== not (a<2 and b>4) 
        push Const  2
        lt
        push Global B
        push Const  4
        gt
        and
        not              <--- ganz am Ende erst "not", also Gesamtexpression
Der Nachteil dieser Präzedenzstufe ist, wir müssen bei der "xor"-Umschreibung auf unmathematische Weise die Klammern um "( (not a) and b )" setzen.
Das soll jeder für sich entscheiden!



9.4.3.4. Einige Worte zur Assoziativität von not

Manche Programmiersprachen bezeichnen den Not-Operator als links- und manche als rechtsassoziativ. Da es sich hier aber um einen unären Operator handelt, stehe ich dazu, dass mich die Sache etwas verwirrt.

Ich als Nichtmathematiker habe mich gefühlsmäßig dem Lager der "Rechtsassoziativen" angeschlossen, weil auch die Compilerausgabe danach aussieht, dass am Ende einer Not-Kette von rechts nach links über die Rücksprünge der vorher aufgerufenen Prozeduren zurückgekehrt wird.
Im Endeffekt ist aber diese Festlegung, nach allem was ich gesehen habe, nicht wirklich wichtig und hat lediglich Einfluss auf den Tabelleneintrag von "not" in der Präzedenztabelle.

Sollte sich im Forum jemand mit tiefergehenden mathematischen Kenntnissen befinden, um uns den Unterschied auseinanderzusetzen, dann bitte ich darum, sich zu outen!

Ein kleines Beispiel in Source-Code und dann lasse ich die Sache auf sich beruhen, weil sie - glaube ich zumindest - eigentlich keinen Einfluss hat:

Code: Alles auswählen

not not not not not -A + B  /*  eigentlich irgendwie völlig sinnlos
                            /*  zeigt Rücklauf der Prozeduren
                             */
Im .ta-File finden wir:

Code: Alles auswählen

        push Global A
        neg
        push Global B
        add
        not
        not
        not
        not
        not
Perfekt!!

Nicht vergessen dürfen wir, dass im vorigen Unterkapitel die Präzedenz von "not" von mir recht weit (auf Pure-Basic-Niveau) heruntergesetzt wurde, der Compiler übersetzt richtigerweise die (Teil-)expression "(-A + B)" vorher, dann läuft er die Not-Operatoren rückwärts.

Erneut können wir in http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml die Assoziativität von "not" nachlesen, hier sind die meisten sogar für linksassoziativ /:-> .
Meine obige Bitte an die Mathematiker hier im Forum ist weiterhin aufrecht :mrgreen: .




9.5. Kurz ein wenig Error Handling (Fehlerbehandlung)


Was passiert eigentlich, wenn wir bei einer unären Operation versehentlich zu viele z.B. "-" schreiben?
  • Probieren wir das einmal in Pure Basic und in Toy-C:

    Code: Alles auswählen

    3---4
    Wir erhalten in Pure Basic eine korrekte Fehlermeldung (Syntax Error)!

    Und in Toy-C?
    Wir bekommen ebenfalls eine Fehlermeldung, unser Compiler erkennt sogar, dass ein "Operand" fehlt, denn beim 1. Minus kennt er sich noch aus (sub), beim 2. Minus erwartet er "unary -" (neg), beim 3. Minus hätte er gerne wieder einen Operanden (Value: also Zahl oder Variablen- oder Prozedurname).

Was passiert eigentlich, wenn wir bei einem Operator, der aus einem Wort besteht (z.B. and, or, not, ...) und deshalb genauso gut ein Variablenname sein könnte, einen Fehler machen?
  • Da in Pure Basic mixed Operations - in der Zusammenfassung am Ende von Kapitel 9 Genaueres darüber - nicht erlaubt sind, wähle ich für PB folgendes Beispiel:

    Code: Alles auswählen

    If X<2 And Or X>=3 : EndIf
          ^^^^--- PB denkt, dies wäre ein Variablenname
    PB gibt die richtige Fehlermeldung aus, meint doch der Compiler korrekterweise, dass jetzt ein Operator kommen müsste, erkennt ein "Or" und findet heraus, dass diese "Variable" ein Pure-Basic-Schlüsselwort ist. Fehler!

    In Toy-C können wir das direkt in Source-Code eingeben:

    Code: Alles auswählen

    X<2 and or X>=3
    Unser Toy-C-Compiler glaubt in dieser Situation hingegen einfach, dass z.B. ein "or" ein Variablenname ist:

    Code: Alles auswählen

            push Global X
        push Const  2
        lt
        push Global OR   <=== ValueFactor soll kommen, na dann: OR = Variable! FALSCH!
        and
        push Global X
        push Const  3
        ge
    Das können wir so lassen und damit leben oder auch nicht.
Ich habe einen Workaround (Englisch: um etwas herum arbeiten, also eine schnelle Lösung, die das Problem zunächst einmal löst) in ValueFactor() eingebaut.




9.6. Zusammenfassung

Wir haben nun einen mathematischen Parser, der folgende Spezifikationen aufweist:
  • Klammerausdrücke ( ... )
  • Unary Operationen: + - not
  • Korrekte Präzedenzbehandlung unserer Wahl (siehe Präzedenztabelle) aller Operatoren
  • korrekte Rechstassoziativität des Potenz-Operators ^
  • mathematische Ausdrück erlauben gemischte Operationen (mixed Operations) aller Art
  • einfachste Fehlererkennung
Was auf den ersten Blick noch fehlt, sind einige Operatoren, die ich aber derzeit nicht brauche, z.B. die bitweisen Operatoren (z.B. | ~ &) oder die Bitschieboperatoren (z.B. << >>).
Vielleicht baue ich sie ein, vielleicht können das die Leser aber auch schon selbst mittlerweile, denn das ist flott erledigt.

Interessant ist, dass gemischte z.B. boolesche und nicht boolesche Operatoren, also das gleichzeitige Auftauchen von z.B. "and" oder "or" und auch z.B. "*" oder "-" uvm. in einem mathematischen Ausdruck problemlos möglich ist.
Pure Basic verbietet das, und ich glaube, dass man das sogar absichtlich mit Mehraufwand verbieten muss, denn an sich, wie man an unserem Parser sieht, ist das von Haus aus erlaubt:

Ein Beispiel:

Wenn wir folgendes Programm in Pure Basic starten, erhalten wir eine Fehlermeldung (zum Verständnis unbedingt starten und durchlesen):

Code: Alles auswählen

Debug 5+(3<2)     ; Fehler! Das geht in PB nur innerhalb von If, While, Until und Bool()
;                                 
; * Das müsste man in PB so umschreiben
; 
Debug 5+Bool(2<3) ; ergibt 6, weil 2<3=#True  (also 1)
Debug 5+Bool(3<2) ; ergibt 5, weil 3<2=#False (also 0)
; 
; * Toy-C braucht Bool() nicht, da geht das einfach so
;
Ja, das ist halt sowas von Basic ;-) . Toy-C akzeptiert das wie seine größeren Brüder problemlos:

Code: Alles auswählen

5+(3<2)     // wird kompiliert von Toy-C
wird zu einem [/b].ta-File[/b] mit folgendem Inhalt:

Code: Alles auswählen

        push Const  5
        push Const  3
        push Const  2
        lt
        add
Die abschließende Präzedenztabelle des Compilers von Kapitel 9:

Code: Alles auswählen

=======================================================================
 Prozedur              Operator            Assoziativität   Präzedenz        
=======================================================================
 ValueFactor()         ( ... )                              höchste
-----------------------------------------------------------------------
 NegValueFactor()      Negation               L *-->
                       bzw. Unäres -|+  
-----------------------------------------------------------------------
 Exponentiation()      ^                      R <--*
-----------------------------------------------------------------------
 MulTerm()             * / %                  L *-->   
-----------------------------------------------------------------------
 AddExpression()       + -                    L *-->
----------------------------------------------------------------------
 Relation()            < <= <> = >= >         L *-->
-----------------------------------------------------------------------
 LogNot()              Unäres log. not        R <--*
 -----------------------------------------------------------------------
 BoolAnd()             and                    L *-->
-----------------------------------------------------------------------
 BoolOrXor()           or xor                 L *-->        niedrigste
=======================================================================
Die EBNF kann sich bei zu viel Zeit und Laune jeder selbst erarbeiten, ergibt sich ohnehin aus den Prozeduren und der Präzedenztabelle.




9.7. Code des Compilers von Kapitel 9
  • ---- weiter im Teil "Code" dieses Kapitels ----


Viel Spaß mit dem Compiler von Kapitel 9.
LG Puretom



*** ENDE KAPITEL 9: TEXT ***

DAS KANN MAN SCHON ERNSTER NEHMEN: BITTE UM BUGBERICHTE, FEEDBACK, LOB, ..., denn das war viel Arbeit
Zuletzt geändert von puretom am 06.10.2013 10:21, insgesamt 16-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

DAS KANN MAN SCHON ERNSTER NEHMEN: BITTE UM BUGBERICHTE, FEEDBACK, LOB, ..., denn das war viel Arbeit


*** KAPITEL 9: CODE ***


9.7. Code des Compilers von Kapitel 9

Abschließend präsentiere ich den Gesamtcode des Compilers von Kapitel 9, ich habe einige Doppelgleisigkeiten entfernt, wie z.B. die Default-Zweige in den Prozeduren des mathematischen Parsers, die nur zu Lernzwecken (wir haben die Prozeduren ja immer geklont) dort waren.
Außerdem habe ich ein wenig aufgeräumt.


Der Gesamtcode des Compilers von Kapitel 9:

Code: Alles auswählen

; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
; X   PARSER/COMPILER (Kapitel 9)                                               X 
; X       mit eingebunden muss sein:                                            X
; X         1) Module Scanner                                                   X
; X         2) Module Code                                                      X
; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

; *******************************************************************************
; * Scanner                                                                     *
; *******************************************************************************
DeclareModule Scanner      
; -
; - Public Declarations ---------------------------------------------------------
; -  
      Global Look                ; Look Ahead Character
      Global Token               ; Token-Typ als Zahl
      Global Lexem.s             ; Lexem = Token als String
     
    ; --- Start-Prozedur ---  
      Declare Start(file_name.s) ; file_name des Source-Files 
    
    ; --- Look Ahead Character holen mit dieser Prozedur ---
      Declare GetChar()          ; holt nächsten Character von *Source_Code                                    

    ; --- Token-Lexem-Paare holen mit diesen Prozeduren ---
      Declare GetToken()         ; holt nächstes Token-Lexem-Paar
      Declare GetName()          ; holt nächsten Name
      Declare GetNum()           ; holt nächste Num (Integer)                                     
      Declare GetString()        ; holt nächsten String                            
      Declare GetOther()         ; holt nächstes Other-Zeichen    

    ; --- Fehlermeldung ausgeben ---
      Declare Error(error_message.s)      ; zeigt Meldung und beendet Compiler
      Declare Expected(expected_object.s) ; zeigt, was erwartet wurde
                                          ; und beendet Compiler
EndDeclareModule
Module Scanner
; -
; - Private Declarations --------------------------------------------------------
; -
      Global Source_Position     ; Zeichen-Position im *Source_Code
      Global *Source_Code        ; Source-Code Zeichen für Zeichen im Speicher
      
    ; --- Lade Source-File ---
      Declare Load(file_name.s)  ; lädt das ASCII-Source-File    
      
    ; --- Is?() - Prozeduren ---
      Declare IsName1(c)         ; testet, ob Zeichen der Start eines Namens ist
      Declare IsName(c)          ; testet, ob Zeichen zu einem Namen gehört
      Declare IsNum(c)           ; testet, ob Zeichen zu einer Nummer gehört
      Declare IsString(c)        ; testet, ob Zeichen der Start eines Strings ist
      Declare IsWhite(c)         ; testet, ob Zeichen ein White-Character ist
      
    ; --- Skip - Prozeduren ---
      Declare SkipWhite()        ; überspringt jedes White-Zeichen
      Declare SkipLineComment()  ; überspringt ab Comment-Start bis Zeilenende
      Declare SkipBlockComment() ; überspringt von Block-Start bis Block-Ende

; - Debug - Prozeduren (am Ende löschen) ----------------------------------------
; -
  Procedure Debug_CharStream()
    
    ; um ersten Look in den Stream zu legen
      GetChar()                 
    
    ; so lange, bis Look = 0-Byte  
      While ( Look<>0 )            
          Debug "'"+Chr(Look)+"' : "+Str(Look)                
          GetChar()          
      Wend
      Debug Str(Look)+"-Byte beendet (außerhalb While-Schleife)" 
       
  EndProcedure
  Procedure Debug_TokenLexemStream0()

    ; so lange, bis Token = 0-Byte  
      While ( Token<>0 )
          Debug RSet(Str(Token),3," ")+" | '"+Chr(Token)+"'  | "+Lexem
          GetToken()
      Wend
      Debug "(außerhalb While-Schleife)"      
      
  EndProcedure
  Procedure Debug_TokenLexemStream1()

    ; so lange, bis Token = 0-Byte  
      While ( Token<>0 )
          If     Token = #LF: Debug RSet(Str(Token),3," ")+" | 'LF' | "
          ElseIf Token = #CR: Debug RSet(Str(Token),3," ")+" | 'CR' | "              
          Else
              Debug RSet(Str(Token),3," ")+" | '"+Chr(Token)+"'  | "+Lexem
          EndIf
          ;
          GetToken()
      Wend
      If Token=0:Debug "'0'-Token beendet (außerhalb While-Schleife)":EndIf      
  EndProcedure  

; - Start - Prozedur ------------------------------------------------------------
; -
  Procedure Start(file_name.s) 
  
    ; laden des Source-Files   
      Load(file_name.s)
      
    ; auf 1. Zeichen stellen
      Source_Position = 0   
      
    ; das erste aktuelle Token-Lexem-Paar holen  
      GetChar()    ; 1. Zeichen in Zeichen-Strom
      SkipWhite()  ; alle White bis zum 1. gültigen Look
      GetToken()   ; anhand dieses Look erstes Token-Lexem-Paar holen
      
    ; --> ab hier ist alles zum Parser-Start vorbereitet
    ; --> ein gültiges Token-Lexem-Paar liegt bereit
    ; --> der Parser kann übernehmen und weitermachen
    
     ;Debug_CharStream()        ; nur zu Debug-Zwecken
     ;Debug_TokenLexemStream0() ; nur zu Debug-Zwecken
     ;Debug_TokenLexemStream1() ; nur zu Debug-Zwecken
  
  EndProcedure  

; - Lade Source-File ------------------------------------------------------------
; -
  Procedure Load(file_name.s)
      ReadFile(0,file_name)
      size = Lof(0)
      *Source_Code = AllocateMemory(size+1) ; damit auch sicher am Ende 0-Byte ist  
      ReadData(0, *Source_Code, size)      
      CloseFile(0)
  EndProcedure

; - Is?() - Prozeduren ----------------------------------------------------------
; -
  Procedure IsName1(c)
			If ((c>='a' And c<='z') Or (c>='A' And c<='Z'))
					ProcedureReturn #True
			EndIf	  
  EndProcedure
  Procedure IsName(c)
			If (IsNum(c) Or IsName1(c) Or c='_')
					ProcedureReturn #True
			EndIf	  
  EndProcedure  
  Procedure IsNum(c)
			If (c>='0' And c<='9')
					ProcedureReturn #True
			EndIf
  EndProcedure
  Procedure IsString(c)
			If c='"'
					ProcedureReturn #True
			EndIf	      
  EndProcedure  
  Procedure IsWhite(c)
			If (c=' ' Or c=#TAB Or c='/' Or c=#LF Or c=#CR Or c=':'Or c=';')
					ProcedureReturn #True
			EndIf	       
    ; Anmerkung: / startet einen Zeilenkommentar mit // (wie in C)
    ;            / startet einen Blockkommentar mit /* (wie in C)
  EndProcedure  

; - Get - Prozeduren ------------------------------------------------------------
; -
  Procedure GetChar()    
      Look = PeekA(*Source_Code+Source_Position) ; aktuelles Zeichen nach Look
      Source_Position+1                          ; auf nächstes Zeichen stellen
  EndProcedure
  Procedure GetToken()

    ; --> in Look ist das 1. Zeichen dieses Token-Lexems
        
    ; Entscheide, welcher Token-Typ vorliegt und verzweige entsprechend    
      If      IsNum   (Look): GetNum()
      ElseIf  IsName1 (Look): GetName()
      ElseIf  IsString(Look): GetString()
      Else                  : GetOther()    
      EndIf       
    
    ; ueberspringe alle White Characters und Comments (zur Sicherheit)
      SkipWhite()
			
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems			
			
  EndProcedure    
  Procedure GetName()

    ; --> in Look ist das 1. Zeichen dieses Token-Lexems
        
    ; 1. Zeichen korrekt fuer Name?
      If Not IsName1(Look):Expected("Name"):EndIf  
      
    ; Token-Typ zuordnen    
      Token = 'x'
      
    ; Lexem mit Name füllen
      Lexem = ""        
      Repeat
          Lexem = Lexem + Chr(Look)
          GetChar()
      Until Not IsName(Look)  

    ; Name-Identifier sind nicht Case sensitiv      
      Lexem = UCase(Lexem)                   
        
    ; ueberspringe alle White Characters und Comments
      SkipWhite()  
  
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems
  
  EndProcedure
  Procedure GetNum() 
  
    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
  
    ; 1. Zeichen korrekt fuer Num?
      If Not IsNum(Look):Expected("Integer"):EndIf  
      
    ; Token-Typ zuordnen    
      Token = '#'
      
    ; Lexem mit Name füllen
      Lexem = ""        
      Repeat
          Lexem = Lexem + Chr(Look)
          GetChar()
      Until Not IsNum(Look)  
       
    ; ueberspringe alle White Characters und Comments
      SkipWhite()  
  
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems

  EndProcedure 
  Procedure GetString()
  
    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
  
    ; 1. Zeichen korrekt fuer String?
      If Not IsString(Look):Expected("String"):EndIf  
      
    ; Token-Typ zuordnen    
      Token = '$'
      
    ; (") String-Start-Zeichen überspringen 
      GetChar()  
      
    ; Lexem mit Name füllen
      Lexem = ""        
      Repeat
          Lexem = Lexem + Chr(Look)
          GetChar()
      Until IsString(Look)  
      
    ; String-Ende-Zeichen überspringen (")
      GetChar() 
            
    ; ueberspringe alle White Characters und Comments
      SkipWhite()  
  
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems

  EndProcedure   
  Procedure GetOther()

    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
     
    ; Token-Typ zuordnen (=genau dieses Zeichen)  
      Token = Look
      
    ; Lexem füllen (=genau dieses Zeichen)
      Lexem = Chr(Look)
      
    ; nächstes Look holen
      GetChar()

    ; ueberspringe alle White Characters und Comments
      SkipWhite()
        
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems      
     
  EndProcedure
   
; - Skip - Prozeduren -----------------------------------------------------------
; -
	Procedure SkipWhite()
      
    ; solange in Look ein White
      While IsWhite(Look)
          
          ; Zeilenkommentar (// ... #LF/0-Byte)
            If Look='/' And PeekA(*Source_Code+Source_Position)='/'
                SkipLineComment()
                   
          ; Blockkommentar (/* ... */)
            ElseIf Look='/' And PeekA(*Source_Code+Source_Position)='*'
                SkipBlockComment()

          ; einfaches (/) als nicht-White im Stream belassen
            ElseIf Look='/'
                ProcedureReturn

          ; sonstige White-Zeichen überspringen
            Else
                GetChar()
            EndIf
          
	    Wend
	    
	EndProcedure
	Procedure SkipLineComment()
      
      ; bis Zeilenende oder Ende des Source-Files (0-Byte)
        While ( Look<>#LF And Look<>#CR And Look<>0 )
            GetChar()
        Wend 
        
      ; --> Look steht auf #LF oder #CR oder 0-Byte
      ; --> v.a. beim 0-Byte ist wichtig, dass es als
      ; --> Token weitergegeben wird, was beim nächsten
      ; --> GetToken() auch passiert, weil Look ja
      ; --> auf dem 0-Byte oder #LF oder #CR steht  
        
	EndProcedure
	Procedure SkipBlockComment()
    
    ; (/) überspringen
      GetChar() 
    
    ; solange bis (*/)  
      Repeat
        
          ; Zeichen holen, bei Ersteintritt (*) überspringen
            GetChar()
          
          ; verschachtelte Block-Kommentare ermöglichen
            If Look='/' And PeekA(*Source_Code+Source_Position)='*'
                SkipBlockComment()
            EndIf
            
          ; auf 0-Byte achten
            If Look=0: ProcedureReturn: EndIf
        
      Until Look='*' And PeekA(*Source_Code+Source_Position)='/'
     
    ; (*/) überspringen  
      GetChar()
      GetChar() 
      
    ; --> Look steht auf 1. Zeichen nach (*/)   
  
  EndProcedure

; - Error - Prozeduren -----------------------------------------------------------
; -
  Procedure Error(error_message.s)
      MessageRequester("Fehler",error_message)
      End
  EndProcedure		
  Procedure Expected(expected_object.s)
      Error(expected_object+" wird erwartet.")  
  EndProcedure

EndModule

; *******************************************************************************
; * Code                                                                        *
; *******************************************************************************
DeclareModule Code
; -
; - Public Declarations ---------------------------------------------------------
; -
      Global  LabelNr                ; Nr. des nächsten Labels                

    ; --- Start-Prozedur  ---
      Declare Start()                ; Vor Code-Modul-Benutzung aufrufen

    ; --- Stack pushes & pops ---
      Declare PushConst(const_value.s)  ; pusht Konstante auf den Stack        
      Declare PushGlobal(var_name.s)    ; pusht Wert einer globalen Variable 
      
    ; --- Mathematischer Parser ---
      Declare _Neg()                    ; mathematische Operationen
      Declare _Exp()  
      Declare _Mul()
      Declare _Div()
      Declare _Mod()   
      Declare _Add()                          
      Declare _Sub()
      Declare _LowerThan()
      Declare _LowerOrEqual()
      Declare _GreaterThan()
      Declare _GreaterOrEqual()
      Declare _Equal()      
      Declare _NotEqual()      
      Declare _LogNot()            
      Declare _And()
      Declare _Or()
      Declare _Xor()      

    ; --- Sprünge ---
      Declare JumpIfFalse(label_text.s,label_nr) ; Sprung bei False (= 0)
      
    ; --- Label-Verwaltung ---
      Declare Label(label_text.s,label_nr)    ; gibt Label aus    
      Declare GetLabel()                      ; gibt aktuelle Labelnummer zurück 

    ; --- Emit-Hilfsprozeduren ---
      Declare EmitS(text.s)                   ; mit linken Leerzeichen (S=Space)   
      Declare Emit(text.s)                    ; ohne Leerzeichen    
                       
EndDeclareModule
Module Code
; -
; - Private Declarations --------------------------------------------------------
; -

; - Start-Prozedur --------------------------------------------------------------
; -   
  Procedure Start()  
    ; Initialisationen
      LabelNr=0  
  EndProcedure

; - Stack pushes & pops ---------------------------------------------------------
; -   
  Procedure PushConst(const_value.s)
      EmitS("push Const  "+const_value)  
  EndProcedure
  Procedure PushGlobal(var_name.s)
      EmitS("push Global "+var_name)  
  EndProcedure  

; - Mathematischer Parser -------------------------------------------------------
; - 
  Procedure _Neg()
      EmitS("neg") ; "-":   Negation, unary +|-     
  EndProcedure 
  Procedure _Exp()  
      EmitS("exp") ; "%":   Mod     
  EndProcedure
  Procedure _Mul()
      EmitS("mul") ; "*":   Multiplikation     
  EndProcedure  
  Procedure _Div()
      EmitS("div") ; "/":   Division      
  EndProcedure
  Procedure _Mod()  
      EmitS("mod") ; "%":   Mod     
  EndProcedure
  Procedure _Add()
      EmitS("add") ; "+":   Addition     
  EndProcedure
  Procedure _Sub()   
      EmitS("sub") ; "-":   Subtraktion     
  EndProcedure
  Procedure _LowerThan()  
      EmitS("lt")  ; "<":   Lower than -> kleiner als     
  EndProcedure
  Procedure _LowerOrEqual()
      EmitS("le")  ; "<=":  Lower or equal -> kleiner oder gleich
  EndProcedure     
  Procedure _GreaterThan()
      EmitS("gt")  ; ">":   Greater Than -> größer als      
  EndProcedure   
  Procedure _GreaterOrEqual()  
      EmitS("ge")  ; ">=":  Greater Or equal -> größer oder gleich      
  EndProcedure     
  Procedure _Equal()
      EmitS("eq")  ; "=":   Equal -> gleich
  EndProcedure
  Procedure _NotEqual()
      EmitS("ne")  ; "<>":  Not equal -> nicht gleich, ungleich      
  EndProcedure
  Procedure _LogNot()
      EmitS("not") ; "not": unary log. Not       
  EndProcedure    
  Procedure _And()
      EmitS("and") ; "and": log. And      
  EndProcedure 
  Procedure _Or()
      EmitS("or")  ; "or":  log. Or      
  EndProcedure   
  Procedure _Xor()
      EmitS("xor") ; "xor": log. Xor      
  EndProcedure   

; - Sprünge ---------------------------------------------------------------------
; - 
  Procedure JumpIfFalse(label_text.s,label_nr)
      EmitS("JF "+UCase(label_text+Str(label_nr)))
  EndProcedure

; - Label-Verwaltung ------------------------------------------------------------
; - 
  Procedure Label(label_text.s,label_nr)
      Emit("["+UCase(label_text+Str(label_nr))+"]")
  EndProcedure
  Procedure GetLabel()
      LabelNr+1                           
      ProcedureReturn LabelNr        
  EndProcedure    
   
; - Emit-Hilfsprozeduren --------------------------------------------------------
; -
  Procedure EmitS(text.s)
      WriteString(1,Space(8)+text+#CRLF$)
  EndProcedure
  Procedure Emit(text.s)
      WriteString(1,text+#CRLF$)
  EndProcedure

EndModule

; *******************************************************************************
; * Parser (Compiler)                                                           *
; *******************************************************************************
DeclareModule Parser
; -
; - Public Declarations ---------------------------------------------------------
; -
    ; --- Start-Prozedur ---
      Declare Compile(file_name.s) ; Compiliert ein Source-File und erzeugt eine
                                   ; Text-Datei in Toy-C-Assembler mit dem Namen
                                   ; "Source-File-Name.ta" .ta = Toy-Assembler
EndDeclareModule
Module Parser
; -
; - Private Declarations --------------------------------------------------------
; -
    ; --- Debug-Sachen ---
      Global Debug_BlockEbene        ; Debug-Zwecke, später löschen

      ; --- Programmstruktur ---                      
      Declare Statement()            ; erkennt eine Anweisung --> Do()-Prozedur
      Declare Block()                ; behandelt Block von Statements
      
    ; --- Mathematischer Parser --- 
      Declare ValueFactor()          ; holt einen Operanden-Wert, ( ... )
      Declare NegValueFactor()       ; unary -|+
      Declare Exponentiation()       ; Potenz: Hoch-Operator: ^ (*rechts assoziativ*)     
      Declare MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      Declare Relation()             ; logische Vergleiche <, <=, <>, =, >=, >
      Declare LogNot()               ; unary logisches Not
      Declare BoolAnd()              ; boolesches And 
      Declare BoolOrXor()            ; boolesches Or, Xor
      Declare Expression()           ; mathematischer Expression Parser 3+4*(4+3) 
      
    ; --- Hilfsprozeduren ---
      Declare SkipToken(token)       ; prüft, ob erwartetes Token 
                                     ; Nein? -> Fehler, Ja? -> GetToken()  
                           
; - Start, Statement, Block -----------------------------------------------------
; -
  Procedure Compile(file_name.s)

    ; Open .ta-File
      CreateFile(1,GetFilePart(file_name, #PB_FileSystem_NoExtension)+".ta")
         
    ; Inits         
      Debug_BlockEbene = 0
      
    ; Starte Code-Modul
      Code::Start()
  
    ; Starte Scanner-Modul (1. Token-Lexem liegt danach im Stream)
      Scanner::Start(file_name.s)
    
    ; so lange, bis Token = 0-Byte
      While ( Scanner::Token<>0 )
          Statement()
      Wend
      Debug "(außerhalb While-Schleife)"      

    ; Close .ta-File
      CloseFile(1) 
      
  EndProcedure
  Procedure Statement()
  
    ; nur für Debugzwecke (später löschen)    
     Debug RSet(Str(Scanner::Token),3," ")+" | '"+Chr(Scanner::Token)+"'  | "+Space(4*Debug_BlockEbene)+Scanner::Lexem     
  
    ; nach Statements/Befehlen suchen
      Select Scanner::Lexem
          
          Case "{"      : Block()
          ; ...
          Default       : Expression()
         
     EndSelect
  
  EndProcedure  
  Procedure Block()
   
    ; Debug-Zwecke, später löschen
      Debug_BlockEbene+1   
   
    ; ------------------------------------------------------   
    ; --> in Token/Lexem ist jetzt ({)   
   
    ; ueberlesen des ({)
      Scanner::GetToken()     

    ; solange kein (}) oder Source-Code-Ende
      While ( Scanner::Token<>'}' And Scanner::Token<>0 )
          Statement()      
      Wend               
        
    ; ueberlesen des (})
    ; Kein (})? Fehler, Block nicht geschlossen mit (})      
      SkipToken('}')         

    ; --> in Token/Lexem ist jetzt das Token/Lexem nach (})
    ; ------------------------------------------------------   
                        
    ; Debug-Zwecke, später löschen
      Debug_BlockEbene-1              
        
  EndProcedure

; - Mathematischer Parser -------------------------------------------------------
; -
  Procedure ValueFactor()
  
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary + | unary -   
    
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token      
      
      Case '#'  : Code::PushConst(Scanner::Lexem)
      
      Case 'x'  : If Scanner::Lexem="AND" Or Scanner::Lexem="OR" Or ; Teste, ob Lexem ein reservierter Operator-Name 
                     Scanner::Lexem="XOR" Or Scanner::Lexem="NOT"
                          Scanner::Error("Ein Variablen- oder Prozedurname darf nicht wie ein Operator heißen: "+Scanner::Lexem+".")
                  EndIf
                  ;
                  Code::PushGlobal(Scanner::Lexem)
                  
      Case '('  : Scanner::GetToken()  ; überspringe "("
                  Expression()         ; ")" wird weiter unten übersprungen
                  
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      
      EndSelect
            
    ; holt nächstes Token (=Operator)
    ; überspringe eventuell ")"
      Scanner::GetToken()
    
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu NegValueFactor()
  
  EndProcedure
  Procedure NegValueFactor()
      
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary + | unary -
      
    ; Ist ein 'unary -' vor ValueFactor?
      If     Scanner::Token='-'               
                Scanner::GetToken()    
                ValueFactor()      
                Code::_Neg()      
              
    ; Ist ein 'unary +' vor ValueFactor?
      ElseIf Scanner::Token='+'            
                Scanner::GetToken()
                ValueFactor()     
                                
    ; 'normaler' ValueFactor
      Else      
              ; Aufstieg zu ValueFactor()
                ValueFactor()                   
      EndIf    
          
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu Exponentiation()

  EndProcedure
  Procedure Exponentiation_LA() ; *** falsch:  links_assoziativ  ***
                                ;     kann entfernt werden, wenn nicht benötigt
                                
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu NegValueFactor()    
      NegValueFactor()
      
    ; Power-Op in Token/Lexem?
      While Scanner::Token='^'        
        
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu NegValueFactor() 
        ; ====> FALSCH! NUR BEI SELBSTAUFRUF RICHTIG RECHTSASSOZIATIV !!! <==== 
        ; ====> siehe richtige Lösung weiter unten
          NegValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
          Code::_Exp()
      
      Wend            

    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu MulTerm  
      
  EndProcedure  
  Procedure Exponentiation()    ; *** richtig: rechts_assoziativ ***
    
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu NegValueFactor()    
      NegValueFactor()    
    
    ; Power-Op in Token/Lexem?                                
      If Scanner::Token='^'        
         
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Rechtsassoziativ !!! --> Selbstaufruf
        ; ====> BEI SELBSTAUFRUF RICHTIG RECHTSASSOZIATIV !!!         
          Exponentiation()
          
        ; Ausgabe des ASM-Codes des Operators
          Code::_Exp()
      
      EndIf      

    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu MulTerm()  
      
  EndProcedure  
  Procedure MulTerm()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu Exponentiation()    
      Exponentiation()
    
    ; Mul-Op in Token/Lexem?
      While Scanner::Token='*' Or Scanner::Token='/' Or Scanner::Token='%'
        
        ; Operator merken
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu Exponentiation()  
          Exponentiation()
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                
          Select operator
          Case '*'  : Code::_Mul()
          Case '/'  : Code::_Div()
          Case '%'  : Code::_Mod()          
          EndSelect
      
      Wend

    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu AddExpression()  
      
  EndProcedure
  Procedure AddExpression()
  
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu MulTerm()    
      MulTerm()    
    
    ; Add-Op in Token/Lexem?
      While Scanner::Token='+' Or Scanner::Token='-'
        
        ; Operator merken
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu MulTerm()  
          MulTerm()
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                
          Select operator
          Case '+'  : Code::_Add()
          Case '-'  : Code::_Sub()
          EndSelect
      
      Wend
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu Relation()  
      
  EndProcedure
  Procedure Relation()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu AddExpression()    
      AddExpression()    
    
    ; Relational-Op in Token/Lexem?
      While  Scanner::Token='<' Or Scanner::Token='>' Or Scanner::Token='='
      
        ; Operator merken, mehrteilige Operatoren erkennen
          If Scanner::Token='<' And Scanner::Look='='
                      operator='k' ; <k>leiner gleich <=
                      Scanner::GetToken()
          ElseIf Scanner::Token='>' And Scanner::Look='='
                      operator='g' ; <g>rößer gleich  >=
                      Scanner::GetToken()
          ElseIf Scanner::Token='<' And Scanner::Look='>'
                      operator='u' ; <u>ngleich <>
                      Scanner::GetToken()                      
          Else          
                      operator = Scanner::Token
          EndIf
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu AddExpression()  
          AddExpression()
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                
          Select operator
          Case '<'  : Code::_LowerThan()      ; <  
          Case 'k'  : Code::_LowerOrEqual()   ; <= 
          Case 'u'  : Code::_NotEqual()       ; <>
          Case '='  : Code::_Equal()          ; =
          Case 'g'  : Code::_GreaterOrEqual() ; >= 
          Case '>'  : Code::_GreaterThan()    ; >  
          EndSelect
      
      Wend
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu LogNot()  
      
  EndProcedure  
  Procedure LogNot()
  
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary not 
    
    ; Ist ein 'unary not' vor ValueFactor?                    
      If Scanner::Lexem = "NOT"

        ; vor Aufstieg nächstes Token holen
        ; d.i 'not' ODER ein Value
          Scanner::GetToken()  
            
        ; Selbstaufruf für 'not not not ...'                  
          LogNot()
            
        ; Ausgabe des ASM-Codes des Operators
          Code::_LogNot()              
             
      Else
      
        ; Aufstieg zu Relation()  
          Relation()
          
      EndIf    
      
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu BoolAnd()

  EndProcedure    
  Procedure BoolAnd()
  
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu LogNot()    
      LogNot()    
    
    ; BoolAnd-Op in Token/Lexem?
      While Scanner::Lexem ="AND"        
         
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu LogNot()
          LogNot()
          
        ; Ausgabe des ASM-Codes des Operators
          Code::_And()
      
      Wend
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu BoolOrXor()() 
      
  EndProcedure
  Procedure BoolOrXor()
    
    ; --> Einsprung von Statement()
    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu BoolAnd()    
      BoolAnd()    
    
    ; BoolOrXor()Xor()-Op in Token/Lexem?
      While Scanner::Lexem ="OR" Or Scanner::Lexem = "XOR"       

        ; Operator merken
          operator.s = Scanner::Lexem
         
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu BoolAnd()  
          BoolAnd()
          
        ; Ausgabe des ASM-Codes des Operators
          Select operator
          Case "OR"  : Code::_Or()
          Case "XOR" : Code::_Xor()
          EndSelect
      
      Wend
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Ende der Expression (Rücksprung zu Statement() über Expression())
      
  EndProcedure  
  Procedure Expression()
      BoolOrXor()
  EndProcedure   

; - Hilfsprozeduren ------------------------------------------------------------
; -
  Procedure SkipToken(token)
      If Scanner::Token<>token
            Scanner::Expected("'"+Chr(token)+"'") 
      Else      
            Scanner::GetToken()
      EndIf
  EndProcedure

EndModule

Parser::Compile("Source-Code.tc")
Viel Spaß mit dem Compiler von Kapitel 9.
LG Puretom


*** ENDE KAPITEL 9: CODE ***

DAS KANN MAN SCHON ERNSTER NEHMEN: BITTE UM BUGBERICHTE, FEEDBACK, LOB, ..., denn das war viel Arbeit
Zuletzt geändert von puretom am 05.10.2013 21:46, insgesamt 12-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

Es gibt etwas Neues zu sehen!

Ein nahezu vollständiger Matheparser steht zur Verfügung!

Bitte um Rückmeldungen!

LG Puretom
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 10: TEXT ***

ÄNDERUNGEN STEHE BEVOR!!!

NICHT VERGESSEN: VARIABLE NICHT DEKLARIER __ I N N E R H A L B ___ EINER EXPRESSION

*** ENDE KAPITEL 10: TEXT ***
Zuletzt geändert von puretom am 06.10.2013 17:15, insgesamt 25-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

reserviert code
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
votan
Beiträge: 3
Registriert: 14.12.2009 16:19

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von votan »

Kann zwar konstruktiv nichts beisteuern da das Projekt meine Fähigkeiten bei weitem übersteigt aber es ist einfach genial, mal einen so detailierten Einblick in den Compilerbau zu bekommen und davon zu lernen! Bitte weitermachen. :)
Nach oben
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

Lieber votan!

Danke für das Feedback!

@all
Ich werde ein wenig umbauen.
Vor allem möchte ich schon viel früher ein funktionierende kleine Skriptsprache Toy-C 0.8 (mit if und while) präsentieren können.

Ich habe nämlich selbst das Gefühl, dass schon zu viele Teile da sind, ohne dass man wirkliche Ergebnisse sieht.

Für die Interessierten:
Keine Angst, die jetzigen Teile sollen bleiben, aber NACH der ersten kleinen Sprache, damit man mal "Ergebnisse sieht". Die jetzigen Teile stellen dann die Erweiterung zu ToyC-0.9 oder was auch immer dar - sozusagen.

Ich hoffe, es interessiert sich noch irgendjemand dafür (SAGT MAL WAS!!!!)!
Ist viel Arbeit, macht aber Spaß, und vor allem ich lerne selbst viel dabei.

LG Puretom

P.S. In 3 Wochen habe ich Urlaub, da mache ich vielleicht wieder etwas mehr. Weiß noch nicht.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Nach oben
Antworten

Zurück zu „FAQ & Tutorials“