Seite 1 von 3

Tutorial - Compiler und Virtual Machine (nicht beschreiben)

Verfasst: 07.10.2013 16:21
von puretom
In diesem Thread hier bitte nichts schreiben


Nach Rücksprache mit Moderator NicTheQuick teile ich mein Tutorial in einen Teil, wo nur das Tutorial sein soll und einen anderen Teil mit Diskussionsbeiträgen.

Technisches Vorwort vor dem Vorwort: :wink:

  • Dieser Thread ist der Tutorial-Thread zu [Tutorial] Compiler und Virtual Machine:
    • Hier sollte nur das Tutorial sein, sonst nichts.
    • Hier bitte nichts beschreiben, keine Anmerkungen und Kritik.
    • Moderator NicTheQuick ist so nett und wirft alles, was hier nicht hereingehört, in den Mülleimer!

  • Der Diskussionsthread zu dem Tutorial hier ist [Tutorial] Compiler und Virtual Machine.
    • Anmerkungen und Kritik, Lob sowie sonstige Meldungen bitte im Diskussionsthread!

Viel Spaß mit dem Tutorial und liebe Grüße

Puretom


In diesem Thread hier bitte nichts schreiben

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 17:09
von puretom
INHALT IM ÜBERBLICK


TEIL EINS: EINLEITUNG
  • 1. Vorwort und Ziele des Tutorials
  • 2. Literaturempfehlungen
  • 3. Überblick über die Arbeitsweise eines Compilers und einer Virtuellen Maschine

TEIL ZWEI: TINY TOY C
  • 4. Lexikalischer Scanner
    5. Kurze Einführung in Assembler/Maschinensprache
    6. Compiler TTCC und Parser TTCP

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 17:29
von puretom
GESAMTINHALTSVERZEICHNIS


TEIL EINS: EINLEITUNG
  • 1. Vorwort und Ziele des Tutorials
    • 1.1. Zu meiner Person
      1.2. Der Plan
      1.3. Aufbau und Konzept des Tutorials
  • 2. Literaturempfehlungen
    • 2.1. Literatur, die mir half, meinen ersten Compiler zu programmieren
      2.2. Literatur, die hilfreich ist, wenn man schon eine Ahnung von Compilern hat
      2.3. Literatur, die mir persönlich überhaupt nichts sagte
      2.4. Abschließende zusammenfassende Betrachtungen
  • 3. Überblick über die Arbeitsweise eines Compilers und einer Virtuellen Maschine
    • 3.1. Vorbemerkungen
      3.2. Graphischer Überblick über die einzelnen Komponenten des Projekts
      3.3. Erklärung der einzelnen Komponenten
      • 3.3.1. Der Compiler
        3.3.2. Der Assembler
        3.3.3. Die Virtual Machine
      3.4. Zusammenfassung


TEIL ZWEI: TINY TOY C

  • 4. Lexikalischer Scanner
    • 4.1. Vorbemerkungen
      4.2. Hintergrundgedanken zum Scanvorgang
      4.3. Das Grundgerüst des Scanners
      4.4. Laden und testen des Character Streams
      4.5. Die ENTER-Taste: das Ende einer Programmzeile
      4.6. Die Is?()-Token-Typ-Erkennungsmacros
      4.7. Die Get-Prozeduren und die Token-Codes
      4.8. Überspringen unnötiger Zeichen
      • 4.8.1. Filtern von White-Zeichen: SkipWhite
        4.8.2. Filtern von Zeilen-Kommentaren
        4.8.3. Filtern von Block-Kommentaren
      4.9. Primitive Fehlerbehandlung
      4.10. Schlussbemerkungen
      4.11. Der Scanner TTCS von Kapitel 4
  • 5. Kurze Einführung in Assembler/Maschinensprache
    • 5.1. Vorbemerkungen
      5.2. Was ist Maschinensprache
      5.3. Was ist ein Stack (Stapelspeicher)?
      5.4. Auswerten von mathematischen Ausdrücken in Assembler
      • 5.4.1. Berechnungen in einer Stack Machine
        5.4.2. Berechnungen in einer Registermaschine mit wenig Registern
  • 6. Compiler TTCC und Parser TTCP
    • 6.1. Wichige Überlegungen, bevor wir starten
      • 6.1.1. Umfang der Sprache TTC 0.5
        6.1.2. Das Modul-, Include-File- und Aufrufkonzept
        6.1.3. Fehlerbehandlung
      6.2. Das Statement
      6.3. Deklarieren globaler Variablen
      6.4. Ein-/Ausgabe auf unterstem Level
      • 6.4.1. Input (Console)
        6.4.2. Print (Console)
      6.5. Variablenzuweisung (Assignment) an globale Integer-Variablen
      6.6. Mathematische Ausdrücke (Expression) mit Integers
      • 6.6.1. Einfache positive konstante Werte (=Values)
        6.6.2. Variablennamen
        6.6.3. Einfache Ausdrücke (Simple Expressions) mit 2 oder mehr Operanden
        6.6.4. Klammerausdrücke
      6.7. Sprünge
      • 6.7.1. Einleitung
        6.7.2. Goto und Sprungmarken (Labels)
        6.7.3. Gosub und return
      6.8. Die bedingte Anweisung if und die Verzweigungen if-else und if-else if-else
      • 6.8.1. Einige Vorbemerkungen
        6.8.2. If-Statement
        6.8.3. If-else-Statement
        6.8.4. If-else if-else-Statement
      6.9. Blocks von Statements und Schleifen
      • 6.9.1. Blocks von Statements
        6.9.2. Die Schleifen Do-While, Do-Until, Do: Das fußgesteuerte Universalgenie
        6.9.3. Die While-Schleife: Der kopfgesteuerte Klassiker
        6.9.4. Die For-Schleife, kein Befehl für TTC 0.5
        6.9.5. Break und continue
      6.10. Rand und end
      6.11. Abschließende Bemerkungen
      6.12. Code-Teil des Parsers

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 18:05
von puretom
TEIL EINS: EINLEITUNG


    • 1. Vorwort und Ziele des Tutorials
      2. Literaturempfehlungen
      3. Überblick über die Arbeitsweise eines Compilers und einer Virtuellen Maschine


Ziel von TEIL EINS ist, nach einem kurzen Vorwort, das die Ziele des Tutorials erläutern will, eine Zusammenfassung der Literatur zu bieten, in der ich mir mein Wissen über Compiler, Virtuelle Maschinen und Scripting angelesen habe.

Zuletzt möchte ich gerne einen kurzen Überblick über die Arbeitsweise eines Compilers und einer Virtuellen Maschine geben.

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 18:05
von puretom
1. Vorwort und Ziele des Tutorials



1.1. Zu meiner Person

Hi Leute! Ich bin ganz neu in diesem Forum, aber nicht bei Pure Basic, das ich schon seit Ewigkeiten besitze. In diesem Forum lese ich schon seit Jahren mit.
Ich bin mittleren Alters :D (Generation Commodore 64!) und programmiere auch schon seit dieser Zeit (also C64-Basic und 6502/6510 Assembler). Ich bin aber ausdrücklich ein Hobbyprogrammierer in der Freizeit, also kein Profi, somit sind alle Angaben, die ich mache, durchaus laienhaft und für den Hausgebrauch.
Alle Angaben sind ohne Gewähr und mit Vorsicht zu genießen. Ich gebe alles aufgrund meiner ureigensten Privatmeinung hier zum Besten.

Nichts davon ist zum kommerziellen Gebrauch gedacht.




1.2. Der Plan

Ich beginne eine Tutorialserie, die sich mit den grundlegenden Techniken der Compilerprogrammierung und der Programmierung einer kleinen Virtual Machine (Abkürzung: VM) beschäftigt.
Der Compiler, den ich vorstelle, soll eine Skriptsprache in eine virtuelle Assemblersprache kompilieren. Eine Virtuelle Maschine soll die Programme dann ausführen.

Das ist ein Konzept, das so ziemlich in jedem heutigen PC-Spiel zur Anwendung kommt, wenn dort Scripting vorgesehen ist. Die meisten Shooter erstellen und steuern auf diese Weise Objekte (Charakter, Gegenstände, Türen, ...). Jedes Adventure arbeitet mit Skripten. Der Flight Simulator von MS arbeitet bei Szenarien damit, uvm.

Einer meiner Beweggründe für dieses Projekt ist auch, dass es eigentlich kaum bis nichts Brauchbares auf Deutsch gibt, diese Lücke würde ich gerne zu schließen versuchen.

Im ersten Teil veröffentliche ich meine ganz persönliche Literaturtippliste an.

Sollte der Wunsch bestehen, dass ich mit meinem Plan weitermache, bitte um rege Nachfrage ausschließlich im Diskussionsthread, dann mache ich weiter.




1.3. Aufbau und Konzept des Tutorials

Das Tutorial soll neben seiner Kapiteleinteilung in so genannte Teile eingeteilt gegliedert werden.

Diese Teile sollen jeweils ein kleines vollständiges Projekt beeinhalten, um recht schnell erste Erfolgserlebnisse zu haben.

Alle Komponenten (also die Skriptsprache, die Virtuelle Maschine, ...), die wir schreiben, sollen das Wort "TOY" vorangestellt haben, was so viel wie Spiel/Spielzeug meint und ausdrücken soll, dass unsere Ergebnisse zu Lern- und Spielzwecken gedacht sind.
Das Wort "TOY" soll aber noch etwas ausdrücken: Es handelt sich bei dieser Programmiersprache um eine Skriptsprache, die man in Spielen zum Scripten einsetzen kann.

Zu Beginn jedes Teiles werde ich in einer kurzen Einführung dessen Ziele erläutern.
Wie in einem Fortsetzungsroman sollen nach und nach neue Teile und Kapitel hinzukommen.



HAFTUNGSAUSSCHLUSS und RECHTLICHE HINWEISE

Wenn jemand das Tutorial brauchbar finden sollte, dann kann jeder, der will, nachdem er mir eine Nachricht zukommen hat lassen, um mich um Zustimmung zu fragen (und nachdem ich die Zustimmung erteilt habe), das Tutorial unter folgenden Bedingungen weiternutzen:

Dieser Thread hier muss zuverlässig verlinkt werden, wenn das Tutorial z.B. woanders gebloggt, ins englische Forum oder in welcher Form auch immer übersetzt wird usw.
Jede Nutzung bedarf allerdings meiner Zustimmung eben über eine Nachricht.
Kommerzielle Nutzung des Tutorials, wie z.B. Druck oder dergleichen, ist ohne meine Zustimmung sowieso ausdrücklich verboten.

