Clever Geek Handbook

Écrire un interpréteur BASIC de style années 80





Depuis plusieurs années, je travaille sur un projet personnel de création (et en fait de recherche) d'un "faux émulateur", c'est-à-dire un émulateur écrit en JavaScript pour un ordinateur qui n'a jamais existé. Cette machine était censée être un hommage aux ordinateurs huit et seize bits des années 80 et 90.



Cependant, j'aime la complexité: cette machine utilise également un nouveau jeu d'instructions. Il est similaire aux kits utilisés à cette époque, mais un peu plus facile à utiliser. Le Retroputer est né . Au fil des ans, l'émulateur s'est développé et s'est amélioré, mais il ne sera probablement jamais "terminé" (après tout, il s'agit d'un projet de recherche personnel).



Quand @bbcmicrobot est apparu, Je voulais créer quelque chose de similaire pour le Retroputer. Mes compétences en développement JS étaient principalement limitées au front-end, ce serait donc une excellente excuse pour acquérir une expérience back-end. Il n'y a qu'un seul problème: Retroputer ne peut comprendre que son propre langage d'assemblage. Il n'a pas encore de support BASIC.



J'ai donc imaginé la création de l'interpréteur BASIC dans le style des années 80, c'est-à-dire complètement en langage d'assemblage, tel qu'il était alors écrit. J'ai décidé que cela valait la peine de partager mon travail, car nous n'avons pas souvent à nous plonger dans des domaines si éloignés des abstractions habituelles. Mon outil quotidien (JavaScript) rend de nombreux aspects triviaux et parfois cela semble même magique. Comprendre le niveau le plus bas des processus aide souvent à comprendre ces abstractions.



Alors, commençons.



Caractéristiques du Retroputer



  • 16 ROM (KERNEL) c 1 (scratch space)
  • 512 , 64
  • 16- 6516, 512 4 64
  • 4025, ,
  • 1125
  • 9800




Lorsque j'écrivais l'assembleur pour Retroputer, je pouvais utiliser l'outil très pratique Pegjs. Il a fourni une syntaxe d'assembleur native rapide, mais malheureusement, rien de tel n'existe pour Retroputer ASM. Autrement dit, nous devrons suivre la voie difficile.



L'analyse proprement dite est effectuée en plusieurs étapes. Un langage qui utilise un compilateur analyse le code dans un arbre de syntaxe abstraite (AST) (ou une autre représentation), puis peut utiliser cet arbre pour générer du code natif fini. Par conséquent, le programme doit être syntaxiquement correct pour une compilation réussie.



Certains interprètes modernes ont également ce concept, car il est souvent utile de générer un AST intermédiaire et de l'exécuter plutôt que le code source.



Mais pour l'interpréteur BASIC sur une machine aux ressources limitées, il sera plus efficace d'analyser en plusieurs étapes, dont certaines se produisent à l'exécution. Cependant, cela signifie que les erreurs de syntaxe ne peuvent pas être détectées tant que vous n'exécutez pas le programme et que vous accédez à la zone du code avec l'erreur.



L'analyse de Retroputer BASIC comprend trois étapes:



  1. Conversion de chaînes
  2. Tokenisation
  3. Vérification de la syntaxe d'exécution


Les deux premières étapes se produisent lorsque l'utilisateur entre dans le programme (ou le télécharge). Ce dernier se produit pendant l'exécution du programme. En gros, les deux premiers créent le fuselage de l'avion, mais ne garantissent pas qu'il décollera. La dernière étape est un pilote d'essai - nous espérons qu'il décolle, mais nous n'en sommes pas sûrs jusqu'à ce qu'il essaie.



Remarque: le code source de Retroputer BASIC (en développement) est disponible sur GitHub .



Conversion de chaînes



C'est la partie la plus simple de tout le processus. La chaîne saisie par l'utilisateur est convertie en majuscules pour simplifier (et accélérer) les processus ultérieurs. BASIC n'est pas sensible à la casse, nous pouvons donc en profiter. 



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


