[Tutorial] Compiler und Virtual Machine

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

[Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

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.
  • Anmerkungen und Kritik, Lob sowie sonstige Meldungen bitte HIER im Diskussionsthread!
Neues Tutorial lesen in Tutorial - Compiler und Virtual Machine

Die alten Beiträge lasse ich zu Dokumentationszwecken

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

Puretom

------------------------------------------------------------------------------------------

*** IHNHALTSVERZEICHNISSE ***

ÜBERBLICK

1. Vorwort, Ziele
2. Literaturempfehlungen
3. Das große Bild
4. Schrittweise Entwicklung eines lexikalischen Scanners
5. Kurze Einführung in Assembler/Maschinensprache
6. Statements und Blocks: Die Struktur eines Programms
7. Parsen und Kompilieren mathematischer Ausdrücke (Expressions)
8. Module Code und ein erster Zwischenstopp
9. Wesentliche Erweiterung des mathematischen Parsers
10. Variablen, Deklarationen, Zuweisungen (Assignments) oder "Wir erzeugen unser erstes echtes Programm"




GESAMTINHALTSVERZEICHNIS


1. Vorwort, Ziele
  • 1.1. Zu meiner Person
    1.2. Der Plan


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. Das große Bild
  • 3.1. Einleitung

    3.2. Überlick über die Teile des gesamten Projekts
    • 3.2.1. Der Compiler
      3.2.2. Der Assembler
      3.2.3. Die Virtual Machine (VM)
    3.3. Zusammenfassung


4. Schrittweise Entwicklung eines lexikalischen Scanners
  • 4.1. Vorbemerkungen
    4.2. Hintergrundgedanken zum Scanvorgang
    4.3. Das Grundgerüst des Scanners, laden und testen des Character Streams
    4.4. Das Ende einer Programmzeile und Semikolons
    4.5. Die Token-Typen und die Is?()-Erkennungsprozeduren

    4.6. Die Get()-Prozeduren und die Token-Codes
    • 4.6.1. GetToken(), GetName(), GetNum(), GetString(), GetOther()
      4.6.2. Die Token-Codes()
    4.7. Heureka! Es funktioniert!
    • 4.7.1. Die neue Start()-Prozedur
      4.7.2. Die Token-Lexem-Schleife des späteren Parsers, eine Debug-Prozedur
      4.7.3. Erster Testlauf des Scanners
      4.7.4. SkipWhite(), das Überspringen von White-Zeichen
      4.7.5. SkipLineComment(), das Überspringen von Zeilenkommentaren
      4.7.6. SkipBlockComment(), das Überspringen von Kommentarblöcken
      4.7.7. Die Error()-Prozeduren
    4.8. Schlussbemerkungen


5. Kurze Einführung in Assembler/Maschinensprache
  • 5.1. Vorbemerkungen
    5.2. Was ist Maschinensprache?
    5.3. Was ist ein Stack?

    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. Statements und Blocks: Die Struktur eines Programms
  • 6.1. Der Plan
    6.2. Einleitende Worte zum Aufbau eines Programms
    6.3. Start-Gerüst für den Parser des 6. Kapitels
    6.4. Compile()-Prozedur: Lesen des Token-Lexem-Stroms

    6.5. Ein Statement (Befehl, Anweisung)
    • 6.5.1. Prozedur Compile() und Prozedur Statement()
      6.5.2. Das Erkennen von Befehlswörtern in Statement()
    6.6. Ein Block von Statements
    6.7. Der Gesamt-Code von Kapitel 6 (mit dem kompletten Scanner von Kapitel 4)




7. Parsen und Kompilieren mathematischer Ausdrücke (Expressions)
  • 7.1. Vorbemerkungen zur Präzedenz von Operatoren
    7.2. Das Gerüst des Expression Parsers
    7.3. Parsen eines Operanden: ValueFactor()

    7.4. Parsen von Addition und Subtraktion: AddExpression()
    • 7.4.1. Einfachste Ausdrücke mit maximal 2 Operanden und einem Operator
      7.4.2. Einfache Ausdrücke mit beliebiger Anzahl von Operatoren
    7.5. Parsen von Multiplikation, Division, Modulo: MulTerm()

    7.6. Wie funktionert der mathematische Parser
    • 7.6.1. Beispiel 1: Höchste Ebene 1-mal erreicht
      7.6.2. Beispiel 2: Höchste Ebene 2-mal erreicht
      7.6.3. Zusammenfassende Erklärung mit 2 expliziten Stacks
    7.7. Klammerausdrücke

    7.8. Negation: negative Zahlen und Klammerausdrücke
    • 7.8.1. Negative Zahlen: Unäre Operatoren
      7.8.2. Negative Klammerausdrücke
    7.9. Abschließende Betrachtungen
    7.10. Code-Teil: Compiler von Kapitel 7


8. Module Code und ein erster Zwischenstopp
  • 8.1. Vorbemerkungen

    8.2. Module Code
    • 8.2.1. Code-Ausgabe in die .ta-Datei
      8.2.2. Die neuen Hilfsprozeduren zur Label-Verwaltung
    8.3. Module Parser
    • 8.3.1. Die neue Hilfsprozedur SkipToken()

    8.4. Das Konzept der Start-Prozeduren
    8.5. Das Gerüst des Compilers von Kapitel 8
    8.6. Der gesamte Code bis Kapitel 8
    8.7. Kurzanleitung für Quereinsteiger


9. Wesentliche Erweiterung des mathematischen Parsers
  • 9.1. Hinzufügen neuer Operatoren: Vergleiche, boolesche Operatoren wie < <= <> = >= > and or xor
    • 9.1.1. Die neue Präzedenztabelle. Eine Diskussion
      9.1.2. Mathematischer Parser, Erweiterung um die Operatoren "< <= <> = >= > and or xor"
    9.2. Umbau der Implementation des Unary -|+

    9.3. Hinzufügen eines neuen Operators: Potenzieren ^
    • 9.3.1. Erster naiver und falscher Ansatz
      9.3.2. Operatorassoziativität und der Vorschlag einer Lösung

    9.4. Hinzufügen des unären logischen Not
    • 9.4.1. Vorüberlegungen
      9.4.2. Diskussion: logisches Not und die Operatoren and, or und xor?
      9.4.3. Diskussion: logisches Not und die restlichen Operatoren?
      • 9.4.3.1. Not-Operator mit sehr hoher Präzedenz (ohne Code)
        9.4.3.2. Not-Operator mit Präzedenz genau über "and, or, xor" (mit Code)
        9.4.3.3. Eine noch niedrigere Präzedenz für not?
        9.4.3.4. Einige Worte zur Assoziativität von not
    9.5. Kurz ein wenig Error Handling (Fehlerbehandlung)
    9.6. Zusammenfassung
    9.7. Code des Compilers von Kapitel 9


10. Variablen, Deklarationen, Zuweisungen (Assignments) oder "Wir erzeugen unser erstes echtes Programm"
  • 10.1. Wichtige taktische Entscheidung: Wer verwaltet die Variablen
    • 10.1.1. Der Assembler verwaltet die Variablen (gewählte Variante)
      10.1.2. Der Compiler verwaltet die Variablen

    10.2. Eine weitere taktische Entscheidung: Müssen Variablen deklariert werden?

    10.3. Aussehen einer Variablendeklaration in VM-ASM
    10.4. Parsen/Kompilieren eines ersten echten Programms
    10.5. Parsen/Kompilieren der Deklaration einer globalen Integer-Variable

    10.6. Assignment: Das Zuweisen eines Wertes an eine Variable
[/list]

... lange Baustelle

*** ENDE IHNHALTSVERZEICHNISSE ***
Zuletzt geändert von puretom am 07.10.2013 17:00, insgesamt 70-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Benutzeravatar
Bisonte
Beiträge: 2427
Registriert: 01.04.2007 20:18

Re: Tutorial: Compiler und Virtual Machine

Beitrag von Bisonte »

Der erste Beitrag und dann gleich sowas ....

:allright: Sauber !
PureBasic 6.04 LTS (Windows x86/x64) | Windows10 Pro x64 | Asus TUF X570 Gaming Plus | R9 5900X | 64GB RAM | GeForce RTX 3080 TI iChill X4 | HAF XF Evo | build by vannicom​​
Benutzeravatar
Regenduft
Beiträge: 574
Registriert: 25.03.2008 15:07
Wohnort: THE LÄÄÄND!

Re: Tutorial: Compiler und Virtual Machine

Beitrag von Regenduft »

Genial! Würde gerne eine Fortsetzung sehen, muss aber gestehen, dass gerade meine Prioritäten auf anderen Dingen liegen. Aber früher oder später würde ich mir das gerne zu Gemüte führen... <)