Wer die Techniken in seine Programmen benutzt, der wäre sehr fair, mich in den Credits seiner Programme zu erwähnen.

Für Schäden, die aus der Nutzung meiner Angaben und Daten entstehen, übernehme ich sicherlich keinerlei Haftung, ich warne sogar davor, meine Angaben zu nutzen und zu verwenden, sie könnten fehlerhaft sein und sie sind sicherlich auch fehlerhaft!

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 18:06
von puretom
2. Literaturempfehlungen



Gerade im Bereich Compilerbau ist es sehr schwer, wirklich brauchbare Literatur zu finden. Natürlich habe ich mir in all den Jahren viel zusammengelesen und bin dann eben zu meiner ganz persönlichen Hit-Liste gekommen.
Viele Bücher in diesem Bereich sind meiner Meinung nach für den Hobbyprogrammierer völlig ungeeignet, obwohl sie tatsächlich immer wieder als Tipps genannt werden. Es stellte sich oft heraus, dass ich nach hunderten Seiten immer noch nicht in der Lage war, einen einfachen Scanner zu programmieren. Woran lag das? Vielleicht an meiner eigenen Begriffsstutzigkeit? Ich habe aber mehrfach gelesen im Netz, dass es nicht nur mir, sondern anderen ebenso erging.

Ein zusätzlicher hemmender Faktor ist, dass die meiste Literatur nur in Englisch vorliegt.
Auch das von mir so hochgelobte Compilerbau-Tutorial von Crenshaw, dem ich eigentlich einen Großteil meines Wissens zu verdanken habe, ist natürlich nur in Englisch zu haben (dafür aber gratis im Internet, was auch ein nicht zu unterschätzender Vorteil ist :lol: ).

Mein Ziel ist es ausdrücklich, es mit meinem Tutorial Crenshaw gleichzutun, ich möchte also einen Crenshaw auf Deutsch machen. Nicht mehr - also kein wissenschaftliches Buch - aber auch nicht weniger.




2.1. Literatur, die mir half, meinen ersten Compiler zu programmieren

Diese Bücher halfen mir schließlich meine ersten lauffähigen Compiler mit Pure Basic zu programmieren.

  1. Let's Build a Compiler, von Jack Crenshaw
    Für mich eine Offenbarung nach ewigem Suchen, für viele leider auf Englisch. Ich muss zugeben, dass ich durch das Lesen dieses Buches wieder in das Englishlesen hineingekommen bin, ich habe nicht nur Compilerprogrammieren durch Crenshaw gelernt.

    Ich werde die Konzepte aus seinem Tutorial hier einfließen lassen.

    Crenshaw kompilert im Original auf Motorola 68000 (der Amiga und der ATARI ST hatten eine CPU auf dieser Grundlage).
    Außerdem verwendet er die Programmiersprache Pascal. Im Netz sah ich auch mal eine C-Version, aber ich gebe offen zu, dass die Pascal-Version für mich lesbarer ist als C.

    Die Originalseite, Motorola 68000
    PDF-Version, besser als im Original formatiert
    besser formatiert, übersichtlich und X86-Code, für mich die derzeit beste Version (derselbe Link wie in der Überschrift)
  2. Blunt Axe Basic: Let's Build a Scripting Engine-Compiler, von S. Arbayo

    Wenn man Crenshaw verstanden hat, dann ist das das Werk der Wahl.
    Es ist in C verfasst, daher für mich ungleich schwerer zu lesen. Somit hätte ich es als Erstlingswerk nicht so wirklich verstanden, vor allem wegen der C-mäßigen Stringbehandlung, mit der ich mich sehr quäle, aber Geschmäcker sind ja bekanntermaßen verschieden.
    Aber als Zweitbuch war es toll für mich. Basiert in seinen Techniken sehr stark auf Crenshaw - ist also etwas wie eine Crenshaw-Variante, compilert auf X86-Assembler bzw. interpretiert im ersten Teil den Code als reiner Interpreter (auch eine interessante Variante).
  3. Compiler Tutorial in Pure Basic, von unbekannt

    Wer Crenshaw verstanden hat, dem wird hier ein kurzes und knappes und sehr gutes Tutorial in Pure Basic (!!!) geliefert, das ich besonders toll finde.
    Der Compiler in diesem Tutorial kompiliert auf eine Registermaschine, noch dazu auf die echte x86-CPU. Das ist eine interessante Alternative für diejenigen, die keinen Stack Code wie ich in meinem Tutorial, sonder einen Registercode komplieren wollen.
    Guten Appetit!
  4. Compiler Construction, von Niklaus Wirth

    Das ist der Mann der Eidgenössischen Technischen Hochschule (ETH) Zürich, der Pascal erfunden und programmiert hat.
    Er hat die englische Version seines Buches auf die ETH-Homepage gestellt. Dieses Buch - als Kaufversion bei Amazon nach wie vor auf Deutsch erhältlich, ich habe es schließlich gekauft - hat mir, nachdem ich Crenshaw verstanden und mit einigen Toy-Compilern schon weiterexperimentiert habe, enorm weitergeholfen, vor allem das Kapitel mit der Virtual Machine (Er compiliert auf eine virtuelle Registermaschine).
    Wirth ist knapp und dirty, ich hätte ihn ohne Crenshaw so von vornherein nicht verstanden, auf Englisch schon gar nicht, verwendet aber, wenn man unter die Motorhaube schaut, sehr ähnliche und in vielen Bereichen sogar dieselben Compilertechniken wie Crenshaw.
    Die deutsche Kaufversion, die neben mir am Tisch liegt, ist nach wie vor bei Amazon erhältlich (Tipp: in Amazon ins Inhaltsverzeichnis schauen unter "Hier klicken Blick ins Buch" in der rechten Ecke des Fotos des Buchcovers!)
  5. Compilers and Compiler Generators an introduction with C++, von P.D. Terry, Rhodes University, 1996

    Vor allem die Kapitel 4, 6 und 7 haben mir beim Thema Virtual Machines und Assembler recht brauchbar weitergeholfen.



2.2. Literatur, die hilfreich ist, wenn man schon eine Ahnung von Compilern hat

  1. Game Scripting Mastery, von Alex Varanese

    Dieses enorm teure Buch auf Englisch ist dann eine Bibel, wenn man schon mehrere erfolgreiche Compiler-Gehversuche hinter sich hat und im Lernen voranschreitet.
    Beginnt auch bei Adam und Eva, ist aber etwas schwerer verständlich als Crenshaw, aber wirklich enorm und unglaublich potent, wenn es um Virtuelle Maschinen, Scripting Systeme für z.B. Ego-Shooter bzw. Role Games oder dergleichen geht, ist ein Grundlagenwerk mit ca. 1272 Seiten und behandelt Compiler und Scripting von Grund auf. Wärmstens zu empfehlen unter der Voraussetzung, dass man schon Vorwissen hat, denn seine Techniken sind - na ja - nicht immer durchsichtig.

    Kann natürlich auch, allein schon wegen des Umfangs und durch die genauesten Erklärungen, durchaus als Einsteigerwerk gelten, ich empfehle dennoch Crenshaw zuerst, weil er übersichtlicher ist zu Beginn, zumal Varanese C benutzt und ich persönlich Pascal übersichtlicher finde, aber wie oben gesagt: Geschmäcker ...
    Die Kaufversion bei Amazon ist nach wie vor erhältlich, außerdem könnte man Glück haben und eine günstigere, aber dadurch auch nicht billige, Version ergattern.
    (Tipp: in Amazon ins Inhaltsverzeichnis schauen unter "Look inside" in der rechten Ecke des Fotos des Buchcovers!)
  2. Compiler Design: Virtual Machines, von Reinhard Wilhelm, Helmut Seidl

    Für das Verstehen einer Stack Machine sehr hilfreich. Kapitel 2 und 5 waren für mich sehr brauchbar. Ist sicher kein Muss, trägt aber durchaus zum Erkenntnisgewinn bei.
    Das Buch gibt es bei Amazon zu kaufen.
    (Tipp: in Amazon ins Inhaltsverzeichnis schauen unter "Look inside" in der rechten Ecke des Fotos des Buchcovers!)
  3. Using Peephole Optimization on Intermediate Code, von Andrew S. Tanenbaum, Hans van Staveren, Johan W. Stevenson, Vrije Universiteit, Amsterdam, The Netherlands

    Wenn man seinen Stack Machine Code mit einem Peephole Optimizer optimieren will oder muss, dann ist dieses kurze wissenschaftliche Paper zwar uralt, aber bibelverdächtig.
    Natürlich gibt es bereits viele neuere Techniken, die aber für einen solch klassischen Compileraufbau wie den unsrigen nicht notwendig sind.

    Ich habe einige dieser Optimierungen in einem kleinen Testprogramm für mich angetestet, die in diesem Paper dargestellt werden, und diese funktionierten sehr gut. Sehr empfehlenswert für Stack Machines.
  4. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, von Terence Parr

    Ist in Java verfasst, womit ich es persönlich schwer habe. Sicher kein Einsteigerwerk, aber das Kapitel Stack Machine ist interessant, aber nicht unbedingt notwendig.
    Ist brauchbar, wenn man sich schon gut auskennt, aber nicht zwingend erforderlich, war für mich aber interessant.
    Auch hier kann man bei Amazon ins Inhaltsverzeichnis schauen.



2.3. Literatur, die mir persönlich überhaupt nichts sagte




2.4. Abschließende zusammenfassende Betrachtungen

Die echten Bibeln sind für mich für ...
  • Compilerbau: Crenshaw, Wirth, das PB Tutorial des unbekannten Autors, Varanese
  • Game Scripting: Varanese
  • Virtual Machine allg.: Varanese, Reinhard Wilhelm und Helmut Seidl
  • Virtual Stack Machine: Reinhard Wilhelm und Helmut Seidl, sowie Tanenbaum et al. zum Optimieren

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 18:37
von puretom
3. Überblick über die Arbeitsweise eines Compilers und einer Virtuellen Maschine



3.1. Vorbemerkungen

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 anderen Personen 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.

Wenn man allerdings zuerst die Grundlagen zu Fuß erlernen möchte, um dann in einige Jahren DEN Supercompiler nach viel Dazulernen zu programmieren, dann ist man zunächst gut beraten, bei den primitivsten Grundlagen zu beginnen.
Nun, das ist das Ziel des Tutorials: Die allerprimitivsten Grundlagen.

Es folgt ein kurzer Überblick über das Gesamtprojekt.




3.2. Graphischer Überblick über die einzelnen Komponenten des Projekts


Aufbau eines Compiler-Gesamtpakets bis zur Virtuellen Maschine:

Code: Alles auswählen


.--------------------.        SOURCE-CODE, SOURCE-PROGRAMM:
| USt = 19+4         |           Das Programm, das wir in unserer
|                    |           Skriptsprache geschrieben haben.
'--------------------'		   
Es sind im Source-File				
einzelne Zeichen, es ist
also in Textform:

|U|S|t| |=| |19|+|4|

          |           
          |  LEXIKALISCHER SCANNER:
          |     Macht aus dem Stream (Strom) von Einzelzeichen
          |     'Token' und 'Lexeme'
          |
          v
.------------------------------.   TOKEN-LEXEM-PAARE:
| Token=#NAME    : Lexem="UST" |      Der Scanner stellt diese für                    
| Token='='      : Lexem=egal  |      den Compiler/Parser bereit.
| Token=#INTEGER : Lexem="19"  |      Er filtert alle unnötigen Teil
| Token='+'      : Lexem=egal  |      wie Leerzeichen, Kommentare, usw.
| Token=#INTEGER : Lexem="4"   |      heraus, sie erreichen den Parser
|                              |      nicht mehr.
'------------------------------'		   
          
          |
          |  PARSER (COMPILER):
          |     Er erzeugt aus Token-Lexem-Strom ein Assemblerprogramm 
          |     in der Assemblersprache, auf die wir kompilieren,
          |     das ist in unserem Fall ToyVM-ASM.
          |     Das Ergebnis hat wieder wie das Source-File Textform.
          |
          v
.------------------------------.   ASSEMBLERPROGRAMM:
| ipushc 19                    |      Der Compiler/Parser erzeugt ein 
| ipushc 4                     |      Assemblerprogramm in Textform.
| iadd                         |
| ipullg UST                   |
|                              |
'------------------------------'		   
          |
          |  ASSEMBLER:
          |     Ist wieder ein vollständiger Compiler.
          |     Er erzeugt aus dem Assemblerprogramm in Textform
          |     ein sogenanntes Binär- oder Exe-File, das nur mehr
          |     aus Zahlen besteht.
          |     Der Assembler hat in sich wieder einen Scanner, der
          |     aus dem Text die Token-Lexeme holt und einen Parser,
          |     der aus dem Text die Zahlenform erzeugt.
          |     Dazwischen kann es noch sein, dass ein Optimizer
          |     den Assemblercode noch effizienter macht, bevor ihn
          |     der Assembler assembliert, und der 1. erzeugte 
          |     Assemblercode nur ein Zwischencode war.
          v
     BINÄR-FILE
      (Zahlen)
          |
          |  VIRTUELLE MASCHINE (oder echte CPU):
          |     Arbeitet einen Befehl (=Zahl) nach dem anderen ab.
          |     Das Programm läuft also IN der CPU oder IN der VM ab.
          |
          v
 "Das Programm läuft"



3.3. Erklärung der einzelnen Komponenten



3.3.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:

  1. 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) , die aber natürlich nicht willkürlich sind, sondern sich zu zusammengehörenden Teilen (Lexeme/Objekten) zusammenbauen (Anm.: Natürlich sind auch andere Kodierungen wie z.B. Unicode oder UTF-8 sind selbstverständlich möglich, siehe PB-Hilfe).

    Wenn wir ein Pure-Basic-Programm (*.pb, *.pbi, *.pbf, ...) mit dem ganz normalen Text-Editor öffnen, dann sehen wir, es ist reiner Text, wir hätten es auch als *.txt speichern können.

    Das können zum Beispiel in unserem zukünftigen Scanner Zahlen wie z.B. #INTEGER, #FLOAT, Zeichenketten in Anführungszeichen (#STRING), Operatoren wie z.B. +,-,=,*,<>, Bezeichner bzw. Namen (engl. Identifier, #NAME)von Variablennamen, reservierten Befehlswörtern, Procedure-Namen usw. sein, nur um einen kurzen Überblick anzudeuten.

    Der Tokenizer erkennt im Zeichenstrom zusammengehörende Teile/Lexeme/Objekte.
    Er ordnet dem Objekt ein Token (eine globale Variable des Scanners) zu, das ist eine Code-Zahl, die angibt, welcher Art das Objekt war, also zum Beispiel ein #NAME.
    In einer globalen String-Variable speichert er dann mit dem Fachausdruck Lexem das Objekt dann selbst.

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


    Ein Beispiel:

    Im Source-File steht:

    Code: Alles auswählen

    USt=19     // USt = Umsatzsteuer
    
    Der Scanner erzeugt nun folgende Token-Lexem-Paare:

    Code: Alles auswählen

    |U|S|t|=|1|9| ---> Zeichenstrom hat 6 Zeichen/Character 
                       (und noch ein Kommentar und auch noch die 
                        Zeilen-Endmarkierung, aber das ist jetzt
                        unwichtig)
    
    
    --> SCANNER erkennt 3 Token-Lexem-Paare:
    
    Token.i = #NAME      |   Lexem.s = "UST"
    Token.i = '='        |   Lexem.s = egal
    Token.i = #INTEGER   |   Lexem.s = "19"
    
    Nicht in jeder Compiler-Implementation wird das Source-File vom Lexer vollständig untersucht und dann diese Token-Lexem-Paare gespeichert.

    Oft 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.

    Es gibt auch Programme, mit denen man Parser und Compiler generieren kann, z.B. Lex undYacc. Mit diesen habe ich aber noch nicht gearbeitet und will ich auch nicht, weil ich etwas über Compilerbau per Hand lernen wollte.
  2. 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) bzw. abstrakten Syntaxbaum 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:
  3. Codegenerator bzw. das Modul Code

    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:

    Code: Alles auswählen

    USt = 19+4    // USt = Umsatzsteuer
    
    Der Parser parst jetzt Token-Lexem- für Token-Lexem-Paar und erzeugt folgenden Byte-Code (=anderer und fast immer gebrauchter Ausdruck für Assembler und Maschinensprache einer Virtuellen Maschine), den der Compiler als Text-File (=ASM- oder Byte-Code-File) abspeichert.
    • Der Parser sieht Token = #NAME, Lexem ="UST":
      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 "UST".
    • Der Parser sieht Token = '=', Lexem =egal:
      Genau das hat der Parser erwartet. Wäre jetzt kein "=" gewesen, hätte er eine Fehlermeldung ausgegeben.
    • Der Parser sieht Token = #INTEGER, Lexem ="3":
      Da ich eine Stack Machine bauen will, gibt der Parser dem Codegenerator den Befehl, dass er die Integer-Konstante "3" auf den Stack legen soll ("ipushc 3" -> i = Integer, c = Constant).
    • Der Parser sieht Token = '+', Lexem =egal:
      Genau das hat der Parser erwartet. Wäre jetzt kein #OP_... gewesen, hätte er eine Fehlermeldung ausgegeben.
      Durch den rekursiven Parser (dazu später mehr), merkt er sich das "+".
    • Der Parser sieht Token =#INTEGER, Lexem ="12":
      Da ich eine Stack Machine bauen will, gibt der Parser dem Codegenerator den Befehl, dass er die Integer-Konstante "12" auf den Stack legen soll ("ipushc 12").
    • Der Parser erkennt aufgrund seiner rekursiven Natur, dass der mathematische Ausdruck (=Expression) zu Ende ist:
      Er hat sich gemerkt, dass "+" noch nicht ausgeführt wurde und gibt dem Codegenerator den Befehl zu addieren ("iadd").
      Weiters weiß er, dass er eine Zuweisung an eine Variable durchführen muss. Dazu hat er sich ja oben den Namen der (globalen) Variable "UST" gemerkt und gibt dem Codegenerator den entsprechenden Befehl ("ipullg UST" -> g = Globale Variable).

      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

      ipushc 3        // lege 3 auf den Stapel (Stack) 
      ipushc 12       // lege 12 auf den Stapel (Stack) 
      iadd            // hole 12 und 3 (oberstes + nächstes Element) vom Stapel         
                         addiere sie und lege Ergebnis auf Stapel
                         ganz oben am Stapel liegt jetzt 15
      ipullg UST      // hole 15 (=oberstes Element) vom Stapel 
                         speichere es in Variable "UST" ab
      
  4. Optimizer, Optimierer, Optimierungsstufe

    Der erzeugte Code ist nicht effizient, das sieht man sofort.
    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.

    Hier sieht man eines der größten Geheimnisse des Compilerbaus:
    Ein einfacher Compiler, der uneffizienten Code erzeugt, ist keine Hexerei und auch für mittelfortgeschrittene Programmierer locker machbar.
    Ein Compiler, der sehr effizienten und superoptimierten und superschnellen ASM-Code erzeugt, der ist ein Meisterstück.
    Da aber für durchschnittliches Scripten ersterer reicht, sage ich wie mein Vorbild Jack Crenshaw: Lasst uns einen Compiler bauen!


    Für eine einfache Scriptsprache, bei der es nicht um Speed geht, empfehle ich sogar, den Optimierungsschritt 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 Byte-Code-ASM-Text-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. "iadd" hier in unserem Beispiel
    Findet also der Optimizer dieses Muster (push Constant, push Constant, Mathe-Befehl), 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

    ipushc 15       // lege 15 (das war vorher 12+3) auf den Stapel (Stack) 
    ipullg UST      // hole 15 (=oberstes Element) vom Stapel 
                       speichere es in Variable "UST" ab
    
    Constant Folding ist eine der einfachsten Optimierungen, im Paper von Andrew S. Tanenbaum et. al. werden eine Vielzahl anderer Optimierungstechniken erklärt.
    Niklaus Wirth (Kapitel 10.2. Delayed code generation) beschreibt in seinem PDF diese Optimierung schon als Teil des Codeerzeugens (durch verzögerte Codeausgabe), 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.3.2. Der Assembler

Das als Text vorliegende Assembler/Byte-Code-File muss jetzt in Zahlen gegossen werden. Das erledigt der Assembler.

Ein Assembler ist technisch gesehen ebenfalls ein Compiler, nur bezeichnet man ihn zumeist nicht so, sondern nimmt den enger gefassten Namen Assembler.

Assembler ist also der Name für einen Compiler, der Assembler/Byte-Code in Textform in Maschinensprache bestehend nur mehr aus Zahlen übersetzt.

Maschinensprache sind die Befehle, die der Mikroprozessor wirklich versteht.
(siehe sehr gut dargestellt in: Assemblersprache)


Wenn ich nicht direkt in ASM meines "echten" Prozessors (z.B. x86 wie PB) übersetze, sondern mir einen Prozessor erfunden habe (wie ich das hier mache, oder JAVA VM, oder .NET VM, oder die alte P-Code-VM für Pascal), diesen also später simuliere und das Programm IN der VM abläuft, 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 wird auch hier als Assembler, manchmal mit dem Zusatz Bytecode-Assembler, bezeichnet.