C'est très facile de faire cela en JavaScript, non? 



theLine = theLine.toUpperCase();


Mais en langage assembleur, ce processus est plus détaillé. Nous devons lire le caractère, le convertir en majuscules, puis le stocker quelque part. 



           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.


Le code ci-dessus ne correspond pas tout à fait à la sémantique de la version JavaScript du code. Une différence importante est qu'aujourd'hui nous utilisons Unicode pour travailler avec du texte, donc la conversion des entrées des minuscules aux majuscules peut souvent être plus difficile et parfois impossible (cela dépend de la langue). Retroputer vit dans le monde ASCII (plus précisément, dans le monde de sa propre variante ASCII appelée RetSCII), c'est-à-dire que tous les caractères pris en charge sont codés sur huit bits. Pour de nombreuses langues, c'est totalement insuffisant, mais cela répond aux réalités de l'époque.



Cela signifie également que nous pouvons utiliser une jolie fonctionnalité ASCII pour convertir des minuscules en majuscules. La majuscule «A» est représentée en code ASCII 65et la minuscule «a» est représentée par le code97... Si vous connaissez les pouvoirs de deux, vous devriez avoir remarqué cette différence.



Ainsi, il s'avère que les lettres minuscules sont spécifiées par un nombre qui est exactement 32 de plus que le nombre de lettres minuscules. Si nous savons que la valeur est dans la plage correcte, il suffit de soustraire 32!



Cette approche fonctionnera, mais nous pouvons simplement modifier un peu les bits. Dans le cas de Retroputer, cela ne sera pas plus rapide que la soustraction, cependant, en l'absence de soustraction, nous n'aurons pas à faire attention au drapeau de report / emprunt lors des calculs. Il s'avère que nous pouvons utiliser bitwise andpour désactiver le bit à la place de la valeur 32. 



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


Mais il y a une subtilité: tout ne peut pas être converti en majuscules. Par exemple, si l'utilisateur a ajouté une chaîne littérale, nous devons être plus prudents, car nous ne voulons pas que Retroputer BASIC crie constamment à l'utilisateur avec des majuscules. (Alors que de nombreux ordinateurs de l'époque n'avaient pas de minuscules, le Retroputer n'en avait pas.)



Par exemple: 



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


Cela signifie que nous devons savoir si nous sommes au milieu d'une chaîne littérale. En BASIC, il n'y a qu'une seule désignation pour cela: les guillemets. Si le caractère est un guillemet double, nous pouvons définir l'indicateur et, en fonction de la valeur de l'indicateur, le convertir en majuscules ou le laisser tel quel.



Il s'avère que JavaScript n'a pas de fonctionnalité intégrée pour cela, mais nous pouvons le créer nous-mêmes: 



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;
    }
}


Maintenant, la logique dans JS correspond plus étroitement à la version de l'assembleur, bien que nous utilisions à nouveau un peu le support Unicode dans JS.



La version assembleur ressemble à ceci: 



           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.


Jusqu'à présent, nous n'avons fait que la conversion du texte d'entrée en majuscules, mais vous pouvez utiliser la définition d'un littéral de chaîne pour une autre possibilité. Nous pouvons faire une autre vérification de syntaxe!



Si à la fin du processus nous découvrons ce qui inStringest toujours vrai ( bl = 0xFF), alors nous pouvons renvoyer une erreur, car cela signifie qu'il y a une chaîne littérale incomplète quelque part dans la chaîne.



Remarque: il s'avère que de nombreuses versions de BASIC sont plutôt indulgentes sur l'absence de guillemets fermants sur les chaînes. J'ai découvert cela en créant mon propre interprète. Même si c'est le cas, cela ne me semble pas correct, donc Retroputer BASIC ne le permet pas.



Tokenisation



La prochaine étape de l'analyse consiste à transformer la chaîne d'entrée en quelque chose de plus efficace pour que l'interpréteur Retroputer BASIC s'exécute. Nous essayons de nous rapprocher le plus possible du concept d'arbre syntaxique abstrait, mais le résultat ne sera toujours pas un arbre. Mais ce sera quelque chose que nous pouvons gérer rapidement au moment de l'exécution.



