😝 🏁 🎇 Schreiben eines BASIC-Interpreters im 80er-Jahre-Stil 💅🏿 😊 ☯️

Seit einigen Jahren arbeite ich an einem persönlichen Projekt, bei dem ein "gefälschter Emulator" erstellt (und tatsächlich erforscht) wird, dh ein in JavaScript geschriebener Emulator für einen Computer, der nie existiert hat. Diese Maschine sollte eine Hommage an die 8- und 16-Bit-Computer der 1980er und 90er Jahre sein.

Ich mag jedoch die Komplexität: Diese Maschine verwendete auch einen neuen Befehlssatz. Es ähnelt den in dieser Zeit verwendeten Kits, ist jedoch etwas einfacher zu bedienen. Der Retroputer wurde geboren . Im Laufe der Jahre wurde der Emulator erweitert und verbessert, aber höchstwahrscheinlich wird er nie "fertig" sein (schließlich handelt es sich um ein persönliches Forschungsprojekt).

Als @bbcmicrobot erschienIch wollte etwas Ähnliches für den Retroputer erstellen. Meine JS-Entwicklungsfähigkeiten beschränkten sich größtenteils auf das Front-End. Dies wäre also eine großartige Gelegenheit, um Back-End-Erfahrungen zu sammeln. Es gibt nur ein Problem: Retroputer kann nur seine eigene Assemblersprache verstehen. Es hat noch keine BASIC-Unterstützung.

Also habe ich mir den BASIC-Interpreter im Stil der 80er Jahre ausgedacht, also komplett in Assemblersprache, wie er damals geschrieben wurde. Ich entschied, dass es sich lohnt, meine Arbeit zu teilen, weil wir nicht oft in Bereiche eintauchen müssen, die so weit von den üblichen Abstraktionen entfernt sind. Mein alltägliches Tool (JavaScript) macht viele Aspekte trivial und manchmal scheint es sogar magisch. Das Verständnis der untersten Prozessebene hilft häufig beim Verständnis dieser Abstraktionen.

Also lasst uns anfangen.

Retroputer-Eigenschaften

16 ROM (KERNEL) c 1 (scratch space)

512 , 64

16- 6516, 512 4 64

4025, ,

1125

9800

Als ich Assembler für Retroputer schrieb, konnte ich das sehr praktische Pegjs-Tool verwenden. Es bot eine schnelle native Assemblysyntax, aber leider gibt es für Retroputer ASM nichts Vergleichbares. Das heißt, wir müssen den harten Weg gehen.

Das Parsen selbst erfolgt in mehreren Schritten. Eine Sprache, die einen Compiler verwendet, analysiert den Code in einen abstrakten Syntaxbaum (AST) (oder eine andere Darstellung) und kann diesen Baum dann verwenden, um fertigen nativen Code zu generieren. Daher muss das Programm für eine erfolgreiche Kompilierung syntaktisch korrekt sein.

Einige moderne Interpreter haben dieses Konzept ebenfalls, da es oft nützlich ist, einen Zwischen-AST zu generieren und ihn anstelle des Quellcodes auszuführen.

Für den BASIC-Interpreter auf einem Computer mit begrenzten Ressourcen ist es jedoch am effizientesten, in mehreren Phasen zu analysieren, von denen einige zur Laufzeit ausgeführt werden. Dies bedeutet jedoch, dass Syntaxfehler erst erkannt werden können, wenn Sie das Programm ausführen und zum Bereich des Codes mit dem Fehler navigieren.

Das Retroputer BASIC-Parsing besteht aus drei Schritten:

Strings konvertieren
Tokenisierung
Überprüfung der Laufzeitsyntax

Die ersten beiden Phasen treten auf, wenn der Benutzer das Programm aufruft (oder herunterlädt). Letzteres tritt während der Programmausführung auf. Grundsätzlich bilden die ersten beiden den Rumpf des Flugzeugs, garantieren jedoch nicht, dass es abheben wird. Die letzte Etappe ist ein Testpilot - wir hoffen, dass er abhebt, aber wir sind uns nicht sicher, bis er es versucht.

Hinweis: Retroputer BASIC-Quellcode (in Entwicklung) ist auf GitHub verfügbar .

Strings konvertieren

Dies ist der einfachste Teil des gesamten Prozesses. Vom Benutzer eingegebene Zeichenfolge wird in Großbuchstaben konvertiert, um nachfolgende Prozesse zu vereinfachen (und zu beschleunigen). BASIC unterscheidet nicht zwischen Groß- und Kleinschreibung, daher können wir dies nutzen.

<pre>print 2+2
' becomes:
PRINT 2+2</pre>

Das ist in JavaScript sehr einfach, oder?

theLine = theLine.toUpperCase();

In der Assemblersprache ist dieser Prozess jedoch detaillierter. Wir müssen das Zeichen lesen, es in Großbuchstaben konvertieren und es dann irgendwo speichern.

           ld  y,  0                # y is our index
_loop:     ld  al, [d, x, y]        # [d,x] is pointer to string
           cmp al, 97               # is al (char) in range?
           brs n   _continue        # Not a lowercase char; continue
           cmp al, 123              # high portion
           brs !n  _continue        # not a lowercase char; continue
           and al, 0b1101_1111      # uppercase!
           st  [d, x, y], al        # store back (we modify the original)
_continue: inc y                    # move our index along
           cmp al, 0                # check for NULL
           brs !z _loop             # No? Go back for more.