Der Assembler braucht wieder einen Lexer und Parser in sich, denn er arbeitet wieder mit Lexemen (z.B. "ipush") und Tokens wie #NAME usw.
Diese Komponenten des Assemblers sind aber einfacher als beim "großen" Compiler für Hochsprachen (v.a. der Parser), da Assembler einfacher und geradliniger zu untersuchen ist.

Ein Beispiel:

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

Code: Alles auswählen

ipushc 15      --> push ist (angenommen) 22
                   der Assembler speichert 22
               --> der Assembler speichert die Zahl 15
ipullg UST     --> pull ist (angenommen) 96
                   der Assembler speichert 96
               --> Die Variable "UST" 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.3.3. Die Virtual Machine

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.
Unser Programm läuft also IN der Virtual Machine.

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.4. Zusammenfassung

Die einzelnen Komponenten sind folgendermaßen aufgebaut:

1. Scanner/Parser/Codegenerator (EINHEIT -> eventuell Optimizer ---> erzeugt Byte-Code-Assemblerprogramm in Textform
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

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 18:49
von puretom
TEIL ZWEI: TINY TOY C


    • 4. Lexikalischer Scanner
      5. Kurze Einführung in Assembler/Maschinensprache
      6. Compiler TTCC und Parser TTCP


Ziel von TEIL ZWEI ist es, eine komplette Umgebung für eine Programmiersprache mit dem Namen TinyToyC (kurz TTC) zu schaffen.
In meiner alten Tutorialserie wollte ich zunächst alle kompliziertesten Grundlagen erklären und durchdiskutieren.
In diesem Teil verfolge ich eine ganz andere Philosophie: möglichst schnelle Ergebnisse.

Aus diesem Grund werde ich manche grundlegende Designentscheidungen treffen, ohne lange zu diskutieren. Ich werde außerdem stark vereinfachen, damit die Sprache einmal sichtbar funktioniert, damit die Forumsleser sehen können, wie leicht es ist, einen (ineffizienten !) Compiler zu schreiben.

Sollte ich dann noch Lust haben, mit dem Tutorial weiterzumachen, dann werde ich vielleicht das Gerüst wieder umbauen, die alten komplizierteren Kapitel einbauen und die Sprache zu ToyC - ohne Tiny* - erweitern.

*) tiny, engl: winzig, klitzeklein; in der Computerfachsprache eine stark abgespeckte, vereinfachte Programmiersprache

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 07.10.2013 19:47
von puretom
4. Lexikalischer Scanner



4.1. Vorbemerkungen

Ich möchte mit dem lexikalischen Scanner (kurz Lexer, auch Tokenizer genannt) beginnen.

Unser kleiner Scanner soll TTCS heißen, also Tiny Toy C Scanner <) .

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.

Die Aufgabe des Scanners ist, aus einzelnen Zeichen des Source-Code-Files klar abgegrenzte Zeichengruppen, also Token zu machen. Dazu füllt der Scanner einen Token-Code (also eine Zahl) in die globale Variable Token und in die ebenfalls globale Variable Lexem den Inhalt der Zeichengruppe (also einen String)

Code: Alles auswählen


.--------------------.
|  einzelne Zeichen  |
| ------------------ |
|    i               |
|    f               |
|    (               |
|    X               |
|    _               |
|    P               |
|    o               |
|    s               |
|    >               |
|    3               |
|    )               |
|   #CR              |
|   #LR              |
'--------------------'
   |
   |
   |   SCANNER
   |   ^^^^^^^
   |
   v 
.--------------------.
|  Token     Lexem   |
| ------------------ |
|  #NAME      if     |
|   '('       egal   |
|  #NAME      x_pos  |
|   '>'       egal   |
|  #INTEGER   3      |
|  #eol       egal   | (#eol=End of Line,
'--------------------'  Ende einer Zeile)



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 "#TAB", Kommentare und sogar die in Java oder allen C-Varianten oder auch Pascal 'heiligen' Semikolons ";" werde ich in meinem Code dazurechnen.
Vor allem die Frage der Behandlung des "#CR" (Carriage Return) bzw. des "#LF" (Line Feed) am Zeilenende sowei des ";" am Ende eines TTC-Befehls ist eine durchaus zu diskutierende. Wir werden #CR und #LF durch ein ein Ersatzzeichen ersetzen (siehe weiter unten Kapitel über Zeilenenden).
Falls eine Erweiterung von TTC vorgesehen ist, werde ich mich dieser Frage wieder zuwenden, jetzt behandeln wir die Sache einmal so und ignorieren diese Zeichen.


Ein Beispiel :

Stellen wir uns eine Textdatei mit dem Namen "source-code.ttcs" vor (.ttcs = Tiny Toy C Source)
Ein Source-Code ist eine so genannte Quelltextdatei. Hier steht also unser Programm der Programmiersprache TinyToyC. Wichtig ist, dass es sich um reine Textform handelt, in der wir diese Datei abspeichern. Aus dieser Datei liest dann der lex. Scanner seine Zeichen aus, und zwar Zeichen für Zeichen, bis er ein 0-Byte sieht und abbricht.
Das Ergebnis werden wir dann im Debug-Fenster bewundern können.

Code: Alles auswählen

if (Var=35)   print(Var) 
Wir würden die Zeile oben zum Einfügen in unsere Source-Code-Datei benutzen. Die nächste Zeile zeigt uns zur Verdeutlichung nur die Leerzeichen "_" und die Zeilenendzeichen (hier wurde beim Eingeben ENTER gedrückt) "#CR" gefolgt von "#LF" (wenn wir Windows benutzen).

Code: Alles auswählen

If _ (Var=35) _ _ _ print(Var) #CR #LF 

Lassen wir unseren Parser laufen, dann arbeitet folgende Schritte ab:


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

Code: Alles auswählen

If _ (Var=35) _ _ _ print(Var) #CR #LF 
^--- 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 _ (Var=35) _ _ _ print(Var) #CR #LF 
     ^--- 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 _ (Var=35) _ _ _ print(Var) #CR #LF 
      ^--- 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 "r"
  • 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 "Var"
    • 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 _ (Var=35) _ _ _ print(Var) #CR #LF 
         ^--- 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 _ (Var=35) _ _ _ print(Var) #CR #LF 
          ^--- in Look ist "3"
  • Der Scanner erkennt mit IsNum(): "3" ist eine Zahl, verzweigt nach GetNumber()
  • GetNumber() holt jetzt Zeichen für Zeichen, bis zum ersten Nicht-Ziffern-Zeichen. Der Scanner steht mit Look auf ")" nach "5"
  • GetNumber() ruft nun SkipWhite() auf, diese Prozedur überspringt alle White-Zeichen (keine da)
  • Am Ende von GetNumber() haben wir folgendes Ergebnis:
    • In Token ist die Code-Zahl von #INTEGER (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 _ (Var=35) _ _ _ print(Var) #CR #LF 
            ^--- in Look ist ")"
  • Das kennen wir schon von oben, GetOther() holt das ")"
  • GetOther() ruft nun SkipWhite() auf, diese Prozedur überspringt 3 White-Zeichen (hier Leerzeichen) 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 _ (Var=35) _ _ _ print(Var) #CR #LF 
                    ^--- 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

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 und Pure Basic uns mit Fehlermeldungen von nicht vorhandenen Prozeduren plagt.

Code: Alles auswählen

; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
; X                                                                 X
; X   LEXIKALISCHER TTC-SCANNER : TinyToyC (TTC) - Kapitel 4        X
; X                                                                 X 
; XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

; *******************************************************************
; * Scanner Version TTCS Kap. 4                                     *
; *******************************************************************
DeclareModule Scanner     
; -
; - Public Declarations ---------------------------------------------
; -  
      Global Look      ; Look Ahead Character
      Global Token     ; Token-Typ als Zahl
      Global Lexem.s   ; Lexem = Token als String
      Global LineNr    ; aktuelle Zeilennummer

    ; --- Start- & Stop-Prozedur ---  
    
      Declare Start(file_name.s="") ; Filename des Source-Files 
      Declare Stop() 
    
    ; --- 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 GetNumber()            ; holt nächste Zahl                                     
      Declare GetString()            ; holt nächsten String    
      Declare GetOther()             ; holt Rest                      

    ; --- Fehlermeldung ausgeben ---
    
      Declare Error(error_message.s)      ; zeigt Meldung, Scanende
      Declare Expected(expected_object.s) ; zeigt, was erwartet 
                                          ; wurde, dann Scanende                              
    ; --- Is?-Erkennungs-Macros ---
      
      Macro IsNumber(c)    ; Zeichen gehört zu einer Zahl?
      EndMacro	       
      Macro IsName1(c)     ; Zeichen ist Start eines Namens?
      EndMacro	       
      Macro IsName(c)      ; Zeichen gehört zu einem Namen?
      EndMacro	       
      Macro IsString(c)    ; Zeichen ist der Start eines Strings?
      EndMacro	       
      Macro IsWhite(c)     ; Zeichen ist ein White-Character?
      EndMacro	       
  
    ; --- Debug-Prozeduren (Im Release löschen) ---
    
      Declare Start_GetChar(file_name.s)    

    ; Anmerkung: / startet einen Zeilenkommentar mit '//' (wie in C)
    ;            / startet einen Blockkommentar mit  '/*' (wie in C)  
                                          
EndDeclareModule
Module Scanner
; -
; - Private Declarations --------------------------------------------
; -

    Global *Source_Code        ; Zeichen für Zeichen im Speicher
    Global *Source_Pos.ASCII   ; nächste Zeichen-Lese-Position
     
  ; --- Lade Source-File ---
  
    Declare Load(file_name.s)  ; lädt das Text-Zeichen-Source-File          

  ; --- Skip - Prozeduren ---
  
    Declare SkipWhite()        ; überspringt  White-Zeichen
    Declare SkipLineComment()  ; überspringt ab Comment-Start bis #eol
    Declare SkipBlockComment() ; überspringt von Block-Start bis -Ende

; -
; - Start - Prozedur -----------------------------------------------
; -
  Procedure Start(file_name.s="")                     :EndProcedure  
  Procedure Stop()                                    :EndProcedure
  Procedure Start_GetChar(file_name.s)                :EndProcedure

; - Lade Source-File -----------------------------------------------
; -
  Procedure Load(file_name.s)                         :EndProcedure
  