Une caractéristique commune des premiers micro-ordinateurs était la mémoire très limitée. Le Retroputer a plus de mémoire que la plupart des machines standard à l'époque, mais toujours beaucoup moins que les ordinateurs modernes. Par conséquent, les programmes BASIC longs peuvent facilement occuper trop de mémoire s'ils sont enregistrés pendant la saisie par l'utilisateur.



Pour économiser de l'espace, les mots clés sont jetés lors de l'entrée du programme en mémoire... Ce processus convertit les mots clés en jetons à un octet. Les mots clés ont toujours une longueur d'au moins deux octets, ce qui vous permet d'économiser davantage à mesure que vous tapez. Cela signifie également que nous pouvons utiliser la table de recherche au moment de l'exécution pour appeler les routines de langage d'assemblage appropriées.



Cependant, Retroputer BASIC est allé un peu plus loin que la plupart des versions BASIC de l'époque. De plus, il convertit les nombres en forme binaire, marque les chaînes, calcule les références de variables, et bien plus encore. Pour être honnête, cela gaspille plus d'espace, mais les avantages en termes de vitesse (et de facilité de mise en œuvre) l'emportent sur cela.



Ainsi, les étapes suivantes sont utilisées ici:







  1. , , . , , , , .




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



    , .




  3. , , , . JavaScript, !



    ( ). , PRINT !




  4. Retroputer BASIC ( ). . , , .



    Retroputer BASIC . , . , Retroputer BASIC.


Dans le post je n'entrerai pas dans les détails sur la mise en œuvre de cette étape en langage d'assemblage, je la laisserai pour le futur. Mais ne vous inquiétez pas, il y a beaucoup de code là-bas .



Vérification de la syntaxe lors de l'exécution



Dernier point mais non le moindre, la vérification de la syntaxe d'exécution est. Après avoir converti le code en une forme tokenisée, il est assez facile de l'implémenter.



Tout d'abord, au moment de l' exécution, BASIC vérifie s'il traite actuellement un jeton. Tous les jetons ont le bit le plus significatif activé (c'est-à-dire qu'ils ont une valeur de 128 et plus). Si un jeton est trouvé, nous pouvons déterminer le sous-programme à appeler en le trouvant dans la table vectorielle . Cela rend également simple l'affichage des erreurs de syntaxe - certains mots-clés n'ont pas de sens en tant qu'opérateurs, de sorte que la table vectorielle pointe simplement vers la procédure qui génère l'erreur de syntaxe.



Une fois le gestionnaire de jetons d'opérateur appelé, le gestionnaire prend en charge tout le travail d'analyse supplémentaire. Pour jetons et il peut utiliser la transition entre eux gettok, gettok-raw,peektok etc. Si le jeton n'est pas prévu par la procédure, la procédure renvoie simplement un code d'erreur. C'est à ce stade que les erreurs de syntaxe et les erreurs de correspondance de type sont détectées.



Si l'opérateur doit évaluer l' expression, une autre étape d'analyse est effectuée. Lors de l'analyse d'une expression, une autre table de recherche vectorielle est utilisée , c'est-à-dire que nous pouvons intercepter les mots-clés qui ne sont pas liés à une expression mathématique et renvoyer les erreurs correspondantes. Par exemple, si vous essayez d'entrerPRINT 2+CLS, alors nous obtenons une erreur de syntaxe sur CLS( CLS- c'est le raccourci pour "effacer l'écran").



Remarque: à partir de ce tableau, nous pouvons également déterminer la priorité des opérateurs mathématiques et le nombre de paramètres requis. Ceci est important pour l'évaluation réelle de l'expression, mais il peut également être utilisé pour détecter les cas où l'utilisateur n'a pas fourni suffisamment d'arguments.