Der obige Code stimmt nicht ganz mit der Semantik der JavaScript-Version des Codes überein. Ein wichtiger Unterschied besteht darin, dass wir heute Unicode verwenden, um mit Text zu arbeiten. Daher kann die Konvertierung von Eingaben von Klein- in Großbuchstaben oft schwieriger und manchmal unmöglich sein (dies hängt von der Sprache ab). Retroputer lebt in der ASCII-Welt (genauer gesagt in der Welt seiner eigenen ASCII-Variante namens RetSCII), dh alle unterstützten Zeichen sind in acht Bits codiert. Für viele Sprachen ist dies völlig unzureichend, aber es entspricht den Realitäten dieser Zeit.

Dies bedeutet auch, dass wir eine niedliche ASCII-Funktion verwenden können, um von Klein- in Großbuchstaben zu konvertieren. Der Großbuchstabe "A" wird im ASCII-Code dargestellt 65, und der Kleinbuchstabe "a" wird durch den Code dargestellt97... Wenn Sie mit den Zweierpotenzen vertraut sind, sollten Sie diesen Unterschied bemerkt haben.

Es stellt sich also heraus, dass Kleinbuchstaben durch eine Zahl angegeben werden, die genau 32 mehr ist als die Anzahl der Kleinbuchstaben. Wenn wir wissen, dass der Wert im richtigen Bereich liegt, müssen wir nur 32 subtrahieren!

Dieser Ansatz wird funktionieren, aber wir können die Bits nur ein wenig modifizieren. Im Fall von Retroputer ist dies nicht schneller als die Subtraktion. Wenn jedoch keine Subtraktion erfolgt, müssen wir bei den Berechnungen nicht auf das Carry / Borrow-Flag achten. Es stellt sich heraus, dass wir anddas Bit anstelle des 32-Werts bitweise ausschalten können.

and al, 0b1101_1111         # turn off bit in 32-place
# versus
clr c                       # clear carry
sub al, 32                  # subtract 32

Aber es gibt eine Subtilität: Nicht alles kann in Großbuchstaben umgewandelt werden. Wenn der Benutzer beispielsweise ein Zeichenfolgenliteral hinzugefügt hat, müssen wir vorsichtiger sein, da Retroputer BASIC den Benutzer nicht ständig mit Großbuchstaben anschreien soll. (Während viele Computer dieser Zeit keine Kleinbuchstaben hatten, hatte der Retroputer dies nicht.)

Zum Beispiel:

print "Hello, World!"
' should become:
PRINT "Hello, World!"
' and not
PRINT "HELLO, WORLD!"

Dies bedeutet, dass wir verfolgen müssen, ob wir uns mitten in einem String-Literal befinden. In BASIC gibt es dafür nur eine Bezeichnung: doppelte Anführungszeichen. Wenn das Zeichen in doppelte Anführungszeichen gesetzt ist, können wir das Flag setzen und je nach Wert des Flags in Großbuchstaben konvertieren oder so lassen, wie es ist.

Es stellt sich heraus, dass JavaScript keine integrierte Funktionalität dafür hat, aber wir können sie selbst erstellen:

const len = theLine.length;
let insideString = false;
for (let i = 0; i < len; i++) {
    const ch = theLine[i];
    if (ch === `"`) insideString = !insideString;
    if (!insideString) {
        const newCh = ch.toUpperCase();
        if (ch !== newCh) theLine[i] = newCh;
    }
}

Jetzt stimmt die Logik in JS besser mit der Assembler-Version überein, obwohl wir die Unicode-Unterstützung in JS wieder ein wenig nutzen.

Die Assembler-Version sieht folgendermaßen aus:

           ld  y,  0                # y is our index
           ld  bl, 0                # === insideString (false)
_loop:     ld  al, [d, x, y]        # [d,x] is pointer to string
           cmp al, 34               # is al a double quote?
           brs !z  check_char       # no? should we uppercase it?
           xor bl, 0xFF             # yes? toggle insideString
_check_char:
           cmp bl, 0xFF             # inside a string?
           brs z   _continue        # yes? don't modify it
           cmp al, 97               # is al (char) in range? "a"
           brs n   _continue        # Not a lowercase char; continue
           cmp al, 123              # high portion           "z"
           brs !n  _continue        # not a lowercase char; continue
           and al, 0b1101_1111      # uppercase!
           st  [d, x, y], al        # store back (we modify the original)
_continue: inc y                    # move our index along
           cmp al, 0                # check for NULL
           brs !z _loop             # No? Go back for more.

Bisher haben wir nur die Konvertierung des Eingabetextes in Großbuchstaben durchgeführt, aber Sie können die Definition eines Zeichenfolgenliteral für eine andere Möglichkeit verwenden. Wir können noch eine Syntaxprüfung durchführen!

Wenn wir am Ende des Prozesses herausfinden, was inStringnoch wahr ist ( bl = 0xFF), können wir einen Fehler zurückgeben, da dies bedeutet, dass irgendwo in der Zeichenfolge ein unvollständiges Zeichenfolgenliteral vorhanden ist.

Hinweis: Es stellt sich heraus, dass viele Versionen von BASIC aufgrund des Fehlens abschließender Anführungszeichen für Zeichenfolgen eher nachsichtig sind. Ich habe das herausgefunden, als ich meinen eigenen Dolmetscher erstellt habe. Auch wenn es so ist, scheint es mir nicht richtig zu sein, also lässt Retroputer BASIC es nicht zu.

Tokenisierung

Der nächste Schritt beim Parsen besteht darin, die Eingabezeichenfolge in etwas Effizienteres umzuwandeln, das der Retroputer BASIC-Interpreter ausführen kann. Wir versuchen, dem Konzept eines abstrakten Syntaxbaums so nahe wie möglich zu kommen, aber das Ergebnis wird immer noch kein Baum sein. Aber es wird etwas sein, das wir zur Laufzeit schnell erledigen können.

