PureBoard

Das deutsche PureBasic-Forum
http://forums.purebasic.com/german/

[Tutorial] Compiler und Virtual Machine

http://forums.purebasic.com/german/viewtopic.php?t=27222

Seite 3 von 10

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 19.09.2013 19:19
von puretom
*** KAPITEL 3 ***

3. Das große Bild


3.1. Einleitung

Ein Compiler besteht aus mehreren Teilen, die einerseits eng ineinander greifen, teilweise aber auch nacheinander stehende eigene Programme sind. Ich plane hier keine wissenschaftliche Abhandlung über Compilertheorie, sondern einen praktischen Ad-Hoc-Ansatz.
Für moderne Compilertheorie verweise ich auf die entsprechende Fachliteratur, die ich als Hobbyist und die meisten ohne (wie die Englischsprechenden sagen) 'Degree in Computer Science' (zumeist Bacc. aufwärts) nur schwer verstehen. Aus diesem Grund sind die Techniken, die ich hier vorstellen möchte, natürlich zum Teil veraltet und Ho-Ruck-mäßig, aber sie funktionieren. Man kann mit ihnen vermutlich keinen kommerziellen Compiler schreiben (oder doch?), aber für eine Scriptsprache in z.B. einem Role Game oder in einer Point&Click-Adventure-Engine oder dergleichen reichen sie aber haushoch.

Es folgt ein kurzer Überblick über das Gesamtprojekt, wobei natürlich in den Kapiteln später die einzelnen Komponenten genauer erklärt und auch Programmcode gezeigt werden soll.



3.2. Überblick über die Teile des gesamten Projekts


3.2.1. Der Compiler

Ein Compiler ist ein Programm, das eine Hochsprache (also C oder eben Pure Basic) in Assembler (ASM) umwandelt. Das macht auch der Pure Basic Compiler. ASM ist aber noch Textform, d.h. es muss danach ein Programm geben, das ASM in Textform in maschinenlesbare Zahlen umwandelt (=Assembler).

Es gibt auch Compiler, die direkt in Maschinensprache in Zahlenform übersetzen (Wirth z.B übersetzt direkt in die Maschinenesprache seiner virtuellen RISC-Maschine). Das ist aber ungemein komplizierter und wie häufig solche Direktcompiler sind, weiß ich nicht, vielleicht kann jemand im Thread aushelfen.
Leichter ist es, in ASM als Text zu übersetzen und dann einem weiteren Compiler, den man in diesem Fall Assembler nennt, die Arbeit zu überlassen, in Maschinensprache in Zahlenform zu übersetzen.

Ein Compiler besteht zumeist aus folgenden Komponenten:
  • lexikalischer Scanner, Scanner, Lexer, Tokenizer (das ist alles dasselbe, sind nur verschiedene Begriffe)

    Das Source-File ist ein Strom von Ascii-Zeichen (Characters, Character Stream, Anm.: auch andere Kodierungen wie z.B. Unicode oder UTF-8 sind selbstverständlich möglich, siehe PB-Hilfe), die aber natürlich nicht willkürlich sind, sondern sich zu zusammengehörenden Teilen (Lexeme/Objekten) zusammenbauen.
    Das können zum Beispiel Zahlen (Number), Zeichenketten in Anführungszeichen (String), Operatoren (Op: z.B. +,-,=,*,<>, ...), Bezeichner (Identifier) von Variablennamen/Kommandowörtern/Procedure-Namen (Name) usw. sein, nur um einen kurzen Überblick anzudeuten.

    Der Tokenizer erkennt im Zeichenstrom zusammengehörende Teile/Lexeme/Objekte.
    Er ordnet dem Objekt ein Token zu, das ist eine Code-Zahl, die angibt, welcher Art das Objekt war, also zum Beispiel ein Name.
    In einen String mit dem Fachausdruck Lexem speichert er das Objekt dann selbst.

    Anmerkung zu Benennung der Variable "Lexem":
    Lexem bedeutet "sprachliche Bedeutungseinheit", also etwas, das zusammengehört.

    Ein Beispiel:

    Code: Alles auswählen

    Zeichenstrom: Im Source-File steht:

Var=22

|V|a|r|=|2|2| ---> 6 Zeichen/Character 

---> 3 Token-Lexem-Paare:

Token.i = #Name |  Lexem.s = "Var"
Token.i = #Op   |  Lexem.s = "="
Token.i = #Num  |  Lexem.s = "22"
    Selten wird das Source-File vom Lexer vollständig untersucht und dann diese Token-Lexem-Paare gespeichert.
    Zumeist sind der Lexer und der Parser so eng verzahnt, dass der Parser, immer wenn er ein neues Token-Lexem-Pärchen braucht, das vom Lexer anfordert und geliefert bekommt.
    Lexer und Parser sind also - so wie ich meinen Compiler programmieren möchte - keine 2 getrennten und hintereinander ausgeführte Programmteile, sondern 2 Komponenten, die gleichzeitig ablaufen und ineinander greifen.

    http://de.wikipedia.org/wiki/Tokenizer

    Es gibt auch Programme, mit denen man Parser und Compiler generieren kann. Mit diesen habe ich aber noch nicht gearbeitet und will ich auch nicht, weil ich etwas über Compilerbau per Hand lernen wollte.
    Der Vollständigkeit halber:

    http://de.wikipedia.org/wiki/Lex_(Informatik)
    http://de.wikipedia.org/wiki/Yacc
  • Parser

    Während den Scanner nur die einzelnen Buchstaben interessieren, aus denen er Lexeme und Token macht, untersucht der Parser, wie ein Programm aufgebaut ist.

    Der Parser schaut, ob die While-Schleife richtig vom Programmierer aufgebaut ist, der Parser untersucht einen mathematischen Ausdruck nach Punkt-vor-Strich-Rechnung/ Klammern usw.
    Ein Beispiel zeige ich beim Codegenerator etwas weiter unten.

    Viele kommerzielle Parser bauen einen sogenannten Parsebaum (Parse Tree, Syntaxbaum, Ableitungsbaum) aus dem Source-Code, den sie dann an einen Codegenerator übergeben.

    In meiner Implementation gibt es zwar ein Modul Code, das aber eng mit dem Parser verzahnt ist. Anders gesagt, der Parser erzeugt bereits selbst Code, indem er Aufträge an den Codegenerator gibt. In der praktischen Umsetzung wird das dann klarer, keine Sorge.

    Genauere Informationen zur akademischen Compilertheorie, die weit über meinen rein praktischen Ad-Hoc-Ansatz hinausgeht, wie zum Beispiel verschiedene Parsingtechniken, siehe folgende Links:

    http://de.wikipedia.org/wiki/Parser
    http://de.wikipedia.org/wiki/Parsebaum
  • Codegenerator

    Mein Codegenerator ist eng verzahnt mit dem Parser. Er erzeugt auf Anweisung und im Auftrag des Parsers Byte Code für die Virtuelle Maschine.

    Ein Beispiel:

    Im Source-Code steht: < Var = 3+12 >

    Der Parser parst jetzt Token/Lexem für Token/Lexem-Paar und erzeugt folgenden Byte Code, den der Compiler als Text-File (nennen wir es Object-File) abspeichert.
    • Der Parser sieht Token =#Name, Lexem ="Var":
      Ist es ein Schlüsselwort/Kommandowort wie z.B. 'if', 'while', ...? --> Nein.
      Ist es ein Procedure-Name (schaut z.B. in einer Map nach)? --> Nein.
      ==> es muss ein Variablenname sein, der Parser vermutet, dass jetzt eine Variablenzuweisung folgen wird, also ein "=", ruft die entsprechende Prozedur auf und merkt sich den Namen "Var".
    • Der Parser sieht Token =#Op, Lexem ="=":
      Genau das hat der Parser erwartet. Wäre jetzt kein "=" gewesen, hätte er eine Fehlermeldung ausgegeben.
    • Der Parser sieht Token =#Num, Lexem ="3":
      Genau das hat der Parser erwartet. Wäre jetzt kein #Num gewesen, hätte er eine Fehlermeldung ausgegeben.
      Da ich eine Stack Machine bauen will, gibt der Parser dem Codegenerator den Befehl, dass er die Nummer "3" auf den Stack legen soll (push 3).
    • Der Parser sieht Token =#Op, Lexem ="+":
      Genau das hat der Parser erwartet. Wäre jetzt kein #Op gewesen, hätte er eine Fehlermeldung ausgegeben.
      Durch den rekursiven Parser (dazu viel später mehr), merkt er sich das "+".
    • Der Parser sieht Token =#Num, Lexem ="12":
      Genau das hat der Parser erwartet. Wäre jetzt kein #Num gewesen, hätte er eine Fehlermeldung ausgegeben.
      Da ich eine Stack Machine bauen will, gibt der Parser dem Codegenerator den Befehl, dass er die Nummer "12" auf den Stack legen soll (push 12).
    • Der Parser erkennt aufgrund seiner rekursiven Natur, dass der mathematische Ausdruck zu Ende ist.
      Er hat sich gemerkt, dass "+" noch nicht ausgeführt wurde und gibt dem Codegenerator den Befehl zu addieren (add).
      Weiters weiß er, dass er eine Zuweisung an eine Variable durchführen muss. Dazu hat er sich ja oben "Var" gemerkt und gibt dem Codegenerator den entsprechenden Befehl (pull Var).

      Der erzeugte Bytecode (in Textform) schaut jetzt folgendermaßen aus (in Klammer sind die Schritte, die die Virtual Machine ausführt, wenn der Code abläuft):

      Code: Alles auswählen

      push 3      // lege 3 auf den Stapel (Stack) 