Puisque le jeton correspond directement à l'entrée de la table de recherche vectorielle, le programme peut être exécuté assez rapidement et avec un minimum d'effort. La tâche d'analyse de chaque type d'opérateur est confiée au gestionnaire lui-même, et en général cela ne pose pas de problèmes particuliers. Les plus difficiles à analyser sont probablement PRINTetINPUT, mais à chaque étape, un jeton est pris à la fois.



Étant donné que de nombreuses vérifications ne sont effectuées qu'au moment de l'exécution du programme, cela signifie que nous pouvons avoir des résultats partiels avant que l'erreur ne se produise. Par exemple: 



PRINT "Hello";CLS
Hello
?Syntax Error


De plus, cela signifie que si le programme laisse l'écran dans un état dans lequel nous ne pouvons pas voir le texte, alors nous pouvons avoir des problèmes avec l'élimination des erreurs. Si une erreur de syntaxe s'affiche mais que nous ne la voyons pas, que devons-nous faire?



Cette façon de vérifier la syntaxe a certes ses inconvénients, mais elle permet un interpréteur assez simple.



Tokenizing de l'entrée utilisateur



Comme mentionné précédemment, il était courant pour les versions BASIC de cette époque d'utiliser des tactiques de tokenisation. Pour économiser de l'espace et augmenter la vitesse d'exécution, les mots-clés ont été «compressés» en jetons à un octet (ou à deux octets, si d'autres mots-clés sont nécessaires).



Imaginons que nous ayons une simple ligne de code qui efface l'écran et imprime un message d'accueil standard: 



CLS: PRINT "Hello, World"


Bien que cela ne prenne pas beaucoup de mémoire en soi, si vous écrivez un programme long, de nombreux mots de ce programme seront des mots clés. Si vous les compressez (tokenize), vous pouvez enregistrer une fraction solide de l'espace. Par exemple, après la tokenisation de la ligne ci-dessus, il y aura quelque chose comme ceci en mémoire: 



8A E3 B5 FC Hello, World 00 00


Il ne devrait pas être trop difficile de reconvertir cela dans la construction d'origine:



Octet Mot-clé Remarques
8A

CLS

E3 ":" Fin de construction
32 "" Nous stockons au plus un espace
B5

IMPRESSION
FB Ligne dans le code Vient ensuite la chaîne littérale
Bonjour, Monde, 00 Les chaînes sont terminées par null
00 Fin de ligne de code Les lignes de code sont également terminées par null


Vous pensez peut-être que c'est beaucoup de travail, mais les économies d'espace peuvent être importantes. Cela n'est pas particulièrement visible dans l'exemple, mais même à partir de celui-ci, vous pouvez imaginer à quelle vitesse l'espace économisé peut s'accumuler. Dans ce cas, le résultat compressé est de 19 octets. Le texte source se compose de 26 octets (y compris l'octet nul de fin).



L'économie d'espace devient importante lorsqu'il s'agit de l'interpréteur BASIC fonctionnant sur une machine avec très peu de RAM pour les programmes utilisateur. Par conséquent, une telle compression est très importante et intéressante, même si elle ne présente pas d'avantages supplémentaires.



Alors, comment symboliser quelque chose comme ça? Au début, il semble que JavaScript soit assez trivial pour faire cela. Avec un tableau de chaînes, vous pouvez rapidement remplacer chaque mot-clé par le jeton correspondant. Vrai?



On dirait que c'est un travail pour String#replace? Avec une approche naïve, vous pouvez essayer quelque chose comme ceci: 



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;
}


Malheureusement, nous nous rendons vite compte que nous ne pouvons pas remplacer les littéraux de chaîne par des jetons. Cela signifie que vous devez effectuer le traitement caractère par caractère, en tenant compte du contexte, afin de ne pas compresser des éléments qui ne sont pas des mots-clés.



Ce nouvel algorithme est plus proche du code du langage assembleur dans Retroputer, mais JS facilite toujours les choses. Voici le début du code JS (nous le développerons progressivement dans cet article): 



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;
}