; - Get - Prozeduren -----------------------------------------------
; -
  Procedure GetChar()                                 :EndProcedure    
  Procedure GetToken()                                :EndProcedure
  Procedure GetName()                                 :EndProcedure
  Procedure GetNumber()                               :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

; *******************************************************************
; * Debug-Prozeduren (außerhalb der Module)                         *
; *******************************************************************
Procedure Debug_GetChar()                             :EndProcedure
Procedure Debug_GetToken()                            :EndProcedure
 
; Aufruf je nach Ziel:
; Debug_GetChar()
; Debug_GetToken()


4.4. Laden und testen des Character Streams

Wir legen uns jetzt einen beliebigen Projektordner und darin ein Textfile mit dem Namen "source-code.ttcs" an, wobei ".ttcs" für Tiny Toy C und das S für Source-Code 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.
Auch sollte IN diesem Projektordner das Pure-Basic-File "ScannerTTC.pb" sein, am besten wir kopieren das Gerüst von Kapitel 4.3. einfach in dieses .pb-File.

In "source-code.ttcs" speichern wir für unsere kommenden Tests folgenden Code, ein " _ " stellt ein Leerzeichen dar. Die üblichen Zeilenendezeichen sind ebenfalls vorhanden, also bitte nach der if-Zeile 1-mal ENTER drücken:

Code: Alles auswählen