push 12     // lege 12 auf den Stapel (Stack) 
add         // hole 12 und 3 (oberstes + nächstes Element) vom Stapel         
               addiere sie und lege Ergebnis auf Stapel
               ganz oben am Stapel liegt jetzt 15
pull Var    // hole 15 (=oberstes Element) vom Stapel 
               speichere es in Variable "Var" ab
    In der Endausbaustufe der Virtuellen Maschine wird der Code etwas genauer sein (z.B. float, integer wird unterschieden werden), aber ich denke, das Beispiel zeigt die Richtung, in die es geht.
  • Optimizer, Optimierer, Optimierungsstufe

    Der erzeugte Code ist nicht effizient. Auf den ersten Blick sieht man, dass man "12+3" eigentlich schon beim Kompilieren ausrechnen hätte können, weil es ja Konstanten sind. Man nennt das Constant Folding.

    Für eine einfache Scriptsprache, bei der es nicht um Speed geht, empfehle ich diesen Schritt sogar wegzulassen, denn der User wird schlicht keinen Unterschied merken. Schauen wir mal, wie weit ich mit dem Tutorial komme und ob ich diesen Schritt herzeige. Ich habe damit selbst erst experimentielle Grundlagentests durchgeführt. Wenn, dann mache ich das als Letztes, frei nach dem Spruch (weiß nicht, wer das gesagt hat, habe ich mal aufgeschnappt): Optimiere funktionierenden Code nie, es sei denn, du musst unbedingt (so oder so ähnlich).

    Der Optimizer ist jetzt tatsächlich ein eigenständiger Programmschritt, liest also nochmals das Object-File ein und sucht nach bestimmten Mustern (Pattern) im Code (und er benutzt dabei wieder unseren Scanner), in diesem Fall ist das:
    • PUSH einer beliebigen Konstante
    • PUSH einer beliebigen Konstante
    • MATHEMATISCHER BEFEHL wie z.B. "add" hier in unserem Beispiel
    Findet also der Optimizer dieses Muster (push const, push const, Mathe), dann optimiert er, indem er sofort das Ergebnis ausrechnet und dieses auf den Stack legt. Er verändert also das Object-File folgendermaßen:

    Code: Alles auswählen

    push 15     // lege 15 (=12+3) auf den Stapel (Stack) 
pull Var    // hole 15 (=oberstes Element) vom Stapel 
               speichere es in Variable "Var" ab
    Constant Folding ist eine der einfachsten Optimierungen, in meiner Literaturliste sind im Paper von Andrew S. Tanenbaum eine Vielzahl erklärt.
    Niklaus Wirth beschreibt diese Optimierung schon als Teil des Codeerzeugens, also ohne eigenständigen Optimizer, geht auch, mir ist nachträgliches Optimieren lieber, weil es das Programm für mich lesbarer macht und auch kompliziertere Optimierungen zulässt.

Jetzt ist die Arbeit des eigentlichen Compilers, also Hochsprache wie C oder Pure Basic in Assembler (ASM) umzuwandeln, abgeschlossen.

Als Endprodukt erhalten wir ein Text-File (=Object-File), in dem der Byte Code als Text gespeichert ist. Dieser kann so natürlich nicht in der Virtual Machine ablaufen, denn die versteht nur Zahlen.



3.2.2. Der Assembler