Fehler sind mir keine aufgefallen. Allerdings würde ich Hervorhebungen wie in "DAS Top-Werk" lieber durch Kursivschrift oder Unterstreichung empfehlen, da Kapitalschrift auch Abkürzungen ("D.A.S.") meinen könnte und somit manchmal irritieren kann. Das ist aber natürlich nur meine persönliche Meinung und "DAS" ist bisher die einzige Hervorhebung dieser Art (falls ich keine übersehen habe).

EDIT: Nanu? Wollte gerade dieses Posting löschen, damit das Tutorial schöner aussieht. Geht das nicht mehr?
Zuletzt geändert von Regenduft am 10.09.2013 01:54, insgesamt 1-mal geändert.
PureBasic 5.73 LTE x86/x64 | Windows 7 (x64)
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

*** KAPITEL 1 ***

1. Vorwort, Ziele


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 selbst 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

Zu meinem Plan: Ich würde gerne versuchen, eine Tutorialserie zu beginnen, die sich mit der Programmierung einer kleinen Spielzeug (Toy) - Scriptsprache, die C-ähnlich ist, beschäftigt. Diese soll dann auf eine Stack Machine als Virtual Machine compilieren und dann eben in einer solchen ablaufen. Ich würde gerne bei den allerersten Grundlagen beginnen, bei Adam und Eva.

