[Tutorial] Compiler und Virtual Machine

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

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 6: TEXT & CODE ***

6. Statements und Blocks: Die Struktur eines Programms



6.1. Der Plan


Steigen wir ein in die Programmierung eines Compilers für eine Hochsprache, nennen wir sie Toy-C (Spielzeug-C), der ASM-Code für eine Virtuelle Stack Machine erzeugt.
Diese Sprache wird sich an C anlehen, manche Konzepte dann aber wieder von Pure Basic und manche doch von C übernehmen. Sie ist unsere Erfindung und deshalb darf sie aussehen, wie wir wollen.

Wer wollte nicht schon immer eine eigene Programmiersprache erfinden, eine ganz persönliche?




6.2. Einleitende Worte zum Aufbau eines Programms

Ein Programm, jedes Programm, besteht aus Anweisungen (oder Befehlen).

Ein Statement ist in einer Programmiersprache eine Anweisung / ein Befehl, also z.B.

Code: Alles auswählen

while (x=2)
if (a=5) 
print(y)
x=3+a
int a
Pro Zeile haben wir hier je 1 Anweisung.

Eine Anweisung / ein Befehl besteht dann aus einem oder mehreren Token-Lexemen.

Für unsere Zwecke definiere ich vereinfacht, dass aus Sicht der Schleife in Compile() (das wird unsere Start-Prozedur sein), das Statement die kleinste Struktur ist.
Die atomare Struktur des Parsers ist also die genau 1 (!) Statement.


Die weiter unten folgende Prozedur Statement() wird die Aufgabe haben, Statements anhand reservierter Schlüsselwörter/Befehlswörter (reserved key words) zu erkennen.
Falls Sie mehr über Statements als solches (meine Darstellung ist grob vereinfachend) wissen wollen: http://de.wikipedia.org/wiki/Anweisung_(Programmierung)

Stellen wir uns also folgenden Source-Code vor, die Einrückung zeigt die Blockstruktur:

Code: Alles auswählen

if (a=3) 
   print(a)
Wenn a also 3 ist, dann wird das Print-Statement ausgeführt.

Was ist aber, wenn wir folgenden Source-Code haben?

Das hätten wir gemeint:

Code: Alles auswählen

if (a=3) 
   print("Die Zahl ist: ")
   print(a)
So versteht es (richtigerweise !) der Computer:

Code: Alles auswählen

if (a=3) 
   print("Die Zahl ist: ")
print(a)
Nur wenn a also 3 ist, dann wird "Die Zahl ist: " geprintet. Print(a) wird immer geprintet.

Wir wollten also einen Block von Statements bilden und haben das dem Compiler nicht mitgeteilt. Er hatte kein Erkennungszeichen.

In C ist das Erkennungszeichen für einen Block von Statements traditionell "{ ... }":

Code: Alles auswählen

if (a=3)
{ 
   print("Die Zahl ist: ")
   print(a)
}
Damit versteht der Compiler dasselbe, das wir auch meinen.

Wir setzen das programmtechnisch um, indem wir später eine Prozedur Block() einführen werden!




6.3. Start-Gerüst für den Parser des 6. Kapitels

Dieses Gerüst ist aus Gründen der Übersichtlichkeit nur für die Prozeduren des 6. Kapitels gedacht.
Es wird dann in den nächsten Kapiteln ausgebaut werden.
Natürlich brauchen wir dazu unseren lexikalischen Scanner vom vorigen Kapitel, binden Sie ihn ein!

Code: Alles auswählen

; ******************************************************************************
; *   PARSER (KAPITEL 6)
; *       mit eingebunden muss sein:
; *         1) Module Scanner
; ******************************************************************************
DeclareModule Scanner                            :EndDeclareModule       
Module Scanner                                   :EndModule               

; ******************************************************************************
; * Modul Parser
; ***
DeclareModule Parser
; - Public Declarations ---------------------------------------------------------
; -
  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 --------------------------------------------------------
; -
  Global Debug_BlockEbene        ; Debug-Zwecke, später löschen
  ;                        
  Declare Statement()            ; erkennt eine Anweisung und führt ihre Be-
                                 ; handlungsprozedur aus
  Declare Block()                ; behandelt Block von Statements
           
; - Start, Statement, Block -----------------------------------------------------
; -
  Procedure Compile(file_name.s)                 :EndProcedure
  Procedure Statement()                          :EndProcedure
  Procedure Block()                              :EndProcedure
  
EndModule

Parser::Compile("Source-Code.tc")




6.4. Compile()-Prozedur: Lesen des Token-Lexem-Stroms

Zunächst retten wir einmal unser Wissen vom Scanner und übertragen die Token-Lexem-Hol-Schleife (Was für ein Wort ;-) ) in eine neue Prozedur Compile(), die als Parameter den Dateinamen des Source-Files hat.
Es handelt sich dabei um die Schleife aus der Prozedur Scanner::Debug_TokenLexemStream0(), also die einfache Version ohne Behübschung, die wir ja nicht benötigen, weil den Parser z.B. #LF usw. nie erreichen. Die von mir durchgeführten leichten Veränderungen sind dem Modul-System und dem späteren Debuggen geschuldet.

Die Prozedur Compile() wird das Source-File kompilieren und eine Text-Datei in Toy-C-Assemblersprache anlegen, die denselben Namen wie das Source-File trägt, nur mit der Endung ".ta", was Toy-Assembler meint.

Code: Alles auswählen

  Procedure Compile(file_name.s)

    ; Open .ta-File
      CreateFile(1,GetFilePart(file_name, #PB_FileSystem_NoExtension)+".ta")
         
    ; Inits         
      Debug_BlockEbene = 0
  
    ; Starte Scanner (1. Token-Lexem liegt danach im Stream)
      Scanner::Start(file_name.s)
    
    ; so lange, bis Token = 0-Byte  <==== DIESER ABSCHNITT IST IM PRINZIP IST AUS Scanner::Debug_TokenLexemStream0() kopiert
      While ( Scanner::Token<>0 )
          Debug RSet(Str(Scanner::Token),3," ")+" | '"+Chr(Scanner::Token)+"'  | "+Space(4*Debug_BlockEbene)+Scanner::Lexem     
          Scanner::GetToken()
      Wend
      Debug "(außerhalb While-Schleife)"      

    ; Close .ta-File
      CloseFile(1) 
      
  EndProcedure
Die Variable Debug_BlockEbene soll Sie zunächst nicht weiter (be)kümmern, wir brauchen Sie etwas später zur besseren Debug-Anzeige.

Erzeugen wir uns noch schnell ein Source-File mit dem Namen "Source-Code.tc" und starten danach unser Werk:

Code: Alles auswählen

/* Variable wird deklariert */
    int Var_1
    Var_1 = 273   // in Var_1 wird 273 gespeichert 

/* Variable wird angezeigt */
    print(Var_1) // 273 wird in Console ausgegeben
Das Ergebnis im Debug-Fenster sollte sein:

Code: Alles auswählen

120 | 'x'  | INT            <=== TOKEN: NAME
120 | 'x'  | VAR_1          <=== TOKEN: NAME
120 | 'x'  | VAR_1          <=== TOKEN: NAME
 61 | '='  | =              <=== TOKEN: OTHER
 35 | '#'  | 273            <=== TOKEN: NUM
120 | 'x'  | PRINTI         <=== TOKEN: NAME
 40 | '('  | (              <=== TOKEN: OTHER
120 | 'x'  | VAR_1          <=== TOKEN: NAME
 41 | ')'  | )              <=== TOKEN: OTHER
(außerhalb While-Schleife)
Wir haben unseren Scanner vom Parser aus verfügbar gemacht, der Parser treibt den Scanner (um eine gängige Redewendung aus der englischen Compilerliteratur zu übernehmen). Der Scanner wird vom Parser aus "ferngesteuert", wenn man so will.




6.5. Ein Statement (Befehl, Anweisung)


6.5.1. Prozedur Compile() und Prozedur Statement()

Ändern wir unsere Prozedur Compile() zu:

Code: Alles auswählen

  Procedure Compile(file_name.s)

    ; Open .ta-File
      CreateFile(1,GetFilePart(file_name, #PB_FileSystem_NoExtension)+".ta")
         
    ; Inits         
      Debug_BlockEbene = 0
  
    ; Starte Scanner (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
Auch die Statement()-Prozedur bauen wir aus.
Die erste Version von Statement() füllen wir plump mit der Debug-Ausgabe und GetToken() und starten unser Programm, das Ergebnis im Debug-Fenster muss dasselbe wie beim vorigen Test sein. Außerdem sollte bereits vorhin ein leeres .ta-File angelegt worden sein, schauen Sie mal, ob es sich in Ihrem Projektordner befindet. (Und ja, in einer Release-Version sollte man CreateFile() testen auf Erfolg).

Code: Alles auswählen

  Procedure Statement()
      
     Debug RSet(Str(Scanner::Token),3," ")+" | '"+Chr(Scanner::Token)+"'  | "+Space(4*Debug_BlockEbene)+Scanner::Lexem     
     Scanner::GetToken()
      
  EndProcedure


6.5.2. Das Erkennen von Befehlswörtern in Statement()

Jetzt wird es ernst und das Vorspiel ist vorbei.

In der Einleitung (siehe Kapitel 6.2.) habe ich bereits angesprochen, dass ein Statement in einer Programmiersprache eine Anweisung / ein Befehl ist.

Die Prozedur Statement() hat die Aufgabe, Statements anhand reservierter Schlüsselwörter/Befehlswörter (reserved key words) zu erkennen und dann entsprechend zu handeln, wie wir bereits erkannt haben.

Das machen wir am besten mit einer Select-Case-Default-Konstruktion:
Wir suchen nach Toy-C-Schlüsselwörtern und springen in die entsprechende weiterführende Prozedur (die Do-Prozeduren hinter Case, siehe Code-Box). Diese weiterführende Prozedur bearbeitet dann je nach Befehl die Token-Lexem-Abfolge weiter.

Anmerkung: Eine schnellere Variante für später statt vielen Stringvergleichen wäre sicher eine Map, die einen entsprechenden Zahlencode zurückgibt. Dieser Zahlencode wird dann in der Select-Case-Default-Konstruktion (und hier wäre dann eine Sprungtabelle noch flotter) überprüft und nicht jeder einzelne Lexem-String.

Ich möchte zum Verständnis hier eine Version von Statement() vorstellen, die dem Aussehen näher kommt, wenn der Compiler bereits weiter fortgeschritten ist. Verwenden Sie sie bitte jetzt noch nicht:

Code: Alles auswählen

  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 "INT"     : Do_Int()
          Case "PRINT"   : Do_Print()
          Case "IF"      : Do_If()
          Case "WHILE"   : Do_While()
          ; ...
          ; ... weitere Statements
          ; ...
          ;  
          Default        : Do_Assignment()
         
      EndSelect
  
  EndProcedure
Die Idee von Statement ist also, die Befehlswörter zu erkennen und weiter zu bearbeiten. Wenn nichts erkannt wurde, dann vermutet Statement() eine Variablenzuweisung (Assignment) wie z.B. x=3. So weit der Plan für später.

Sehen wir uns jetzt an, wie wir mit Statement() beginnen wollen.

Die erste Version von Statement() :

Code: Alles auswählen

  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 "INT"                ; <=== HIER IST DER FEHLER
          ; ...
          ; ... weitere Statements
          ; ...
          ;  
          Default                   : Scanner::GetToken()
         
      EndSelect
  
  EndProcedure
In den Default-Zweig legen wir (zunächst für den Anfang) GetToken(), damit der Parser bei einem unbekannten Befehlswort dennoch einfach weitermacht.

Starten Sie den Compiler (wir haben immer noch den Source-Code von weiter oben)! Der Parser bleibt bei "INT" hängen. Warum?
Weil im Case-Teil zu "INT" kein nächstes Token-Lexem-Paar geholt wird.
In Token/Lexem bleibt also auf ewig "INT" und wir kommen nie wieder aus der Schleife. Sie sehen das sehr schön in der Debug-Ausgabe.

Das führt uns zu einer wichtigen Regel!
Wir müssen immer darauf achten, dass nach der Select-Case-Default-Konstruktion ein neues, sprich das nächste, Token-Lexem-Paar in den beiden Variablen Token und Lexem liegt.
Ergibt sich das durch den Parse-Vorgang nicht automatisch am Ende jeder Do-Prozedur (das sind die hinter "Case"), dann müssen wir eben dort mittels GetToken() oder dergleichen selbst dafür sorgen
(schon oft vergessen und viel geflucht deshalb).

Wenn Sie in den Case-Teil "Scanner::GetToken()" schreiben, dann ist alles wieder brauchbar und sollte wie vorhin aussehen. Ändern Sie die Zeile bitte entsprechend ab und testen Sie den Compiler:

Code: Alles auswählen

          Case "INT": Scanner::GetToken()



6.6. Ein Block von Statements

In Toy-C ist liegt dann ein Block vor, wenn er mit "{" geöffnet und wieder mit "}" geschlossen wird.
In diesem Block können von 1 (was man ev. eher selten macht) bis zu beliebig viele Statements und auch weitere Blöcke sein.
Blöcke können auch in Blöcken sein, man kann sie ineinander verschachteln.

Die Sprache C macht es dem Compiler/Parser-Programmierer sehr einfach, die Blockstruktur umzusetzen, d.h. diese Art Blöcke, die C verwendet, ist leicht zu parsen (leichter als die Blöcke von z.B. Pure Basic oder Lua. Vielleicht mache ich einen extra Anhang dazu, wie man eine PB-artige Blockstruktur parst). Auch Pascal-Blöcke sind genauso aufgebaut, ersetzt Pascal doch einfach die "{ ... }" durch die Wörter "Begin ... End".

Eine Beispiel in Toy-C:

Code: Alles auswählen

if(x>0)  
{                                
     if(x=1)  
     {
          print("Die Zahl ist ")
          print("1.")
     } 
     else if(x=2) 
     {
          print("Die Zahl ist ")
          print("2.")
     }
     else
     {
          print("Die Zahl ist weder 1 noch 2. ")
          print("Sie ist unerlaubt!")
     }
}            
else
{
     print("Die Zahl ist 0 oder ")
     print("kleiner als 0. ")
     print("Sie ist unerlaubt!")
}          
Zum Verständnis der äquivalente Pure-Basic-Code (bei geöffneter Console):

Code: Alles auswählen

If x>0   
     If x=1  
          Print("Die Zahl ist ")
          Print("1.")            
     ElseIf x=2  
          Print("Die Zahl ist ")
          Print("2.")            
     Else
          Print("Die Zahl ist weder 1 noch 2. ")
          Print("Sie ist unerlaubt!")
     EndIf
Else
     Print("Die Zahl ist 0 oder ")
     Print("kleiner als 0. ")
     Print("Sie ist unerlaubt!")      
EndIf
Zunächst müssen wir einmal dafür sorgen, dass ein Block überhaupt erkannt wird.

Wir erweitern Statement() zu:

Code: Alles auswählen

  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 "INT"    : Scanner::GetToken()      ; <=== DAS KANN AB JETZT ENTFERNT WERDEN 
          Case "{"      : Block()                  ; <=== HIER NEUERUNGEN 
          ; ... 
          ;  
          Default       : Scanner::GetToken()
         
     EndSelect
  
  EndProcedure  
Wenn also ein Lexem "{" ist, dann verzweigt der Parser in die Prozedur Block().

Die Zeile "Case "INT" ..." kann jetzt entfernt werden, weil jetzt ein anderer Case-Teil da ist und wir diese Zeile momentan nicht benötigen.

Beachten wir unbedingt, dass in der Mitte der Debug-Zeile die Variable Debug_BlockEbene eingebaut ist.
Wenn wir dann unser Werk testen, soll je nach Block-Ebene das Lexem um eine bestimmte Anzahl von Leerzeichen eingerückt werden, um gut erkennen zu können, ob die Blöcke korrekt betreten und wieder korrekt verlassen werden.
Damit ist sichergestellt, dass wir gut sehen, ob die Prozedur Block() richtig arbeitet.

Zunächst präsentiere ich eine Version von Block() ohne alle Debug-Werkzeuge, damit wir besser verstehen können, wie sie arbeitet.
Zum Testen des Parsers verwende ich dann aber die Version weiter unten.

Die Prozedur Block() ohne Debug-Werkzeuge:

Code: Alles auswählen

  Procedure Block()
   
    ; --> in Token/Lexem ist jetzt ({)   
   
    ; ueberlesen des ({)
      Scanner::GetToken()     

    ; solange kein (}) oder Source-Code-Ende
      While ( Scanner::Token<>'}' And Scanner::Token<>0 )
          Statement()      
      Wend                         

    ; prüfen, ob 0-Byte (=Source-Code-Ende)
    ; Ja? Fehler, Block nicht geschlossen mit (})
      If Scanner::Token=0: Scanner::Expected("'}'"):EndIf                                  
        
    ; ueberlesen des (})
      Scanner::GetToken()         

    ; --> in Token/Lexem ist jetzt das Token/Lexem nach (})
        
  EndProcedure
Der Ablauf von Block():
  • Statement() erkennt ein "{" und ruft Block() auf
  • In Token/Lexem ist immer noch "{" ---> GetToken() überspringt das
WHILE solange bis Token="}" oder bis Token=0-Byte
  • Token ruft wieder Statement() auf und in Statement() könnte wieder ein Block sein.
    Sollte in Statement() irgendwann wieder "{" sein, dann beginnt wieder eine neue Instanz von Block().
    Diese neue Instanz von Block() ruft wieder Statement() auf und in Statement() könnte wieder ein Block sein, und so weiter.
    Das ist Rekursion!
ENDWHILE
  • In Token/Lexem ist "}" ---> GetToken() überspringt das
    Das erklärt auch, warum unsere Debug-Anzeige das schließende "}" nicht anzeigt, denn es wird hier aufgegessen.
  • Token/Lexem steht auf dem Token/Lexem nach "}"
  • Block() endet und kehrt zurück zu Statement, das seinerseits zu Block() zurückkehren könnte und so weiter.

Legen wir uns einen neuen Source-Code an:

Code: Alles auswählen

aussen_davor_1
aussen_davor_2
{
   block_1a
   block_1b
   {
      block_2a
      block_2b
   }
   block_1c
   block_1d
}
aussen_danach_1
aussen_danach_2

Unsere rekursive Konstruktion Statement() -> Block () -> Statement() -> ... usw. ... sollte dieses File folgendermaßen durchlaufen:

Code: Alles auswählen

Statement: "aussen_davor_1"
Statement: "aussen_davor_2"
Statement: "{"                 --> Block() Ebene 1 -->     Statement: "block_1a"
                                                           Statement: "block_1b"      
                                                           Statement: "{"           --> Block() Ebene 2 -->    Statement: "block_2a"
                                                                                                               Statement: "block_2b"
                                                           Statement: "block_1c"  <--- Block() 2 verlassen --- While-Schleife sieht "}"
                                                           Statement: "block_1d"                                                 
Statement: "aussen_danach_1"  <--- Block() 1 verlassen --- While-Schleife sieht "}"
Statement: "aussen_danach_2"
Statement: 0-Token

Schauen wir, ob das stimmt!

Fügen wir die Block()-Prozedur mit allen Debug-Werkzeugen ein.

Die Prozedur Block() mit Debug-Werkzeugen:

Code: Alles auswählen

  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                         

    ; prüfen, ob 0-Byte (=Source-Code-Ende)
    ; Ja? Fehler, Block nicht geschlossen mit (})
      If Scanner::Token=0: Scanner::Expected("}"):EndIf                                  
        
    ; ueberlesen des (})
      Scanner::GetToken()         

    ; --> in Token/Lexem ist jetzt das Token/Lexem nach (})
    ; ------------------------------------------------------   
        
        
    ; Debug-Zwecke, später löschen
      Debug_BlockEbene-1              
        
  EndProcedure