name  "Ich String"  56547 // Zeilenkommentar
( <  < >  <= > /*Blockkommentar*/
6/2

Code: Alles auswählen

Zur Verdeutlichung nochmals Zeile 2:

( <  < >  <= > /*Blockkommentar*/
^ ^  ^^^  ^^ ^
| |   |    | |      Token
| |   |    | |      -----
| |   |    | '--- >  '>'
| |   |    '----- <= 'k'leinergkleich
| |   '---------- <> 'u'ngleich
| '-------------- <  '<'
'---------------- (  '('

Code: Alles auswählen

name _ _ "Ich _ String" _ _ 56547 _ // _ Zeilenkommentar #CR #LF
( _ < _ _ < _ > _ _ <= _ > _ /*Blockkommentar*/ #CR #LF
6/2
Anmerkung:
Ich verwende dafür den Programmierer-Notepad Notepad++, weil ich damit auf einfache Weise ein Syntax-Highlighting in meiner erfundenen Sprache realisieren kann. Für Toy C stelle ich die Einstellung einfach auf "C", denn Toy C ist C-ähnlich.



Wir müssen zunächst eine Start()-Prozedur programmieren, die für uns alle notwendigen Initialisierungen und Vorbereitungen durchführt:

Code: Alles auswählen

  Procedure Start_GetChar(file_name.s) 
  
    ; --> Die Prozedur heißt aus Debug-Gründen Start_GetChar()
    ; --> Die echte Start-Prozedur wird nur mehr Start() heißen
  
    ; laden des Source-Files   
      Load(file_name.s)     
      
    ; '*Source_Pos' auf 1. Zeichen stellen
      *Source_Pos = *Source_Code      
    
    ; das erste aktuelle Zeichen (Look) holen  
      GetChar()   
      
    ; --> ab hier ist alles zum Character-Stream-Test bereit
    ; --> ein gültiger Look liegt im Stream
  
  EndProcedure  
Anmerkung: Später wird diese Prozedur einfach nur Start() heißen. Der Name oben ist dem noch folgenden Debug-Vorgang geschuldet.

Mit dieser Prozedur beginnen wir später den Vorgang des Kompilierens, also immer Scanner:Start() aufrufen, bevor kompilert werden soll.
  • Wir laden in dieser Prozedur unser Source-File.
  • Wir stellen den Zeichenzeiger *Source_Pos auf den Start des Memorybereichs *Source_Code, der den Text unseres Source-Codes aufnimmt.
    Der Zeiger *Source_Pos zeigt auf die nächste Scanposition, dieser Zeiger zeigt also exakt auf das Zeichen im Source-Code, das beim nächsten Aufruf von GetChar() nach Look geholt werden wird.
  • An der Prozedur Start() sehen wir durch den Aufruf von GetChar()/ an dieser Stelle eine Tatsache deutlich.
    Wir müssen wir den Character-Strom einmal das erste Mal "aufpumpen", sprich das erste Zeichen noch vor irgendeiner Schleife mit Look vorbelegen. Warum? Der Scanner erwartet nämlich, dass immer ein aktuelles Look-Zeichen in Look bereits vorhanden ist, also auch ganz zu Beginn.


Die Prozedur Load() zum Laden des Codes im Source-File in einen Memorybereich namens *Source_Code:

Code: Alles auswählen

  Procedure Load(file_name.s)
      
    ; lade Source-File mit Filename   
      file = ReadFile(#PB_Any,file_name)   
      If Not file
          Error("Das Source-File "+#DQUOTE$+file_name+#DQUOTE$+
                " konnte nicht geöffnet werden.")
      EndIf     
      
    ; speichere Source-File in Memory-Bereich                               
      size = Lof(file)
      *Source_Code = AllocateMemory(size+1) ; damit am Ende 0-Byte  
      ReadData(file, *Source_Code, size)      
      CloseFile(file)
    
  EndProcedure
  • Das Source-File laden wir ganz einfach in einen Speicherbereich, dessen Startpunkt wir mit einem Zeiger mit dem Namen *Source_Code adressieren.
  • Am Ende des Memory-Bereichs muss ein 0-Byte sein, deshalb size+1 im Befehl AllocateMemory (siehe Code).
    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 ;-) .


Als Nächstes programmieren wir die bereits erwähnte Prozedur GetChar(). Ich weiß, hier ist ein Pointer besser als eine Funktion.

Code: Alles auswählen

  Procedure GetChar() 
   
    ; Look aus dem Source-Code-Stream holen
      Look = PeekA(*Source_Pos)
      *Source_Pos+1                
      
  EndProcedure
Im Code dieses Kapitels setze ich letztlich die auch nicht schwerer zu verstehende Pointer-Variante um. Wir dürfen aber hier nicht vergessen, die Variable *Source_Pos als *Source_Pos.Ascii zu deklarieren:

Code: Alles auswählen

  Procedure GetChar()    
           
    ; Look aus dem Source-Code-Stream holen
      Look = *Source_Pos\a  
      *Source_Pos+1               
         
  EndProcedure  
Dies Prozedur macht dasselbe wie die erste Version, nur ist sie etwas schneller.
  • Die Prozedur GetChar() hat zunächst die Aufgabe, bei Aufruf das Zeichen (Char = Character) vom Source-File-Speicherbereich an der *Source_Pos in die globale Variable Look zu holen.
  • Dann wird *Source_Pos um ein Zeichen erhöht und zeigt somit auf das Zeichen im Zeichenstrom, das beim nächsten Aufruf von GetChar() geladen werden würde.


Programmieren wir uns jetzt noch schnell eine Debug-Prozedur (außerhalb des Moduls – siehe Gerüst) mit dem Namen Debug_GetChar, um alles, was wir bis hierher programmiert haben, zu testen.
Die Debug-Prozedur Debug_GetChar() müssen kurz besprechen:

Code: Alles auswählen

Procedure Debug_GetChar()
    
  ; --> wir laden Start_GetChar() aus Debug-Zwecken
  ; --> später heißt die Prozedur nur mehr Start()    
  
    Scanner::Start_GetChar("source-code.ttcs")

    While ( Scanner::Look <> 0 )
        Debug " | "+Chr(Scanner::Look)+              ; CHAR des ASCII-Codes
              " | "+Scanner::Look                    ; CHAR-Code in Look
        Scanner::GetChar()
    Wend 
    Debug "0-Byte: außerhalb der While-Schleife"

EndProcedure
  • Nachdem wir die Start-Prozedur des Scanners gestartet haben, geht eine While-Schleife durch den Speicherbereich *Source_Code (über den Zeiger *Source_Pos), aber nur, wenn kein 0-Byte als Terminator (Ende-Signalzeichen) in Look ist.
  • Dabei bekommen wir im Debug-Fenster links das Zeichen als Character und rechts den entsprechenden Character-Code dieses Zeichens angezeigt, wenn wir Debug_GetChar() starten.
  • 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 laufenl, indem wir Debug_GetChar() aufrufen.
Falls bei mir andere Zeichen zu sehen sind, dann liegt es daran, dass ich als Schriftart für die Debug-Ausgabe "Courier New" eingestellt habe.

Alles sollte funktionieren und folgende Debug-Ausgabe sollte zu sehen sein (andere Systeme als Windows könnten am Zeilenende andere Ergebnisse haben – dazu gleich im nächsten Unterkapitel mehr):

Code: Alles auswählen

 | n | 110
 | a | 97  
 | m | 109
 | e | 101
 |   | 32  <== ASCII 32 = Leerzeichen
 |   | 32
 | " | 34  <== Start: String
 | I | 73
 | c | 99
 | h | 104
 |   | 32
 | S | 83
 | t | 116
 | r | 114
 | i | 105
 | n | 110
 | g | 103
 | " | 34  <== Ende: String
 |   | 32
 |   | 32
 | 5 | 53
 | 6 | 54
 | 5 | 53
 | 4 | 52
 | 7 | 55
 |   | 32
 | / | 47  <== Start: Zeilenkommentar
 | / | 47
 |   | 32
 | Z | 90
 | e | 101
 | i | 105
 | l | 108
 | e | 101
 | n | 110
 | k | 107
 | o | 111
 | m | 109
 | m | 109
 | e | 101
 | n | 110
 | t | 116
 | a | 97
 | r | 114
 |         <== Ende: Zeilenkommentar
 | 13      <== ASCII 13: #CR -> Zeilenende (ENTER-TASTE)
 | 
 | 10      <== ASCII 10: #LF -> Zeilenende (ENTER-TASTE)
 | ( | 40  
 |   | 32
 | < | 60  <== ASCII 60 = Char-Code für "<"
 |   | 32
 |   | 32
 | < | 60  -.
 |   | 32   | <>: mehrteiliger Operator 'u'ngleich
 | > | 62  -'     (mit White-Zeichen dazwischen)
 |   | 32
 |   | 32
 | < | 60  -.
 | = | 61  -' <=: mehrteiliger Operator 'k'leinergleich
 |   | 32
 | > | 62
 |   | 32
 | / | 47  <== Start: Blockkommentar
 | * | 42
 | B | 66
 | l | 108
 | o | 111
 | c | 99
 | k | 107
 | k | 107
 | o | 111
 | m | 109
 | m | 109
 | e | 101
 | n | 110
 | t | 116
 | a | 97
 | r | 114
 | * | 42
 | / | 47  <== Ende: Blockkommentar
 | 
 | 13      <== ASCII 13: #CR -> Zeilenende (ENTER-TASTE)
 | 
 | 10      <== ASCII 10: #LF -> Zeilenende (ENTER-TASTE)
 | 6 | 54
 | / | 47  <== einfaches '/': Division
 | 2 | 50
0-Byte: außerhalb der While-Schleife
             
           .-------------------------------------.
           | Die Kombination 13 10 ist typisch   |
           | für WINDOWS als Zeilenende (ENTER). |
           | Andere Systeme können abweichen!    |
           '-------------------------------------'



4.5. Die ENTER-Taste: das Ende einer Programmzeile

Interessant ist, was bei der ENTER-Taste passiert.
Windows setzt die Enter-Taste (= das Zeilenendezeichen) als 2 Zeichen um: die Kombination "#CR" (ASCII 13: Carriage Return) und "#LF" (ASCII 10: Line Feed). Dafür gibt es bei Pure Basic die beiden genannten 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 danach "#CR", also umgekehrt zu Windows oder auch einfach nur ein einfaches "#CR". Alles ist möglich, selbst exotische Zeichen auf manchen Servern.
Ich verweise hier auf Wikipedia-Eintrag über den Zeilenumbruch, der verschiedene Möglichkeiten erklärt. Die englischsprachige Wikipedia über Newline ist hier viel genauer, aber eben leider auf Englisch.


Was bedeutet das für die Praxis? Eine neue GetChar()-Prozedur!

Wir sollten eine Prozedur schreiben, die mit allen möglichen Zeilenenden fertig wird, auch schon deshalb, weil jemand, der unseren Compiler z.B. in einem Mac oder auf Linux benutzt, Probleme bekommt, wenn wir hier nicht hilfreich diese Probleme im Vorfeld vermeiden.


Die neue Prozedur GetChar(), die mit vielen gängigen Zeilenumbruchsvarianten zurechtkommt:

Code: Alles auswählen

  Procedure GetChar()    
           
    ; Look aus dem Source-Code-Stream holen
      Look = *Source_Pos\a  
      *Source_Pos+1               

    ; alle möglichen Zeilenenden zu '¶' umwandeln
    ; in '¶'=182: End of Line, Zeilenende   
    ; Zeilenummer hochzählen
      If    (Look=#CR And *Source_Pos\a=#LF) Or 
            (Look=#LF And *Source_Pos\a=#CR)    
                Look='¶'
                LineNr+1
                *Source_Pos+1       ; überspringe 2. Zeichen 
                
      ElseIf Look=#CR Or Look=#LF               
                Look='¶'
                LineNr+1
      EndIf
               
  EndProcedure     
Diese Prozedur schickt ein von uns definiertes Token mit der Konstante 182 statt den anderen Zeilenendzeichen als Look weiter.
Es tauscht also etwas im Character Stream aus. Ein zweite wichtige Sache ist hier eingbaut, jedesmal wenn ein Zeilenende erfolgt, wird die Zeilennummer um 1 erhöht. Damit können wir später den Ort eines Fehlers eingrenzen.


Starten wir jetzt noch einmal den Scanner, dann müssten alle "13 10" am Ende ausgetauscht sein gegen Token-Code Nr. 182, den ich durchaus bewusst (wie viele andere Token-Codes auch) so gewählt habe. Hier ist es ein von Word verwendeter Code, der ein Zeilenende anzeigt und sich als Zeichen im Debug-Fenster schön anzeigen lässt (Code 182 ist das "¶" - Paragraphzeichen, bei uns sagt man im Volksmund "die Pi's" dazu wegen der Ähnlichkeit zu PI).
Wir hätten prinzipiell auch jede andere beliebige Zahl wählen können.

Code: Alles auswählen

alte Lösung:
^^^^^^^^^^^

  ... gekürzt ...

 | * | 42
 | / | 47  <== Ende: Blockkommentar
 | 
 | 13      <== ASCII 13: #CR -> Zeilenende (ENTER-TASTE)
 | 
 | 10      <== ASCII 10: #LF -> Zeilenende (ENTER-TASTE)
 | 6 | 54
 | / | 47
 | 2 | 50
0-Byte: außerhalb der While-Schleife


neue Lösung:
^^^^^^^^^^^

  ... gekürzt ...

 | * | 42
 | / | 47  <== Ende: Blockkommentar
 | ¶ | 182 <=== AUSGETAUSCHT GEGEN TOKEN-CODE 182  
 | 6 | 54
 | / | 47
 | 2 | 50
0-Byte: außerhalb der While-Schleife



4.6. Die Is?()-Token-Typ-Erkennungsmacros

Im Kapitel "Hintergrundgedanken zum Scanvorgang" erwähne ich immer wieder Prozeduren wie IsName() oder IsNumber().
Ich werde sie als Macros implementieren.
Diese Macros sollen anhand des Look erkennen, welcher Token-Typ folgen könnte. Außerdem kann ein Is?()-Macro anhand eines Zeichens erkennen, ob dieses in einem bestimmten Token-Typ vorkommt.

Hier eine Auflistung der Is?()-Erkennungsmacros:

Code: Alles auswählen

=============================================================
Erkennungs-     Zeichen          Anmerkung
macro                                           
=============================================================
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
-------------------------------------------------------------
IsNumber()      0..9 .           Zahl
-------------------------------------------------------------
IsString()      "                Start-Zeichen eines Strings
                                 Ende-Zeichen eines Strings  
-------------------------------------------------------------
IsWhite()       Leerzeichen      Zeichen, die der Scanner
                #TAB ¶ ;         überspringt
                /                (bzw. / löst Kommentar aus)                                 
=============================================================
Die als Macros ausgeführten Is?()-Macros:

Code: Alles auswählen

  
    ; --- Is?-Erkennungs-Macros ---
      
      Macro IsNumber1(c)    ; Zeichen gehört zu Start einer Zahl?
        (c>='0' And c<='9')
      EndMacro	       
      Macro IsNumber(c)     ; Zeichen gehört zu einer Zahl?
        ((c>='0' And c<='9') Or c='.')
      EndMacro	       
      Macro IsName1(c)     ; Zeichen ist Start eines Namens?
        ((c>='a' And c<='z') Or (c>='A' And c<='Z'))
      EndMacro	       
      Macro IsName(c)      ; Zeichen gehört zu einem Namen?
        (IsNumber(c) Or IsName1(c) Or c='_')
      EndMacro	       
      Macro IsString(c)    ; Zeichen ist der Start eines Strings?
        c='"'
      EndMacro	       
      Macro IsWhite(c)     ; Zeichen ist ein White-Character?
        (c=' ' Or c=#TAB Or c='/' Or c=';' Or c='¶')
      EndMacro	
     ;Anmerkung: / startet einen Zeilenkommentar mit '//' (wie in C)
     ;           / startet einen Blockkommentar mit  '/*' (wie in C)  

Sehr schön ist auch, dass man, wenn man zum Beispiel Token 182 ('¶') - wir haben gerade über End of Line weiter oben diskutiert - nicht mehr als White-Zeichen führen will, es einfach aus dem Macro 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.7. Die Get-Prozeduren und die Token-Codes

Die wichtigste Prozedur, die zumeist vom Parser aufgerufen werden wird, ist die GetToken()-Prozedur.
Sie dient als Verteiler. Mittels den Is?()-Macros 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() sorgt dafür.


Die zentrale Verteilerprozedur GetToken():

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         
			
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems			
			
  EndProcedure    


Die folgenden Get()-Prozeduren holen jeweils 1 Token aus dem Strom von Zeichen des Source-Codes.



Die Prozedur, die Namen holt - GetName():

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("Ein Variablen-, Prozedurname oder TTC-Befehlswort")
      EndIf  
    
    ; Token mit Token-Code (=78) für Name füllen
      Token = 'N'

    ; Lexem mit Name füllen
      Lexem = ""        
      Repeat
          Lexem = Lexem + Chr(Look)
          GetChar()
      Until Not IsName(Look)

    ; Name-Identifier sind nicht Case sensitiv      
      Lexem = LCase(Lexem)          
      
    ; am Ende ueberspringe alle White Characters und Comments
      SkipWhite()       
  
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems
  
  EndProcedure
  • GetName() holt zunächst in der Repeat-Schleife alle Zeichen, die in ein Name-Token gehören. Beim ersten Nicht-Name-Zeichen ist das Lexem korrekt gefüllt.
  • Es wird überprüft, ober das Lexem ein reserviertes Schlüsselwort ist und dessen Token zugewiesen.
  • Es ist irgendein Variablen- oder Prozedurname und das Token 'N' (Code 78) wird zugewiesen.


Die Prozedur, die Zahlen holt - GetNumber():

Code: Alles auswählen

  Procedure GetNumber() 
  
    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
  
    ; 1. Zeichen korrekt fuer Number?
      If Not IsNumber1(Look):Expected("Eine Zahl"):EndIf       
      
    ; Lexem mit Number füllen
      Lexem = ""        
      Repeat
          Lexem = Lexem + Chr(Look)
          GetChar()
          If Look='.':point+1:EndIf
      Until Not IsNumber(Look)  
       
    ; Float-Number, Fehler oder Integer?
      If     point=0:
                  Token='I'
                  
      ElseIf point=1:
                  Token='F'
                ; Testen, ob zu kurz?
                  If Len(Lexem)<3:
                      Error("Die Fließkommazahl ist unvollständig.")
                  EndIf 
                             
      Else        
                  Error("In einer Fließkommazahl darf nur maximal "+
                        "ein Kommapunkt vorkommen und nicht "+Str(Point)+".")
      EndIf       
            
       
    ; ueberspringe alle White Characters und Comments
      SkipWhite()  
  
    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems

  EndProcedure 
  • GetNumber() holt eine Zahl, Ziffer für Ziffer. Bei der ersten Nichtziffer ist das Lexem korrekt gefüllt. Es wird hier unterschieden zwischen Integer (ohne Dezimalpunkt) und Float.
  • Anmerkung: Genau hier könnte man auch z.B. eine Hex-Zahl oder Ähnliches erkennen und der jeweiligen Situation entsprechende Token-Codes zuweisen und/oder Umwandlungen vornehmen.


Die Prozedur, die Strings holt - GetString():

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("Ein konstanter String in "+#DQUOTE$+#DQUOTE$)
      EndIf  
      
    ; Token mit Token-Code (=83) für String füllen
      Token = 'S'
      
    ; '"' String-Start-Zeichen überspringen 
      GetChar()  
      
    ; Lexem mit String füllen
    ; bis Ende-Zeichen '"'
      Lexem = ""        
      While Not IsString(Look)
          Lexem = Lexem + Chr(Look)
          GetChar()
      Wend
      
    ; 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   
  • GetString() holt einen String innerhalb von Anführungszeichen. Wir dürfen nicht vergessen, dass wir die Erkennungszeichen in IsString() eigenhändig definiert haben. Wir könnten das DORT jederzeit z.B. auf einfache Anführungszeichen, oder was auch immer wir wünschen, ändern, wenn wir das wollen würden.


Die Prozedur, die mehrteilige Operatoren und alles andere holt, also den Rest, der übrig bleibt - GetOther():

Code: Alles auswählen

  Procedure GetOther()

    ; --> in Look ist jetzt das 1. Zeichen dieses Token-Lexems
     
     ; Look sichern
       look1 = Look
     
     ; nächsten nicht-White-Character holen (siehe SkipWhite())
       GetChar() 
       
     ; ueberspringe alle White Characters und Comments      
       SkipWhite()           
     
     ; ** mehrteilige Operatoren testen und abschicken **
       If     look1='<' And Look='>' : Token='u' ; 'u'ngleich       
                                       GetChar() ;   Token-Code 117 
       
       ElseIf look1='<' And Look='=' : Token='k' ; 'k'leinergleich
                                       GetChar() ;   Token-Code 107            
       
       ElseIf look1='>' And Look='=' : Token='g' ; 'g'rößergleich      
                                       GetChar() ;   Token-Code 103  
       
       Else                          : Token = look1 
                                       Lexem = Chr(look1)  

       EndIf                   
    
    
    ; ueberspringe alle White Characters und Comments      
      SkipWhite()      

    ; --> in Look ist jetzt das 1. Zeichen des nächsten Token-Lexems      
     
  EndProcedure
  • GetOther() 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() wird auch alle mathematischen Operatoren (sowohl einteilige als auch mehrteilige) aufnehmen.
  • GetOther() sucht nach mehrteiligen mathematischen Operatoren (wie "<>", ">=", ...) und weist bei Fund den entsprechenden Token-Code (siehe oben) zu. Dabei werden dann natürlich 2 Look übersprungen.
  • Durch diese Implementation der mehrteiligen Operatoren darf man einen mehrteiligen Operator auch durch ein White-Zeichen trennen, also es ist z.B. "< LEERZEICHEN >" oder auch "< ENTER >" erlaubt.
  • Findet GetOther() keinen mehrteiligen Operator, dann schickt er als Token-Nr. einfach die ASCII-Zahl des Look (hier konkrekt look1) weiter, als Lexem den String von Look. Wir müssen also darauf achten, niemals einen Token-Code zu erfinden, der gleichzeitig als Other weitergeschickt werden sollte.
    Warum ich hier nicht auch für alle anderen Zeichen, wie z.B. einteilige Operatoren oder die Klammer usw., eine Token-Nr. vergeben lasse? Speed und unnötige Arbeit, eine Code-Zahl ist eine Code-Zahl , auch wenn sie vorher "zufällig" die Ascii-Zahl des Look war.


Abschließend noch eine zusammenfassende Übersichtstabelle, die die Tokencodes in gruppierter n Form mit den entsprechenden Prozeduren zeigt.


Zusammenfassung der Tokencodes in TTC:

Code: Alles auswählen

=============================================================
Bearbeitungs-   Token-                            Lexem für
prozedur        Codes                             den Parser
                                                  notwendig?             
=============================================================
                   
               Variablennamen, Prozedurenamen
               reservierte Schlüsselwörter, ...
GetName()                                             ja 
               bekommt TOKEN-Code 78, 'N'ame                                                                   

=============================================================

               Integer-Zahl oder Float-Zahl
GetNumber()                                           ja
               bekommt Token-Code 73, 'I'nteger
               bekommt Token-Code 70, 'F'loat

=============================================================

               String in "..." 
GetString()                                           ja
               bekommt Token-Code 83, 'S'tring

=============================================================

               mehrteiliger Operator wie:
                 <>: 117, 'u'gleich
                 <=: 107, 'k'leinergleich
                 >=: 103, 'g'rößergleich             nein            
               
               jeder Operator bekommt 
               einen EIGENEN TOKEN-Code 

GetOther()   ------------------------------------------------

               nichts von allem -> Rest

               jedes Zeichen (es handelt sich       
               hier nur mehr um jeweils              zum Teil
               1 Zeichen) bekommt als     
               TOKEN-Code seinen eigenen 
               ASCII-Code 


               Anmerkung:
               ^^^^^^^^^ 
               Neben den einteiligen Operatoren 
               (wie <,>,=,*,...), 
               und anderen Zeichen ({,},...), 
               die der Scanner nicht näher einordnen 
               kann, ist auch das 0-BYTE für das 
               Ende des Parse-Vorgangs hier als Other
               dabei.               

=============================================================
Erklärung zur Frage: "Lexem für den Parser notwendig?"
-------------------------------------------------------------
nein: Parser kann Token bereits aus Token-Code-Zahl erkennen,
      ohne das Lexem weiter untersuchen zu müssen.

zum
Teil: manche Token, z.B. "{" als Block-Beginn-Zeichen oder 
      "[" als Label-Kennung für den Assembler, werden be-
      nötigt werden, deshalb wird ein einfaches Other mit
      seinem Character als Lexem weitergeschickt.	

ja:   Parser wird das Lexem weiter untersuchen bzw. be-
      nützen müssen oder wollen.
=============================================================

Re: Tutorial - Compiler und Virtual Machine (nicht beschreib

Verfasst: 10.10.2013 18:12
von puretom
4.8. Überspringen unnötiger Zeichen


4.8.1. Filtern von White-Zeichen: SkipWhite()

Zunächst wollen wir unseren Scanner wieder testen.

Dazu schreiben wir uns erneut eine Debug-Prozedur (außerhalb aller Module). Diesmal arbeiten wird aber nicht mehr mit einzelnen Zeichen, sondern bereits mit den Zeichengruppen, also mit Tokens und den Lexemen.

Die neue Start-Prozedur können wir auch mit Start() (also nicht mehr Start_GetChar()) benennen, diese Version ist schon die "echte" Startprozedur für den späteren Parser:

Code: Alles auswählen

  Procedure Start(file_name.s="") 
  
    ; laden des Source-Files in Memory-Bereich *Source_Code
    ; Wenn Argument leer, dann kein neues Laden!  
      If file_name<>"":Load(file_name.s):EndIf
      
    ; '*Source_Pos' auf 1. Zeichen stellen
      *Source_Pos = *Source_Code      
      
    ; LineNr auf 1. Zeile stellen
      LineNr=1
      
    ; das erste aktuelle Token-Lexem-Paar holen  
      Lexem = ""   ; falls kein Neuladen erfolgt ist
      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    
  
  EndProcedure  
  • Die Prozedur Start() führt wieder diverse Initialisierungen durch (wie gehabt)
  • falls Start() ohne Parameter aufgerufen wird, dann wird in *Source_Code kein neues File geladen, das alte bleibt bestehen. Wir werden dieses Feature irgendwann nutzen, wenn wir über einen Text 2-mal hintereinander (2 Passes) scannen wollen. Dann müssen wir nicht bei jedem einzelnen Pass immer neu laden.
  • Für den Fall, dass kein neues File geladen worden ist, muss das Lexem mit Lexem="" gelöscht werden, es könnte noch ein altes vorhanden sein.
  • Wir müssen jetzt, da wie statt mit Characters ab jetzt mit Tokens arbeiten, unsere Regel befolgen, dass immer ein gültiges Objekt vor Start des Parsers (vorher Scanners - wir sind ab jetzt schon eine Ebene höher, auf der Tokenebene) im Token-Lexem-Paar-Stream ist.

Eine Prozedur Stop() befreit uns von einem Memorybereich. Wir sollten sie immer am Ende eines Scannerlaufs aufrufen.

Code: Alles auswählen

  Procedure Stop()
      FreeMemory(*Source_Code)  
  EndProcedure

Die Debug-Prozedur Prozedur Debug_GetToken():

Code: Alles auswählen

Procedure Debug_GetToken()  
   
  Scanner::Start("source-code.ttcs")

  While ( Scanner::Token <> 0 )
        Debug " | "+Chr(Scanner::Token)+              ; CHAR des Token-Codes
              " | "+RSet(Str(Scanner::Token),3," ")+  ; Code-Nr des Tokens
              " | "+Scanner::Lexem                    ; Lexem
        Scanner::GetToken()  
  Wend   
  Debug "0-Token: außerhalb der While-Schleife"

EndProcedure
Sie zeigt uns einfach der Reihe nach alle Tokens an.
Wir werden bei unseren restlichen Tests mit dem Scanner in diesem Kapitel ab jetzt diese Prozedur statt Debug_GetChar() aufrufen (einfach auskommentieren).


Erinnern wir uns an unseren Source-Code zum Testen, um die Erkennung aller Tokens überprüfen zu können:

Code: Alles auswählen

name  "Ich String"  56547 // Zeilenkommentar
( <  < >  <= > /*Blockkommentar*/
6/2
Dieser Source-Code hat Kommentare, Leerzeichen, aber auch sinnvolle Token-Lexeme (siehe oben).


Starten wir Debug_GetToken()!
Auf der linken Seite sehen wir den Token-Code als Character mit Chr() ausgedruckt, in der Mitte des Token-Code als Zahl und rechts den Lexem-String.
Ich habe für uns zusätzlich alle Tokens, die wird mit den Skip-Prozeduren ignorieren werden, mit '-' und alles, was ein "echtes" Token ist, mit '+' markiert. Diese Markierungen sowie meine Anmerkungen finden wir nicht in der Debug-Ausgabe von PB.
Darüber hinaus ist alles klein geschrieben, das liegt am LCase() in GetName(), weil TTC nicht Case-sensitiv ist.

Code: Alles auswählen

+| N |  78 | name            <== echtes 'N'-Token mit Lexem "name"
-|   |  32 |                 <== Leerzeichen, in Lexem bleibt alter Wert, wir belegen 
-|   |  32 |                     keinen neuen in den Get-Prozeduren aus Speed-Gründen.
+| S |  83 | Ich String      <== echtes 'S'-Token mit Lexem "Ich String"
-|   |  32 | 
-|   |  32 | 
+| I |  73 | 56547           <== echtes 'I'-Token mit Lexem "56547"
-|   |  32 | 
-| / |  47 | /               <== '/'-Token, aber das wird einmal ein
-| / |  47 | /                   Start für Zeilenkommentar werden
-|   |  32 | 56547
-| N |  78 | zeilenkommentar
-| ¶ | 182 |                 <== Zeilenende, auch Ende Zeilenkommentar
+| ( |  40 | (               <== echtes '('-Token 
-|   |  32 | 
+| < |  60 | <               <== echtes '<'-Token 
-|   |  32 | 
-|   |  32 | 
+| < |  60 | <                --. die beiden zusammen werden einmal <>
+|   |  32 |                    | werden, da aber SkipWhite() noch nicht
+| > |  62 | >                --' funktioniert, trennt sie noch ein Leerzeichen
-|   |  32 | 
-|   |  32 | 
+| k | 107 |                 <== echtes 'k'-Token, 'k'leinergkeich: <=
-|   |  32 |  
+| > |  62 | >               <== echtes '>'-Token 
-|   |  32 | 
-| / |  47 | /               <== '/'-Token, aber das wird einmal ein
-| * |  42 | *                   Start für Blockkommentar werden
-| N |  78 | blockkommentar 
-| * |  42 | *               <== Ende Blockkommentar
-| / |  47 | /
-| ¶ | 182 | 
+| I |  73 | 6               <== echtes 'I'-Token mit Lexem "6"
+| / |  47 | /               <== echtes '/'-Token: Division 
+| I |  73 | 2               <== echtes 'I'-Token mit Lexem "2"
0-Token: außerhalb der While-Schleife

Lassen wir zunächst alle White-Zeichen, so wie wir sie in IsWhite() festgelegt haben, verschwinden und schreiben eine erste Version von Skipwhite[/b]:

Code: Alles auswählen

  Procedure SkipWhite()

    ; solange in Look ein White
      While IsWhite(Look)

          GetChar()

      Wend
	    
  EndProcedure
  • Diese Prozedur filtert alle White-Zeichen aus dem Token-Lexeme-Strom heraus.
  • Die While-Schleife wird beim ersten Nicht-White-Zeichen verlassen.
  • In Look liegt also das 1. Nicht-White-Zeichen, ganz exakt so, wie wir das wollen.

Starten wir erneut Debug_GetToken()!

Code: Alles auswählen

+| N |  78 | name
+| S |  83 | Ich String
+| I |  73 | 56547           
-| N |  78 | zeilenkommentar <== noch falsch, weil noch kein SkipLineComment()
+| ( |  40 | (
+| < |  60 | <
+| u | 117 | <               <== durch SkipWhite() geht jetzt < _ > 
+| k | 107 | <                   (bei 'u' & 'k' bleiben die alten Lexeme - egal)
+| > |  62 | >
-| * |  42 | *
-| N |  78 | blockkommentar
-| * |  42 | *
+| I |  73 | 6               <== hier ist zunächst '/' verloren gegangen
+| I |  73 | 2 
0-Token: außerhalb der While-Schleife
  • Alle White-Zeichen sind verschwunden, insbesondere die Leerzeichen.
  • Da auch das Zeichen '/' ein White-Zeichen ist, bleibt vom Block-Kommentar nur das '*' über.
    Deshalb werden wir logischerweise die Kommentare in SkipWhite() hinzufügen.
  • Vom Zeilenkommentar sind sowieso alle '/' herausgefiltert worden.
  • Wir dürfen aber nicht vergessen, dass wir '/' auch als Divisionsoperator benötigen werden.


4.8.2. Filtern von Zeilen-Kommentaren

Wie bereits angedeutet, werden wir die Zeilenkommentare in SkipWhite() einfügen, weil ein '/' als White-Zeichen durch IsWhite() erkannt wird.

Ein Zeilenkommentar ist definiert, dass er mit '//' beginnt und mit einem #eol oder dem Datei-Ende (= 0-Token).
Letzteres dürfen wir nicht vergessen, sonst hängt der Scanner, wenn in der letzten Zeile ein Zeilenkommentar ist und der Programmierer nach dem Zeilenkommentar kein Enter gedrückt hat. Dasselbe gilt dann auch für einen Block-Kommentar.


Die erweiterte Version von Skipwhite[/b], angepasst an Zeilenkommentare, auch hier recyclen wir wieder den Look1, wenn wir ihn schon für die #eol-Behandlung geladen haben:

Code: Alles auswählen

  Procedure SkipWhite()

    ; solange in Look ein White
      While IsWhite(Look)
          
          ; Zeichen hinter Look holen
          ; *Source_Pos steht nach letztem
          ; GetChar() schon richtig darauf
            behind_look = *Source_Pos\a  

          ; Zeilenkommentar '// ... #eol/0-Byte'
            If Look='/' And behind_look='/'
                SkipLineComment()                   

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

          ; sonstige White-Zeichen überspringen
           Else
                GetChar()
           EndIf

      Wend
	    
  EndProcedure
Die Lösung für den mathematischen Divisionsoperator '/' ist etwas unstrukturiert programmiert, dafür aber sehr funktional ;-) .


Die dazugehörende Prozedur SkipLineComment, die in der While-Schleife angesprungen wird, wenn ein '//' als Startkombination für einen Zeilenkommentar erkannt wurde:

Code: Alles auswählen

  Procedure SkipLineComment()

    ; bis Zeilenende oder Ende des Source-Files (0-Byte)
      While ( Look<>'¶' And Look<>0 )
          GetChar()
      Wend 
        
    ; --> Look steht auf #eol 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 #eol steht  
        
  EndProcedure
Ich denke, der Code erklärt sich selbst.


Starten wir erneut Debug_GetToken(), und tatsächlich: Alle Zeilenkommentare sind verschwunden einerseits, aber andererseits die '/', die als einfache '/' erkannt werden solen und Divisionsoperatoren sind, sind wieder da:

Code: Alles auswählen

+| N |  78 | name
+| S |  83 | Ich String
+| I |  73 | 56547
+| ( |  40 | (
+| < |  60 | <
+| u | 117 | <
+| k | 107 | <
+| > |  62 | >
+| / |  47 | /              <== Start: Blockkommentar
 | * |  42 | *
 | N |  78 | blockkommentar
 | * |  42 | *
 | / |  47 | /              <== Ende: Blockkommentar
+| I |  73 | 6
+| / |  47 | /              <== '/' wieder als Division da
+| I |  73 | 2
0-Token: außerhalb der While-Schleife


4.8.3. Filtern von Block-Kommentaren

Von Zeilenkommentaren ist es nur ein ganz kleiner Schritt zu Blockkommentaren.


Die nochmals erweiterte Version von Skipwhite[/b], angepasst an Blockkommentare, auch hier recyclen wir wieder den Look1, wenn wir ihn schon für die #eol-Behandlung geladen haben.
Wir wenden einfach dieselbe Technik an wie beim Zeilenkommentar und wir dürfen auch hier nicht vergessen, dein einfachen mathematischen Operator '/' im Token-Strom zu belassen (nebenbei: alles Probleme, die wir nicht hätten, wenn wir andere Zeichen, wie z.B. ';' in PB oder '{ ... }' in Pascal als Kommentarbegrenzer verwenden würden):

Code: Alles auswählen

  Procedure SkipWhite()

    ; solange in Look ein White
      While IsWhite(Look)
          
          ; Zeichen hinter Look holen
          ; *Source_Pos steht nach letztem
          ; GetChar() schon richtig darauf
            behind_look = *Source_Pos\a  

          ; Zeilenkommentar '// ... #eol/0-Byte'
            If Look='/' And behind_look='/'
                SkipLineComment()
                   
          ; Blockkommentar '/* ... */'
            ElseIf Look='/' And behind_look='*'
                SkipBlockComment()

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

          ; sonstige White-Zeichen überspringen
           Else
                GetChar()
           EndIf

      Wend
	    
  EndProcedure
Jetzt erkennen wir auch '/*' und verzweigen wieder in eine entsprechende Prozedur.


Die dazugehörende Prozedur SkipBlockComment, die in der While-Schleife angesprungen wird, wenn ein '/*' als Startkombination für einen Blockkommentar erkannt wurde:

Code: Alles auswählen

  Procedure SkipBlockComment()

    ; '/' überspringen
      GetChar() 
    
    ; solange bis '*/'  
      Repeat      
            
          ; Zeichen holen, bei Ersteintritt '*' überspringen
            GetChar()
          
          ; Zeichen hinter Look holen
          ; *Source_Pos steht nach letztem
          ; GetChar() schon richtig darauf
            behind_look = *Source_Pos\a  

          ; verschachtelte Block-Kommentare ermöglichen
            If Look='/' And behind_look='*'
                SkipBlockComment()
            EndIf
            
          ; auf 0-Byte achten -> sofort raus
            If Look=0: ProcedureReturn: EndIf
        
      Until Look='*' And behind_look='/'
     
    ; '*/' 2-mal ü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 z.B. auch folgende Situationen kein Problem:

Code: Alles auswählen

/**/
/*/**/*/

Starten wir erneut Debug_GetToken(), und tatsächlich: Alle Zeilenkommentare UND Blockkommentare sind verschwunden.

Code: Alles auswählen

 | N |  78 | name
 | S |  83 | Ich String
 | I |  73 | 56547
 | ( |  40 | (
 | < |  60 | <
 | u | 117 | <
 | k | 107 | <
 | > |  62 | >
 | I |  73 | 6
 | / |  47 | /
 | I |  73 | 2
0-Token: außerhalb der While-Schleife
Fertig!




4.9. Primitive Fehlerbehandlung


Wir können bereits auf Scanner-Ebene eine einfache Fehlerbehandlung realisieren.
Die Get()-Prozeduren haben ziemlich zu Beginn eine Abfrage ihrer entsprechenden Is()-Prozedur eingebaut.
Wofür?

Der Parser wird in bestimmten Situationen nicht immer GetToken() aufrufen. Wenn er zum Beispiel weiß, dass er sicher einen Name oder eine Integer-Zahl erwartet, dann ruft er gleich GetName() bzw. GetNumber() 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.

Code: Alles auswählen

  Procedure Error(fehlertext.s)
  
  ; Fehlertext in Message Requester ausgeben.
    MessageRequester("Scanner Error",
                      fehlertext+#CRLF$+#CRLF$+
                      "Token-Zeichen: "+Chr(Token)+#CRLF$+
                      "Token-Code: "+Token+#CRLF$+
                      "Lexem: "+Lexem+#CRLF$+
                      "Zeile: "+LineNr) 
  
  ; Scan- und somit Compilevorgang brutal abbrechen 
    End  
      
  EndProcedure

Code: Alles auswählen

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


4.10. Schlussbemerkungen

So, wir haben jetzt einen einfachen 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 natürlich auch der Parser das als End-Of-Source-File verwendet, um sich zu beenden (wie man wir auch in Debug_GetToken() machen).