Nous commençons avec une liste très simplifiée de jetons, car personne ne veut voir la table entière dans ce format ( c'est long, et Retroputer crée en fait des tables de jetons à partir d'un fichier JS! ), Mais pour nos besoins, cela suffira. Le principe ici est que lorsque nous voyons un jeton, nous écrivons son index dans le tableau de sortie.



À ce stade, nous avons une fonction qui, pour l'instant, convertit simplement la chaîne en ses codes de caractères équivalents. Bien qu'il ne soit pas particulièrement utile, il peut servir de cadre pratique.



La version en langage assembleur est assez similaire à celle illustrée ci-dessus. 



  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


Je n'ai pas inclus dans l'exemple ci _get-source-index- dessus ni dans d'autres fonctions, car leurs tâches sont claires d'après le nom: ils obtiennent simplement, définissent les index source et cible, et les parcourent également. Il est à noter que, contrairement à JS, il n'y a pas de tableaux alloués dynamiquement en langage d'assemblage, donc cet algorithme alloue un tampon de taille suffisante. Au fur et à mesure que nous descendons la ligne d'entrée, nous devons savoir où écrire le prochain jeton dans le tampon cible et ce que fait l'index cible ci-dessus. Chacune des fonctions ci-dessus renvoie un index dans Y. Par exemple, la fonction _adv-target-indexincrémente l'index cible de un (équivalent y++).



Soyez prudent avec les littéraux



Nous devons être prudents: les chaînes littérales peuvent être déroutantes pour le tokenizer - nous ne pouvons pas simplement remplacer chaque chaîne de caractères qui correspond à un mot-clé par une valeur de jeton. Si nous voyons un littéral de chaîne contenant "CLS", nous ne devrions pas chercher à le tokeniser. Il ne devrait pas être exécutable, et si nous le sortons ... alors à la place de cela, nous sortons l'octet correspondant au jeton. Très probablement, ce n'est pas ce que le développeur voulait dire.



D'un autre côté, les littéraux numériques ne devraient pas avoir ce problème, car BASIC n'a pas de mots-clés numériques. Même ainsi, il est inutile de rechercher un mot-clé face à un nombre - pourquoi perdre votre temps?



Tokeniser les littéraux de chaîne



Alors, vérifions d'abord si la ligne commence - dans JS, ce n'est pas particulièrement difficile: 



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;
}


Le guillemet double est représenté par le code de caractère 34. D'autres langages de programmation peuvent reconnaître beaucoup plus de styles de guillemets (comme JS ou C), mais avec BASIC c'est simple: soit des guillemets doubles, soit rien.



Quand nous voyons qu'une chaîne commence, nous pouvons simplement prendre les caractères restants et les ajouter au tableau de sortie jusqu'à ce que nous rencontrions un autre guillemet.



Après avoir lu la chaîne entière, un octet zéro doit être ajouté car Retroputer BASIC utilise des chaînes de style C. Si nous voulions utiliser des chaînes de style Pascal, nous pourrions stocker un compteur et insérer la longueur du littéral de chaîne. Dans tous les cas, cela ne pose pas de problème particulier. La seule raison pour laquelle j'ai utilisé des chaînes terminées par null est qu'elles sont très faciles à utiliser en langage assembleur - nous avons juste besoin de comparer avec un octet nul, pas de stocker un compteur.



Donc, JavaScript n'était pas particulièrement difficile. Je pense que la plupart d'entre vous décideraient d'utiliser quelque chose de plus abstrait, comme une expression régulière. Je pense que ce code rendra nos intentions plus évidentes. 



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;
}


Le code ci-dessus est à peu près le même, mais au lieu de la validation caractère par caractère, nous laissons le JS s'exécuter match. Nous savons que nous aurons une correspondance (nous sommes dans une chaîne), donc nous n'avons même pas besoin de vérifier si la correspondance a réussi. Nous incrémentons ensuite l'index de la longueur de la chaîne et copions les caractères dans le tableau de sortie. À mon avis, ce code est beaucoup plus facile à comprendre (cependant, il implique une compréhension des expressions régulières, ainsi que des particularités de la syntaxe ES6, par exemple, …et des fonctions fléchées).