Das eigentliche Block() befindet sich innerhalb der beiden horizontalen Linien, der Rest ist Debug und später zu streichen.

Starten Sie den Parser! Mein Debug-Fenster zeigt an (wie immer ohne meine Kommentare):

Code: Alles auswählen

120 | 'x'  | AUSSEN_DAVOR_1
120 | 'x'  | AUSSEN_DAVOR_2
123 | '{'  | {
120 | 'x'  |     BLOCK_1A
120 | 'x'  |     BLOCK_1B
123 | '{'  |     {
120 | 'x'  |         BLOCK_2A
120 | 'x'  |         BLOCK_2B         <=== das schließende "}" wurde von Block() gegessen
120 | 'x'  |     BLOCK_1C
120 | 'x'  |     BLOCK_1D             <=== das schließende "}" wurde von Block() gegessen
120 | 'x'  | AUSSEN_DANACH_1
120 | 'x'  | AUSSEN_DANACH_2
(außerhalb While-Schleife)
Alles funktioniert offenbar.
Die Blöcke werden korrekt erkannt, sie werden korrekt betreten und korrekt wieder verlassen.

Wichtig, nicht verwechseln:
Die Einrückungen im Debug-Fenster entstehen NICHT durch die Einrückungen im Source-Code, denn die entfernt der Scanner bereits.


Die Einrückungen im Debug-Fenster entstehen durch folgende Zeile mit der Variable Debug_BlockEbene in der Prozedur Statement():

Code: Alles auswählen

      Debug RSet(Str(Scanner::Token),3," ")+" | '"+Chr(Scanner::Token)+"'  | "+Space(4*Debug_BlockEbene)+Scanner::Lexem     
                                                                                       *****************
Die Prozedur Block() erhöht Debug_BlockEbene bei Eintritt und erniedrigt Debug_BlockEbene bei Verlassen, das führt zu jeweils mehr oder weniger Leerzeichen (Space) vor dem Lexem in der Debug-Anzeige:

Code: Alles auswählen

  Procedure Block()

    ; Debug-Zwecke, später löschen
      Debug_BlockEbene+1
      
      ... 
      
    ; Debug-Zwecke, später löschen
      Debug_BlockEbene-1
      
  EndProcedure
Die richtige Anzahl der Leerzeichen zeigt uns, die Blocklogik funktioniert.
Das 0-Token am Ende des Source-Codes wird auch berücksichtigt, sonst würden wir in der While-Schleife festhängen.




6.7. Der Gesamt-Code von Kapitel 6 (mit dem kompletten Scanner von Kapitel 4)

Code: Alles auswählen

; ******************************************************************************
; *   PARSER (KAPITEL 6)
; *       mit eingebunden muss sein:
; *         1) Module Scanner
; ******************************************************************************
DeclareModule Scanner       
; - Public Declarations ---------------------------------------------------------
; -  
      Global Look    ; Look Ahead Character
      Global Token   ; Token-Typ als Zahl
      Global Lexem.s ; Lexem = Token als String
     
    ; --- Start mit Aufruf dieser 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
      ;
      Declare Load(file_name.s)  ; lädt das ASCII-Source-File    
      ;      
      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
      ;
      Declare GetChar()          ; holt nächsten Character von *Source_Code   
			;
      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 - Prozeduren ----------------------------------------------------------
; -
  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
  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
  
; - 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 SkipWhite1()

    ; solange in Look ein White
      While IsWhite(Look)
      
          ; einfaches (/) als nicht-White im Stream belassen
            If Look='/': ProcedureReturn: EndIf
	    
	        ; nächsten Look laden
	          GetChar()
	          
      Wend
	    
  EndProcedure
	Procedure SkipLineComment()
      
      ; bis Zeilenende oder Ende des Source-Files (0-Byte)
        While Look<>#LF And Look<>0 
            GetChar()
        Wend 
        
      ; --> Look steht auf #LF 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 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

; ******************************************************************************
; * Modul Parser
; ***
DeclareModule Parser
; - Public Declarations ---------------------------------------------------------
; -
  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 --------------------------------------------------------
; -
  Global Debug_BlockEbene        ; Debug-Zwecke, später löschen
  ;                        
  Declare Statement()            ; erkennt eine Anweisung und führt ihre Be-
                                 ; handlungsprozedur aus
  Declare Block()                ; behandelt Block von Statements
           
; - 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 Scanner (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       : Scanner::GetToken()
         
      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                         

    ; prüfen, ob 0-Byte (=Source-Code-Ende)
    ; Ja? Fehler, Block nicht geschlossen mit (})
      If Scanner::Token=0: Scanner::Expected("'}'"):EndIf                                  
        
    ; ueberlesen des (})
      Scanner::GetToken()         

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

Parser::Compile("Source-Code.tc")

*** ENDE KAPITEL 6: TEXT & CODE ***
Zuletzt geändert von puretom am 06.10.2013 21:28, insgesamt 7-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
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 7: TEXT ***

7. Parsen und Kompilieren mathematischer Ausdrücke (Expressions)



7.1. Vorbemerkungen zur Präzedenz von Operatoren

Ein mathematischer Parser löst mathematische Ausdrücke (Expression) auf, er ist der schwierigste Teil eines Compilers und auch dessen Herzstück. Einmal einen geschrieben und verstanden, kann man das immer wieder. Versprochen!

Anmerkung:
Ich werde im laufenden Text immer die Begriffe Compiler und Parser wechselnd und synonym verwenden. Diese Perspektive stimmt, denn wenn wir unseren Parser aufrufen, dann kompilieren wir bereits Source-Code in VM-ASM.

Zurück zum Expression Parser:
Er gibt also den kompilierten ASM-Code eines mathematischen Ausdrucks in der richtigen Reihenfolge aus, und das muss nicht unbedingt in der Reihenfolge sein, wie die Befehle der Reihe nach im Source-Code stehen.