Ich möchte nicht zu viele Versprechungen im Voraus machen und glaube auch, dass ich nur ca. 1-mal im Monat zu einem Teil kommen werde, v.a. aus beruflichen Gründen.

Als ersten Teil biete ich mal meine ganz persönliche Literaturtippliste an.

Sollte der Wunsch bestehen, dass ich mit meinem Plan weitermache, bitte um rege Nachfrage hier in diesem Thread, dann mache ich weiter.

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

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, 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 was auch immer übersetzt wird usw.
Jede Nutzung bedarf allerdings meiner Zustimmung eben über eine Nachricht.
Kommerzielle Nutzung ohne meine Zustimmung ist sowieso ausdrücklich verboten.
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!

*** ENDE KAPITEL 1 ***
Zuletzt geändert von puretom am 05.10.2013 23:11, insgesamt 17-mal geändert.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von STARGÅTE »

An deiner Stellen würde ich noch mal n neues Thema anfangen, und dieses Thema hier als Feedback-Thread nutzen.
Denn sonst zerhacken wir Feedbackgeber dein Tutorial ... wäre schöner wenns am stück ist.

Zum Feedback:

Es ist zwar gut das du Verweise angibst zu den einzelnen Bereichen, allerdings werden die meisten auf WIKI selber suchen.
Schöner wäre es, wenn du zB nach "langem suchen" eine schöne PowerPointPräsentation findest oder ein Gutes PDF, unabhängig von deiner Literaturempfehlung am anfang.

Zum Lexer: "Das Source-File ist ein Strom von Ascii-Zeichen" würde ich nicht so stehen lassen.
Lexer durchaus mit UTF8 oder Unicode arbeiten, um so zB auch griechische Buchstaben zu erkennen, ohne Maskierungszeichen, denn nicht in allen Sprachen sind Sonderzeichen in Variablennamen verboten.

Zum Parser: Was in deinem Tutorial vllt etwas unter geht, ist, dass es verschiedene arbeitsweisen bei Parsern gibt, Stichwort: Top-Down, Bottom-Up.
Oder zu mindest solltest du erwähnen, dass du für dein Beispiel das Modell eines LR-Parser (ggf. erklären) verwendest.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

@ Stargate
Zum Lexer: "Das Source-File ist ein Strom von Ascii-Zeichen" würde ich nicht so stehen lassen.
Lexer durchaus mit UTF8 oder Unicode arbeiten, um so zB auch griechische Buchstaben zu erkennen, ohne Maskierungszeichen, denn nicht in allen Sprachen sind Sonderzeichen in Variablennamen verboten.
korrekt, aber so genau möchte ich es gar nicht treiben.
Wer seine ersten Spielcompiler geschrieben hat in PB, für den, denke ich, ist das eh' selbstverständig, oder?
Ich möchte einfach primitivste Compilertechniken zeigen, va. auf Deutsch, weil ich nach jahrelangem Englischlesen mal endlich zumindest 1/4 von dem, was Crenshaw gemacht hat, an die deutschsprachige Community weitergeben will. Ich bin, wie erwähnt, kein Profi, sondern irgendwo im bestenfalls Mittellevel, hab aber schon einige Toy-Script-Compiler und Toy-VM's zum Laufen gebracht.
Zum Parser: Was in deinem Tutorial vllt etwas unter geht, ist, dass es verschiedene arbeitsweisen bei Parsern gibt, Stichwort: Top-Down, Bottom-Up.
Oder zu mindest solltest du erwähnen, dass du für dein Beispiel das Modell eines LR-Parser (ggf. erklären) verwendest.
Selbstverständlich hast du auch hier wieder recht. Genau deshalb war der Wiki-Hinweis von mir eingefügt, weil ich eben so genau NICHT sein möchte. Siehe meine Meldung oben. Compilerbau ist wohl einer der (wenn man es so wirklich auf Uni-Niveau, das ich nicht habe, betreibt) kompliziertesten Gebieten überhaupt. Und von vielem verstehe ich nur wenig. Ich möchte auf Deutsch vieles von dem, was ich vor allem von Crenshaw, Varanese, Wirth gelernt habe, teilen. Mehr habe ich auch nicht drauf, aber ich denke, in meiner Einleitung habe ich darauf hingewiesen.