Bien sûr, en langage assembleur, nous devons effectuer manuellement tout le travail effectué par JS. Le résultat est très similaire à notre première tentative d'écriture de code JS: 



  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:


Il vaut la peine d'ajouter une note sur l'analyseur du langage d'assemblage Retroputer - il a un support de base pour les constructions de haut niveau telles que les blocs et les boucles. Par conséquent, il if Z {…}exécutera le contenu à l'intérieur du bloc lorsque l'indicateur zéro est défini, et continuepeut être utilisé pour revenir au début du bloc ( breakégalement utilisé pour quitter le bloc). L'assembleur traduit cela en diverses instructions de comparaison et de branchement, de sorte que le processeur ne voit pas les parties de haut niveau du code, mais cela rend le code un peu plus facile à écrire.



Numéros de tokenisation



De plus, il n'est pas logique d'essayer de rechercher des nombres dans la liste des mots-clés, nous pouvons donc simplement les ignorer. La plupart des versions de BASIC font quelque chose de similaire à la manipulation de chaîne illustrée ci-dessus - si le caractère lu est un chiffre, il sera concaténé à la sortie, après quoi le compresseur prendra le relais.



Retroputer BASIC (et certaines autres versions de BASIC, comme Atari BASIC) va encore plus loin: il convertit un nombre au format binaire approprié. C'est très facile à faire - si nous rencontrons un chiffre, nous multiplions l'accumulateur par 10 et ajoutons le chiffre, en continuant ainsi tant que les chiffres continuent à apparaître. (Il convient de noter, cependant, que si Retroputer BASIC ne fonctionne qu'avec des valeurs entières, l'ajout de nombres à virgule flottante est déjà dans ma liste de tâches.)



(Je dois dire qu'actuellement, Retroputer BASIC ne fait rien lorsqu'un débordement d'entier se produit, qu'il soit signé ou non. Lorsque j'ajoute des nombres à virgule flottante, Retroputer se convertit également en virgule flottante.)



Retroputer BASIC va encore plus loin. : il reconnaît également les nombres hexadécimaux et les convertit en leur équivalent binaire. Il est utilisé comme désignation pour de tels nombres 0x(comme dans JS), et le langage lui-même a une logique supplémentaire pour garantir qu'une erreur est renvoyée si plusieurs caractères sont spécifiés x.



En langage assembleur, vérifier si un caractère est un chiffre n'est pas si difficile, mais cela nécessite quelques comparaisons: vous devez vous assurer que le code de caractère est compris entre 0x30et0x39... (Ce sont les codes de caractères "0" et "9".)



Après avoir reçu un caractère-chiffre, nous pouvons utiliser une autre propriété pratique du jeu de caractères. 0x30- c'est le code de caractère "0", 0x31- le code "1", etc. Nous pourrions soustraire si nous le voulions 0x30, mais il existe un moyen plus simple: il suffit de supprimer les quatre bits les plus significatifs: 



and dl, 0b0000_1111


Malheureusement, cela ne fonctionnera pas si nous devons gérer des nombres hexadécimaux. Dans ce cas, vous pouvez soustraire puis comparer avec 10, puis le réduire de 7 à nouveau si le code est supérieur à 10 (étant donné que les nombres hexadécimaux sont "A" - "Z" en majuscules).



Dans JS, vous pouvez à nouveau utiliser des expressions régulières, puis lorsque nous obtenons une correspondance avec le nombre, nous pouvons l'appeler Number(), ce qui nous donne un autre avantage: les nombres hexadécimaux sont également convertis de manière triviale, car il le Number()fait automatiquement si le nombre commence par 0x.



À quoi cela ressemble-t-il en JavaScript? 



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;
}


L'expression régulière vous permet d'utiliser n'importe quelle combinaison de nombres ou de chiffres hexadécimaux (plus xpour passer en mode hexadécimal). L'expression n'est pas idéale, par exemple, elle permet d'en utiliser plusieurs x, mais pour l'instant cela suffit.