Man nennt diese Tatsache, dass manche Operatoren zuerst oder zuletzt ausgewertet werden, Operatorrangfolge, -wertigkeit, -priorität oder -präzedenz (häufig begegnet man hier dem englischen Ausdruck precedence).


Der Parser weiß um die Regel: Punkt vor Strich:
  • 5+3*2 = 11 und nicht 16
  • Der Parser wertet zuerst 3*2=6 aus.
  • Dann rechnet er 5+6=11.
  • Er hat sich also eine geistige Klammer vorgestellt: 5+(3*2)
  • Hier in unserem Beispiel hat "*" eine höhere Präzedenz/Wertigkeit als "+".

Der Parser weiß auch um die Regel: Klammern zuerst:
  • Klammerausdrücke haben also eine höhere Präzedenz.

Es gibt Präzedenzregeln, die sind unstrittig.
Dann aber gibt es Operatoren, da gibt es von Programmiersprache zu Programmiersprache grobe Unterschiede, welche Operatoren zuerst ausgewertet werden.

Ich möchte hier auf eine 2 Tabellen mit Präzedenzebenen verweisen:.
Keine der beiden ist richtiger oder falscher als die andere, d.h. vieles ist einfach Geschmackssache.

Und wir können uns unsere Präzedenztabelle selbst basteln, wie wir wollen.
Wir werden diese Präzedenzebenen einfach über die Reihenfolge der Prozeduren, die die einzelnen Operatoren bearbeiten, erzeugen. Noch nicht klar? Ich will damit nur sagen, dass die Sache eigentlich recht einfach zu programmieren ist, wenn man einmal gelernt hat wie (von selbst hätte ich das allerdings nie entdeckt ;-), vielen Dank Mr. Jack Crenshaw).

Nur manche Regeln muss man wirklich immer einhalten und daran halten sich beide, C und Pascal, selbstverständlich, zum Beispiel:
  • Klammerausdrücke
  • Punkt vor Strich
Zum Abschluss verlinke ich eine besonders übersichtliche Präzedenztabelle mit verschiedenen Programmiersprachen im Vergleich (unbedingt ansehen): http://montcs.bloomu.edu/~bobmon/Inform ... scal.shtml


7.2. Das Gerüst des Expression Parsers

Hier das Gerüst des Mathe-Parsers, den wir in den nächsten Seiten entwickeln werden.
Eingebunden muss das Modul Scanner sein und vorhanden alle Prozeduren, die wir bis jetzt bereits haben.

Achtung!
Kopieren Sie bitte den den bereits entwickelten Parser und fügen Sie alle neuen Dingen hinzu.
Oder: Übernehmen Sie dieses Gerüst und füllen Sie alle Prozeduren mit denen, die wir bereits erarbeitet haben.
Tatsache ist, wir benötigen die bereits vorhandene Version mit Block() und Statement() usw. und erweitern diese.

Code: Alles auswählen

; ******************************************************************************
; *   PARSER (KAPITEL 7)
; *       mit eingebunden muss sein:
; *         1) Module Scanner
; ******************************************************************************
DeclareModule Scanner                            :EndDeclareModule       
Module Scanner                                   :EndModule               

; ******************************************************************************
; * Modul Parser
; ***
DeclareModule Parser
; - Public Declarations ---------------------------------------------------------
; -
  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 --------------------------------------------------------
; -
  Global Debug_BlockEbene        ; Debug-Zwecke, später löschen
  ;                        
  Declare Statement()            ; erkennt eine Anweisung und führt ihre Be-
                                 ; handlungsprozedur aus
  Declare Block()                ; behandelt Block von Statements
  ;
  Declare ValueFactor()          ; holt einen Operanden-Wert
  Declare MulTerm()              ; bearbeitet mul-Ops: *, /
  Declare AddExpression()        ; bearbeitet add-Ops: +, -
  Declare Expression()           ; mathematischer Expression Parser 3+4*(4+3)
  
; - Start, Statement, Block -----------------------------------------------------
; -
  Procedure Compile(file_name.s)                 :EndProcedure
  Procedure Statement()                          :EndProcedure
  Procedure Block()                              :EndProcedure

; - Mathematischer Parser--------------------------------------------------------
; -
  Procedure ValueFactor()                        :EndProcedure
  Procedure MulTerm()                            :EndProcedure
  Procedure AddExpression()                      :EndProcedure
  Procedure Expression()                         :EndProcedure

EndModule

Parser::Compile("Expr_Test01.tc")


7.3. Parsen eines Operanden: ValueFactor()

Wir beginnen damit, einen (genau 1) Operanden zu parsen.

Genauer gesagt:
Der Wert eines Operanden (deshalb Value = Wert) wird ermittelt und auf den Operanden-Stack gelegt (gepusht).