Solltet ihr alle hier durch jahrelanges Programmieren mehr draufhaben, dann sollte man meinen Fred vielleicht ins Anfängerforum verschieben, denn an Anfänger (und mich hätte das als Anfänger damals vor Jahren gefreut) richte ich mich auch irgendwie, die einen allerersten Einstieg in dieses komplexe Thema suchen.
An deiner Stellen würde ich noch mal n neues Thema anfangen, und dieses Thema hier als Feedback-Thread nutzen.
Denn sonst zerhacken wir Feedbackgeber dein Tutorial ... wäre schöner wenns am stück ist.
Gute Idee, was meinst du, bin ich bei Tutorials zu Basic-Level, soll ich's hier oder im Anfängerforum posten?

Vielen Dank für dein Feedback.
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von STARGÅTE »

Das Thema ist hier bei Tutorials richtig!
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
ts-soft
Beiträge: 22292
Registriert: 08.09.2004 00:57
Computerausstattung: Mainboard: MSI 970A-G43
CPU: AMD FX-6300 Six-Core Processor
GraKa: GeForce GTX 750 Ti, 2 GB
Memory: 16 GB DDR3-1600 - Dual Channel
Wohnort: Berlin

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von ts-soft »

Wenn er den letzten Teil erreicht hat, einfach einen neuen Thread aufmachen und alle Teile hintereinander
einfügen. Hier die Teile durch einen Link ersetzen und dann wird es wieder übersichtlich, denke ich mal.

Ansonsten, danke für das nützliche Tutorial :allright:
PureBasic 5.73 LTS | SpiderBasic 2.30 | Windows 10 Pro (x64) | Linux Mint 20.1 (x64)
Nutella hat nur sehr wenig Vitamine. Deswegen muss man davon relativ viel essen.
Bild
Drago
Beiträge: 148
Registriert: 02.02.2010 18:22
Computerausstattung: Win XP SP3, AMD Sempron (MMX) 1.2 GHz, 512 MB, Nvidia GeForce FX 5200, 128 MB, DirectX 9.0c
Wohnort: Westerwald

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von Drago »

Also, ich bin ABSOLUTER NIXVERSTEHER bei diesem Thema und ich muss sagen,
wirklich super toll erklärt, sodas sogar ICH es verstehe.
Und es macht mich neugierig.....

:allright:
puretom
Beiträge: 109
Registriert: 06.09.2013 22:02

Re: [Tutorial] Compiler und Virtual Machine

Beitrag von puretom »

@ts-soft
ts-soft hat geschrieben:Wenn er den letzten Teil erreicht hat, einfach einen neuen Thread aufmachen und alle Teile hintereinander
einfügen. Hier die Teile durch einen Link ersetzen und dann wird es wieder übersichtlich, denke ich mal.

Ansonsten, danke für das nützliche Tutorial
Ja, WENN ich den letzten Teil je erreiche /:->

Dann mache ich es mal so, dann brauche ich zunächst auch keinen neuen Fred aufmachen, denn mir wäre es schon angenehm, unter jedem Teil direkt Feedback zu bekommen, sonst kenn ICH mich dann nicht mehr aus, v.a. wenn ich dann Code poste und ihr ev. unvermeidliche Bugs findet oder bessere Programmiertechniken als Feedback habt usw.

@Drago
Danke

@Stargate
Habe noch einige Anmerkungen dazugemacht.

@alle
Frage:
ASCII-Art als Abbildung geht ja irgendwie nicht richtig, weil die Schrift proportional ist.
Wenn ich ein Bild (oder PDF oder ZIP,...) uppen will, welchen gratis (!) Dienst, bei dem die Bilder auch länger oben bleiben, ohne gelöscht zu werden, würdet ihr mir empfehlen? Am liebsten würde ich mich nicht schon wieder wo registrieren, sondern einfach einen Link nach dem Upload bekommen (das war mal bei Rapidshare zu Dinosaurierzeiten so).
Windows 7 und Windows 10 (Laptop), PB 5.62 | Projekt: Tutorial - Compiler und Virtual Machine | vielleicht einmal ein Old School Text-Adventure Tutorial | Neu: Spielereien, Üben rund um OOP in PB
Antworten