Dans le code ci-dessus, la conversion de nombres en octets peut être discutable. Number()a fait tout le travail acharné pour transformer une chaîne de nombres en un nombre avec lequel JavaScript peut fonctionner, mais nous devons maintenant le représenter comme une séquence d'octets. Vous pouvez utiliser les mathématiques pour faire ceci: 



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


... et c'est facile à faire pour un entier. Mais grâce à l'utilisation de tableaux JS typés, vous ne pouvez pas faire tous ces calculs, mais en même temps vous préparer à gérer les nombres à virgule flottante dans le futur (nous allons simplement remplacer Uint16Arraypar Float64Array).



Le code en langage assembleur pour cette tâche est légèrement plus long , mais il en fait un peu plus. Retroputer utilise une autre optimisation: si le nombre est petit, il est enregistré dans un format plus petit. Cela signifie que 0-255 peut être stocké dans un octet, tandis que les nombres plus longs en prennent deux.



Rechercher des mots-clés



Nous avons donc fait pas mal de travail, mais jusqu'à présent, nous n'avons pas compressé un seul mot-clé. Après avoir traité des nombres et des chaînes littérales, nous pouvons être sûrs que tout le reste est soit un mot-clé, soit un nom de variable. (Ou un espace, mais c'est facile à vérifier.)



En BASIC, les mots-clés ne commencent pas toujours par un caractère alphabétique; les opérateurs et les délimiteurs sont également considérés comme des jetons. Mais les variables commencent également par un caractère alphabétique. Nous ne pouvons donc pas déterminer immédiatement si nous allons compresser un mot-clé ou une variable. Cela nous convient - si nous ne trouvons pas de correspondance dans la liste des jetons, nous supposerons qu'il s'agit d'une variable.



Alors, comment vérifier qu'un mot clé potentiel est bien un mot clé? Si nous écrivions en JavaScript, nous pourrions utiliser le Array#findIndex. 



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


La méthode Array#findIndexitère sur le tableau tokenset nous pouvons vérifier si elle commence inStr(par l'actuel idx) avec le jeton que nous vérifions. En travaillant avec notre liste simplifiée de jetons, nous ferons quelque chose comme (supposons que inStr.substr(idx)===”PRINT”):



jeton .startsAvec (jeton)? Indice
CLS faux 0
IMPRESSION vrai 1


Remarque: comme indexOfavec JS, si rien n'est trouvé, nous obtenons -1.



Si une correspondance est trouvée, vous pouvez stocker son index dans le tableau renvoyé. Mais comment distinguer plus tard un jeton d'un symbole? Facile: activez le bit le plus significatif, ce qui peut être fait en ajoutant 128 à la valeur du jeton



(Remarque: si nous avons besoin de plus de jetons que 128, alors pour certains jetons, nous devrons utiliser deux octets. Cela complique un peu les choses, mais pas tellement. Certaines versions de BASIC le font, par exemple, dans divers Microsoft BASIC.)



Nous en avons terminé avec JavaScript, mais comment le faire en langage assembleur?



Il s'avère que c'est presque le même, mais le code sera beaucoup plus long. 



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


Eh bien, ça n'a pas l'air si mal. L'algorithme est presque le même, seule la table des jetons du langage d'assemblage est structurée légèrement différemment. Cela ressemble à quelque chose comme ceci: 



CLS   00 80
PRINT 00 81
:     00 82


Chaque mot-clé se termine par un octet nul suivi d'un numéro de jeton.



Cependant, il nous manque quelque chose d'important ici - comment cette comparaison de chaînes est-elle effectuée? Il y a une procédure au cœur de Retroputer STRCMPque nous pouvons utiliser, mais à quoi cela ressemble-t-il? 



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
}


Je ne sais pas pour vous, mais je commence à aimer String#startsWithde plus en plus la méthode de JS. Oui, cela fait la même chose, mais nous n'avons pas à écrire toute la logique interne!