Um die Zusammenhänge zwischen den Ebenen besser darstellen zu können, verwende ich die so genannte Backus-Naur-Form (BNF bzw. EBNF: http://de.wikipedia.org/wiki/Backus-Naur-Form, http://de.wikipedia.org/wiki/Erweiterte ... -Naur-Form)
Mit dieser Darstellung lässt sich die Grammatik des Toy-C-Expression-Parsers sehr schön beschreiben. Und das Beste ist, BNF ist über weite Strecken hinweg selbserklärend (zumindest habe ich das so empfunden).

Eine sehr schöne Darstellung eines Expression Parsers in EBNF finden Sie hier (unbedingt anschauen!): http://karmin.ch/ebnf/examples

Nun, was ein Num und ein Name ist, das wissen wir, das beschreibe ich nicht mit EBNF, doch was ist ein ValueFactor (Wert)? Fürs Erste ist das (werden wir später erweitern) Folgendes:

Code: Alles auswählen

ValueFactor  =  Num | Name ;      <=== ein gültiger Factor kann Num oder Name sein
Expression   =  ValueFactor ;     <=== in Expression() wir ValueFactor() aufgerufen
Ich denke, jeder hat erkannt, dass "|" ein Oder ist.

Anmerkung:
In den gängigen Darstellungen wird diese Ebene als Factor bezeichnet. Da ich diese Bezeichnung wenig assoziativ finde und sie in meinen Parsern auch nicht verwendet wird, habe ich mich zu einem Kompromiss entschlossen, damit ich Ihnen keine zu großen Abweichungen von der gängigen Praxis lerne. Das Ergebnis sehen Sie an allen Bezeichnungen.


Zunächst ändern wir die Prozedur Statement(), die bei neuen Befehlen immer als Erste geändert werden muss. Ich gebe nur die Select-Konstruktion wieder:

Code: Alles auswählen

    ; nach Statements/Befehlen suchen
      Select Scanner::Lexem
          
          Case "INT"    : Scanner::GetToken() 
          Case "{"      : Block()
          Default       : Expression()
         
     EndSelect
Die Prozedur Expression() lassen wir zunächst einfach auf ValueFactor() zeigen (wie die EBNF-Darstellung etwas weiter oben bereits zeigt):

Code: Alles auswählen

  Procedure Expression()
      ValueFactor()
  EndProcedure  
Diese Prozedur werden wir mehrfach ändern, indem wir ValueFactor() austauschen.

Die Prozedur ValueFactor() bearbeitet eine Num oder einen Name:

Code: Alles auswählen

  Procedure ValueFactor()
  
    ; --> Token/Lexem steht auf Value
    
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token
      Case '#'  : WriteString(1,"push Const  " + Scanner::Lexem + #CRLF$)
      Case 'x'  : WriteString(1,"push Global " + Scanner::Lexem + #CRLF$)
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect
    
    ; holt nächstes Token (=Operator)
      Scanner::GetToken()
    
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator

  EndProcedure
Ich möchte kurz der Aufbau von ValueFactor() analysieren:
  • In Statement() erkennt die Case-Konstruktion, dass kein bekanntes Befehlswort vorliegt und vermutet, es ist eine Expression(), und verzweigt dorthin. Expression() ruft dann unser Value() auf:
  • Bei Eintritt: in Token/Lexem liegt eben der gesuchte ValueFactor()
  • Token wird jetzt untersucht, ob es Num oder Name ist:
    Je nachdem wird ein Pseudo-Code (der aber dem späteren bereits recht ähnlich ist) erzeugt.
    • '#': push Const <Num> legt oben auf den Operandenstack den Wert von <Num>
    • 'x': push Global <Name> legt oben auf den Operandenstack den Wert der globalen Variable <Name>
    • Default: Fehlerbehandlung ist auch bereits eingebaut.
    Der ASM-Pseudo-Code wird in die .ta-Datei geschrieben.
  • GetToken() holt nächstes Token/Lexem
  • Bei Austritt: in Token/Lexem liegt Token/Lexem exakt nach Value bereit.
Zum Testen legen wir uns ein Source-File mit dem Namen "Expr_Test01.tc" an. Dieses werde ich aber laufend verändern und nicht jedesmal ein neues anlegen, wenn wir den math. Ausdruck leicht verändern.

Code: Alles auswählen

543
x1
98
Prozentanteil_Nr_23
Starten Sie den Parser. In der .ta-Datei sollten Sie Folgendes finden:

Code: Alles auswählen

push Const  543
push Global X1
push Const  98
push Global PROZENTANTEIL_NR_23
Wir haben zum ersten Mal etwas geparst und sogar in ASM-Code kompilert!



7.4. Parsen von Addition und Subtraktion: AddExpression()


7.4.1. Einfachste Ausdrücke mit maximal 2 Operanden und einem Operator

Die nächste Ebene, oft bereits als erste Stufe direkt in der Prozedur Expression() zu finden, nenne ich AddExpression(), was über ihren Inhalt aussagt, dass add-Operatoren (+,-) mit ihr abgehandelt werden.

Tauschen Sie in Expression() die Prozedur ValueFactor() gegen AddExpression() aus!

Schauen wir uns die EBNF unseres Mathe-Parsers an:

Code: Alles auswählen

ValueFactor    =  Num | Name
AddExpression  =  ValueFactor [ ("+" | "-") ValueFactor ] ;   <=== [ ... ] ist optional: keinmal oder 1-mal
Expression     =  AddExpression ;                             <=== Expression() ruft AddExpression() auf (Zeile austauschen!)
Zu beachten ist, dass alles, was innerhalb der eckigen Klammern ([ ... ]) steht, keinmal oder exakt 1-mal vorkommen darf, aber nicht mehrmals (siehe { ... } weiter unten).

Die Prozedur AddExpression(), sie sollte exakt dem EBNF von oben entsprechen und ist somit in der Code-Box oben bereits erläutert worden:

Code: Alles auswählen

  Procedure AddExpression()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu ValueFactor()    
      ValueFactor()    
    
    ; add-Op in Token/Lexem?
      If Scanner::Token='+' Or Scanner::Token='-'
        
        ; Operator merken
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu ValueFactor()  
          ValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
          Select operator
          Case '+'  : WriteString(1,"add"+#CRLF$)
          Case '-'  : WriteString(1,"sub"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          EndSelect
      
      EndIf
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
      
  EndProcedure
Man muss hier peinlichst darauf achten, dass immer das passende Token/Lexem geladen ist, sonst kommt der Parser aus dem Tritt, also aufpassen, wenn Sie solche Prozeduren entwerfen.

Starten Sie den Parser mit folgendem Source-Code (in "Expr_Test01.tc" austauschen und speichern):

Code: Alles auswählen

543 + ping
XXXXXXXXXX
x1-pong
XXXXXXXXXX
98
XXXXXXXXXX
Prozentanteil_Nr_23 + Kunde
Bitte wundern Sie sich nicht über die Zeilen mit "XXXXXXXX". Der Compiler lädt sie als normale 'x'-Tokens und pusht sie korrekterweise als "Global" auf den Stack. Sie dienen nur dazu, dass Sie besser sehen, wo die eine Rechnung endet und die nächste beginnt.

Im .ta-File sollte sein:

Code: Alles auswählen

push Const  543                         
push Global PING                 
add                             <=== beide gepusht und dann addiert, Zuweisungen wie a=543+ping werden möglich
push Global XXXXXXXXXX          <--- (oben erwähntes Trennzeichen)
push Global X1
push Global PONG
sub
push Global XXXXXXXXXX
push Const  98                  <=== 98 wir einfach nur gepusht, das ermöglicht später Zuweisungen wie x=98
push Global XXXXXXXXXX
push Global PROZENTANTEIL_NR_23 
push Global KUNDE
add
Interessant ist auch die Debug-Ausgabe:

Code: Alles auswählen

 35 | '#'  | 543
120 | 'x'  | X1
 35 | '#'  | 98
120 | 'x'  | PROZENTANTEIL_NR_23
(außerhalb While-Schleife)
Hier sieht man deutlich, wann in die Prozedur Statement() zurückgekehrt wird, denn nur dort findet ja unsere Ausgabe statt. Alles was verschluckt wird, ist woanders als in Statement() (also z.B. in ValueFactor() oder AddExpression() usw.) verwendet und mit z.B. GetToken() übersprungen worden. Das kann hier nicht auftauchen.


7.4.2. Einfache Ausdrücke mit beliebiger Anzahl von Operatoren

Die Änderung wird von einer bloß geringfügigen Änderung der EBNF unseres Mathe-Parsers ermöglicht:

Code: Alles auswählen

ValueFactor    =  Num | Name ;
AddExpression  =  ValueFactor { ("+" | "-") ValueFactor } ;  <=== { ... } ist optional: keinmal oder beliebig oft
Expression     =  AddExpression ;                            
Zu beachten ist, dass alles, was innerhalb der geschweiften Klammern ({ ... }) steht, beliebig oft, jedoch auch keinmal vorkommen kann.
Die eckigen Klammern ([ ... ]) erlaubten nur ein 1-maliges oder keinmaliges Vorkommen, aber KEIN mehrmaliges.

Mehrfaches Vorkommen wird in Pure Basic mit einer Schleife umgesetzt, wieder sehen wir sehr schön, wie die EBNF direkt zu einer Umsetzung in PB-Code führt.

Die erweiterte Prozedur AddExpression():

Code: Alles auswählen

  Procedure AddExpression()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu ValueFactor()    
      ValueFactor()    
    
    ; add-Op in Token/Lexem?
      While Scanner::Token='+' Or Scanner::Token='-'      ;<=== "IF" EINFACH MIT "WHILE" AUSGETAUSCHT
        
        ; Operator merken
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu ValueFactor()  
          ValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
          Select operator
          Case '+'  : WriteString(1,"add"+#CRLF$)
          Case '-'  : WriteString(1,"sub"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          EndSelect
      
      Wend                                                ;<=== "ENDIF" EINFACH MIT "WEND" AUSGETAUSCHT
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value     
      
  EndProcedure
Beachten Sie meine Kommentare "<===". Die Veränderungen erklären sich selbst.

Testen wir folgenden Source-Code:

Code: Alles auswählen

543 + ping + pong - 2
XXXXXXXXXX
x1+44
XXXXXXXXXX
98
Der Stack-Machine-ASM-Code im .ta-File sollte so aussehen:

Code: Alles auswählen

push Const  543
push Global PING
add
push Global PONG
add
push Const  2
sub
push Global XXXXXXXXXX
push Global X1
push Const  44
add
push Global XXXXXXXXXX
push Const  98
Der "Kettenausdruck", der einfache Ausdruck und der einfache Value funktionieren.



7.5. Parsen von Multiplikation, Division, Modulo: MulTerm()

Eine Änderung der EBNF unseres Mathe-Parsers zeigt die Ebene, in der wir MulTerm() einfügen:

Code: Alles auswählen

ValueFactor    =  Num | Name ;
MulTerm        =  ValueFactor { ("*" | "/" | "%") ValueFactor } ;
AddExpression  =  MulTerm { ("+" | "-") MulTerm } ; 
Expression     =  AddExpression ;                           
Die Prozedur MulTerm() ist nahezu identisch mit AddExpression().
Ich drucke hier absichtlich alle 3 Ebenen ab, denn wir wollen die Parse-Technik anschließend analysieren:

Code: Alles auswählen

  Procedure ValueFactor()
  
    ; --> Token/Lexem steht auf Value
    
    ; je Token-Art: Ausgabe des Values als ASM-Code               < VALUE PUSHEN >
      Select Scanner::Token
      Case '#'  : WriteString(1,"push Const  " + Scanner::Lexem + #CRLF$)
      Case 'x'  : WriteString(1,"push Global " + Scanner::Lexem + #CRLF$)
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect
    
    ; holt nächstes Token (Operator)
      Scanner::GetToken()
    
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu MulTerm()                           <=== vvv ABSTIEG AUF NIEDRIGERE EBENE
  
  EndProcedure

Code: Alles auswählen

  Procedure MulTerm()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu ValueFactor()                          
      ValueFactor()                                      ;<=== ^^^ AUFSTIEG NÄCHSTHÖHERE EBENE
                                                         ;         (1. VALUE)
    ; mul-Op in Token/Lexem?
      While Scanner::Token='*' Or Scanner::Token='/'  Or Scanner::Token='%'
        
        ; Operator merken                                         < OPERATOR MERKEN >
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu ValueFactor()                      
          ValueFactor()                                  ;<=== ^^^ AUFSTIEG NÄCHSTHÖHERE EBENE
                                                         ;         (2. VALUE)
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                                  < OPERATOR AUSGEBEN >
          Select operator
          Case '*'  : WriteString(1,"mul"+#CRLF$)
          Case '/'  : WriteString(1,"div"+#CRLF$)
          Case '%'  : WriteString(1,"mod"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          EndSelect
      
      Wend
          
    ; --> in Token/Lexem ist Token/Lexem nach dem Operator ODER
    ; --> in Token/Lexem ist Token/Lexem nach dem Value  
    ; --> Abstieg zu AddExpression()                      <=== vvv ABSTIEG AUF NIEDRIGERE EBENE
      
  EndProcedure

Code: Alles auswählen

  Procedure AddExpression()

    ; --> Einsprung von Statement()                       <===     EIN-SPRUNG VON STATEMENT
    ; --> Token/Lexem steht auf Value                              ´´´´´´´´´´´´´´´´´´´´´´´´
      
    ; Aufstieg zu MulTerm()    
      MulTerm()                                          ;<=== ^^^ AUFSTIEG NÄCHSTHÖHERE EBENE
    
    ; add-Op in Token/Lexem?
      While Scanner::Token='+' Or Scanner::Token='-'
        
        ; Operator merken                                         < OPERATOR MERKEN >
          operator = Scanner::Token
          
        ; vor Aufstieg nächstes Token (=Value) holen
          Scanner::GetToken()

        ; Aufstieg zu MulTerm()  
          MulTerm()                                      ;<=== ^^^ AUFSTIEG NÄCHSTHÖHERE EBENE
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                                  < OPERATOR AUSGEBEN >
          Select operator
          Case '+'  : WriteString(1,"add"+#CRLF$)
          Case '-'  : WriteString(1,"sub"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          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())    
    ;                                                     <===     RÜCK-SPRUNG ZU STATEMENT
    ;                                                              ^^^^^^^^^^^^^^^^^^^^^^^^
  EndProcedure
Testen Sie Ihren Parser mit folgendem Source-Code:

Code: Alles auswählen

5+2*3
Im .ta-File müssten Sie das finden:

Code: Alles auswählen

push Const  5
push Const  2
push Const  3
mul
add

7.6. Wie funktionert der mathematische Parser

Machen wir an dieser Stelle einen kurzen Zwischenstopp, um uns zu überlegen, wie unser Parser eigentlich arbeitet.

Unser einfacher mathematischer Parser ist (Klammern kommen später) fürs Erste mal fertig.
Er kann 2 Präzedenz-Ebenen unterscheiden, nämlich mul-Operatoren (höhere Präzedenz) und add-Operatoren (niedrigere Präzedenz).

Die große Frage ist, was tut der Mathe-Parser da eigentlich, wie funktioniert er?



7.6.1. Beispiel 1: Höchste Ebene 1-mal erreicht

Ich versuche mittels einer Grafik folgende Rechnung darzustellen, sie sollten auch in den Prozeduren des vorigen Kapitels mitschauen bzw. die Grafik weiter unten verwenden:

Code: Alles auswählen

   5 + 3*2        <=== 3*2 = 6 --> 5 + 6 = 11
                  <=== zuerst 3*2 berechnen, dessen Ergebnis 6 addieren wir mit 5
1. Schritt: Aufstieg, bis das Ende der höchsten Ebene erreicht ist (Values pushen und Operanden merken).
Das ist, wenn in MulTerm() der 2. Value geholt und gepusht wurde.

Code: Alles auswählen

ValueFactor    =    Num ====> "push Const 5"   Num ====> "push Const 3"     Num ====> "push Const 2" (ENDE DES AUFSTIEGS)
                       ^         |               ^             |              ^          (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                       | (5)     | kein MulOp?   | (3)         | (* gemerkt)  | (2)
                       |         | weiter        |             v              |
MulTerm        =  ValueFactor  ? abwärts     ValueFactor { ("*" | "/") ValueFactor } 
                       ^         |               |
                       | (5)     | (+ gemerkt)   | (3)
                       |         v               |
AddExpression  =  MulTerm  { ("+" | "-") MulTerm }    
  ---------------------^  
2. Schritt: Abstieg (gemerkte Operanden ausgeben).

Code: Alles auswählen

ValueFactor    =                                                           (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                                                                              |       
                                                                 (* gemerkt)  |
                                                                    "mul"     v
MulTerm        =                               /<---------------------------/
                                     "add"       |
                                   (+ gemerkt)   v
  <----------------------------------------------/
AddExpression  =  MulTerm  { ("+" | "-") MulTerm }                               
Im .ta-File müssten Sie das finden.
Schauen sie sich Aufstieg und Abstieg an, alles wird genau in dieser Reihenfolge ausgegeben:

Code: Alles auswählen

push Const  5
push Const  3
push Const  2
mul
add

7.6.2. Beispiel 2: Höchste Ebene 2-mal erreicht

Versuchen wir folgende Rechnung:

Code: Alles auswählen

   10*2 + 50/2        <=== 20 + 25 = 45
1. Schritt: Aufstieg, bis das Ende der höchsten Ebene erreicht ist (Values pushen und Operanden merken).
Das ist, wenn in MulTerm() der 2. Value geholt und gepusht wurde.

Code: Alles auswählen

ValueFactor    =    Num ====> "push Const 10"   Num ====> "push Const 2" (ENDE DES AUFSTIEGS)
                       ^            |              ^         (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                       | (10)       | (* gemerkt)  | (2)
                       |            v              |
MulTerm        =  ValueFactor { ("*" | "/") ValueFactor }         
                       ^
                       | (10)
                       |
AddExpression  =  MulTerm { ("+" | "-") MulTerm }   
  ---------------------^                            
2. Schritt: Abstieg (gemerkte Operanden ausgeben).

Code: Alles auswählen

ValueFactor    =                                (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                                                   |              
                                      (* gemerkt)  |    
                                         "mul"     v
MulTerm        =              /<-----------------/        
                                |
                                | 
                                v
AddExpression  =  MulTerm { ("+" | "-") MulTerm }   
1. Schritt: ERNEUTER Aufstieg, bis WIEDER das Ende der höchsten Ebene erreicht ist (Values pushen und Operanden merken).
Das ist, wenn in MulTerm() der 2. Value geholt und gepusht wurde.

Code: Alles auswählen

ValueFactor    =                            Num ====> "push Const 50"    Num ====> "push Const 2" (ENDE DES AUFSTIEGS)
                                               ^                   |        ^         (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                                               | (50)  (/ gemerkt) |        | (2)
                                               |                   v        |
MulTerm        =                        ValueFactor    { ("*" | "/") ValueFactor }      
                                .              ^
                                | (+ gemerkt)  | (50)
                                v              |
AddExpression  =  MulTerm { ("+" | "-") MulTerm }   
2. Schritt: ERNEUTER Abstieg (gemerkte Operanden ausgeben).

Code: Alles auswählen

ValueFactor    =                                                         (HÖCHSTE EBENE MIT 2. VALUE ERREICHT)
                                                                            |         
                                                       (/ gemerkt)          |    
                                                          "div"             v
MulTerm        =                             /<---------------------------/      
                                    "add"      |
                                  (+ gemerkt)  v     
  <--------------------------------------------/
AddExpression  =  MulTerm { ("+" | "-") MulTerm }   
Im .ta-File müssten Sie das finden
Schauen sie sich Aufstieg und Abstieg an, alles wird genau in dieser Reihenfolge ausgegeben:

Code: Alles auswählen

push Const  10
push Const  2
mul
push Const  50
push Const  2
div
add
Fahren Sie die Grafiken mit dem Finger auf den Pfeilen nach und notieren Sie auf einem Zettel der Reihe nach die Texte, die Sie in " ... " finden.
Ihre Notizen sollten den Ausgaben des Compilers in den .ta-Files gleichen.
Es zahlt sich auch aus, Rechnungen mit den PB-Prozeduren vor Augen händisch auf dem Zettel nachzustellen, also Computer zu spielen.
Das habe ich alles gemacht und dann habe ich das Prinzip verstanden.
Und Sie sollten das Prinzip unbedingt verstanden haben, denn wir werden im Laufe der Toy-C-Entwicklung nämlich weitere Operanden hinzufügen .

Am Ende biete ich noch eine Grafik, mit der ich versuche, den Programmlauf einer Rechnung darzustellen.
Außerdem sieht man auch die Schritte, die die Stack Machine bei der Bearbeitung durchführt:

Bild
http://abload.de/img/mathe_erklrungkse0s.png
(Bitte schnell speichern, wen es interessiert, ich weiß nicht, wie lange die Grafik auf "abload" verfügbar bleibt)



7.6.3. Zusammenfassende Erklärung mit 2 expliziten Stacks

Erinnern wir uns und fassen wir zusammen:
Durch lokale Variablen hat jede aufgerufene Instanz einer Prozedur eigene Werte und eigene gemerkte Operatoren.
Und weil die Prozeduren nacheinander aufgerufen werden, entsteht automatisch ein Stack, der, wenn die Aufrufkette rückwärts läuft nach "EndProcedure", logischerweise auch rückwärts abgearbeitet wird. Das geschieht immer dann, wenn die höchste nicht unäre (siehe weiter unten) Operatoren-Präzedenzebene (ab da läuft es rückwärts) erreicht worden ist, d.i. von uns definiert derzeit "*" und jeweils immer die letzte Prozedur vor ValueFactor().


Dadurch entsteht implizit durch die Bauweise der Prozeduren eine Struktur mit 2 Stacks:
  • ein Stack mit den gemerkten Operatoren (lokale Variable operator in den Prozeduren)
  • ein Stack mit den Operanden (die "push"-Zeilen in ValueFactor())

Ich möchte jetzt - Varanese folgend - die beiden Stacks explizit mit einer Rechnung darstellen. Wie gesagt, in den Prozeduren entsteht das durch Aufrufreihenfolge vor- wie rückwärtslaufend automatisch/implizit beim Programmlauf:

Die Angaberechnung:

Code: Alles auswählen

1+2*3    // sollte 7 ergeben
  • Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator     
    
                         +---+
                         + 1 +
     +---+               +---+
    
                         push Const 1
     
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator      
    
     +---+               +---+
     + + +               + 1 +
     +---+               +---+
    
    gemerkt +            push Const 1  
     
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator       
    
                         +---+
                         + 2 +
     +---+               +---+
     + + +               + 1 +
     +---+               +---+
     
    gemerkt +            push Const 1  
                         push Const 2
                         
    -  Ist "+" die höchste nicht unäre Präzedenzebene?
    => Nein! Also weitermachen!
     
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator     
                             
     +---+               +---+
     + * +               + 2 +
     +---+               +---+
     + + +               + 1 +
     +---+               +---+
     
    gemerkt +            push Const 1  
    gemerkt *            push Const 2
     
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator     
                             
                         +---+
                         + 3 +
     +---+               +---+
     + * +               + 2 +
     +---+               +---+
     + + +               + 1 +
     +---+               +---+
    
    gemerkt +            push Const 1  
    gemerkt *            push Const 2
                         push Const 3                     
                         
    -  Beide mit "*" verbundenen Operatoren sind jetzt am Stack.
    -  Mit "*" ist höchste nicht unäre Präzedenzebene erreicht.
    => Es geht im Stapel (und in den Prozeduren) ab jetzt rückwärts.
    
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator     
    
                         +---+
                         + 3 +
     +---+   .---------  +---+
     + * +   |           + 2 +
     +---+   v           +---+
     + + +               + 1 +
     +---+               +---+
    
    gemerkt +            push Const 1  
    gemerkt *            push Const 2
                         push Const 3
                         mul
                         
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator                                
                              
                         +---+
                         + 6 +
     +---+   .---------  +---+
     + + +   |           + 1 +
     +---+   v           +---+
    
    gemerkt +            push Const 1  
    gemerkt *            push Const 2
                         push Const 3
                         mul
                         add
                         
    

    Code: Alles auswählen

     lokale
    Variable      "push" in ValueFactor()
    operator                              
                                                      
                         +---+
                         + 7 +
     +---+               +---+
    
    gemerkt +            push Const 1  
    gemerkt *            push Const 2
                         push Const 3
                         mul
                         add
                         
    
Man könnte also auch einen Mathe-Parser bauen, der genau mit solchen explizit vorandenen Stacks arbeitet und das hat man vor Zeiten der rekursiven Prozeduren mit lokalen Variblen auch gemacht, ist jetzt aber nicht mehr notwendig.



7.7. Klammerausdrücke

Klammerausdrücke sind besonders leicht zu realisieren.
In einem Klammerausdruck liegt wieder eine vollständige Expression.
Wir rufen in ValueFactor() also enfach Expression() auf, wenn wir eine "(" sehen, mehr müssen wir nicht tun.

Dazu erweitern wir unser EBNF folgendermaßen:

Code: Alles auswählen

ValueFactor    =  Num | Name | "(" Expression ")" ;       <==== ÄNDERUNG HIER
MulTerm        =  ValueFactor { ("*" | "/" | "%") ValueFactor } ;
AddExpression  =  MulTerm { ("+" | "-") MulTerm } ;
Expression     =  AddExpression ;                   
Die Änderung in ValueFactor() umfasst 2 (!!!) Programm-Zeilen, und das, obwohl ich früher dachte, das sei kompliziert zu implementieren:

Code: Alles auswählen

  Procedure ValueFactor()
  
    ; --> Token/Lexem steht auf Value
    
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token
      Case '#'  : WriteString(1,"push Const  " + Scanner::Lexem + #CRLF$)
      Case 'x'  : WriteString(1,"push Global " + Scanner::Lexem + #CRLF$)
      Case '('  : Scanner::GetToken()  ; überspringe "("                     <==== ÄNDERUNG HIER
                  Expression()         ; ")" wird weiter unten übersprungen  <==== ÄNDERUNG HIER
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect
    
    ; holt nächstes Token (Operator)
    ; überspringe eventuell ")"                                              <==== ÄNDERUNG HIER
      Scanner::GetToken()
    
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu MulTerm()
  
  EndProcedure
Worauf wir trotz aller Einfachheit aber wieder achten müssen, ist, dass wir nicht aus dem Tritt kommen beim Parsen des Token-Lexem-Streams. Deshalb kurz überlegt und mit der "Debug Scanner::Lexem : End"-Methode getestet und erkannt, dass wir im Case-Teil die schließende Klammer nicht überspringen dürfen (geschieht nämlich einige Zeilen darunter), sonst hätten wir 2 Tokens übersprungen und landen im Irgendwo.

Testen Sie folgenden Source-Code:

Code: Alles auswählen

2+4*5+15      // 2 +  20  + 15  -->  37
XXXXXXXXXXXXXX
(2+4)*(5+15)  // 6 * 20         -->  120
Das Ergebnis ist korrekt:

Code: Alles auswählen

push Const  2
push Const  4
push Const  5
mul
add
push Const  15
add
push Global XXXXXXXXXXXXXX
push Const  2
push Const  4
add
push Const  5
push Const  15
add
mul


7.8. Negation: negative Zahlen und Klammerausdrücke


7.8.1. Negative Zahlen: Unäre Operatoren

Was ist aber, wenn wir z.B. Folgendes als Source-Code eingeben:

Code: Alles auswählen

-3*2
oder:

Code: Alles auswählen

3--4
Falls Ihnen das letzte Beispiel seltsam erscheint, testen Sie es in Pure Basic mit "Debug 3--4". PB akzeptiert das und Toy-C wird es auch akzeptieren.

Arbeiten wir daran, die Sache zu reparieren.
Im Englischen nennt man diese Situation "unary minus" oder "unary negative", im Deutschen "unäres Minus" (d.h. alleinstehendes, einfaches). Der Name rührt daher, weil mit einem unären Operator nie 2 Operanden verbunden werden (z.B. 2+3), sondern weil er eben nur 1 Operanden (z.B. -23) hat.
Natürlich gibt es das auch mit einem Plus, ich könnte also "+2*+4" schreiben wollen. Erlauben wir in Toy-C beides.
(weitere Infos, leider auf Englisch:http://en.wikipedia.org/wiki/Unary_oper ... d_positive)

Die Änderungen an ValueFactor() sind auch diesmal nur einige Zeilen:

Code: Alles auswählen

  Procedure ValueFactor()
  
    ; --> Token/Lexem steht auf Value ODER
    ; --> auf unary + | unary -
    
    ; pruefe auf Vorzeichen (unary - | unary +)          <==== HINZUGEFÜGT ABSCHNITT HIER
    ; Ja? Überspringe es und setze bei "-" ein Flag
      If     Scanner::Token = '-': Scanner::Token(): negate = #True        
      ElseIf Scanner::Token = '+': Scanner::Token()                        
      EndIf            
    
    ; je Token-Art: Ausgabe des Values als ASM-Code
      Select Scanner::Token
      Case '#'  : WriteString(1,"push Const  " + Scanner::Lexem + #CRLF$)
      Case 'x'  : WriteString(1,"push Global " + Scanner::Lexem + #CRLF$)
      Case '('  : Scanner::GetToken()  ; überspringe "("
                  Expression()         ; ")" wird weiter unten übersprungen
      Default   : Scanner::Expected("Korrekter Operand (Konstante Zahl, Variablen- oder Prozedurname)")
      EndSelect

    ; Teste Flag "negate"                                <==== HINZUGEFÜGT ABSCHNITT HIER
    ; Ja? Führe "unary -" durch: negiere Value
      If negate = #True
          WriteString(1,"neg"+#CRLF$)
      EndIf           
    
    ; 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 MulTerm()
  
  EndProcedure
Ich nutze diesmal eine If-Konstruktion, damit ich eine optische Unterscheidung im Code zur Select-Case-Konstruktion habe. Sonst hat das keinen tieferen Sinn.

Testen Sie folgenden Source-Code:

Code: Alles auswählen

-3*+5--3
Als Ergebnis sollte herauskommen:

Code: Alles auswählen

push Const  3
neg
push Const  5
mul
push Const  3
neg
sub
Testen Sie jetzt unbedingt folgenden Source-Code, wir werden daran etwas diskutieren: Als Ergebnis sollte herauskommen:

Code: Alles auswählen

push Const  3
neg
Warum haben wir nicht gleich den Compiler so programmiert, dass er uns

Code: Alles auswählen

push Const  -3
herausgibt? Unsere Lösung wirkt dümmlich und ineffizient und sie wirkt nicht nur so. Kein Programmierer würde von Hand solchen Stack-Machine-ASM-Code schreiben.

Das hat mehrere Gründe:
  • Ich möchte den Compiler nicht mit Sonderfällen überladen, ein Optimizer löst solche Situationen fast auf den ersten Blick und im Vorbeigehen. Kein Grund, den Compiler zu belasten.
  • Beim Compiler-Programmieren ist es zumeist besser, allgemeine Situationen allgemein zu halten. Hier ensteht z.B. der Vorteil, dass negative Klammerausdrücke automatisch auch funktionieren.


7.8.2. Negative Klammerausdrücke

Wie oben angedeutet, funktionieren sie aufgrund unseres allgemein gehaltenen Aufbaus in ValueFactor() bereits einfach von selbst.
Es ist für den Parser gleichgültig, ob er eine Zahl negiert oder eine ganze Expression.

Testen wir es, sonst gibt es nichts mehr von mir dazu hinzuzufügen ;-)!

Source-Code:

Code: Alles auswählen

100/-(5+5)  // 100/ -(10) --> -10
VM-ASM-Code:

Code: Alles auswählen

push Const  100
push Const  5
push Const  5
add
neg
div


7.9. Abschließende Betrachtungen

Sie haben jetzt einen mathematischen Parser, der recht wetterfest ist und eine einfache Grammatik und damit eine einfache Präzedenztabelle unterstützt.

Vielleicht könnten Sie ihn bereits selbst um weitere Ebenen erweitern oder neue Operatoren hinzufügen?


Sie haben sicher erkannt, dass jede Ebene mit der Aufrufreihenfolge der Prozeduren zusammenhängt:
  • Ganz oben befindet sich ValueFactor(): Pusht den Operanden und lädt nächsten Operator
  • Die Prozedur, die aufgerufen wird (=Callee), ist die nächsthöhere Ebene.
  • Die Prozedur, die die nächste aufruft (=Caller), ist eine Ebene niedriger.

Ich empfehle, die Prozeduren so wie ich auch im PB-Programm in genau der richtigen Reihenfolge zu halten:

Code: Alles auswählen

; - Mathematischer Parser----------------------------------
; -
  Procedure ValueFactor()       <==== HÖHERE PRÄZEDENZ
  Procedure MulTerm()                            
  Procedure AddExpression()     <==== NIEDRIGERE PRÄZEDENZ                  
  Procedure Expression()                          
Die bis jetzt erarbeitete Grammatik (Ausschnitt) unserer geparsten Sprache:

Code: Alles auswählen

ValueFactor    =  ["-"|"+"] Num  |  ["-"|"+"] Name  |  ["-"|"+"] "(" Expression ")" ;  <==== HÖHERE PRÄZEDENZ     
MulTerm        =  ValueFactor { ("*" | "/" | "%") ValueFactor } ;               
AddExpression  =  MulTerm { ("+" | "-") MulTerm } ;                                    <==== NIEDRIGERE PRÄZEDENZ
Expression     =  AddExpression ;                       
Die sich daraus automatisch ergebende Präzedenztabelle:

Code: Alles auswählen

 Prozedur              Operator                 Präzedenz        
-----------------------------------------------------------
 ValueFactor()         ( ... )                  höchste
-----------------------------------------------------------
 ValueFactor()         Negation 
                       bzw. Unäres -|+          
-----------------------------------------------------------
 MulTerm()             * / %                           
-----------------------------------------------------------
 AddExpression()       + -                      niedrigste
Änderungen und Erweiterungen sind leicht durchgeführt:
  • Wollen wir also zwischen MulTerm() und AddExpression() eine neue Präzedenz-Ebene einfügen, dann machen wir das einfach.
    In AddExpression() muss nur (an 2 Stellen) die aufgerufene Prozedur (=Aufstieg) angepasst werden.
  • Wollen wir einen neuen Operator hinzufügen, z.B. in MulTerm(), dann müssen wir dort einfach eine neue Case-Option hinzufügen.


Die Präzedenz ergibt einfach aus der Reihenfolge der Prozeduren automatisch und von selbst. Das wars!

Besteht unser Mathe-Parser tatsächlich nur aus 3 - gesprochen drei - Prozeduren? Ja!


7.10. Code-Teil: Compiler von Kapitel 7
  • ---- weiter im Teil "Code" dieses Kapitels ----

*** ENDE KAPITEL 7: TEXT ***
Zuletzt geändert von puretom am 05.10.2013 21:16, 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
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 7: CODE ***


7.10. Code-Teil: Compiler von Kapitel 7

Der Gesamtcode von Kapitel 7 mit allem Drum und Dran, teilweise neu formatiert und kommentiert zu besseren Übersicht. Viel Spaß!

Code: Alles auswählen

; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
; X   PARSER/COMPILER (Kapitel 7)                                              X 
; X       mit eingebunden muss sein:                                           X
; X         1) Module Scanner                                                  X
; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

; ******************************************************************************
; * 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 - Prozeduren ----------------------------------------------------------
; -
  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
  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
  
; - 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 SkipWhite1()

    ; solange in Look ein White
      While IsWhite(Look)
      
          ; einfaches (/) als nicht-White im Stream belassen
            If Look='/': ProcedureReturn: EndIf
	    
	        ; nächsten Look laden
	          GetChar()
	          
      Wend
	    
  EndProcedure
	Procedure SkipLineComment()
      
      ; bis Zeilenende oder Ende des Source-Files (0-Byte)
        While Look<>#LF And Look<>0 
            GetChar()
        Wend 
        
      ; --> Look steht auf #LF 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 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

; ******************************************************************************
; * Parser (Compiler)
; ***
DeclareModule Parser
; -
; - Public Declarations ---------------------------------------------------------
; -
  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 MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      Declare Expression()           ; mathematischer Expression Parser 3+4*(4+3)       
                           
; - 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 Scanner (1. Token-Lexem liegt danach im Stream)
      Scanner::Start(file_name.s)
    
    ; so lange, bis Token = 0-Byte  <==== DIESER ABSCHNITT IST IM PRINZIP IST AUS Scanner::Debug_TokenLexemStream0() kopiert
      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 "INT"    : Scanner::GetToken() 
          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                         

    ; prüfen, ob 0-Byte (=Source-Code-Ende)
    ; Ja? Fehler, Block nicht geschlossen mit (})
      If Scanner::Token=0: Scanner::Expected("'}'"):EndIf                                  
        
    ; ueberlesen des (})
      Scanner::GetToken()         

    ; --> 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 -
    
    ; 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 '#'  : WriteString(1,"Push Const  " + Scanner::Lexem + #CRLF$)
      Case 'x'  : WriteString(1,"Push Global " + Scanner::Lexem + #CRLF$)
      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
          WriteString(1,"Neg"+#CRLF$)
      EndIf           
    
    ; 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 MulTerm()
  
  EndProcedure
  Procedure MulTerm()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu ValueFactor()    
      ValueFactor()    
    
    ; 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 ValueFactor()  
          ValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                
          Select operator
          Case '*'  : WriteString(1,"Mul"+#CRLF$)
          Case '/'  : WriteString(1,"Div"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          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()
  
    ; --> Einsprung von Statement()
    ; --> 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 '+'  : WriteString(1,"Add"+#CRLF$)
          Case '-'  : WriteString(1,"Sub"+#CRLF$)
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          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()
      AddExpression()
  EndProcedure  

EndModule

Parser::Compile("Source-Code.tc")



*** KAPITEL 7: CODE ***
Zuletzt geändert von puretom am 05.10.2013 16:22, insgesamt 9-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
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

So, es war mal wieder Großreinemachetag!

Mich hat der Unterschied zwischen Kapitel- und Teilnummer bereits so verwirrt.
Jetzt ist pro Teil genau 1 Kapitel, alle farbcodiert zum besseren Finden (auch für mich beim Editieren)

LG
Puretom

P.S. Sollte man einen neuen Thread in Erwägung ziehen, in dem ich die Teile der Reihe nach gebe? Langsam wirds verwirrend und ich hätte nicht gedacht, so schnell so viel zu posten, aber es hat sich eben unerwartet in diese Richtung entwickelt <) !

P.P.S. Kapitel 8 in Arbeit und noch erwünscht? Ein bisschen Feedback und Hilfe bei Fehlern wäre wirklich toll, ich habe langsam das Gefühl, der Einzige im Universum zu sein. Werde ich bald zu einem Solipsisten? :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
Benutzeravatar
Kiffi
Beiträge: 10621
Registriert: 08.09.2004 08:21
Wohnort: Amphibios 9

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von Kiffi »

puretom hat geschrieben:ich habe langsam das Gefühl, der Einzige im Universum zu sein.
neinnein, bist Du nicht. Ich z.B. verfolge das mit großem Interesse. Habe momentan
aber leider nicht die Zeit, mich eingehender damit zu beschäftigen.

Weitermachen! :allright:

Danke & Grüße ... Kiffi
Hygge
Benutzeravatar
Bisonte
Beiträge: 2427
Registriert: 01.04.2007 20:18

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von Bisonte »

Kiffi hat geschrieben:Weitermachen! :allright:

Danke & Grüße ... Kiffi
Das unterschreibe ich.... Wir "lauschen" ganz gespannt ;) Deswegen sagt keiner was ....
PureBasic 6.04 LTS (Windows x86/x64) | Windows10 Pro x64 | Asus TUF X570 Gaming Plus | R9 5900X | 64GB RAM | GeForce RTX 3080 TI iChill X4 | HAF XF Evo | build by vannicom​​
votan
Beiträge: 3
Registriert: 14.12.2009 16:19

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von votan »

Definitiv weitermachen!
Denke mal, keiner will dein Turtorial unnötig durch "Zwischenrufe" stören!?.... sondern dich lieber in Ruhe machen lassen und dein Schaffen schweigend aber aufmerksam verfolgen.
Benutzeravatar
Danilo
-= Anfänger =-
Beiträge: 2284
Registriert: 29.08.2004 03:07

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von Danilo »

Kenne mich auch mit dem Thema aus, aber warte noch bis zum Ende um dann
eventuell etwas zu kommentieren, wenn mir dann danach ist.

Momentan sind mir das zu viele kleine Einzelschnipsel, die man irgendwie
zusammen fügen soll. Einige Vorgehensweisen in den Schnipseln kommen mir
vom Gefühl her etwas komisch vor. Sieht auch beim groben Überfliegen aus
wie ein Ein-Pass-Compiler (wie PureBasic), der direkt beim ersten parsen den
Code erzeugt. Ist OK für den Einstieg (und wie Crenshaw), aber für fortgeschrittene
Dinge (Optimierungen, Semantische Analyse (Datentypen usw.)) nicht zu empfehlen.
Auch musst Du dann wieder Vorwärtsdeklarationen (Declare in PB) usw. hinzufügen,
was bei vielen moderneren Sprachen eigentlich nicht mehr nötig ist. Dazu kommen
dann auch wieder extra Checks, ob das Declare dann mit der Funktion auch letztendlich
übereinstimmt, etc.
Bei 2 Funktionen die sich gegenseitig aufrufen brauchst Du dann schon das Declare.

Zur ausführlichen Fehlerbehandlung im Lexer und Parser habe ich jetzt noch nicht so viel gesehen - habe mir die Änderungen
aber auch nicht mehrmals durchgelesen.
Ich finde es sehr wichtig alle möglichen Infos aus dem Source zu sammeln (Zeilen- und Zeichennummer, Datei-, Funktion- und Includename,
Typinformationen von Variablen und Rückgabetyp von Funktionen und deren Parameter-Typen usw.), um gute Fehlermeldungen ausgeben
zu können, was dem Programmierer dann auch weiter hilft (PB ist da eher mittelmässig und meint oft nur "Syntax Error").

Soweit ich das überblickt habe, hast Du bisher noch keine Möglichkeit für Includes dabei.
Das heisst, bei Dir wird nur eine alleinstehende Datei kompiliert, oder?
Für kleine SourceCodes OK, aber letztendlich nicht in realen Umgebungen mit größeren Codes
zu gebrauchen.
Um einfach Includes (wie PB) zu erlauben, ist zumindest ein Stack/eine Liste nötig, von der
der Lexer liest. Das heist bei einem "Include" wird ein neuer Eintrag auf den Stack gepusht (mit
Dateiname, neuen Zeilennummern usw.), von dem der Lexer nun liest.
Beim Dateiende wird dann der oberste Eintrag gelöscht und beim vorherigen Source fortgesetzt.

Ich kenne natürlich noch nicht das Endziel. Welche Operatoren kommen noch beim Expression Parser hinzu?
+, -, *, /, % (mod), ^ (pow), Or, And, Xor, Not, << (Shift Left), >> (Shift Right), =, <, >, <>, <=, >=, &, |, !, ˜
sind so die gängigsten Operatoren. Dafür brauchst Du eventuell ein paar mehr Prioritätsebenen.
Ich habe das in meinem Expression Parser mit 8 Ebenen implementiert (Kommentar-Tabelle "order of operator precedence").

Die nächste offene Frage ist, welche Datentypen noch hinzu kommen.
Byte, Word, Int32, Int64, Float, Double, extended Double, Strukturen, Pointer,
Listen, Arrays (statisch mit [] und dynamisch), alle Standardtypen als signed und unsigned...
Die fertige Sprachspezifikation sollte vielleicht mehr am Anfang stehen,
nach der Einführung. Dann werden alle Elemente nach einander implementiert.

Den Fehler mit / am Anfang hast Du scheinbar ausgeglichen. Also das Problem mit Divisionsoperator
und Kommentaren, die mit /* anfangen.

Du meintest noch das man kein Block-Ende braucht. In C ist das ';', bei BASIC das Zeilenende.
Das kann allerdings zu Problemen führen, weil dann manchmal nicht klar ist, wo ein Block endet
oder zu welchem Block ein Statement dazu gehört. Werde dazu vielleicht am Ende ein Beispiel
geben, wenn Du das so implementierst. Ich denke das ist ein Fehler, und wird auch in der entspr.
Fachliteratur so mit Beispielen erläutert (If-Else Problem kommt Dir vielleicht bekannt vor).
Aber mal abwarten wie Du das machen wirst...

Vielleicht solltest Du zu jedem Kapitel am Ende einen fertigen SourceCode zum Download zur Verfügung stellen,
so dass der Leser das auch einfach testen kann, ohne sich selbst zig Teile zusammen kopieren zu müssen.
Also immer den Source des jeweiligen Kapitels, vielleicht in Unterkapitel geteilt. So wie das bei so ziemlich allen
Büchern ist (Beilage-CD oder Download vom Internet).

Die Ansprache des Lesers mit "Sie" klingt m.M.n. vielleicht etwas hochtrabend. Ist doch nur ein kleines Tutorial,
und kein Fachbuch für Rechtsanwälte. ;)
Vielleicht kann man das mit einem "Wir" umschiffen, so wie "Nun wenden wir uns dem Teil XXX zu...",
"Als nächstes werden wir XXX implementieren", "Wir haben jetzt den fertigen Parser, und werden uns nun...", usw.

Ansonsten denke ich auch: Erstmal so weiter machen!

Compilerbau Ist ein komplexes Thema, womit man locker einige 500-Seiten-Bücher füllen könnte, um es ausführlichst
und bis ins kleinste Detail des aktuellen Forschungsstands zu erklären. In einem Tutorial bleiben natürlich einige Sachen auf der Strecke,
aber als Einführung für Interessierte finde ich das schon ganz OK.
Kommt mir momentan nur etwas zersplittert vor, da es so viele (nicht einzeln lauffähige) Mini-Code-Schnipsel sind.
Wenn es dann mal als Ganzes zur Verfügung steht, werde ich es bestimmt mal testen und kann dann vielleicht auch
eher auf Probleme im System hinweisen, die ich beim lesen des kompletten Codes oft schon erkennen kann.
cya,
...Danilo
"Ein Genie besteht zu 10% aus Inspiration und zu 90% aus Transpiration" - Max Planck
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

Lieber Danilo!

Vielen Dank für dein Feedback, danke, dass sich jemand interessiert.

Code: Alles auswählen

 Einige Vorgehensweisen in den Schnipseln kommen mir
vom Gefühl her etwas komisch vor.
Welche? Will ich unbedingt wissen.
Sieht auch beim groben Überfliegen aus
wie ein Ein-Pass-Compiler (wie PureBasic), der direkt beim ersten parsen den
Code erzeugt.
Ja, er erzeugt beim ersten Parsen bereits (extrem uneffizienten) Code,
aber:
Auch musst Du dann wieder Vorwärtsdeklarationen (Declare in PB) usw. hinzufügen,
was bei vielen moderneren Sprachen eigentlich nicht mehr nötig ist.
Das habe ich eigentlich nicht vor. Er wird 2 Passes machen, er sammelt zuerst die Prozeduren (doch davon sind wir weit entfernt, wer weiß, ob ich bis dahin noch Lust habe).
Zur ausführlichen Fehlerbehandlung im Lexer und Parser habe ich jetzt noch nicht so viel gesehen - habe mir die Änderungen
aber auch nicht mehrmals durchgelesen.
Tatsächlich nicht, das ist etwas, womit ich mich auch noch nicht auseinandergesetzt habe, ich schreibe auch kein 100€ teueres Buch, sondern ein Tutorial für Einsteiger in dieses Thema. Eine Fehlerbehandlung werde ich auch kaum einbauen, das mögen andere tun, die mehr Zeit und Können haben.
Sprich: Eine Nummer zu groß für mich.
Includes (wie PB) zu erlauben
Hatte ich in meinen Spiel-Compilern schon eingebaut - ist eigentlich recht unproblematisch, aber davon sind wir hier weit entfernt (vielleicht später)
Ich kenne natürlich noch nicht das Endziel. Welche Operatoren kommen noch beim Expression Parser hinzu?
Fast alle von dir genannten sind im dem Teil dabei, in dem die Dinge hinzukommen, wo auch Verzweigungen und Schleifen bearbeitet werden. Mit einer Diskussion über Präzedenzen.
Außerdem diletiere ich das erste Mal in meinem Leben mit BNF/EBNF in diesem Teil. Vielleicht könntest du mich dabei unterstützen? :oops:
Die nächste offene Frage ist, welche Datentypen noch hinzu kommen.
Byte, Word, Int32, Int64, Float, Double, extended Double, Strukturen, Pointer,
Listen, Arrays (statisch mit [] und dynamisch), alle Standardtypen als signed und unsigned...
Das sind für mein Ziel viel zu viele:
Integer (wie PB ein signed Integer) und String für den Anfang, eventuell bei Lust Float und eine kleine Mini-Diskussion über Type Casts.

Damit du weißt, was meine Ziele, bevor ich ein Tut machen wollte, mit dem Compiler waren.
Ich habe eine kleine Text-Adventure-Engine schreiben wollen (die aber nie fertig wurde, also die Scriptsprache samt Compiler wurden fertig, die VM teilweise, die Engine dann aber leider nie :oops: ) und dazu brauchte ich eine Scriptsprache (mein Vorbild war: http://quest5.net/wiki/Script_commands, http://textadventures.co.uk/). Du siehst, für so viele Datentypen habe ich mich gar nie interessiert und auch hier keine Skills in der Programmierung von ihnen erlernt.
Auch dieses Tut soll eine einfache Skriptsprache (erwähne ich - glaube ich am Anfang? auch) werden, mehr nicht. Also so ein bisschen für den Hausgebrauch des blutigen Noobs in dieser Thematik
Es soll keine - wie könnte ich auch so anmaßend sein - moderne Hochsprache werden!

Sprich: Mehrere Nummern zu groß für mich einerseits und andererseits gar nie mein Ziel gewesen, so viele Datentypen (die für eine Text-Adv-Engine keiner braucht) zu haben.

Du meintest noch das man kein Block-Ende braucht. In C ist das ';', bei BASIC das Zeilenende.
Das kann allerdings zu Problemen führen, weil dann manchmal nicht klar ist, wo ein Block endet
oder zu welchem Block ein Statement dazu gehört. Werde dazu vielleicht am Ende ein Beispiel
geben, wenn Du das so implementierst. Ich denke das ist ein Fehler, und wird auch in der entspr.
Fachliteratur so mit Beispielen erläutert (If-Else Problem kommt Dir vielleicht bekannt vor).
Aber mal abwarten wie Du das machen wirst...
If-Else Problem kommt Dir vielleicht bekannt vor
Ja, aber bis jetzt hatte ich keine Probleme damit.

Aber machen wir das so (mit dem Abwarten von dir), denn ich hatte damit noch keine Probleme bei Blockenden, wenn dann welche auftauchen, wäre toll, wenn du mich unterstützt.
Aber selbst verschachteltste If-else in If-else und noch schleifen, die je nachdem mit "Break" oder "Continue" verlassen bzw. weitergeführt werden. Alle Labels saßen im VM-ASM bis jetzt immer richtig. Aber falls ich mich irre, danke für deine Unterstützung im Voraus!

Aber: Eine Sache ist tatsächlich bei diesem Ansatz (also ";" zu ignorieren) möglicherweise problematisch (wobei das immer im Auge des Sprachenerfinders ist, denn er definiert den Look&Feel seiner Programmiersprache), wir können so keine leeren Blöcke bilden (in Python ist das mit einem eigenen Befehl "pass" geregelt, in PB kann man einen leeren Block einfach leer lassen, in Toy-C geht das mit meinem Ansatz nicht, da bräuchte es ein "pass").
Die Ansprache des Lesers mit "Sie" klingt m.M.n. vielleicht etwas hochtrabend.
Ja, das ist richtig. Und mit "wir" klingt es wie die Grundschullehrerin ("Wir wollen jetzt die Hefte nehmen").
Im Ernst. Es ist, wie du richtig sagst
Ist doch nur ein kleines Tutorial,
und kein Fachbuch für Rechtsanwälte.
und ich bin irgendwann in diese Art beim Tippen ohne groß aufzupassen hineingerutscht und weil ich ein Tutorial schreibe, lege ich nicht jedes Wort auf die Goldwaage. Ich mag es selbst nicht sehr. Ich hoffe, du bist mir nicht böse, dass ich jetzt nicht alles ändere (ist ja nur ein Tut), werden aber in Zukunft schauen, dass mir beim Tippen nicht die Pferde durchgehen. :wink:
Compilerbau Ist ein komplexes Thema, womit man locker einige 500-Seiten-Bücher füllen könnte, um es ausführlichst
und bis ins kleinste Detail des aktuellen Forschungsstands zu erklären.
Könnte ich auch gar nicht, weil ich selbst noch nicht so weit bin von meinen Kenntnissen (habe ich auch in meiner Einleitung geschrieben)
Das ist sowieso mehrere Nummern zu groß für mich.
aber als Einführung für Interessierte finde ich das schon ganz OK.
Danke, mehr kann ich auch selbst nicht und will ich auch nicht.
Kommt mir momentan nur etwas zersplittert vor, da es so viele (nicht einzeln lauffähige) Mini-Code-Schnipsel sind.
Meine "pädagogische " Idee (habe ich natürlich auch von meinem Lehrmeister Crenshaw abgeguckt).

Gerüst in PB einfügen, Tutorial mit aktiver Mitarbeit durchmachen und nach und nach die Procedure-Dummys auffüllen. Nach jedem Kapitel sollte lauffähiger Code dasein. Also bei mir läuft der, sonst gingen ja die Source-Code-Tests nicht. Die müssten auch an der Stelle laufen, an der die Leser im Tut auffordere einen Test durchzuführen. Die leeren Dummy-Prozeduren sind teilweise absichtlich im Test-und-Lern-Prozess im Text absichtlich eingearbeitet (z.B: SkipWhite ist noch leerer Dummy und filtert deshalb beim ersten Test nichts raus, wir füllen die Proc, jetzt filtert er etwas, usw.).
Der Code läuft bei mir, wenn das nicht so sein sollte, bitte SOFORT SAGEN, denn dann habe ich eventuell einen Blödsinn ins Tut kopiert!
Wenn es dann mal als Ganzes zur Verfügung steht, werde ich es bestimmt mal testen und kann dann vielleicht auch
eher auf Probleme im System hinweisen, die ich beim lesen des kompletten Codes oft schon erkennen kann.
Aus deiner Formulierung lese ich heraus, dass du vom Compilerbau um Welten mehr Ahnung hast als ich.

Ich kenne meine Grenzen des Programmierkönnens und möchte bis zu dieser Grenze andere an meinem Wissen teilhaben lassen. Vielleicht in 3 Jahren, wenn ich mehr kann, gibts mehr Wissen oder ich interessiere mich längst für etwas anderes.

Ich würde mich freuen, wenn du - aber bitte vergiss nicht die Zielgruppe und mein Ziel, einen kleinen Crenshaw auf Deutsch und kein Drachenbuch oder ähnlich Professionelles zu machen, wenn du mich weiterhin mit Tipps unterstützt.
Wenn du allerdings ein ganz anderes Konzept wie Crenshaw (vom Code-Aufbau her) hast (Parse-Trees - keine Ahnung habe ich z.B. davon), dann müsste man aber wahrscheinlich ein neues Tut mit moderneren und professionelleren Konzepten machen.
Meinem Konzept sieht man den Crenshaw als Vater definitiv mit jeder Faser seines (Code-)körpers an. :lol:

Nochmals danke!
Total toll, dass du dir die Mühe gemacht hast, ein so langes Feedback zu verfassen.

LG
Puretom

P.S.
@votan und an alle natürlich
Danke fürs "schweigend" mitverfolgen, aber ich bin auch nur ein Mensch und brauche

1) Hilfe beim Code-testen
2) Tipps bei Code-Konzepten
3) Kritik bei Blödsinn und Hilfe beim Ausbessern
4) Unterstützung bei Tippfehlern (bitte PN's, ich kann nicht alles 300-mal durchlesen, ich kann meine eigenen Texte langsam nicht mehr "hören" und doch wette ich, dass da noch massig Fehler drin sind)
5) last but not least: Motivation! Wenns wer mag und gut ankommt, dann freue ich mich und mache weiter! :oops: -> sozusagen psychische Streicheleinheiten. :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
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 8 ***


8. Module Code und ein erster Zwischenstopp



8.1. Vorbemerkungen


Ich habe groß aufgeräumt in unserem Code.
Keine Angst, nichts hat sich so stark verändert, dass wir den Code nicht wiedererkennen würden.

Ziele dieses Kapitels sind zwei.

Erstens möchte ich beginnen, die Ausgabe des VM-ASM-Codes in einem Modul zu kapseln.
Das hat den Vorteil, dass wir, wenn wir später andere Befehle ausgeben möchten, einfach nur die Code-Modul-Prozeduren verändern müssen.

Zweitens möchte ich am Ende dieses Kapitels den gesamten bisherigen Code abdrucken.
Aus diesem Grund habe ich das hier vorgesehene Kapitel - Verzweigungen und Schleifen - auf Leserwunsch verschoben, um dieses Kapitel vorzuziehen.

Gehen wir die Veränderungen Modul für Modul durch.




8.2. Module Code

Ich bespreche zunächst einige Eck-Prozeduren des Module Code.
Da ich sowieso den Gesamttext danach abdrucke, lasse ich die vollständige Implementierung dort.
Wir können uns von dort dann alle Infos holen.


8.2.1. Code-Ausgabe in die .ta-Datei

Zunächst einigen wir uns darauf, dass jede ASM-Zeile eine bestimmte Anzahl von Zeichen eingerückt ist (hier 8 Spaces), Labels ([...]) sind nicht eingerückt.

Eine typische Code-Prozedur schaut folgendermaßen aus:

Code: Alles auswählen

  Procedure _Add()
      EmitS("add") ; "+":  Addition     
  EndProcedure
EmitS() sorgt für die Ausgabe mit 8 Spaces.

Code: Alles auswählen

  Procedure EmitS(text.s)
      WriteString(1,Space(8)+text+#CRLF$)
  EndProcedure
Es gibt natürlich auch ein Emit() ohne Space-Einrückungen.
Diese benutzt dann zum Beispiel folgende Prozedur, deren Aufgabe es ist, ein Label auszugeben:

Code: Alles auswählen

  Procedure Label(label_text.s,label_nr)
      Emit("["+UCase(label_text+Str(label_nr))+"]")
  EndProcedure
Labels möchte ich grundsätzlich großschreiben.

Ich denke, das Prinzip ist klar, Kapselung der Code-Ausgabe in eigene Prozeduren.
Soll "push Const" später "pushc" heißen, eine Änderung.


8.2.2. Die neuen Hilfsprozeduren zur Label-Verwaltung

Jedes Label (Sprungmarke) muss anders heißen, sonst ist der spätere Assembler nicht in der Lage, sein Ziel eindeutig zu finden.
Die globale Variable LabelNr (ist eine Zahl) speichert immer die aktuelle Label-Nummer.
Die Prozedur GetLabel() erhöht die Label-Nr und gibt diese Label-Nummer zurück.

Code: Alles auswählen

  Procedure GetLabel()
      LabelNr+1                           
      ProcedureReturn LabelNr        
  EndProcedure    
Anmerkung: Wie vieles in meinem Code würde ich hier gerne ein Macro benutzen. Dann wird der Code aber unaufgeräumter und Geschwindigkeit ist ohnehin nicht unser Problem.




8.3. Module Parser


8.3.1. Die neue Hilfsprozedur SkipToken()

SkipToken() nimmt als Parameter den Char-Code eines Zeichens (am besten mit '..').

Code: Alles auswählen

  Procedure SkipToken(token)
      If Scanner::Token<>token
            Scanner::Expected("'"+Chr(token)+"'") 
      Else      
            Scanner::GetToken()
      EndIf
  EndProcedure
SkipToken() testet das aktuelle Token, holt also kein neues vor dem Testen! Ist der Test erfolgreich, dann lädt SkipToken() das darauf folgende. Nach SkipToken() ist also das Token unmittelbar nach dem getesteten im Stream.

Wir könnten jetzt diese Prozedur einfach zur Übersichtlichkeit auch an Stellen einsetzen, an denen ohnehin klar ist, welches Token-Lexem im Stream ist. Wer das machen will (Crenshaw hat das aus pädagogischen Gründen auch gemacht), nur zu. Das Bisschen an "Overhead" (= unnötige Teile, die bremsen) in dieser Prozedur ist sicherlich bei den heutigen PCs und den Anforderungen an die Geschwindigkeit eines Scriptsprachen-Compilers sicher keine Diskussion.




8.4. Das Konzept der Start-Prozeduren

Ich habe mir angewöhnt, für jedes Modul, das untergeordnet verwendet wird, eine Start-Prozedur anzulegen, um die Modul-eigenen Initialisierungen, z.B. Variablen vorbelegen usw., durchzuführen.
Dadurch entsteht für mich mehr Übersichtlichkeit.




8.5. Das Gerüst des Compilers von Kapitel 8

Ich möchte meinem Gerüst-Konzept treu bleiben, denn dann sieht man recht gut, welche Prozeduren wo und wie im Code vorhanden sind. Die Sache war für mich insofern sehr schwierig, weil ich eigentlich mit dem Mathe-Parser, den Ifs und While usw. schon weiter war und dummerweise die Version ohne nicht gespeichert habe und jetzt den Code für Kapitel 8 dummerweise zurückbauen musste:

Code: Alles auswählen

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

; ******************************************************************************
; * 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()                   : Endprocedure
  Procedure Debug_TokenLexemeStream0()           : Endprocedure
  Procedure Debug_TokenLexemeStream1()           : Endprocedure
  
; - Start - Prozeduren ----------------------------------------------------------
; -
  Procedure Start(file_name.s)                   : Endprocedure    

; - Lade Source-File ------------------------------------------------------------
; -
  Procedure Load(file_name.s)                    : Endprocedure  
  
; - Is?() - Prozeduren ----------------------------------------------------------
; -
  Procedure IsName1(c)                           : Endprocedure  
  Procedure IsName(c)                            : Endprocedure  
  Procedure IsNum(c)                             : Endprocedure  
  Procedure IsString(c)                          : Endprocedure  
  Procedure IsWhite(c)                           : Endprocedure  


; - Get - Prozeduren ------------------------------------------------------------
; -
  Procedure GetChar()                            :EndProcedure
  Procedure GetToken()                           :EndProcedure
  Procedure GetName()                            :EndProcedure
  Procedure GetNum()                             :EndProcedure
  Procedure GetString()                          :EndProcedure
  Procedure GetOther()                           :EndProcedure
   
; - Skip - Prozeduren -----------------------------------------------------------
; -
  Procedure SkipWhite()                          :EndProcedure
  Procedure SkipLineComment()                    :EndProcedure
  Procedure SkipBlockComment()                   :EndProcedure

; - Error - Prozeduren -----------------------------------------------------------
; -
  Procedure Error(error_message.s)               :EndProcedure
  Procedure Expected(expected_object.s)          :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 _Add()                          ; mathematische Operationen
      Declare _Sub()
      Declare _Mul()
      Declare _Div()
      Declare _Mod()
      Declare _Neg()

    ; --- 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()                              :EndProcedure

; - Stack pushes & pops ---------------------------------------------------------
; -   
  Procedure PushConst(const_value.s)             :EndProcedure
  Procedure PushGlobal(var_name.s)               :EndProcedure

; - Mathematischer Parser -------------------------------------------------------
; - 
  Procedure _Add()                               :EndProcedure
  Procedure _Sub()                               :EndProcedure
  Procedure _Mul()                               :EndProcedure
  Procedure _Div()                               :EndProcedure
  Procedure _Mod()                               :EndProcedure
  Procedure _Neg()                               :EndProcedure

; - Sprünge ---------------------------------------------------------------------
; - 
  Procedure JumpIfFalse(label_text.s,label_nr)   :EndProcedure

; - Label-Verwaltung ------------------------------------------------------------
; - 
  Procedure Label(label_text.s,label_nr)         :EndProcedure
  Procedure GetLabel()                           :EndProcedure   
   
; - Emit-Hilfsprozeduren --------------------------------------------------------
; -
  Procedure EmitS(text.s)                        :EndProcedure
  Procedure Emit(text.s)                         :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, ( ... ), unary -|+
      Declare MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      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)                 :EndProcedure
  Procedure Statement()                          :EndProcedure
  Procedure Block()                              :EndProcedure

; - Mathematischer Parser -------------------------------------------------------
; -
  Procedure ValueFactor()                        :EndProcedure
  Procedure MulTerm()                            :EndProcedure
  Procedure AddExpression()                      :EndProcedure
  Procedure Expression()                         :EndProcedure

; - Hilfsprozeduren ------------------------------------------------------------
; -
  Procedure SkipToken(token)                     :EndProcedure

EndModule

Parser::Compile("Source-Code.tc")

Am Ende der Code-Box steht "Parser::Compile("Source-Code.tc")" ohne einen speziellen File-Namen wie z.B. "Lex_Test01.tc" oder Ähnliches.
Das wird ab jetzt so bleiben, denn im Rahmen dieses Tutorials verliere ich 1. langsam den Überblick über die verschiedenen Source-Codes und 2. ist es völlig egal, denn jeder Leser kann seinen Code wohl selbst irgendwie unter seinem Lieblingsnamen speichern (Vielleicht ändere ich das auch in den anderen Kapiteln, wenn ich viel Zeit habe. /:-> )




8.6. Der gesamte Code bis Kapitel 8

Wer bis jetzt mitgearbeitet hat, der hatte schon längst einen funktionierenden Compiler (na ja, was eben bis jetzt fertig ist :roll: ).
Bitte aber ab jetzt den neuen von hier benutzen, denn der ist aufgeräumter, hat mehr Kommentare und führt das von mir so begeistert geliebte Modul-Konzept (Liebe PB-Programmierer, ganz großen Dank dafür - muss auch einmal gesagt werden) verstärkt fort.

Ich möchte kurz zusammenfassen, was wir an lauffähigem Code schon implementiert haben:
  • Lexikalischer Scanner: funktioniert und liefert auf Anforderung Token und Lexem aus einem Zeichenstrom (=Source-Datei).
  • Modul Code: liefert auf Anforderung die passenden Opcodes in der Assemblersprache der Virtuellen Maschine für Toy-C.
  • Toy-C-Compiler/Parser:
    • sehr einfacher mathematischer Parser mit grundlegendsten Operatoren, der aber negieren kann und Klammerausdrücke problemlos verarbeitet. Jederzeit einfachstens (siehe Folgekapitel) ausbaubar.
    • Blockstruktur ist vollständig implementiert.
    • Primitivste Fehlerbehandlung, die sich aus dem Scan- und Parsevorgang von selbst ergibt. Mehr ist auch nicht das Ziel.
Das Gesamtwerk bis Kapitel 8, bitte testen, ich teste gerade selbst, aber ich wette, dass jemand doch noch Bugs findet. Ich habe weiter oben schon erwähnt, dass die Situation sehr schwierig war, weil ich eigentlich mit dem Mathe-Parser, den Ifs und While usw. schon weiter war und den Code für Kapitel 8 dummerweise zurückbauen musste, so etwas kann zu vermehrten Bugs führen.
Aber ich wollte einen Leserwunsch erfüllen und einmal allen Code am Stück posten, und jetzt, wo ich ihn so vor mir sehe, weiß ich, dass das ein guter Vorschlag war, wir haben einen Zwischenstart-Punkt für weitere Ausflüge:

Code: Alles auswählen

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

; ******************************************************************************
; * 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|#CR|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 _Add()                          ; mathematische Operationen
      Declare _Sub()
      Declare _Mul()
      Declare _Div()
      Declare _Mod()
      Declare _Neg()

    ; --- 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 _Add()
      EmitS("add") ; "+":  Addition     
  EndProcedure
  Procedure _Sub()   
      EmitS("sub") ; "-":  Subtraktion     
  EndProcedure
  Procedure _Mul()
      EmitS("mul") ; "*":  Multiplikation     
  EndProcedure
  Procedure _Div()
      EmitS("div") ; "/":  Division      
  EndProcedure
  Procedure _Mod()
      EmitS("mod") ; "%":  Mod     
  EndProcedure
  Procedure _Neg()
      EmitS("neg") ; "-":  Negation      
  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, ( ... ), unary -|+
      Declare MulTerm()              ; bearbeitet Mul-Ops: *, /, %
      Declare AddExpression()        ; bearbeitet Add-Ops: +, -
      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  <==== DIESER ABSCHNITT IST IM PRINZIP IST AUS Scanner::Debug_TokenLexemStream0() kopiert
      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 ({)
      SkipToken('{')     

    ; 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 -
    
    ; 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()
    
    ; --> in Token/Lexem ist Token/Lexem nach Value
    ; --> wenn die Expression weitergeht, ist das ein Operator    
    ; --> Abstieg zu MulTerm()
  
  EndProcedure
  Procedure MulTerm()

    ; --> Token/Lexem steht auf Value
      
    ; Aufstieg zu ValueFactor()    
      ValueFactor()    
    
    ; 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 ValueFactor()  
          ValueFactor()
          
        ; Ausgabe des ASM-Codes des Operators
        ; mit gemerktem Operator                
          Select operator
          Case '*'  : Code::_Mul()
          Case '/'  : Code::_Div()
          Case '%'  : Code::_Mod()          
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          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()
          Default   : Scanner::Expected("Korrekter Operator (z.B. +,-,*,=,<>,...)")         
          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()
      AddExpression()
  EndProcedure   

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

EndModule

Parser::Compile("Source-Code.tc")



8.7. Kurzanleitung für Quereinsteiger

Wer nur hier dieses Kapitel gelesen hat und sich ärgert, warum geht das nicht (so gehts mir auch oft mit Codes aus dem Forum), eine Anmerkung:
Man muss sich mit einem Text-Editor im selben Ordner wie der Code in der Box hier darüber eine File namens "Source-Code.tc" anlegen.
Dort schreibt man x-beliebige Rechnungen.

Erlaubt sind außer Integer-Zahlen folgende Zeichen:

Code: Alles auswählen

+ - * / % (  ) 
Ein Beispiel (jeder kann viele eigene Rechungen eintippen) - in "Source-Code.tc" speichern wir:

Code: Alles auswählen

1+-(2*3)/(4+-3)
Abspeichern nicht vergessen!

Code gleich mit F5 starten und im selben Ordner die Datei "Source-Code.ta" (neue Endung .ta beachten) suchen und mit dem Editor öffnen.
Das Ergebnis sollte sein:

Code: Alles auswählen

        push Const  1
        push Const  2
        push Const  3
        mul
        neg
        push Const  4
        push Const  3
        neg
        add
        div
        add
Wer wissen will, was da geschehen ist und wozu das Zeug gut sein sollte, der muss natürlich das Tutorial lesen.
Viel Spaß damit! LG Puretom


*** ENDE KAPITEL 8 ***
Zuletzt geändert von puretom am 05.10.2013 19:40, insgesamt 20-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
Antworten