Ein gemeinsames Merkmal der frühen Mikrocomputer war der sehr begrenzte Speicher. Der Retroputer hat mehr Speicher als die meisten Standardmaschinen zu dieser Zeit, aber immer noch viel weniger als moderne Computer. Daher können lange BASIC-Programme leicht zu viel Speicher beanspruchen, wenn sie während der Benutzereingabe gespeichert werden.

Um Platz zu sparen, werden Schlüsselwörter beim Programmeintrag in den Speicher mit einem Token versehen... Dieser Prozess konvertiert Schlüsselwörter in Einzelbyte-Token. Schlüsselwörter sind immer mindestens zwei Byte lang, sodass Sie während der Eingabe mehr Einsparungen erzielen. Dies bedeutet auch, dass wir die Nachschlagetabelle zur Laufzeit verwenden können, um die entsprechenden Assembler-Routinen aufzurufen.

Retroputer BASIC ging jedoch etwas weiter als die meisten BASIC-Versionen dieser Zeit. Darüber hinaus werden Zahlen in Binärform konvertiert, Zeichenfolgen markiert, Variablenreferenzen berechnet und vieles mehr. Um ehrlich zu sein, verschwendet dies mehr Platz, aber die Vorteile der Geschwindigkeit (und der einfachen Implementierung) überwiegen.

Daher werden hier die folgenden Schritte verwendet:

, , . , , , , .
, , , . , PRINT "Hello, World" «Hello, World» , .

, .
, , , . JavaScript, !

( ). , PRINT !
Retroputer BASIC ( ). . , , .

Retroputer BASIC . , . , Retroputer BASIC.

In der Post werde ich nicht näher auf die Implementierung dieser Phase in Assemblersprache eingehen, sondern sie für die Zukunft belassen. Aber keine Sorge, da ist viel Code .

Überprüfen der Syntax zur Laufzeit

Last but not least ist die Laufzeitsyntaxprüfung. Nach der Konvertierung des Codes in ein Token-Formular ist es recht einfach, ihn zu implementieren.

Zunächst prüft BASIC zur Laufzeit, ob derzeit ein Token verarbeitet wird. Für alle Token ist das höchstwertige Bit aktiviert (dh sie haben einen Wert von 128 und höher). Wenn ein Token gefunden wird, können wir bestimmen, welches Unterprogramm aufgerufen werden soll, indem wir es in der Vektortabelle finden . Es macht es auch trivial, Syntaxfehler anzuzeigen - einige Schlüsselwörter sind als Operatoren nicht sinnvoll, sodass die Vektortabelle einfach auf die Prozedur verweist, die den Syntaxfehler generiert.

Nachdem der Operator-Token-Handler aufgerufen wurde, übernimmt der Handler alle zusätzlichen Parsing-Arbeiten. Für Token und den Übergang zwischen ihnen verwenden kann gettok, gettok-raw,peektok usw. Wenn das Token von der Prozedur nicht erwartet wird, gibt die Prozedur einfach einen Fehlercode zurück. In diesem Stadium werden sowohl Syntaxfehler als auch Typanpassungsfehler abgefangen.

Wenn der Operator den Ausdruck auswerten muss , wird eine weitere Analysephase durchgeführt. Beim Parsen eines Ausdrucks wird eine andere Vektor-Nachschlagetabelle verwendet . Das heißt, wir können Schlüsselwörter abfangen, die sich nicht auf einen mathematischen Ausdruck beziehen, und die entsprechenden Fehler zurückgeben. Zum Beispiel, wenn Sie versuchen einzutretenPRINT 2+CLS, dann erhalten wir einen Syntaxfehler auf CLS( CLS- dies ist die Abkürzung für "Bildschirm löschen").

Hinweis: Aus dieser Tabelle können wir auch die Priorität der mathematischen Operatoren und die Anzahl der erforderlichen Parameter bestimmen. Dies ist wichtig für die tatsächliche Auswertung des Ausdrucks, kann jedoch auch verwendet werden, um Fälle zu erfassen, in denen der Benutzer nicht genügend Argumente angegeben hat.

Da das Token direkt dem Vektor-Lookup-Tabelleneintrag zugeordnet ist, kann das Programm relativ schnell und mit minimalem Aufwand ausgeführt werden. Die Aufgabe, jeden Operatortyp zu analysieren, wird dem Handler selbst übertragen, und dies verursacht im Allgemeinen keine besonderen Probleme. Wahrscheinlich am schwierigsten zu analysieren sind PRINTundINPUT, aber bei jedem Schritt wird jeweils ein Token genommen.

Da viele der Überprüfungen erst zur Laufzeit des Programms durchgeführt werden, bedeutet dies, dass möglicherweise Teilergebnisse vorliegen, bevor der Fehler auftritt. Zum Beispiel:

PRINT "Hello";CLS
Hello
?Syntax Error

Dies bedeutet außerdem, dass wir möglicherweise Probleme mit der Beseitigung von Fehlern haben, wenn das Programm den Bildschirm in einem Zustand verlässt, in dem wir den Text nicht sehen können. Was sollen wir tun, wenn ein Syntaxfehler angezeigt wird, der jedoch nicht angezeigt wird?

Diese Art der Syntaxprüfung hat sicherlich ihre Nachteile, ermöglicht jedoch einen relativ einfachen Interpreter.

Benutzereingaben tokenisieren