Manipulation variable



La compression des touches est maintenant terminée, nous pouvons donc terminer. Mais Retroputer BASIC fait un autre pas en avant: la tokenisation des variables. Il me semble que seules quelques versions de BASIC des années 80 et 90 l'ont fait, car dans des conditions de mémoire limitée, cela peut être nocif. Mais s'il y a beaucoup de mémoire, la tokenisation des variables permet d'améliorer les performances.



Voici ce que fait Retroputer BASIC:



  • Il lit jusqu'aux deux premiers caractères du nom de la variable. (C'était un inconvénient standard des versions BASIC de l'époque en raison de contraintes de mémoire.)
  • A partir de ces deux caractères, il détermine l'indice de la variable. "A" est la variable 0, "A0" est la variable 53, et ainsi de suite. L'équation est assez simple, mais elle ne nous intéresse pas pour le moment.
  • BASIC . , $ BASIC . .
  • BASIC , . !


(Remarque: lorsque Retroputer BASIC apprend à allouer dynamiquement de la mémoire pour les variables, nous remplacerons l'index par un pointeur vers une variable. Un autre élément dans la liste de tâches!)



Cela rend la recherche de variables incroyablement rapide à l'exécution: nous n'avons pas à analyser le nom de la variable et à calculer l'index à chaque fois lorsque nous rencontrons une variable. Dans les cycles continus, les économies peuvent être substantielles. Mais cela a un coût élevé: nous devons stocker le pointeur et le nom de la variable ensemble, donc pour chaque variable que nous rencontrons, nous devons ajouter quatre octets supplémentaires à la sortie.



C'est à vous de décider si cela en vaut la peine.



Quoi qu'il en soit, en JavaScript, il est également facile de déterminer si le reste du flux de caractères est une variable: 



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;
}


Je ne décrirai pas en détail le code que Retroputer utilise actuellement pour tokeniser les variables, il est trop verbeux. Nous y reviendrons lorsque j'ajouterai une allocation de mémoire dynamique pour les variables.



Tokenisation terminée



Si nous testons maintenant notre code dans JS, nous obtenons un tableau d'octets similaire à celui que Retroputer BASIC utilise en interne: 



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, quel travail pour économiser quelques octets. Mais quand il n'y a que quelques kilo-octets de mémoire libre, ça vaut le coup! Mais ce n'est pas le seul avantage de compresser le texte saisi par l'utilisateur, on accélère également l'exécution du programme.



Pour expliquer pourquoi cela se produit, nous devons comprendre comment Retroputer exécute le code. Je n'entrerai pas dans les détails pour l'instant, mais en un mot, ce qui suit est nécessaire pour exécuter le code:



  • Obtenez un octet de la mémoire
  • Si l'octet a le bit le plus significatif activé, alors c'est un jeton, sinon c'est une erreur de syntaxe (ou NUL; dans tous les cas, c'est là que nous finissons de travailler avec la ligne de programme)
  • Nous recherchons un gestionnaire de jetons dans un tableau - ce tableau contient des pointeurs vers les fonctions elles-mêmes qui traitent le jeton
  • Nous appelons le gestionnaire (il est responsable de la réception des arguments et autres)
  • Nous répétons encore une fois


C'est une autre raison de tokeniser les mots-clés - l'exécution de la logique du mot-clé devient triviale, il suffit de trouver l'adresse dans le tableau et de l'appeler.



Je voudrais souligner que si la tokenisation est importante pour économiser de l'espace, elle améliore également la vitesse d'exécution.



Par exemple, une boucle d'exécution JS peut ressembler à ceci: 



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


Bien sûr, en réalité tout n'est pas si simple, c'est bien plus, mais c'est déjà un sujet pour un autre post!



Ressources







La publicité



VPS puissant avec protection DDoS et matériel le plus récent. Tout cela concerne nos serveurs épiques . La configuration maximale est de 128 cœurs de processeur, 512 Go de RAM, 4000 Go de NVMe.





More articles:


All Articles