Das als Text vorliegende Object-File muss jetzt in Zahlen gegossen werden.
Ein Assembler ist ein Compiler. Er übersetzt ein Assemblerprogramm (=Maschinensprache als Text, ASM in Pure Basic) in Maschinensprache als Zahl.
Maschinensprache sind die Befehle, die der Mikroprozessor wirklich versteht.
(siehe sehr gut dargestellt in: http://de.wikipedia.org/wiki/Assemblersprache)


Ein Compiler, der eine Hochsprache wie Pure Basic in Assembler (ASM) übersetzt, ist ein Compiler, einer der Assembler als Text in Maschinensprache als Zahl übersetzt, heißt zumeist nicht Compiler, obwohl er das ist, sondern Assembler.

Wenn ich nicht direkt in ASM meines Prozessors übersetze, sondern mir einen Prozessor erfunden habe, diesen also später simuliere, dann habe ich eine Virtuelle (=nicht echte, simulierte, erfundene, emulierte, ...) Maschine.
Die Sprache dieses erfundenen Mikroprozessors nennt man zumeist Byte-Code-Maschinensprache in Analogie zum echten Mikroprozessor, das Übersetzungsprogramm in Zahlen auch wie beim echten Assembler.

Der Assembler braucht wieder einen Lexer und Parser in sich, denn er arbeitet wieder mit Lexemen (z.B. "push") und Tokens wie #Num usw.
Diese sind aber einfacher als beim Compiler für Hochsprachen (v.a. der Parser), da Assembler einfacher und geradliniger ist.

Ein Beispiel:

Unser Assembler übersetzt unseren Code in folgende Zahlenfolge (die Zahlen sind einfach mal angenommen):

Code: Alles auswählen

push 15   --> push ist (angenommen) 22
              der Assembler speichert 22
          --> der Assembler speichert die Zahl 15
pull Var  --> pull ist (angenommen) 96
              der Assembler speichert 96
          --> Die Variable "Var" ist im Speicher (z.B ein Array)
              (angenommen) an Index 4
              der Assembler speichert 4

Die Bytecode-Befehlsfolge lautet also:
22 15 96 4
Diese Zahlenfolge speichern wir nun ab.



3.2.3. Die Virtual Machine (VM)

Die Virtuelle Maschine ist ein PB-Programm, das das File mit der Zahlenfolge lädt und Schritt für Schritt ausführt. Es ist ein simulierter Prozessor.

Ein Beispiel:

Code: Alles auswählen

22: Die VM sieht 22 und weiß, sie muss die nächste Zahl pushen
15: Die VM sieht 15 und pusht 15
96: Die VM sieht 96 und weiß, sie muss die 15 vom Stack pullen
    Sie weiß auch, dass sie diese 15 in eine Variable speichern muss
    Index folgt mit er nächsten Zahl
 4: Die VM sieht 4 und speichert 15 in die Variable mit Index 4.

3.3. Zusammenfassung

Die einzelnen Komponenten sind folgendermaßen aufgebaut:

1. Scanner/Parser/Codegenerator -> Optimizer ---> erzeugt Byte-Code-Assemblerprogramm in Textform (Object-File)
2. Byte-Code-Assembler ---> erzeugt Binär-File in Zahlenform
3. Virtual Machine: führt Binär-File in Zahlenform Schritt für Schritt aus

*** ENDE KAPITEL 3 ***

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 19.09.2013 19:34
von puretom
*** KAPITEL 4 ***

4. Schrittweise Entwicklung eines lexikalischen Scanners



4.1. Vorbemerkungen

Ich möchte mit dem Scanner/Lexer/Tokenizer beginnen. Diese Komponente ist die am einfachsten zu realisierende.
Ich halte mich dabei mit einigen Verfeinerungen, die ich über die Jahre nach und nach eingebaut habe, an Crenshaw/Wirth/Arbayo.

Crenshaw beginnt in seiner Erklärung mit Lexemen, die aus nur einem Buchstaben bestehen, weil er der Meinung ist, dass dadurch die Techniken des Parsens für die Leser leichter zu erkären seien.
Nun, das ist nur bedingt richtig. Crenshaw hat ja seine damalige Serie geschrieben, während er die diskutierten Programme erst "live" sozusagen vor den Augen der Leser getestet und entwickelt hat. Ich mache für dieses Tutorial auch alles neu, weiß aber durch mein vorher Gelesenes uns schon Programmiertes, was geht und was nicht.
Dadurch habe ich gegenüber Crenshaw einen Vorteil, ich weiß, wo der Zug fahren kann und wo nicht.

Der Lexer belastet die Verständlichkeit des Späteren eben nicht, weil es aus Sicht des späteren Parsers egal ist, ob er nur wie bei Crenshaw 1 Zeichen mit einer Prozedur namens GetChar(), d.i. hole genau 1 Zeichen, oder eben mit GetToken() gleich ein ganzes Token-Lexem-Paar vom Scanner anfordert. Aus Sicht des Parsers ist es egal, er macht eine Anforderung und bekommt geliefert.
Also steigen wir gleich und sofort mit mehrbuchstabigen Lexemen ein, ohne Crenshaws Umweg über die 1-Zeichen-Lexeme.

Ein Beispiel:

Code: Alles auswählen

Normaler Code mit mehrbuchstabigen Lexemen:
if (a=3)
    printn(a)

In den ersten Kapiteln von Crenshaw könnte der Einbuchstabencode dafür lauten (ein von mir jetzt erfundenes Beispiel):
i(a=3)p(a)
Eine wichtige Sache vor Beginn:

Ich werde nicht immer die effizienteste Implementierung wählen.
  • Das kann 2 Gründe haben:
  • ganz profan: Ich weiß selber nichts Besseres :wink:
    Wird wohl teilweise so sein, bin ja selbst kein Vollprofi.
  • absichtlich: aus Gründen der Übersichtlichkeit wähle ich einfach die geradlinigste Implementierung, weil es mir ja nicht um Speed, sondern Verständlichkeit geht.
An Stellen, wo ich schon ahne, dass man etwas besser machen kann, werde ich bereits den einen oder anderen Wink geben.
Interessierte Leser können und sollen die Diskussion bereichern, indem sie alternative (bessere? schnellere?) Code-Möglichkeiten im Diskussionsthread vorschlagen.



4.2. Hintergrundgedanken zum Scanvorgang

Das 1. Zeichen jedes NOCH NICHT GESCANNTEN Lexems ist ein Nicht-White-Zeichen (gleich mehr) und wird Look Ahead Character (wörtlich: Schau-eins-nach-vorn-Zeichen) genannt. Wir nennen die Variable, die wir verwenden, um den Look Ahead zu speichern, Look.

Anders formuliert:
Ist der Scanner mit einem Token-Lexem-Paar fertig, dann hat er das aktuelle Token-Lexem-Paar in den Variablen Token und Lexem gespeichert, in Look steht das 1. Zeichen des nächsten Token-Lexem-Pärchens.

Ein White Character ist jedes Zeichen, von dem wir wollen, dass der Scanner es ignoriert, also einfach überspringt. Das naheliegendste ist das White Space (daher auch der Name für diesen Zeichentyp), aber auch den Tabulator, Kommentare, Carriage Return, Line Feed, ja sogar Semikolons ";" und Doppelpunkte ":" werde ich in meinem Code dazurechnen.

Ein Beispiel:

Im Source-File steht (Die Punkte setze ich für Leerzeichen):

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
^--- in Look ist "i"    (Anmerkung: Look ist kein String, also liegt in Look der Char-Code von "i")
  • Der Scanner erkennt mit IsName1(): "i" ist ein Buchstabe und verzweigt nach GetName()
  • GetName() holt jetzt Zeichen für Zeichen, bis zum ersten Nicht-Name-Zeichen. Der Scanner steht mit Look auf dem Leerzeichen nach "f"
  • GetName() ruft nun SkipWhite() auf, diese Prozedur überspringt alle White-Zeichen (1 Zeichen)
  • Am Ende von GetName() haben wir folgendes Ergebnis:
    • In Token ist die Code-Zahl von #Name (zu den Codes später mehr)
    • In Lexem ist der String "if"
    • In Look ist "(", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems
Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
   ^--- in Look ist "("
  • Der Scanner erkennt kein genau definiertes Zeichen (wir nennen es #Other, dazu später mehr)
  • GetOther() holt jetzt 1 Zeichen. Der Scanner steht mit Look auf "V" nach "("
  • GetOther() ruft nun SkipWhite() auf, diese Prozedur überspringt alle White-Zeichen (keine da)
  • Am Ende von GetOther() haben wir folgendes Ergebnis:
    • In Token ist die Code-Zahl von "(" (warum das so ist, dazu später mehr)
    • In Lexem ist der String "("
    • In Look ist "V", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems
Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
    ^--- in Look ist "V"
  • Der Scanner erkennt mit IsName1(): "V" ist ein Buchstabe und verzweigt nach GetName()
  • GetName() holt jetzt Zeichen für Zeichen, bis zum ersten Nicht-Name-Zeichen. Der Scanner steht mit Look auf dem "=" nach "e"
  • GetName() ruft nun SkipWhite() auf, diese Prozedur überspringt alle White-Zeichen (keine da)
  • Am Ende von GetName() haben wir folgendes Ergebnis:
    • In Token ist die Code-Zahl von #Name (gleich mehr)
    • In Lexem ist der String "VarName"
    • In Look ist "=", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems

Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
           ^--- in Look ist "="
  • Das kennen wir schon von oben, GetOther() holt das "="
    • In Look ist "3", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems

Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
            ^--- in Look ist "3"
  • Der Scanner erkennt mit IsNum(): "3" ist eine Zahl, verzweigt nach GetNum()
  • GetNum() holt jetzt Zeichen für Zeichen, bis zum ersten Nicht-Ziffern-Zeichen. Der Scanner steht mit Look auf ")" nach "5"
  • GetNum() ruft nun SkipWhite() auf, diese Prozedur überspringt alle White-Zeichen (keine da)
  • Am Ende von GetNum() haben wir folgendes Ergebnis:
    • In Token ist die Code-Zahl von #Number (gleich mehr)
    • In Lexem ist der String "35"
    • In Look ist ")", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems
Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
              ^--- in Look ist ")"
  • Das kennen wir schon von oben, GetOther() holt das ")"
  • GetOther() ruft nun SkipWhite() auf, diese Prozedur überspringt 3 White-Zeichen zwischen ")" und "p"
    • In Look ist "p", das erste Nicht-White-Zeichen des NÄCHSTEN Token/Lexems

Der Parser fordert vom Scanner mit GetToken() ein neues aktuelles Token-Lexem-Paar an:

Code: Alles auswählen

if.(VarName=35)...printn(VarName)
                  ^--- in Look ist "p"
  • und so weiter und so weiter
Am Ende des Toy-C-Source-Programms muss dann ein 0-Byte stehen, das durch size+1 bereits beim Laden erzeugt wird.

Hier sieht man auch etwas, das ich im Vergleich zu Crenshaw geändert habe.
Während er sein SkipWhite() vor dem Holen z.B. einer Nummer oder eines Namens aufruft, mache ich es danach. Crenshaw steht also nach einem GetToken()-Durchgang mit Look auf dem ersten White-Zeichen nach dem aktuellen Token-Lexem-Paar.
Ich stehe mit Look auf dem ersten Zeichen des nächsten Token-Lexem-Paars, weil ich, bevor ich Look belege, noch alle White-Zeichen überspringe.



4.3. Das Grundgerüst des Scanners, laden und testen des Character Streams

Ich lege mir jetzt einen Projektordner zu und darin ein Textfile mit dem Namen "Scanner_Test01.tc" an, wobei ".tc" für Toy-C steht. Das ist das Source-File in der von uns erfundenen neuen Hochsprache. Bitte aufpassen, einfache Ascii-Kodierung zu verwenden, also bitte kein Unicode oder dergleichen. Wer das später möchte, bekommt das sicher alleine hin, wenn er es schafft, einen Compiler zu programmieren.

In "Scanner_Test01.tc" speichere ich folgenden Code, wieder ist ein "." ein Leerzeichen. "{enter}" ist die Enter-Taste:

Code: Alles auswählen

...int..a=0{enter}
Anmerkung:
Ich verwende dafür den Programmierer-Notepad Notepad++ (http://notepad-plus-plus.org/), weil ich damit so schön Syntax-Highlighting meiner erfundenen Sprache machen kann. Für Toy-C stelle ich die Einstellung einfach auf "C".
Ich bin sicher, dass andere Programmierer andere Vorlieben haben. Vielleicht hat jemand Tipps im Thread?

Entwerfen wir ein Grundgerüst des Scanners, das wir dann laufend füllen werden (sollte selbsterklärend sein).
Alle Prozeduren sind zunächst Dummys, damit beim schrittweisen Erstellen keine Prozeduren fehlen.

Code: Alles auswählen

; ******************************************************************************
; *   Module:  LEXIKALISCHER 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 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 Load(file_name.s)                                    : Endprocedure  
  Procedure Start(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

Scanner::Start("Scanner_Test01.tc")
Das Source-File laden wir ganz einfach in einen Speicherbereich, den wir mit dem Zeiger *Source_Code adressieren. In Source_Position läuft dann die aktuelle Char-Position mit.
Am Ende des Memory-Bereichs muss ein 0-Byte sein, deshalb size+1. Wenn wir später mal bei einem Programmdurchlauf das size+1 weglassen, sehen wir ja, was passiert.
Natürlich sollte man in einer Release-Version auch testen, ob das File überhaupt geöffnet werden konnte.

Code: Alles auswählen

  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
Als Nächstes programmieren wir die Prozedur GetChar(). Sie hat die Aufgabe, bei Aufruf das Zeichen (Char = Character) vom Source-File-Speicherbereich *Source_Code in die globale Variable Look zu holen. Die Variable Source_Position gibt dabei die Position innerhalb von *Source_Code an. Dann wird Source_Position um ein Zeichen erhöht.
Ich weiß, hier wäre wohl ein Pointer besser als eine Funktion, so scheint es mir aber schlank und verständlich zu sein. Alternativen im Thread, wenn jemand will.

Code: Alles auswählen

  Procedure GetChar()  
      Look = PeekA(*Source_Code+Source_Position) ; aktuelles Zeichen nach Look
      Source_Position+1                          ; auf nächstes Zeichen stellen
  EndProcedure
Die Prozedur Start() ruft das Laden des Source-Files auf, stellt die Source_Position auf das erste Zeichen im Memory-Bereich des *Source_Code und tut dann etwas, das sie später nicht tun wird, sie ruft eine Debug-Prozedur auf, damit wir unser Werk einmal testen können.

Code: Alles auswählen

  Procedure Start(file_name.s)    
      Load(file_name.s)
      Source_Position = 0   
      ;
      Debug_CharStream() ; nur zu Debug-Zwecken
  EndProcedure
Die Debug-Prozedur Debug_CharStream() müssen wir eingehender besprechen.

Code: Alles auswählen

  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
Zunächst, und das werden wir dann auch beim Token-Lexem-Holen sehen, müssen wir den Character-Strom einmal das erste Mal "aufpumpen", sprich das erste Zeichen noch vor irgendeiner Schleife mit Look vorbelegen. Warum? Lesen wir uns oben nochmals durch, wie der Scanner arbeitet. Er erwartet nämlich, dass immer ein aktuelles Look-Zeichen in Look bereits vorhanden ist, also auch ganz zu Beginn.
Dann geht eine While-Schleife durch den Speicherbereich *Source_Code, aber nur, wenn kein 0-Byte als Terminator (Ende-Signalzeichen) des *Source_Code in Look ist.
Dabei bekommen wir das Zeichen und den Char-Code im Debug-Fenster angezeigt.
Am ENDE der While-Schleife wird Look für den NÄCHSTEN Durchlauf geladen, d.h. der Debug-Befehl innerhalb der Schleife bekommt das 0-Byte nie zu sehen. Genauso wird dann auch mit Token verfahren werden, dazu später beim Parser mehr.

Lassen wir den Scanner laufen, alles sollte funktionieren und folgende Debug-Ausgabe sollte nicht nur bei mir zu sehen sein (ohne Anmerkungen natürlich):

Code: Alles auswählen

' ' : 32        <------ Chr(32) - Leerzeichen 
' ' : 32                          (das sind WHITE-Zeichen)
' ' : 32
'i' : 105
'n' : 110
't' : 116
' ' : 32
' ' : 32
'a' : 97
'=' : 61
'0' : 48
'               <------ Enter-Taste (Erklärung folgt sofort)
' : 13                  (werden wir als WHITE-Zeichen behandeln)
'
' : 10
0-Byte beendet (außerhalb While-Schleife)

4.4. Das Ende einer Programmzeile und Semikolons

Interessant ist, was bei der ENTER-Taste passiert.
Windows setzt die Enter-Taste (= das Zeilenendezeichen) als 2 Zeichen um: die Kombination #CR (13: Carriage Return) und #LF (10: Line Feed). Dafür gibt es bei Pure Basic die Einzelkonstanten und auch die Kombinationskonstante #CRLF$ als String. Andere Bezeichnungen für Zeilenendezeichen sind auch New Line oder End Of Line (EOL).
Wer nicht mit Windows arbeitet, der ist zumeist mit einem einfachen #LF als Zeilenende konfrontiert. Es gibt aber sogar die Kombination #LF und #CR, also umgekehrt zu Windows oder nur #CR.
Ich verweise hier auf Wikipedia (http://de.wikipedia.org/wiki/Zeilenumbruch#ASCII), die verschiedene Möglichkeiten erklärt. Die englischsprachige Wikipedia ist hier viel genauer, aber eben auf Englisch (http://en.wikipedia.org/wiki/Newline).

Was bedeutet das für die Praxis?
Sollten wir also wollen, dass bei jedem New Line ein Zeilenzähler um eins hochgezählt wird, um zum Beispiel später in einem Debugger "Fehler in Zeile 25" ausdrucken zu können, dann sollten wir uns auf keinen Fall nur mit einer Lösung begnügen (Ja, zum Üben, aber zuletzt nicht). Wir sollten eine Prozedur schreiben, die mit allen möglichen Zeilenenden fertig wird.
In der Line-Comment-Schleife (kommt später) werde ich sicherheitshalber beides, also #CR und #LF, abfragen.

In meiner Implementation eines Scanners - das muss man nicht unbedingt so machen - werden die Zeilenenden, also die Zeichen #CR und #LF als White-Zeichen einfach ignoriert werden.

Verhaspelt sich dann der Parser nicht, wenn er keine Zeilenenden hat, fragt sich der eine oder andere sicher?
Bevor ich antworte, gehe ich noch einen Schritt weiter.

Sogar die oft gehassten Semikolons ";", die wir von C oder Pascal oder Java her kennen, sind bei mir White-Zeichen, also einfach zu überspringen.
Verhaspelt sich dann der Parser nicht, wenn er keine Semikolons hat, die die Befehle abschließen, fragt sich der eine oder andere sicher noch intensiver?

Nein, der Parser braucht weder das eine noch das andere, werden wir sehen.



4.5. Die Token-Typen und die Is?()-Erkennungsprozeduren

Im Kapitel "Hintergrundgedanken zum Scanvorgang" erwähne ich immer wieder Prozeduren wie IsName() oder IsNum().
Diese Prozeduren sollen anhand des Look erkennen, welcher Token-Typ folgen könnte. Außerdem kann eine Is?()-Prozedur anhand eines Zeichens erkennen, ob er in einem bestimmten Token-Typ vorkommt.

Hier eine Auflistung der Erkennungsprozeduren:

Code: Alles auswählen

Erkennungs-     Zeichen          Anmerkung
prozedur                                           
-------------------------------------------------------------
IsName1()       a..z  A..z       1. Zeichen eines Namens
-------------------------------------------------------------
IsName()        a..z  A..z       ab 2. Zeichen eines Namens
                0..9  _          z.B. Variable_01
-------------------------------------------------------------
IsNum()         0..9             Integer-Zahl
-------------------------------------------------------------
IsString()      "                Start-Zeichen eines Strings
                                 Ende-Zeichen eines Strings  
-------------------------------------------------------------
IsWhite()       #SPACE #TAB /    Zeichen, die der Scanner
                #LF #CR ; :      überspringt
                                 (bzw. / löst Kommentar aus)
Anmerkung:
Wer bis jetzt gut mitgedacht hat, dem wird auffallen, dass ich irgendwo weiter oben vom Typ #Op (Operand: z.B. = + - ) geschrieben habe und der hier in der Tabelle fehlt. Diesen Typ werde ich nicht als ausdrücklichen Operatortyp, sondern als bei den Get()-Prozeduren behandeln.

Diese Is?()-Prozeduren sind wirklich nicht viel mehr als Tester. Sie liefern #True zurück, wenn die Bedingung für den übergebenen Char-Code zutrifft. Achtung, die Prozeduren testen KEINE Strings, die Zeichen sind Char-Code, wie an den ' ' zu erkennen ist.
Ich habe das schon mit Macros, aber auch mit Select...Case gemacht. Hier mal mit If...Then, aber die exakte Ausführung des Codes ist nebensächlich, das kann jeder halten, wie er will:

Code: Alles auswählen

  Procedure IsNum(c)
      If (c>='0' And c<='9')
          ProcedureReturn #True
      EndIf
  EndProcedure
  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 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
Sehr schön ist auch, dass man, wenn man zum Beispiel das #CR nicht mehr als White-Zeichen führen will, es einfach aus der Prozedur herauslöscht, und schon ist die Sache gelöst. Es wird dann zu einem Other-Token.
Man braucht nicht hundertmal an verschiedenen Stellen die Abfrage löschen.



4.6. Die Get()-Prozeduren und die Token-Codes


4.6.1. GetToken(), GetName(), GetNum(), GetString(), GetOther()

Die wichtigste Prozedur, die zumeist vom Parser aufgerufen werden wird, ist die GetToken()-Prozedur.
Sie dient als Verteiler. Mittels den Is?()-Prozeduren wird der aktuelle Look getestet, und dann zur passenden Get()-Prozedur verzweigt.

Achtung: Wenn der Parser die Get()-Prozeduren aufruft, dann muss vorher schon ein aktuelles Look-Zeichen im Stream sein, das das 1. Zeichen des jetzt zu scannenden Token-Lexem-Pärchens ist. Die Prozedur Start() müssen wir dann später so verändern, dass sie GetChar() und danach SkipWhite() aufruft, um den 1. gültigen Look Character zu laden.


Obwohl die einzelnen Get()-Prozeduren jeweils ein SkipWhite() am Ende haben (SkipWhite() überspringt alle White-Zeichen und belegt Look mit dem ersten Zeichen des nächsten Token-Lexem-Paares), steht auch ein Aufruf am Ende von GetToken(), einfach zur Sicherheit. Mutige können den Aufruf weglassen.

Code: Alles auswählen

  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
Die folgenden Get()-Prozeduren sollten selbsterklärend sein. GetName() holt einen Namen nach Token/Lexem, GetNum() eine Integer-Zahl.
GetString() holte einen String, der mit " beginnt und mit " endet, als Begrenzung hätte auch jedes andere Zeichen dienen können, definiert haben wir das in IsString(). Innerhalb von "..." wird nicht SkipWhite() angesprungen, d.h. in den String werden alle Zeichen übernommen, auch White-Zeichen.
Diese Get()-Prozeduren schauen alle fast identisch aus, nur das Objekt, das sie ins Token-Lexem-Paar holen, ist jeweils unterschiedlich.

Code: Alles auswählen

  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

Code: Alles auswählen

  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

Code: Alles auswählen

  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
Kommen wir zu GetOther(), die Prozedur, die auch die Operatoren aufnehmen wird. Beim Programmieren des mathematischen Scanners wird klar werden, warum ich diese Form der Einfachheit gewählt habe.
Diese Prozedur bleibt bei GetToken() als Default-Möglichkeit über. Wenn also das 1. Zeichen eines Token-Lexem-Paares keine der anderen Typen ist, dann bleibt als letzte Möglichkeit nur Other (engl., anders, ein anderes) über.
GetOther() liest 1 Zeichen, überspringt alle White-Zeichen danach und übergibt als Token den Char-Code des gelesenen 1. Zeichens, als Lexem den String des gelesenen 1. Zeichens.

Code: Alles auswählen

  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
4.6.2. Die Token-Codes()

Die Token-Codes sind Zahlen, die in der Variable Token von den Get()-Prozeduren gespeichert werden.
Die 4 Tokentypen, die ich in meiner Implementierung unterscheide, kennen wir bereits: Name, Num, String, Other.
In der Tabelle stehen die entsprechenden Token-Codes.

Ich habe mich allerdings dazu entschlossen, keine Konstanten dafür anzulegen, also nicht z.B. #Name oder #Num, obwohl das in der Literatur üblich ist (z.B. Wirth), weil mir der Trick von Crenshaw gefällt.
Ich verwende die Char-Codes als in einfache Anführungszeichen eingeschlossene Zeichen, die Pure Basic als entsprechenden Char-Code, also als Zahl in das PB-Programm einfügt. Das Nummerzeichen für Zahlen, einen Buchstaben für einen Namen, ein Dollar für einen String und bei einem Other ist der Char-Code des Zeichen selbst in Token abgespeichert. Überprüfen Sie das in der jeweiligen Get()-Prozedur.

Code: Alles auswählen

       Char-Code         Typ und           Beispiele
als Zeichen  als Zahl    Get()-Prozedur   
----------------------------------------------------------------
   'x'         35        Name              Variablennamen
                                           C-Befehle        	       
----------------------------------------------------------------
   '#'        120        Num               Integer-Zahlen
----------------------------------------------------------------
   '$'         36        String            alles zwischen "..."
----------------------------------------------------------------
 das Zeichen selbst      Other             alles, was nicht
                                           'x' '#' '$' ist
                                           (auch das 0-Byte wird
                                           hier zu einem 0-Token)

4.7. Heureka! Es funktioniert!


4.7.1. Die neue Start()-Prozedur

Um dem Parser zu ermöglich, sich des Scanners zu bedienen, bauen wir jetzt die Start-Prozedur etwas um.

Code: Alles auswählen

  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 1. gültigem 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_TokenLexemeStream0() ; nur zu Debug-Zwecken
     ;Debug_TokenLexemeStream1() ; nur zu Debug-Zwecken
  
  EndProcedure
Der Parser ruft zunächst Scanner::Start(Source-File-Name) auf.
Zunächst wird durch Start() das Source-File in den Speicherbereich geladen, dann Source_Position auf das 1. Zeichen gesetzt.
Wesentlich ist der nächste Absatz. Da der Parser ab jetzt mit Token arbeitet und nicht mehr mit einzelnen Zeichen, müssen wir dafür sorgen, dass der Parser, bevor er das erste Mal eine Analyse der Token vornimmt, auch ein Token im Token Stream vorfindet. Danach springt der Scanner zurück zum aufrufenden Parser.
Die Debug-Prozeduren habe ich zunächst auskommentiert.


4.7.2. Die Token-Lexem-Schleife des späteren Parsers, eine Debug-Prozedur

Die Token-Lexem-Schleife sieht eigentlich genauso aus wie die Look-Schleife in Debug_CharStream() von Kapitel 4.3.
Statt dem Look Ahead Character werden aber jetzt jeweils ein Token-Lexem-Paar angefordert.
Die Prozedur Start() hat das erste Token-Lexem-Pärchen schon in den Token-Lexem-Strom gelegt.
Ich habe 2 Prozeduren erstellt. Die erste macht genau dasselbe wie die zweite, nur dass die 1. zum Vergleichen mit der Look-Schleife übersichtlicher ist und die zweite einen übersichtlicheren Debug-Ausdruck macht.

Code: Alles auswählen

  Procedure Debug_TokenLexemeStream0()

    ; 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

Code: Alles auswählen

  Procedure Debug_TokenLexemeStream1()

    ; 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
4.7.3. Erster Testlauf des Scanners

Ich beginne mit den Scanner-Tests gleich mit Debug_TokenLexemeStream1(), indem ich bei dieser Prozedur in Start() den Kommentar entferne.
Legen wir eine neue ".tc"-Datei mit dem Namen "Scanner_Test02.tc". In diese Datei geben wir kein Toy-C-Programm, sondern eine Sammlung von Lexemen, um zu sehen, ob unser Scanner alles korrekt erkennt. Wieder gilt: "." ist Leerzeichen, "{enter}" ist die Enter-Taste (Tipp: Man kann in jedem ernstzunehmenden Notepad den "." mit "ersetzen" zu einem Leerzeichen umändern und damit ebenso einfach alle {enter} automatisch löschen lassen):

Code: Alles auswählen

.Name_Variable_03{enter}
.452348{enter}
."Ich.bin.ein.///.String"{enter}
.+.-.={enter}
.<.>{enter}
.<>{enter}
.6/2{enter}
.//.Zeilenkommentar{enter}
./*.Blockkommentar.*/{enter}
Jetzt kommt der große Moment, lassen wir unseren Scanner laufen, indem wir am Ende den Aufrauf auf die neue Toy-C-Datei "Scanner_Test02.tc" ändern:

Code: Alles auswählen

Scanner::Start("Scanner_Test02.tc")
Der Testlauf sollte erfolgreich sein, außer den Kommentaren von mir und eventuellen Unterschieden wegen Linux bei {enter} sollte das Ergebnis im Debug-Fenster wie in der nächsten Code-Box unten aussehen.

Da die Skip()-Prozeduren noch Dummys sind, in ihnen als nichts gemacht wird, sollten alle White-Zeichen noch da sein. Ich markiere am Rand mit <---, was mit Skip() alles verschwinden sollte, mit <=== die erkannten Token.

Die erste Spalte zeigt den Inhalt der Variable Token an, also den Token-Code, die zweite Spalte zeigt, den Token-Code als Zeichen an, die 3. Spalte das Lexem im String Lexem.

Code: Alles auswählen

 32 | ' '  |                        <--- Skip: Leerzeichen                  
120 | 'x'  | NAME_VARIABLE_03       <=== TOKEN: NAME
 13 | 'CR' |                        <--- Skip: Zeilenende (enter) 
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen
 35 | '#'  | 452348                 <=== TOKEN: NUM
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen   
 36 | '$'  | Ich bin ein /// String <=== TOKEN: STRING (mit allen Zeichen von " bis ")
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen 
 43 | '+'  | +                      <=== TOKEN: OTHER (Zeichen selbst wird als Token-Code übernommen)
 32 | ' '  |                        <--- Skip: Leerzeichen  
 45 | '-'  | -                      <=== TOKEN: OTHER (Zeichen selbst ...)
 32 | ' '  |                        <--- Skip: Leerzeichen  
 61 | '='  | =                      <=== TOKEN: OTHER (Zeichen selbst ...)
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen                  
 60 | '<'  | <                      <=== TOKEN: OTHER (Zeichen selbst ...)
 32 | ' '  |                        <--- Skip: Leerzeichen                  
 62 | '>'  | >                      <=== TOKEN: OTHER (Zeichen selbst ...)
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen                  
 60 | '<'  | <                      <=== TOKEN: OTHER (Zeichen selbst ...)
 62 | '>'  | >                      <=== TOKEN: OTHER (Zeichen selbst ...)
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen                  
 35 | '#'  | 6                      <=== TOKEN: NUM          
 47 | '/'  | /                      <=== TOKEN: OTHER (Zeichen selbst ...)
 35 | '#'  | 2                      <=== TOKEN: NUM
 13 | 'CR' |                        <--- Skip: Zeilenende (enter)
 10 | 'LF' |                        <--- Skip: Zeilenende (enter)
 32 | ' '  |                        <--- Skip: Leerzeichen 
 47 | '/'  | /                      <--- Skip: TOKEN: OTHER (Zeichen selbst ...)
 47 | '/'  | /                           Hier sollte Skip() erkennen, dass ein Zeilenkommentar vorliegt
 32 | ' '  |                             Noch nimmt der Scanner das Zeichen als Other
120 | 'x'  | ZEILENKOMMENTAR             ...
 13 | 'CR' |                             ...
 10 | 'LF' |                             ... Ende Zeilenkommentar 
 32 | ' '  |                        <--- Skip: Leerzeichen                  
 47 | '/'  | /                      <--- Skip: TOKEN: OTHER (Zeichen selbst ...)
 42 | '*'  | *                           Hier sollte Skip() erkennen, dass ein Blockkommentar vorliegt
 32 | ' '  |                             ...                
120 | 'x'  | BLOCKKOMMENTAR              ...
 32 | ' '  |                             ...                  
 42 | '*'  | *                           ...
 47 | '/'  | /                           ... Ende Blockkommentar
'0'-Token beendet (außerhalb While-Schleife)
Interessant ist das letzte Zeichen. Ein 0-Byte ist aus Sicht des Scanners ein enfaches Other. Er gibt in Token und Lexem einfach das 0-Byte als 0-Token weiter. Dadurch kann die Token-Lexem-Schleife in Debug_TokenLexemeStream1() beendet werden, denn sie endet, wenn ein Token 0 beeinhaltet.


4.7.4. SkipWhite(), das Überspringen von White-Zeichen

Als Erstes lassen wir alle unnötigen White-Zeichen verschwinden, bevor wir uns um die Kommentare kümmern. Die Prozedur SkipWhite() ist zunächst sehr einfach und kurz:

Die erste Version für einfache White-Zeichen: Skipwhite() (V 1.0):

Code: Alles auswählen

  Procedure SkipWhite()
      
    ; solange in Look ein White
      While IsWhite(Look)
	        GetChar()
      Wend
	    
  EndProcedure
Starten wir den Scanner! Ah! Das Ergebnis ist im Vergleich zu vorher schon besser, alle White-Zeichen (alle, die wir in IsWhite() definiert haben) sind verschwunden. Nur mehr gültige Token-Lexem-Paare werden auf Anforderung an den Parser übergeben werden. Der Datenmüll oder das Datenrauschen dazwischen wird den Parser nie mehr erreichen, der Scanner filtert das heraus.

Code: Alles auswählen

120 | 'x'  | NAME_VARIABLE_03          <=== TOKEN: NAME
 35 | '#'  | 452348                    <=== TOKEN: NUM
 36 | '$'  | Ich bin ein /// String    <=== TOKEN: STRING (mit allen Zeichen von " bis ")
 43 | '+'  | +                         <=== TOKEN: OTHER (Zeichen selbst wird als Token-Code übernommen)
 45 | '-'  | -                         <=== TOKEN: OTHER  -"-
 61 | '='  | =                         <=== TOKEN: OTHER  -"-
 60 | '<'  | <                         <=== TOKEN: OTHER  -"-
 62 | '>'  | >                         <=== TOKEN: OTHER  -"-             
 60 | '<'  | <                         <=== TOKEN: OTHER  -"- 
                                            Das Leerzeichen zwischen <  > ist verschwunden!
                                            Anmerkung dazu weiter unten.
 62 | '>'  | >
 35 | '#'  | 6                         <=== TOKEN: NUM
                                            DAS / ZWISCHEN 6/2 IST WEG  ->  D A S   I S T   F A L S C H !!!
 35 | '#'  | 2                         <=== TOKEN: NUM
120 | 'x'  | ZEILENKOMMENTAR           <--- Hier müssen wir noch etwas mit den Kommentaren tun.
 42 | '*'  | *                              ...
120 | 'x'  | BLOCKKOMMENTAR                 ...
 42 | '*'  | *                              ...
'0'-Token beendet (außerhalb While-Schleife)
Anmerkung: Wo ist das "//" vor dem Wort "Zeilenkommentar" hingekommen? Wo ist das "/" zwischen "6/2". Die "/" hat SkipWhite() als einfache White-Zeichen übersprungen. Dasselbe gilt für das "/" vor "*" bei "Blockkommentar" und danach.

Das Problem damit ist nur, das ist nicht richtig!
Was ist, wenn wir eine Division als mathematischen Ausdruck wie hier "6/2" in unserem Source-Code haben?
Eben! Der Scanner schluckt auch alle einfachen "/"-Zeichen. Das wäre kein Problem, wenn wir wie Pure Basic zum Beispiel ";" als Kommentarbeginn definiert hätten, wir verwenden aber wie C das doppelte "/", also "//" als Zeilenkommentar und die Kombination "/* ... */" als Blockkommentar.

Das ist aber leicht zu reparieren.

Die zweite Version für einfache White-Zeichen: Skipwhite() (V 2.0):

Code: Alles auswählen

  Procedure SkipWhite()
      
    ; 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
Diese Version schaut zunächst seltsam umständlich aus. Die umständliche Vorgangsweise ergibt nachfolgend einen Sinn.

Wenn wir den Scanner jetzt laufen lassen, dann passt das Ergebnis: Alle "/" sind als einfache Other-Zeichen wieder da.

Code: Alles auswählen

120 | 'x'  | NAME_VARIABLE_03
 35 | '#'  | 452348
 36 | '$'  | Ich bin ein /// String
 43 | '+'  | +
 45 | '-'  | -
 61 | '='  | =
 60 | '<'  | <
 62 | '>'  | >
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 6
 47 | '/'  | /
 35 | '#'  | 2
 47 | '/'  | /
 47 | '/'  | /
120 | 'x'  | ZEILENKOMMENTAR
 47 | '/'  | /
 42 | '*'  | *
120 | 'x'  | BLOCKKOMMENTAR
 42 | '*'  | *
 47 | '/'  | /
'0'-Token beendet (außerhalb While-Schleife)
Abschließende Bemerkungen zum SkipWhite-Vorgang:

Oben in der Code-Box habe ich als Beispiel den Ungleich-Operator "<>" als beliebiges Beispiel hergenommen (einmal mit und einmal ohne Leerzeichen dazwischen: "<>" und "<.>"), um zu zeigen:
Für den Parser werden folgende Situationen keinen Unterschied machen, alles fließt über die Zeilenenden, Leerzeichen, Tabulatoren, Kommentare hindurch. Das macht die Programmiersprache ungemein flexibel. Tatsächlich ist es so, dass es schwieriger ist, solche Flexibilitäten zu verbieten (also z.B. Zeilenenden mehr beachten), als sie zu erlauben.

Jedes "if(a<>2)" hier sollte die exakt identische Token-Lexem-Folge ergeben:

Code: Alles auswählen

if (a <> 2) 

if (a  <   >  2)

if (a <
      > 
      2 )
Erzeugen Sie sich selbst einfach eine solche ".tc"-Datei, die einen ähnlichen Inhalt wie in der Code-Box oben hat, machen Sie Tabulatoren, Leerzeichen usw., dann lassen Sie sie scannen.
Sie werden sehen, dass die Token-Lexem-Paare brav hintereinander kommen, die Zeilenumbrüche, die Leerzeilen, die Tabulatoren, alles ist weg. Hier mein Ergebnis:

Code: Alles auswählen

120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
'0'-Token beendet (außerhalb While-Schleife)
Wir sehen 3-mal dieselben "if(a<>2)", egal wie sie im Source-File geschrieben wurden. Leerzeichen, Zeilenenden, ja sogar Kommentare zwischen den Tokens (müssen wir erst einbauen, siehe nächstes Kapitel) werden vom Scanner vollständig entfernt, es bleiben nur gültige Token-Lexem-Paare für den Parser übrig.


4.7.5. SkipLineComment(), das Überspringen von Zeilenkommentaren

Die große Frage, die sich stellt, ist: Wo fangen wir die Kommentare ab?
Wer Englisch nicht scheut, kann in Crenshaw eine Diskussion über das Abfangen von Kommentaren lesen.

Möglichkeit 1 ist, das bereits in GetChar() zu tun, dann sind aber in Strings auch keine "//" und "/*" erlaubt, mehr noch, der Scanner würde im String in den Kommentar-Modus springen und Dinge aus dem Char-Stream herausschneiden. Das kann man zwar wieder mit einem Statusflag (z.B. IsStringMode oder Ähnliches) vermeiden, aber der Aufwand lohnt sich meiner Meinung nach nicht. Besser ist Methode 2.

Möglichkeit 2, die ich in meiner Implementation wähle, ist, die Kommentare in SkipWhite() abzufangen.
Das habe ich in IsWhite() bereits vorbereitet. Wer sich gewundert hat, warum eines der White-Zeichen in IsWhite() ein "/" ist und warum wir dann in SkipWhite() wieder bei "/" zurückspringen (wirkt sinnlos), der bekommt jetzt die Erklärung dafür.
"/" muss ein White-Zeichen sein, sonst wird unsere Abfrage in der gleich folgenden erweiterten SkipWhite()-Prozedur nie erreicht, da der Kopf der While-Schleife für ein Verlassen der Schleife sorgt.

Das für Zeilenkommentare erweiterte SkipWhite() (V 3.0):

Code: Alles auswählen

	Procedure SkipWhite()
      
    ; solange in Look ein White
      While IsWhite(Look)
          
          ; Zeilenkommentar (// ... #LF/0-Byte)
            If Look='/' And PeekA(*Source_Code+Source_Position)='/'
                SkipLineComment()                   

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

          ; sonstiges White-Zeichen überspringen
            Else
                GetChar()
            EndIf
          
	    Wend
	    
	EndProcedure
Wir erweitern die While-Schleife um eine If-ElseIf-Abfrage mit Else-Block.

Sollte ein Zeilenkommentar, der mit "//" beginnt, erkannt werden, dann springt das Programm nach SkipLineComment() (=überspringe Zeilenkommentar).
In Look ist ja bereits ein "/", denn das hat ja den Einsprung in die While-Schleife erlaubt. Source_Position wurde von GetChar bereits um 1 erhöht, d.h. es steht exakt richtig auf dem Look unmittelbar nach dem 1. "/" (Anmerkung: Diesmal wirklich auf dem exakt nächsten Zeichen, d.h. Leerzeichen zwischen Kommentarerkennungszeichen sind anders wie bei zum Beispiel "< >" nicht erlaubt). Dieses Zeichen sollte auch "/" sein und wir haben einen Line Comment erkannt.

Sollte nach "/" irgendetwas anderes als "/" folgen (wie bei uns 6/2, da folgt nach "/" ein "2"), dann bleibt das "/" als Token-Lexem im Token-Lexem-Stream und wird auch als "/" (Other) an den Parser weitergereicht, weil KEIN GetChar() erfolgt, sondern sofort ein ProcedureReturn.


Die Prozedur SkipLineComment():

Code: Alles auswählen

  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
SkipLineComment() überspringt so lange alle Zeichen, bis es am Zeilenende (erinnern wir uns an Line Feed #LF und Linux!) angelangt ist.

Ein Sonderfall ist, wenn in einem Source-File der Cursor nach dem allerletzten Zeichen nicht weiterbewegt wurde, vom Programmierer insbesondere kein {enter} gedrückt wurde. Wenn die letzte Zeile eines Programms ein Zeilenkommentar ohne Enter ist, dann kommt kein Zeilenende, also auch kein #LF. Der Scanner stürzt ab und läuft im Speicher nach dem 0-Byte Amok, vielleicht trifft er ja irgendwann zufällig auf ein #LF (= Zahl 10) oder auch nicht. Dieses Problem werden wir auch in SkipBlockComment() nicht vergessen.
Diesem Fehler bin ich aufgesessen und habe ewig danach gesucht. Die Lösung ist bestechend einfach. Sehen Sie sich diese in der Code-Box an.

Eine andere Möglichkeit wäre, einfach am Ende jedes allozierten *Source_Code statt mit size+1 ein 0-Byte anzuhängen, händisch ein #LF und dann ein 0-Byte anzufügen. Habe ich auch schon gemacht, ich mag die vorige Lösungsvariante mehr. Wieder gilt: Geschmäcker ...

Jetzt können wir wieder "Scanner_Test02.tc" scannen lassen:

Code: Alles auswählen

120 | 'x'  | NAME_VARIABLE_03
 35 | '#'  | 452348
 36 | '$'  | Ich bin ein /// String
 43 | '+'  | +
 45 | '-'  | -
 61 | '='  | =
 60 | '<'  | <
 62 | '>'  | >
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 6
 47 | '/'  | /                <=== TOKEN: OTHER, KORREKT!
 35 | '#'  | 2                
                              <=== ZEILENKOMMENTAR IST WEG, KORREKT!
 47 | '/'  | /                <--- Skip: Noch als OTHER gehandhabt
 42 | '*'  | *                <--- Skip: Noch OTHER 
120 | 'x'  | BLOCKKOMMENTAR   <--- Skip: Noch NAME 
 42 | '*'  | *                <--- Skip: Noch OTHER 
 47 | '/'  | /                <--- Skip: Noch OTHER 
'0'-Token beendet (außerhalb While-Schleife)
Sehr schön, der Zeilenkommentar ist verschwunden, der Blockkommentar ist natürlich noch da. Auch das "/" in "6/2" ist als Other-Zeichen korrekt vorhanden.


4.7.6. SkipBlockComment(), das Überspringen von Kommentarblöcken

Die Prozedur SkipWhite() muss zunächst für die Verwendung von Block-Kommentaren angepasst werden.

Das für Blockkommentare erweiterte SkipWhite() (V 4.0):

Code: Alles auswählen

	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

          ; sonstiges White-Zeichen überspringen
            Else
                GetChar()
            EndIf
          
	    Wend
	    
	EndProcedure
Wir erweitern die While-Schleife um einen weiteren ElseIf-Block.


Die Prozedur SkipBlockComment():

Code: Alles auswählen

  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
  • Zunächst wird "/" übersprungen und Look steht auf "*".
REPEAT
  • Nach dem ersten Eintritt in die Repeat-Schleife holt GetChar() das nächste Look und überspringt damit "*".
    In der laufenden Repeat-Schleife holt ChetChar() immer den nächsten Look Ahead Character.
  • Sollte irgendwann innerhalb des Blockkommentars wieder "/*" folgen, wird voll auf Rekursion gesetzt und erneut SkipBlockComment() aufgerufen. Verschachtelte Kommentare sind also kein Problem und bereits eingebaut.
    --> bei Punkt 1 gehts in der neuen Instanz von SkipBlockComment() wieder los.
UNTIL Look = "*/"
  • 2-mal GetChar(), um "*/" zu überspringen, damit Look auf 1. Zeichen nach "*/" steht.

Daher sind folgende Situationen kein Problem:

Code: Alles auswählen

/**/
/*/**/*/
Jetzt können wir wieder "Scanner_Test02.tc" scannen lassen ...

Code: Alles auswählen

120 | 'x'  | NAME_VARIABLE_03
 35 | '#'  | 452348
 36 | '$'  | Ich bin ein /// String
 43 | '+'  | +
 45 | '-'  | -
 61 | '='  | =
 60 | '<'  | <
 62 | '>'  | >
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 6
 47 | '/'  | /                <=== TOKEN: OTHER, KORREKT!
 35 | '#'  | 2
'0'-Token beendet (außerhalb While-Schleife)
... und stellen fest. Der Blockkommentar ist verschwunden, das einfache "/" in "6/2" ist korrekterweise noch da! Voila!

Testen Sie, testen Sie, testen Sie! Verschachteln Sie Kommentare, ignorieren Sie Zeilenenden. Schauen Sie, ob alles funktioniert!


4.7.7. Die Error()-Prozeduren

Wir können bereits auf Scanner-Ebene eine einfache Fehlerbehandlung realisieren.
Sie haben sicher bemerkt, dass alle Get()-Prozeduren (als Beispiel drucke ich GetNum() in der folgenden Code-Box ab) eine Abfrage ihrer entsprechenden Is?()-Prozedur eingebaut haben. Wofür?

Code: Alles auswählen

  Procedure GetNum() 
  
    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
  
    ; 1. Zeichen korrekt fuer Num?
      If Not IsNum(Look):Expected("Integer"):EndIf  <=== HIER BEFINDET SICH DIE GEMEINTE ABFRAGE
                                                         
    ; 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
Der Parser wird in bestimmten Situationen nicht immer GetToken() aufrufen. Wenn er zum Beispiel weiß, dass er sicher einen Name oder eine Num erwartet, dann ruft er gleich GetName() bzw. GetNum() auf. Sollte jetzt im Source-Code z.B. kein Name folgen, den der Parser erwartet, dann erhalten wir richtigerweise eine Fehlermeldung.
Die beiden Fehlerprozeduren, die das ermöglichen, erklären sich selbst.

Auf ein "Fehler in Zeile X" verzichte ich der Einfachheit halber, vielleicht baue ich das später ein. Es ist nicht schwer zu realisieren, aber je mehr Programmzeilen wir erzeugen, desto unübersichtlicher wird der Code und ich möchte eigentlich beim Thema Compilergrundlagentechnik bleiben. Wenn man dann diese sicher und zuverlässig verstanden hat, dann kann man den Compiler später "aufpeppen". Außerdem lasse ich den Compiler beim ersten Fehler, den er findet, enden, es wird keine Warnungsliste oder dergleichen erstellt.

Code: Alles auswählen

  Procedure Error(error_message.s)
      MessageRequester("Fehler",error_message)
      End
  EndProcedure

Code: Alles auswählen

  Procedure Expected(expected_object.s)
      Error(expected_object+" wird erwartet.")  
  EndProcedure
4.8. Schlussbemerkungen

So, wir haben einen Scanner, der unseren Ansprüchen zunächst genügen wird. Sollten Änderungen da und dort nötig werden, werden diese im Laufe der weiteren Programmentwicklung nachträglich eingebaut werden.


Der Scanner wird folgendermaßen aufgerufen, verwendet und wieder beendet:
  • Start: Gestartet wird er vom Parser mit Scanner::Start(Name des Source-Files.FileExtension)
  • Lauf: Weitergetrieben wird er vom Parser mit Scanner::GetToken(), Scanner::GetName(), Scanner::GetNum(), Scanner::GetString(), Scanner::GetOther() - je nach Verwendungszweck. Für besondere Fälle steht auch Scanner::GetChar() zur Verfügung, doch Vorsicht, den Scanner nicht aus dem Schritt bringen mit dem Lesen von einzelnen Look Ahead Charactern!
  • Ende: Da der Scanner ein 0-Byte am Ende von *Source_Code findet und als Other-Token zurückgibt, bietet es sich an, dass der Parser das als End-Of-Source-File verwendet, um sich zu beenden.

Ein kleiner Scherz zuletzt, der aber die Leistungsfähigkeit des Scanners zeigt:

Code: Alles auswählen

if (a <> 2) 

if (a  <  /*Kommentar mitten im Ungleich-Operator gefällig*/ >  2)

if (a <   // kleiner
      >   // größer
      2   // Nummer 2 
      /* noch ein Blockkommentar vor der Klammer gefällig*/ )
Es sollte dennoch nur 3-mal "if(a<>2)" gescannt werden und alles andere herausgefiltert sein.
Mein Scanner gibt aus:

Code: Alles auswählen

120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
120 | 'x'  | IF
 40 | '('  | (
120 | 'x'  | A
 60 | '<'  | <
 62 | '>'  | >
 35 | '#'  | 2
 41 | ')'  | )
'0'-Token beendet (außerhalb While-Schleife)
Was allerdings nicht funktioniert (weder gewollt noch üblich), sind Kommentare mitten in Token-Lexemen (also z.B. mitten in Namen oder Nummern).
Kommentare (jedes White) sind aber an jeder Stelle zwischen Token-Lexemen möglich.

*** ENDE KAPITEL 4 ***

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 19.09.2013 20:36
von computerfreak
wirklich super :allright: :allright: :allright: :allright:
Bitte unbedingt weitermachen !

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 20.09.2013 18:32
von puretom
*** KAPITEL 5 ***

5. Kurze Einführung in Assembler/Maschinensprache



5.1. Vorbemerkungen

Diese Einführung stellt noch nicht die genaue Darstellung der VM dar.
Sie ist gedacht, um dem Leser einen Leitfaden zu geben, damit er den Vorgang des Komplilierens versteht, vor allem den Code des mathematischen Expression Parsers.




5.2. Was ist Maschinensprache?

Maschinensprache ist die Sprache, die die CPU bzw. die VM (wenn wir eine Virtual Machine haben) wirklich versteht.
Die einzelnen Opcodes (=Operationscodes, Befehle) tun zumeist recht elementare Dinge, wie z.B. addieren, subtrahieren, springen, usw.


Ein Assemblerprogramm besteht oft aus 3 Elementen:
  • Zeilen mit Opcodes, das sind einzelne Befehle:

    Code: Alles auswählen

         push Const 4   // Opcode "push Const" mit Paramenter "4"
     push Const 3   // Opcode "push Const" mit Paramenter "3"
     add            // Opcode "add" ohne Paramenter
  • Zeilen mit Labels, das sind Stellen/Positionen im Programm, man nennt sie auch Sprungmarken, weil sie mit Sprungbefehlen angesprungen werden können:

    Code: Alles auswählen

         push Const 40     
     push Const 30         
     push Const 1   // 1 liegt am oben am Stack
     JZ WEITER      // Jump if Zero -> wenn Stack=0, dann springe zu Label "WEITER"
                    // (ist er hier aber nicht, oberstes Element = 1)
     sub
[WEITER]            // Label (viele ASM-Sprachen verwenden Label wie PB mit ":"  
                    // dahinter, unsere schauen so aus)
     add
  • Zeilen mit Pseudobefehlen, das sind Anweisungen an den Assembler:

    Code: Alles auswählen

    [v_BREITE] int      // Anweisung an den Assembler, sich für diese Variable im Speicher
                    // einen Speicherort in einer Liste zu merken. Es wird kein ASM-Code
                    // erzeugt, nur der Ort (=Index-Nummer) vom Assembler intern notiert.



5.3. Was ist ein Stack?

Ein Stack ist ein Speicherbereich, der wie ein Stapel oder Keller aussieht.

Was man oben als Letztes drauflegt, muss man auch wieder als Erstes nehmen.
Dieses Prinzip nennt man auch Last-In-First-Out-Prinzip (LIFO), also "Als Letztes rein, als Erstes raus" genannt.

Zum Arbeiten mit dem Stack werden zumeist folgende Operationen zur Verfügung gestellt:
  • push (schieben, stoßen) legt das Objekt oben auf den Stapel.
  • pop (nehmen) liefert das oberste Objekt und entfernt es vom Stapel.
    Bei manchen Prozessoren wie dem MOS Technology 6502 wird diese Aktion dagegen pull (herunterziehen) genannt.
  • peek (nachsehen) liefert das oberste Objekt, ohne es zu entfernen.
(Zitat vgl: http://de.wikipedia.org/wiki/Stapelspei ... onsprinzip)


Ein Beispiel mit dem Stack:

Code: Alles auswählen

push 6  push 1  push 7   pop     pop    peek    push 2  push 3

                +---+                                   +---+
                + 7 +                                   + 3 +
        +---+   +---+   +---+                   +---+   +---+
        + 1 +   + 1 +   + 1 +                   + 2 +   + 2 +
+---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
+ 6 +   + 6 +   + 6 +   + 6 +   + 6 +   + 6 +   + 6 +   + 6 +
+---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+



5.4. Auswerten von mathematischen Ausdrücken in Assembler

Zum Auswerten nicht nur, aber besonders von mathematischen Ausdrücken benötigt man unbedingt einen Stack.
Jeder weiß, dass man in einer mathematischen Rechnung z.B. die Punktrechnungen vor den Strichrechnungen berechnet und dass z.B. Klammerausdrücke überhaupt die höchste Prioriät haben.

Damit, wie man das in ASM kompiliert, beschäftige ich mich im nächsten Kapitel, jetzt kümmern wir uns darum, dass wir das von Hand in ASM können, um zu verstehen, was der Compiler übersetzt.



5.4.1. Berechnungen in einer Stack Machine

Unsere Virtual Machine soll eine Stack Machine werden.
Stack Code ist am leichtesten durch einen Compiler zu erzeugen.

Nehmen wir folgende Rechnung:

Code: Alles auswählen

1+2*3
Wir sehen auf den ersten Blick, dass wir 2*3 zuerst auswerten müssen.
Versuchen wir einen intuitiv verständlichen Stack Code dafür zu schreiben.

Code: Alles auswählen

push Const 1
push Const 2
push Const 3
mul
add
Mit einer Grafik wird alles klar:

Code: Alles auswählen

        push 1  push 2  push 3   mul             add  
                                 2*3=6 ---.      1+6=7 ---.
                        +---+     ^       |       ^       |             
                        + 3 +     |       v       |       |              
                +---+   +---+     |     +---+     |       |
                + 2 +   + 2 +     |     + 6 +     |       v 
        +---+   +---+   +---+   +---+   +---+     |     +---+                
        + 1 +   + 1 +   + 1 +   + 1 +   + 1 +     |     + 7 +                
+---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
Ich möchte für Sie in Worte fassen, was hier passiert ist:
  • Stack ist leer (bzw. in einem bestimmten Ur-Zustand)
  • push 1: auf dem Stack liegt 1 (rechts hier ist oben beim Stack)
  • push 2: auf dem Stack liegt 1,2
  • push 3: auf dem Stack liegt 1,2,3
  • mul:
    • entfernt die beiden obersten Elemente vom Stack: 1
    • multipliziert sie --> 6
    • pusht das Ergebnis auf den Stack: 1,6
  • add:
    • entfernt die beiden obersten Elemente vom Stack: -
    • addiert sie --> 7
    • pusht das Ergebnis auf den Stack: 7
  • Stack ist nicht leer, d.h es ist 1 Element mehr als im Ur-Zustand am Stack, nämlich das Ergebnis der Rechnung "1+2*3".
Man sieht, dass das Erzeugen von Stack-Code recht einfach sein wird, denn der Stack ist implizit immer vorhanden.

Anders gesagt: Um die Stackverwaltung braucht sich der Compiler keine Sorgen machen, darum kümmert sich die Zielmaschine (hier unsere Stack-VM), auf dem das Programm dann abläuft, durch die Opcodes von selbst.

Die meisten echten CPUs sind allerdings keine Stack Machines, Stack Machines sind ein Domäne der Virtuellen Maschinen (der Klassiker: Die Java Virtual Machine).



5.4.2. Berechnungen in einer Registermaschine mit wenig Registern

Die meisten Silikon-CPUs (also die echten) sind Register-Maschinen, d.h. sie haben mehr oder weniger in der CPU liegende schnelle Speicherstellen.

Nehmen wir den Fall, wir kompilieren auf eine CPU, die wenige Register zur Verfügung hat.

Stellen wir uns vor, wir hätten 2 Register zur Verfügung: EAX, EBX (nur "zufällig" ähnlich dem x86).
Und natürlich haben wir auch einen Stack. Eine Registermaschine kann aber nur IN den Registern rechnen, anders als die Stack Machine, die direkt vom und zum Stack rechnet. Auch Werte können wir nur mit den Registern laden.

D.h. wir müssen bei einer Register Machine unseren Stack von Hand bedienen und die Register, in denen wir rechnen, von Hand laden (pop) und von Hand auf den Stack sichern (push).

Nehmen wir wieder die Rechnung:

Code: Alles auswählen

1+2*3
Wir sehen auch jetzt wieder auf den ersten Blick, dass wir 2*3 zuerst auswerten müssen.

Code: Alles auswählen

mov   EAX, 1    // lade Register EAX mit 1, da wir es laufend benötigen, müssen wir den Inhalt immer wieder sichern
push  EAX       // push 1 (= sichern des Inhalts auf den Stack)
mov   EAX, 2    // lade Register EAX mit 2
push  EAX       // push 2
mov   EAX, 3    // lade Register EAX mit 3
push  EAX       // push 3
pop   EAX       // pop Stack nach EAX = 3, Rechenregister laden, wir können nur IN den Registern rechnen
pop   EBX       // pop Stack nach EBX = 2, Rechenregister laden, wir können nur IN den Registern rechnen
mul   EAX, EBX  // EAX(6) = EAX(3) * EBX(2)
push  EAX       // push 6
pop   EAX       // pop Stack nach EAX = 6, Rechenregister laden, wir können nur IN den Registern rechnen
pop   EBX       // pop Stack nach EBX = 1, Rechenregister laden, wir können nur IN den Registern rechnen
add   EAX, EBX  // EAX(7) = EAX(6) + EBX(1)
push  EAX       // push 7 (wenn wir das Ergebnis am Stack wollen)
Wirklicher ASM-Code schaut noch ein bisschen anders aus, etwas effizienter, denn das hier ist ein bisschen tollpatschig.
Denken Sie sich die unnötigen "push EAX -> pop EAX" einfach weg, dann ist die Sache realistisch, aber auch verwirrender. Deshalb für unsere Zwecke, gut so.

Ich denke aber, der Unterschied zur Stack Machine ist klar:
  • Stack von Hand pushen und popen
  • Rechnen und laden nur in Registern

Im Internet gibt es unzählige Diskussionen, ob man seine VM nun als Stack Machine (wie die Java) oder als Register Machine (wie Googles Dalvik) programmiert.
Instinktiv und auf den ersten Blick wirkt Register Code länger und umständlicher, aber das ist nur ein Scheinargument. Ich habe im Internet viel darüber gefunden, dass auch Register-VMs hocheffizient sind. Weiter möchte ich die Diskussion gar nicht vertiefen. Mir ging es nur um eine kurze Einführung, um den Unterschied zu zeigen.

Eins ist aber klar:
Beim Kompilieren und zum Lernen des Compilerbaus ist eine Stack Machine leichter und ideal.
Wer die Stack Machine kann, der kann auch (auf den ersten Blick umständlicheren) Register Code schreiben.

*** ENDE KAPITEL 5 ***

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 20.09.2013 20:24
von puretom
... Platzhalter - Umbau ...

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 20.09.2013 22:20
von puretom
... Platzhalter ...

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 21.09.2013 21:11
von puretom
Simple mathematische Ausdrücke funktionieren (sehr rudimentär noch)

LG Puretom

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 21.09.2013 23:43
von puretom
Jetzt auch mit globalen Variablen.

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 22.09.2013 12:29
von puretom
Liebe PB-Gemeinde!

Ich habe mich dazu entschlossen, den mathematischen Parser doch vor der Programmiersprache zu machen, denn ich habe erkannt, dass die ganzen Simple-Prozeduren alles nicht vereinfachen, sondern im Gegenteil eher komplizieren, sie sind die Arbeit nicht wert, weil mit einem mathematischen Parser vieles wie von selbst sich ergibt beim Parsen.

Ich mache ja immer dazwischen scheinbar sinnlose "Zwischenmeldungen" (mit eben dem Hintergedanken bezüglich eventuellen Umbauens), jetzt kann ich sie nutzen und die Änderungen einfüllen.

Ich baue deshalb umfangreich um!

Das ist der Preis mir zuzusehen, dass ich das in "real time" mache. :wink:

LG
Puretom

P.S. Hoffentlich ist niemand böse, aber es muss sein und macht viel Mühe jetzt.

P.P.S. Kommt alles wieder - nichts ist verschwunden -, nur übersichtlicher und besser strukturiert, versprochen!

Re: [Tutorial] Compiler und Virtual Machine

Verfasst: 22.09.2013 15:52
von RSBasic
@puretom
Bitte verwende möglichst nicht so viele Formatierungen wie rote Schrift und große Schrift, sonst sieht es zu bunt und chaotisch aus.
Ein bisschen hervorheben kannst du schon, aber nicht gleich übertreiben. ;)
Alle Zeiten sind UTC+02:00
Seite 3 von 10

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de