Wie bereits erwähnt, war es in BASIC-Versionen dieser Zeit üblich, Tokenisierungstaktiken zu verwenden. Um Platz zu sparen und die Ausführungsgeschwindigkeit zu erhöhen, wurden Schlüsselwörter in Einzelbyte-Token (oder Doppelbyte, wenn mehr Schlüsselwörter benötigt werden) "komprimiert".

Stellen wir uns vor, wir hätten eine einfache Codezeile, die den Bildschirm löscht und eine Standardbegrüßung druckt:

CLS: PRINT "Hello, World"

Während dies an sich nicht viel Speicherplatz beansprucht, sind viele Wörter in diesem Programm Schlüsselwörter, wenn Sie ein langes Programm schreiben. Wenn Sie sie komprimieren (tokenize), können Sie einen festen Teil des Speicherplatzes sparen. Zum Beispiel wird nach der Tokenisierung der oben gezeigten Zeile so etwas im Speicher sein:

8A E3 B5 FC Hello, World 00 00

Es sollte nicht allzu schwierig sein, dies wieder in das ursprüngliche Konstrukt umzuwandeln:

Byte	Stichwort	Anmerkungen
8A	CLS
E3	":"	Ende der Bauarbeiten
32	""	Wir speichern höchstens einen Raum
B5	DRUCKEN
FB	Code eingeben	Als nächstes kommt das String-Literal
Hallo Welt, 00		Zeichenfolgen sind nullterminiert
00	Ende der Codezeile	Codezeilen sind ebenfalls nullterminiert

Sie mögen denken, dass dies viel Arbeit ist, aber die Platzersparnis kann erheblich sein. Dies macht sich im Beispiel nicht besonders bemerkbar, aber selbst daraus können Sie sich vorstellen, wie schnell sich der eingesparte Speicherplatz ansammeln kann. In diesem Fall beträgt das komprimierte Ergebnis 19 Byte. Der Quelltext besteht aus 26 Bytes (einschließlich des abschließenden Nullbytes).

Platzersparnis wird wichtig, wenn der BASIC-Interpreter auf einem Computer mit sehr wenig RAM für Benutzerprogramme ausgeführt wird. Daher ist eine solche Komprimierung sehr wichtig und attraktiv, auch wenn sie keine zusätzlichen Vorteile bietet.

Wie können wir so etwas tokenisieren? Auf den ersten Blick scheint JavaScript ziemlich trivial zu sein, um dies zu tun. Mit einem Array von Zeichenfolgen können Sie jedes Schlüsselwort schnell durch das entsprechende Token ersetzen. Wahr?

Scheint, als wäre dies ein Job für String#replace? Mit einem naiven Ansatz können Sie so etwas ausprobieren:

const tokens = ["CLS", "PRINT", ":" ];
function tokenize (inStr) {
    const newStr = inStr;
    tokens.forEach((token, idx) => newStr = newStr.replace(
        new RegExp(token, "g"), String.fromCharCode(128+idx)
    );
    return newStr;
}

Leider stellen wir schnell fest, dass wir String-Literale nicht durch Token ersetzen können. Dies bedeutet, dass Sie die Verarbeitung zeichenweise unter Berücksichtigung des Kontexts durchführen müssen, um Elemente, die keine Schlüsselwörter sind, nicht zu komprimieren.

Dieser neue Algorithmus ist näher am Assembler-Code in Retroputer, aber JS macht die Dinge noch viel einfacher. Hier ist der Anfang des JS-Codes (wir werden ihn in diesem Beitrag schrittweise erweitern):

const tokens = ["CLS", "PRINT", ":" ];

function tokenize(inStr) {
    let out = [];                    // return value is "crunched" array
    let idx = 0;                     // index into inStr
    let ch = "";                     // current character
    while (idx < inStr.length) {
        ch = inStr.charCodeAt(idx);  // get the current character code
        
        // our logic is going to go here

        out.push(ch);                // for now push the character
        idx++;                       // and keep going (next char)
    }
    out.push(0);                     // we end with NUL
    return out;
}

Wir beginnen mit einer sehr vereinfachten Liste von Token, da niemand die gesamte Tabelle in diesem Format sehen möchte ( es ist lang und Retroputer erstellt tatsächlich Tokentabellen aus einer JS-Datei! ). Für unsere Zwecke wird dies jedoch ausreichen. Das Prinzip hier ist, dass wenn wir ein Token sehen, wir seinen Index in das Ausgabearray schreiben.

Zu diesem Zeitpunkt haben wir eine Funktion, die die Zeichenfolge vorerst einfach in ihre entsprechenden Zeichencodes konvertiert. Obwohl es nicht besonders nützlich ist, kann es als praktischer Rahmen dienen.

Die Assembler-Version ist der oben gezeigten ziemlich ähnlich.

  do {
    call _get-source-index     # get next character index (in y)
    dl := <BP+source>,y        # read next char from our source string (ch)
    call _adv-source-index     # advance our source index
    call _get-target-index     # get position in target   ("out" in JS)
    <BP+target>,y := dl        # store to target          (out[y] = ch)
    call _adv-target-index     # move it along
    cmp dl, 0                  # was char 0? if so, break
  } while !z

Ich habe das obige Beispiel _get-source-indexoder andere Funktionen nicht aufgenommen, da ihre Aufgaben aus dem Namen ersichtlich sind: Sie erhalten einfach die Quell- und Zielindizes, setzen sie und navigieren auch durch sie. Es ist anzumerken, dass es im Gegensatz zu JS keine dynamisch zugewiesenen Arrays in Assemblersprache gibt, sodass dieser Algorithmus einen Puffer mit ausreichender Größe zuweist. Während wir die Eingabezeile entlang gehen, müssen wir wissen, wo das nächste Token in den Zielpuffer geschrieben werden soll und was der Zielindex oben tut. Jede der oben genannten Funktionen gibt einen Index in zurück Y. Beispielsweise _adv-target-indexerhöht die Funktion den Zielindex um eins (äquivalent y++).

Seien Sie vorsichtig mit Literalen

Wir müssen vorsichtig sein: Zeichenfolgenliterale können für den Tokenizer verwirrend sein - wir können nicht einfach jede Zeichenfolge, die einem Schlüsselwort entspricht, durch einen Tokenwert ersetzen. Wenn wir ein String-Literal sehen, das "CLS" enthält, sollten wir nicht versuchen, es zu tokenisieren. Es sollte nicht ausführbar sein, und wenn wir es ausgeben ... dann geben wir stattdessen das dem Token entsprechende Byte aus. Dies ist höchstwahrscheinlich nicht das, was der Entwickler gemeint hat.

Auf der anderen Seite sollten numerische Literale dieses Problem nicht haben, da BASIC keine numerischen Schlüsselwörter hat. Trotzdem macht es keinen Sinn, nach einem Schlüsselwort zu suchen, wenn Sie mit einer Zahl konfrontiert werden - warum sollten Sie Ihre Zeit verschwenden?

Tokenisieren von String-Literalen

Lassen Sie uns zunächst prüfen, ob die Zeile beginnt - in JS ist dies nicht besonders schwierig:

if (ch === 34) {
  out.push (0xFB);             // string-in-code token
  idx++;
  ch = inStr.charCodeAt(idx);  // get next character after the quote
  while (ch !== 34 && idx < inStr.length) {
    out.push(ch);
    idx++;
    ch = inStr.charCodeAt(idx);
  };
  idx++;                       // go past the quote
  out.push(0);                 // end of string
  continue;
}

Das doppelte Anführungszeichen wird durch den Zeichencode 34 dargestellt. Andere Programmiersprachen können viel mehr Arten von Anführungszeichen (wie JS oder C) erkennen, aber mit BASIC ist es einfach: entweder doppelte Anführungszeichen oder nichts.

Wenn wir sehen, dass eine Zeichenfolge beginnt, können wir einfach die verbleibenden Zeichen nehmen und zum Ausgabearray hinzufügen, bis wir auf ein anderes Anführungszeichen stoßen.

Nach dem Lesen der gesamten Zeichenfolge muss ein Null-Byte hinzugefügt werden, da Retroputer BASIC Zeichenfolgen im C-Stil verwendet. Wenn wir Zeichenfolgen im Pascal-Stil verwenden möchten, können wir einen Zähler speichern und die Länge des Zeichenfolgenliteral einfügen. In jedem Fall ist dies kein besonderes Problem. Der einzige Grund, warum ich nullterminierte Zeichenfolgen verwendet habe, ist, dass sie in Assemblersprache sehr einfach zu verarbeiten sind. Wir müssen nur mit einem Null-Byte vergleichen und keinen Zähler speichern.

JavaScript war also nicht so schwer. Ich denke, die meisten von Ihnen würden sich für etwas Abstrakteres entscheiden, wie einen regulären Ausdruck. Ich denke, dieser Code wird unsere Absichten offensichtlicher machen.

if (ch === 34) {
  out.push (0xFB);             // string-in-code token
  const stringLiteral = inStr.substr(idx+1).match(/^[^"]*/)[0];
  idx += stringLiteral.length+1;
  out.push(...Array.from(stringLiteral, ch => ch.charCodeAt(0)));
  idx++;                       // go past the quote
  out.push(0);                 // end of string
  continue;
}

Der obige Code ist ungefähr der gleiche, aber anstelle der zeichenweisen Validierung lassen wir den JS einfach ausführen match. Wir wissen, dass wir ein Match bekommen werden (wir sind in einer Reihe), daher müssen wir nicht einmal überprüfen, ob das Match erfolgreich war. Wir erhöhen dann den Index um die Länge der Zeichenfolge und kopieren die Zeichen in das Ausgabearray. Meiner Meinung nach ist dieser Code viel einfacher zu verstehen (dies impliziert jedoch ein Verständnis der regulären Ausdrücke sowie der Besonderheiten der ES6-Syntax …und der Pfeilfunktionen).

Natürlich müssen wir in Assemblersprache alle Arbeiten, die JS erledigt, manuell ausführen. Das Ergebnis ist unserem ersten Versuch, JS-Code zu schreiben, sehr ähnlich:

  cmp dl, constants.QUOTE         # is dl a quote?
  brs !Z not-a-string             # nope; not a string

  call _get-target-index          # get next position in crunch target
  dl := brodata.TOK_CODE_STRING   # "String" token
  <bp+target>,y := dl             # Store it into the crunch target
  call _adv-target-index

still-a-string:
  call _get-source-index
  dl := <bp+source>,y             # get string character
  call _adv-source-index
  cmp dl, constants.QUOTE         # if it's a quote, we can zero it
  if Z { 
    dl := 0 
  }
  call _get-target-index
  <bp+target>,y := dl             # write to target
  call _adv-target-index
  cmp dl, 0                       # are we done?
  brs !Z still-a-string           # no, keep going
  continue                        # next!
not-a-string:

Es lohnt sich, einen Hinweis zum Parser der Assembler-Sprache Retroputer hinzuzufügen - er bietet grundlegende Unterstützung für Konstrukte auf hoher Ebene wie Blöcke und Schleifen. Daher if Z {…}wird der Inhalt innerhalb des Blocks ausgeführt, wenn das Null-Flag gesetzt ist, und es continuekann verwendet werden, um zum Anfang des Blocks zurückzukehren (wird breakauch zum Verlassen des Blocks verwendet). Der Assembler übersetzt dies in verschiedene Vergleichs- und Verzweigungsanweisungen, sodass die CPU die übergeordneten Teile des Codes nicht sieht, aber das Schreiben des Codes etwas erleichtert.

Tokenisieren von Zahlen

Es ist auch nicht sinnvoll, die Liste der Schlüsselwörter nach Zahlen zu durchsuchen, sodass wir sie einfach überspringen können. Die meisten Versionen von BASIC führen etwas Ähnliches wie die oben gezeigte Zeichenfolgenmanipulation aus. Wenn das gelesene Zeichen eine Ziffer ist, wird es mit der Ausgabe verknüpft, wonach der Kompressor übernimmt.

Retroputer BASIC (und einige andere Versionen von BASIC, wie Atari BASIC) gehen noch einen Schritt weiter: Es konvertiert eine Zahl in das entsprechende Binärformat. Dies ist sehr einfach. Wenn wir eine Ziffer treffen, multiplizieren wir den Akkumulator mit 10 und addieren die Ziffer, solange die Ziffern weiterhin vorkommen. (Es ist jedoch erwähnenswert, dass Retroputer BASIC zwar nur mit ganzzahligen Werten funktioniert, das Hinzufügen von Gleitkommazahlen jedoch bereits in meiner Aufgabenliste enthalten ist.)

(Ich muss sagen, dass Retroputer BASIC derzeit nichts unternimmt , wenn ein ganzzahliger Überlauf auftritt, egal ob mit oder ohne Vorzeichen. Wenn ich Gleitkommazahlen hinzufüge, konvertiert Retroputer ebenfalls in Gleitkommazahlen.)

Retroputer BASIC geht noch einen Schritt weiter. : Es erkennt auch Hexadezimalzahlen und konvertiert sie in ihre binäre Entsprechung. Es wird als Bezeichnung für solche Zahlen verwendet 0x(wie in JS), und die Sprache selbst verfügt über eine zusätzliche Logik, um sicherzustellen, dass ein Fehler zurückgegeben wird, wenn mehrere Zeichen angegeben werden x.

In der Assemblersprache ist es nicht so schwierig zu überprüfen, ob ein Zeichen eine Ziffer ist, aber es sind einige Vergleiche erforderlich: Sie müssen sicherstellen, dass der Zeichencode zwischen 0x30und liegt0x39... (Dies sind die Zeichencodes "0" und "9".)

Nachdem wir eine Ziffer erhalten haben, können wir eine andere bequeme Eigenschaft des Zeichensatzes verwenden. 0x30- Dies ist der Zeichencode "0", 0x31- Der Code "1" usw. Wir könnten subtrahieren, wenn wir wollten 0x30, aber es gibt einen einfacheren Weg: Verwerfen Sie einfach die vier wichtigsten Bits:

and dl, 0b0000_1111

Leider funktioniert dies nicht , wenn wir Hex-Zahlen verarbeiten müssen. In diesem Fall können Sie subtrahieren und dann mit 10 vergleichen und dann erneut um 7 verringern, wenn der Code größer als 10 ist (vorausgesetzt, die Hexadezimalzahlen sind in Großbuchstaben "A" - "Z").

In JS können Sie wieder reguläre Ausdrücke verwenden. Wenn wir dann eine Übereinstimmung mit der Nummer erhalten, können wir anrufen Number(), was uns einen weiteren Vorteil verschafft: Hexadezimalzahlen werden ebenfalls trivial konvertiert, da Number()dies automatisch erfolgt, wenn die Nummer mit beginnt 0x.

Wie sieht es in JavaScript aus?

if (ch >= 48 && ch <= 57) {
  out.push (0xFD);           // number token
  const numberLiteralStr = inStr.substr(idx).match(/^[\d|A-F|a-f|x|X]+/)[0];
  idx += numberLiteralStr.length;
  const numberLiteral = Number(numberLiteralStr);
  const bytes = new Uint8Array(new Uint16Array([numberLiteral]).buffer);
  out.push(...bytes)
  continue;
}

Mit dem regulären Ausdruck können Sie eine beliebige Kombination von Zahlen oder hexadezimalen Ziffern verwenden (plus x, um in den hexadezimalen Modus zu wechseln). Der Ausdruck ist nicht ideal, zum Beispiel können Sie mehrere verwenden x, aber im Moment reicht dies aus.

Im obigen Code kann das Konvertieren von Zahlen in Bytes fraglich sein. Number()hat die ganze harte Arbeit gemacht, eine Zahlenfolge in eine Zahl umzuwandeln, mit der JavaScript arbeiten kann, aber jetzt müssen wir sie als eine Folge von Bytes darstellen. Sie können Mathe verwenden, um dies zu tun:

const hiByte = (numberLiteral & 0xFF00) >> 8;
const loByte = (numberLiteral & 0x00FF);

... und es ist einfach für eine ganze Zahl zu tun. Aber dank der Verwendung von typisierten JS - Arrays können Sie alle diese Berechnungen nicht tun, aber zur gleichen Zeit die Vorbereitungen für die Zukunft Gleitkommazahlen Handling (wir nur ersetzen Uint16Arraymit Float64Array).

Der Assembler-Code für diese Aufgabe ist etwas länger , macht aber etwas mehr. Retroputer verwendet eine weitere Optimierung: Wenn die Anzahl klein ist, wird sie in einem kleineren Format gespeichert. Dies bedeutet, dass 0-255 in einem Byte gespeichert werden können, während längere Zahlen zwei belegen.

Suche nach Schlüsselwörtern

Wir haben also einiges an Arbeit geleistet, aber bisher haben wir kein einziges Keyword komprimiert. Nachdem wir uns mit Zahlen und String-Literalen befasst haben, können wir sicher sein, dass alles andere entweder ein Schlüsselwort oder ein Variablenname ist. (Oder ein Leerzeichen, aber dies ist leicht zu überprüfen.)

In BASIC beginnen Schlüsselwörter nicht immer mit einem alphabetischen Zeichen. Operatoren und Trennzeichen werden auch als Token betrachtet. Variablen beginnen aber auch mit einem alphabetischen Zeichen. Wir können also nicht sofort bestimmen, ob wir ein Schlüsselwort oder eine Variable komprimieren. Dies passt zu uns - wenn wir in der Liste der Token keine Übereinstimmung finden, gehen wir davon aus, dass dies eine Variable ist.

Wie überprüfen wir also, ob ein potenzielles Keyword tatsächlich ein Keyword ist? Wenn wir in JavaScript schreiben würden, könnten wir das verwenden Array#findIndex.

const tokenMatch = tokens.findIndex(token => 
  inStr.substr(idx).startsWith(token));
if (tokenMatch > -1) {
  out.push(tokenMatch + 128);
  idx += tokens[tokenMatch].length;
  continue;
}

Die Methode Array#findIndexdurchläuft das Array iterativ tokensund wir können überprüfen, ob es inStr(mit dem aktuellen idx) mit dem zu überprüfenden Token beginnt . Wenn wir mit unserer vereinfachten Liste von Token arbeiten, gehen wir wie folgt vor inStr.substr(idx)===”PRINT”:

Zeichen	.startsWith (Token)?	Index
CLS	falsch	0
DRUCKEN	wahr	1

Hinweis: Wie indexOfbei JS erhalten wir, wenn nichts gefunden wird -1.

Wenn eine Übereinstimmung gefunden wird, können Sie den Index im zurückgegebenen Array speichern. Aber wie unterscheiden wir später einen Token von einem Symbol? Einfach: Aktivieren Sie das höchstwertige Bit

. Dies kann durch Hinzufügen von 128 zum Token-Wert erfolgen. (Hinweis: Wenn wir mehr Token als 128 benötigen, müssten wir für einige Token zwei Bytes verwenden. Dies erschwert die Dinge ein wenig , aber nicht so sehr. Einige Versionen von BASIC tun dies beispielsweise in verschiedenen Microsoft BASICs.)

Wir sind mit JavaScript fertig, aber wie machen wir das in Assemblersprache?

Es stellt sich heraus, dass es fast dasselbe ist, aber der Code wird viel länger sein.

search-keywords:
  bl := [d, x]                 # get first character of current token
  cmp bl, constants.NUL        # if it's NUL, we've exhausted the list
  brs Z exit-keyword-search    # so we're clearly not a keyword
  clr Z                        # compare strings, but with partial equality
  call [vectors.STRCMP]        # so that our source doesn't need NUL between
                               # tokens; c will now be how many chars got 
                               # compared
  if !Z {
    do {                       # no match; advance past our token in the list
      inc x                    # character by character
      bl := [d, x]             # tokens are terminated with NULs
      cmp bl, constants.NUL    # so if we see it, we can stop
    } while !z
    inc x                      # go past the token #
    inc x                      # in the lookup table
    brs search-keywords        # and keep looking for a match
  }
  clr c                        # found the match!
  add x, c                     # c is the length of the match
  inc x                        # past the NUL
  bl := [d, x]                 # bl is now the token #
  call _get-target-index
  <bp+target>,y := bl          # write the token #
  call _adv-target-index
  call _get-source-index       # advance past the token in the source
  clr c
  add y, c                     # by adding the character count
  dec y                        # back off by one (we'll advance again later)
  call _set-source-index
  continue

Nun, es sieht nicht so schlecht aus. Der Algorithmus ist fast der gleiche, nur die Token-Tabelle der Assemblersprache ist etwas anders strukturiert. Es sieht ungefähr so aus:

CLS   00 80
PRINT 00 81
:     00 82

Jedes Schlüsselwort wird mit einem Null-Byte gefolgt von einer Token-Nummer abgeschlossen.

Hier fehlt uns jedoch etwas Wichtiges - wie wird dieser String-Vergleich überhaupt durchgeführt? Im Kern von Retroputer gibt es ein Verfahren STRCMP, das wir verwenden können, aber wie sieht es aus?

strcmp: {
  enter 0x00
  push a
  push b
  push d
  push y
  pushf
  if Z {
    bl := 0x00                  # Checking for full equality
  } else {
    bl := 0x01                  # only checking for partial equality
  }
_main:
  y := 0                        # start of string
top:
  cl := [d, x, y]               # character in string A
  al := <bp+4>,y                # character in string B
  cmp bl, 0x01                  # check if we're doing full equality
  if Z {
    cmp cl, 0                   # we're not, so check for an early nul
                                # in string b
    brs Z strings-are-equal     # if it's NUL, we calling them equal
  }
  cmp cl, al                    # check character
  if Z {
    cmp cl, 0                   # equal, but check for NUL
    brs Z strings-are-equal     # NUL reached, strings are equal
    inc y                       # next character
    brs top                     # not NUL, so keep going...
  }
 # if here, the strings aren't equal
  if N {
    popf                        # string is less than
    set N
    clr Z
    brs _out
  } else {
    popf                        # string is greater than
    clr N
    clr Z
    brs _out
  }
strings-are-equal:
  popf
  clr N                         # Not less than
  set Z                         # but Equal
_out:
  c := y                        # make sure we know how many chars
                                # were compared
  pop y
  pop d
  pop b
  pop a
  exit 0x00
  ret
}

Ich weiß nichts über dich, aber ich fange an, die Methode String#startsWithvon JS immer mehr zu lieben . Ja, es macht dasselbe, aber wir müssen nicht die gesamte interne Logik schreiben!

Variable Handhabung

Die Tastenkomprimierung ist jetzt abgeschlossen, sodass wir fertig sind. Retroputer BASIC macht jedoch einen weiteren Schritt nach vorne - das Tokenisieren von Variablen. Es scheint mir, dass nur wenige Versionen von BASIC aus den 80ern und 90ern dies getan haben, da es unter Bedingungen mit begrenztem Speicher schädlich sein kann. Wenn jedoch viel Speicher vorhanden ist, hilft die Tokenisierung von Variablen, die Leistung zu verbessern.

Folgendes macht Retroputer BASIC:

Es liest bis zu den ersten beiden Zeichen des Variablennamens. (Dies war eine Standard-Unannehmlichkeit der BASIC-Versionen der Ära aufgrund von Speicherbeschränkungen.)
Aus diesen beiden Zeichen wird der Index der Variablen bestimmt. "A" ist Variable 0, "A0" ist Variable 53 und so weiter. Die Gleichung ist ziemlich einfach, aber sie interessiert uns momentan nicht.
BASIC . , $ BASIC . .
BASIC , . !

(Hinweis: Wenn Retroputer BASIC lernt, Speicher für Variablen dynamisch zuzuweisen, ersetzen wir den Index durch einen Zeiger auf eine Variable. Ein weiteres Element in der Aufgabenliste!)

Dies macht das Auffinden von Variablen zur Laufzeit unglaublich schnell: Wir müssen den Variablennamen nicht jedes Mal analysieren und den Index berechnen wenn wir eine Variable treffen. In kontinuierlichen Zyklen können die Einsparungen erheblich sein. Dies ist jedoch mit hohen Kosten verbunden: Wir müssen den Zeiger und den Variablennamen zusammen speichern, sodass wir für jede Variable, auf die wir stoßen, der Ausgabe vier zusätzliche Bytes hinzufügen müssen.

Es liegt an Ihnen zu entscheiden, ob es sich lohnt.

Wie auch immer, in JavaScript ist es auch einfach festzustellen, ob der Rest des Zeichenstroms eine Variable ist:

const variableMatch = inStr.substr(idx).match(/^[A-Z]+[A-Z0-9]*[\$]*/);
if (variableMatch) {
  const variableName = variableMatch[0];
  idx += variableName.length;
  // tokenize it (omitted; nothing new here)
  continue;
}

Ich werde den Code , den Retroputer derzeit zum Tokenisieren von Variablen verwendet, nicht im Detail beschreiben , er ist zu ausführlich. Wir werden darauf zurückkommen, wenn ich die dynamische Speicherzuordnung für Variablen hinzufüge.

Tokenisierung abgeschlossen

Wenn wir jetzt unseren Code in JS testen, erhalten wir ein Byte-Array ähnlich dem, das Retroputer BASIC intern verwendet:

console.log(toHex(tokenize(`CLS: PRINT "Hello, World"`)));
// 80 82 20 81 20 FB 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 00 00

Wow, was für eine Menge Arbeit, um ein paar Bytes zu sparen. Aber wenn es nur ein paar Kilobyte freien Speicher gibt, lohnt es sich! Dies ist jedoch nicht der einzige Vorteil der Komprimierung des vom Benutzer eingegebenen Texts, sondern wir beschleunigen auch die Programmausführung.

Um zu erklären, warum dies geschieht, müssen wir verstehen, wie Retroputer den Code ausführt. Ich werde vorerst nicht auf Details eingehen, aber kurz gesagt, ist Folgendes erforderlich, um den Code auszuführen:

Holen Sie sich ein Byte aus dem Speicher
Wenn für ein Byte das höchstwertige Bit aktiviert ist, handelt es sich um ein Token, andernfalls um einen Syntaxfehler (oder NUL; in jedem Fall endet hier die Programmzeile).
Wir suchen nach einem Token-Handler in einem Array - dieses Array enthält Zeiger auf die Funktionen selbst, die das Token verarbeiten
Wir rufen den Handler an (er ist für den Empfang von Argumenten und dergleichen verantwortlich).
Wir wiederholen noch einmal

Dies ist ein weiterer Grund für das Tokenisieren von Schlüsselwörtern. Das Ausführen der Logik des Schlüsselworts wird trivial. Suchen Sie einfach die Adresse im Array und rufen Sie sie auf.

Ich möchte betonen, dass Tokenisierung zwar wichtig ist, um Platz zu sparen, aber auch die Ausführungsgeschwindigkeit verbessert.

Beispielsweise könnte eine JS-Ausführungsschleife ungefähr so aussehen:

const handlers = [ cls, print, endOfStmt ];
bytes.forEach(byte => handlers[byte] && handlers[byte]());

Natürlich ist in Wirklichkeit nicht alles so einfach, es ist viel mehr, aber dies ist bereits ein Thema für einen anderen Beitrag!

Schreiben eines BASIC-Interpreters im 80er-Jahre-Stil

Retroputer-Eigenschaften