🤞🏻 ⏸️ 👨‍💻 80年代スタイルのBASICインタープリターを書く 🉐 👓 🤙🏿

私は数年間、「偽のエミュレーター」、つまり、存在しなかったコンピューター用にJavaScriptで記述されたエミュレーターを作成する（そして実際に研究する）という個人的なプロジェクトに取り組んできました。このマシンは、1980年代と90年代の8ビットと16ビットのコンピューターのメモリへのオマージュであると考えられていました。

しかし、私はその複雑さが大好きです。このマシンも新しい一連の命令を使用していました。それはその時代に使用されたキットに似ていますが、操作が少し簡単です。Retroputerが誕生しました。何年にもわたって、エミュレーターは拡張および改善されてきましたが、おそらく「完成」することはありません（結局のところ、これは個人的な研究プロジェクトです）。@bbcmicrobot

が登場したとき、Retroputerに似たものを作りたかった。私のJS開発スキルは主にフロントエンドに限定されていたので、これはバックエンドの経験を積むための素晴らしい言い訳になります。問題は1つだけです。Retroputerは独自のアセンブリ言語しか理解できません。まだBASICをサポートしていません。

そこで私は、80年代のスタイルで、つまり完全にアセンブリ言語でBASICインタープリターを作成することを思いつきました。通常の抽象化から遠く離れた領域に飛び込む必要がないことが多いので、自分の仕事を共有する価値があると判断しました。私の日常のツール（JavaScript）は、多くの側面を些細なものにし、時には魔法のようにさえ思えます。最も低いレベルのプロセスを理解することは、これらの抽象化を理解するのに役立つことがよくあります。

それでは始めましょう。

Retroputerの特性

16 ROM (KERNEL) c 1 (scratch space)

512 , 64

16- 6516, 512 4 64

4025, ,

1125

9800

Retroputerのアセンブラーを書いていたとき、非常に便利なPegjsツールを使用できました。高速なネイティブアセンブラ構文を提供しましたが、残念ながら、RetroputerASMにはこのようなものはありません。つまり、私たちは困難な道を歩まなければなりません。

解析自体はいくつかの段階で実行されます。コンパイラを使用する言語は、コードを解析して抽象構文ツリー（AST）（または他の表現）にし、このツリーを使用して完成したネイティブコードを生成できます。したがって、コンパイルを成功させるには、プログラムが構文的に正しい必要があります。

一部の最新のインタープリターにもこの概念があります。これは、ソースコードではなく、中間ASTを生成して実行すると便利な場合が多いためです。

ただし、リソースが限られているマシン上のBASICインタープリターの場合、いくつかの段階で解析するのが最も効率的であり、その一部は実行時に発生します。ただし、これは、プログラムを実行してエラーのあるコードの領域に移動するまで、構文エラーを検出できないことを意味します。

Retroputer BASIC解析は、次の3つの段階で構成されます。

文字列の変換
トークン化
ランタイム構文チェック

最初の2つの段階は、ユーザーがプログラムに入る（またはプログラムをダウンロードする）ときに発生します。後者は、プログラムの実行中に発生します。基本的に、最初の2つは航空機の胴体を作成しますが、離陸することを保証するものではありません。最後のレグはテストパイロットです-彼が離陸することを願っていますが、彼が試みるまでそれについてはわかりません。

注： Retroputer BASICソースコード（開発中）はGitHubで入手できます。

文字列の変換

これは、プロセス全体の中で最も単純な部分です。ユーザーが入力した文字列は大文字に変換され、後続のプロセスが簡素化（および高速化）されます。BASICは大文字と小文字を区別しないため、それを利用できます。

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

JavaScriptでこれを行うのはとても簡単ですよね？

theLine = theLine.toUpperCase();

しかし、アセンブリ言語では、このプロセスはより詳細です。文字を読み、大文字に変換して、どこかに保存する必要があります。

           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.

上記のコードは、JavaScriptバージョンのコードのセマンティクスと完全には一致していません。重要な違いは、今日ではUnicodeを使用してテキストを処理しているため、入力を小文字から大文字に変換するのが難しい場合が多く、不可能な場合もあります（言語によって異なります）。 RetroputerはASCIIの世界（より正確には、RetSCIIと呼ばれる独自のASCIIバリエーションの世界）に存在します。つまり、サポートされているすべての文字は8ビットでエンコードされます。多くの言語にとって、これは完全に不十分ですが、それは当時の現実を満たしています。

これは、かわいいASCII機能を使用して小文字から大文字に変換できることも意味します。大文字の「A」はASCIIコード65で表され、小文字の「a」はコードで表されます。97..。 2の累乗に精通している場合は、この違いに気付いたはずです。

したがって、小文字は小文字の数よりも正確に32多い数で指定されていることがわかります。値が正しい範囲にあることがわかっている場合は、32を引くだけで済みます。

このアプローチは機能しますが、ビットを少し変更するだけです。 Retroputerの場合、これは減算よりも高速ではありませんが、減算がない場合は、計算中にキャリー/ボローフラグに注意を払う必要はありません。and32値の代わりにビットワイズを使用してビットをオフにできることがわかりました。

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

ただし、微妙な点が1つあります。すべてを大文字に変換できるわけではありません。たとえば、ユーザーが文字列リテラルを追加した場合、Retroputer BASICが常に大文字でユーザーに怒鳴りたくないので、もっと注意する必要があります。（当時の多くのコンピューターには小文字がありませんでしたが、Retroputerにはありませんでした。）

例：

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

これは、文字列リテラルの途中にいるかどうかを追跡する必要があることを意味します。BASICでは、これに対する指定は2つだけです。二重引用符です。文字が二重引用符の場合、フラグを設定し、フラグの値に応じて大文字に変換するか、そのままにしておくことができます。

JavaScriptにはこのための組み込み機能がないことがわかりましたが、自分で作成することはできます。

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

JSのUnicodeサポートを少し利用しますが、JSのロジックはアセンブラーのバージョンとより厳密に一致するようになりました。

アセンブラのバージョンは次のようになります。

           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.

これまでのところ、入力テキストの大文字への変換のみを行ってきましたが、別の可能性として文字列リテラルの定義を使用できます。もう1つの構文チェックを実行できます！

プロセスの最後にinStringまだ真（bl = 0xFF）が何であるかがわかった場合、エラーを返す可能性があります。これは、文字列のどこかに不完全な文字列リテラルがあることを意味します。

注： BASICの多くのバージョンは、文字列に閉じ引用符がないことに対してかなり寛大であることがわかりました。私は自分の通訳を作成しているときにこれを見つけました。たとえそうだとしても、それは私には正しくないように思われるので、RetroputerBASICはそれを許可しません。

トークン化

解析の次のステップは、入力文字列をRetroputerBASICインタープリターが実行するためのより効率的なものに変換することです。抽象構文ツリーの概念にできるだけ近づけようとしていますが、結果はまだツリーではありません。しかし、それは実行時に迅速に処理できるものになります。

初期のマイクロコンピュータの共通の特徴は、非常に限られたメモリでした。 Retroputerは、当時のほとんどの標準的なマシンよりも多くのメモリを備えていますが、それでも最新のコンピュータよりもはるかに少ないです。したがって、長いBASICプログラムは、ユーザー入力中に保存すると、メモリを大量に消費する可能性があります。

スペースを節約するために、キーワードはプログラムがメモリに入力されるときにトークン化されます..。このプロセスは、キーワードをシングルバイトトークンに変換します。キーワードは常に少なくとも2バイトの長さであるため、入力するにつれてさらに節約できます。また、実行時にルックアップテーブルを使用して、適切なアセンブリ言語ルーチンを呼び出すことができることも意味します。

ただし、Retroputer BASICは、当時のほとんどのBASICバージョンよりも少し進んでいます。さらに、数値をバイナリ形式に変換したり、文字列にマークを付けたり、変数参照を計算したりします。正直なところ、これはより多くのスペースを浪費していますが、速度（および実装の容易さ）の利点はそれを上回ります。

したがって、ここでは次の手順を使用します。

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

, .
, , , . JavaScript, !

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

Retroputer BASIC . , . , Retroputer BASIC.

投稿では、アセンブリ言語でのこのステージの実装については詳しく説明しませんが、将来のために残しておきます。しかし、心配しないでください。そこにはたくさんのコードがあります。

実行時の構文の確認

最後になりましたが、ランタイム構文チェックはです。コードをトークン化された形式に変換した後、それを実装するのは非常に簡単です。

まず、実行時に、 BASICは現在トークンを処理しているかどうかを確認します。すべてのトークンで最上位ビットが有効になっています（つまり、値が128以上です）。トークンが見つかった場合、ベクトルテーブルでトークンを見つけることにより、呼び出すサブルーチンを決定できます。また、構文エラーを表示することも簡単になります。一部のキーワードは演算子として意味をなさないため、ベクトルテーブルは単に構文エラーを生成するプロシージャを指します。

オペレータートークンハンドラーが呼び出された後、ハンドラーはすべての追加の解析作業を引き受けます。それはそれらの間の移行を使用することができ、トークンの場合やgettok、gettok-raw、peektokなどトークンがプロシージャによって予期されていないものである場合、プロシージャは単にエラーコードを返します。構文エラーとタイプマッチングエラーの両方が検出されるのはこの段階です。

オペレーターが式を評価する必要がある場合は、解析の別の段階が実行されます。式の解析中に、別のベクトルルックアップテーブルが使用されます。つまり、数式に関連しないキーワードをインターセプトして、対応するエラーを返すことができます。たとえば、入力しようとするとPRINT 2+CLS、次に構文エラーが発生しますCLS（CLS-これは「画面のクリア」の省略形です）。

注：この表から、数学演算子の優先度と必要なパラメーターの数を決定することもできます。これは、式の実際の評価にとって重要ですが、ユーザーが十分な引数を提供していない場合をキャッチするためにも使用できます。

トークンはベクタールックアップテーブルエントリに直接マップされるため、プログラムは最小限の労力でかなり迅速に実行できます。各タイプの演算子を解析するタスクはハンドラー自体に委ねられており、通常、これによって特別な問題が発生することはありません。ある解析するおそらく最も難しいPRINTとINPUT、ただし、各ステップで一度に1つのトークンが取得されます。

多くのチェックはプログラムの実行時まで実行されないため、これは、エラーが発生する前に部分的な結果が得られる可能性があることを意味します。例えば：

PRINT "Hello";CLS
Hello
?Syntax Error

また、プログラムがテキストを表示できない状態で画面を離れると、エラーの除去に問題が発生する可能性があることを意味します。構文エラーが表示されても表示されない場合は、どうすればよいですか？

構文をチェックするこの方法には確かに欠点がありますが、かなり単純なインタープリターが可能です。

ユーザー入力のトークン化

前述のように、その時代のBASICバージョンではトークン化戦術を使用するのが一般的でした。スペースを節約し、実行速度を上げるために、キーワードはシングルバイトトークン（または、さらにキーワードが必要な場合はダブルバイト）に「圧縮」されました。

画面をクリアして標準の挨拶を印刷する簡単なコード行があるとしましょう。

CLS: PRINT "Hello, World"

これ自体はあまりメモリを消費しませんが、長いプログラムを作成すると、そのプログラムの多くの単語がキーワードになります。それらを圧縮（トークン化）すると、スペースのかなりの部分を節約できます。たとえば、上記の行をトークン化した後、メモリには次のようなものがあります。

8A E3 B5 FC Hello, World 00 00

これを元の構成に戻すのはそれほど難しいことではありません。

バイト	キーワード	ノート
8A	CLS
E3	"："	工事終了
32	「」	最大1つのスペースに保管します
B5	印刷
FB	コードの行	次は文字列文字です
こんにちは、ワールド、00		文字列はnullで終了します
00	コード行の終わり	コード行もnullで終了します

これは大変な作業だと思われるかもしれませんが、スペースの節約は重要です。これはこの例では特に目立ちませんが、そこからでも、節約されたスペースがどれだけ早く蓄積されるかを想像することができます。この場合、圧縮された結果は19バイトです。ソーステキストは26バイト（終了ヌルバイトを含む）で構成されます。

ユーザープログラム用のRAMが非常に少ないマシンで実行されるBASICインタープリターに関しては、スペースの節約が重要になります。したがって、このような圧縮は、追加の利点がない場合でも、非常に重要で魅力的です。

では、このようなものをどのようにトークン化するのでしょうか？最初は、JavaScriptでこれを行うのは非常に簡単なようです。文字列の配列を使用すると、各キーワードを対応するトークンにすばやく置き換えることができます。本当ですか？

これはの仕事のようString#replaceですか？素朴なアプローチでは、次のようなことを試すことができます。

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

残念ながら、文字列のリテラルをトークンに置き換えることはできないことにすぐに気付きました。これは、キーワードではない要素を圧縮しないように、コンテキストを考慮して、文字ごとに処理を行う必要があることを意味します。

この新しいアルゴリズムは、Retroputerのアセンブリ言語コードに近いものですが、JSを使用すると作業がはるかに簡単になります。これがJSコードの始まりです（この投稿で徐々に拡張していきます）：

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

テーブル全体をこの形式で表示したくないため（長く、Retroputerは実際にはJSファイルからトークンテーブルを作成します！）、トークンの非常に単純化されたリストから始めますが、私たちの目的にはこれで十分です。ここでの原則は、トークンを見つけたら、そのインデックスを出力配列に書き込むことです。

この時点で、今のところ、文字列を同等の文字コードに変換するだけの関数があります。特に有用ではありませんが、便利なフレームワークとして機能します。

アセンブリ言語のバージョンは、上記のバージョンと非常によく似ています。

  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

上記の例_get-source-indexや他の関数には、タスクが名前から明らかであるため、含まれていません。それらは、ソースインデックスとターゲットインデックスを取得、設定し、それらをナビゲートするだけです。JSとは異なり、アセンブリ言語には動的に割り当てられた配列がないため、このアルゴリズムは十分なサイズのバッファーを割り当てます。入力行を下に移動するとき、ターゲットバッファの次のトークンをどこに書き込むか、およびターゲットインデックスが上記で何を行っているかを知る必要があります。上記の各関数は、でインデックスを返しますY。たとえば、この関数_adv-target-indexはターゲットインデックスを1つインクリメントします（同等y++）。

リテラルに注意してください

注意する必要があります。文字列リテラルはトークナイザーを混乱させる可能性があります。キーワードに一致するすべての文字文字列をトークン値に単純に置き換えることはできません。「CLS」を含む文字列リテラルが表示された場合、それをトークン化しようとすべきではありません。実行可能であってはならず、出力すると...その代わりにトークンに対応するバイトが出力されます。これは、開発者が意図したものではない可能性があります。

一方、BASICには数値キーワードがないため、数値リテラルにはこの問題はありません。それでも、数字に直面したときにキーワードを検索しても意味がありません-なぜ時間を無駄にするのですか？

文字列リテラルのトークン化

それで、最初に行が始まるかどうかを確認しましょう-JSではこれを行うことは特に難しいことではありません：

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

二重引用符は文字コード34で表されます。他のプログラミング言語では、さらに多くのスタイルの引用符（JSやCなど）を認識できますが、BASICを使用すると、二重引用符を使用するか、何も使用しないかという単純なものになります。

文字列が始まるのを確認したら、残りの文字を取得して、別の引用符が見つかるまで出力配列に追加するだけです。

Retroputer BASICはCスタイルの文字列を使用するため、文字列全体を読み取った後、ゼロバイトを追加する必要があります。Pascalスタイルの文字列を使用する場合は、カウンターを格納して文字列リテラルの長さを挿入できます。いずれにせよ、これは特に問題にはなりません。 nullで終了する文字列を使用した唯一の理由は、アセンブリ言語での操作が非常に簡単であるためです。カウンタを格納するのではなく、nullバイトと比較するだけで済みます。

したがって、JavaScriptはそれほど難しくありませんでした。ほとんどの人は、通常の表現のように、もっと抽象的なものを使うことに決めると思います。このコードは私たちの意図をより明確にするだろうと思います。

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

上記のコードはほぼ同じですが、文字ごとの検証の代わりに、JSにを実行させmatchます。一致することがわかっているので（文字列内にあります）、一致が成功したかどうかを確認する必要もありません。次に、文字列の長さだけインデックスをインクリメントし、文字を出力配列にコピーします。私の意見では、このコードははるかに理解しやすいです（ただし、正規の式、たとえばES6構文の特性、…および矢印関数の理解を意味します）。

もちろん、アセンブリ言語では、JSが行うすべての作業を手動で行う必要があります。結果は、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:

Retroputerアセンブリ言語パーサーについてのメモを追加する価値があります-ブロックやループなどの高レベルの構造を基本的にサポートしています。したがって、if Z {…}ゼロフラグが設定されている場合、ブロック内のコンテンツを実行し、ブロックcontinueの先頭に分岐するために使用できます（ブロックbreakを終了するためにも使用されます）。アセンブラはこれをさまざまな比較および分岐命令に変換するため、CPUはコードの高レベルの部分を認識しませんが、コードを少し簡単に記述できます。

トークン化番号

また、キーワードのリストで数字を検索しようとしても意味がないため、スキップすることができます。 BASICのほとんどのバージョンは、上記の文字列操作と同様のことを行います。読み取られた文字が数字の場合、出力に連結された後、コンプレッサーが引き継ぎます。

Retroputer BASIC（およびAtari BASICなどの他のバージョンのBASIC）は、さらに一歩進んで、数値を適切なバイナリ形式に変換します。これを行うのは非常に簡単です。数字に出会った場合、アキュムレータに10を掛けて数字を加算し、数字が出現し続ける限り続けます。（ただし、Retroputer BASICは整数値でのみ機能しますが、浮動小数点数の追加はすでに私のToDoリストに含まれていることに注意してください。）

（現在、Retroputer BASICは、符号付きか符号なしかに関係なく、整数オーバーフローが発生しても何もしません。浮動小数点数を追加すると、Retroputerも浮動小数点に変換されます。）

RetroputerBASICはさらに一歩進んでいます。：また、16進数を認識し、それらを同等の2進数に変換します。これは0x（JSのように）そのような番号の指定として使用され、言語自体には、複数の文字が指定された場合にエラーが返されるようにするための追加のロジックがありますx。

あなたは、文字コードの間であることを確認する必要があります。文字は難しいが、それは比較のカップルを必要とすることが数字ではありませんされているかどうかをチェックするアセンブリ言語では、0x30と0x39..。（これらは文字コード「0」と「9」です。）

文字桁を受け取ったら、文字セットの別の便利なプロパティを使用できます。0x30-これは文字コード「0」、0x31-コード「1」などです。必要に応じて減算することもできます0x30が、もっと簡単な方法があります。最上位4ビットを破棄するだけです。

and dl, 0b0000_1111

残念ながら、16進数を処理する必要がある場合、これは機能しません。この場合、減算して10と比較し、コードが10より大きい場合は、再度7ずつ減らすことができます（16進数が大文字の「A」-「Z」の場合）。

JSでは、通常の式を再度使用できます。その後、番号が一致したときにを呼び出すことができますNumber()。これにより、別の利点Number()が得られ0xます。番号が。で始まる場合は自動的に変換されるため、16進数も簡単に変換されます。

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

通常の式では、数字または16進数の任意の組み合わせを使用できます（さらにx、16進数モードに切り替えることもできます）。この式は理想的ではありません。たとえば、複数を使用できますxが、今のところこれで十分です。

上記のコードでは、数値をバイトに変換することは疑わしい場合があります。Number()数字の文字列をJavaScriptが処理できる数字に変換するという大変な作業をすべて行いましたが、今度はそれをバイトのシーケンスとして表す必要があります。これを行うには、数学を使用できます。

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

...そしてそれは整数に対して行うのは簡単です。しかし、JSの使用のおかげで、あなたはすべてのこれらの計算を避けるが、同時に（私たちは、単に置き換えます将来的には浮動小数点数を扱うために準備することができ、配列を入力Uint16ArrayしてFloat64Array）。

このタスクのアセンブリ言語コードは少し長くなりますが、少し長くなります。Retroputerはもう1つの最適化を使用します。数値が小さい場合は、小さい形式で保存されます。これは、0〜255を1バイトに格納できるのに対し、長い数値は2を占めることを意味します。

キーワードを検索する

そのため、かなりの作業を行いましたが、これまでのところ、単一のキーワードを圧縮していません。数字と文字列のリテラルを扱ってきたので、他のすべてがキーワードまたは変数名のいずれかであると確信できます。（またはスペースですが、これは簡単に確認できます。）

BASICでは、キーワードは必ずしもアルファベット文字で始まるとは限りません。演算子と区切り文字もトークンと見なされます。ただし、変数もアルファベット文字で始まります。したがって、キーワードと変数のどちらを圧縮するかをすぐに決定することはできません。これは私たちに適しています-トークンのリストに一致するものが見つからない場合、これは変数であると見なされます。

では、潜在的なキーワードが実際にキーワードであることをどのように確認するのでしょうか。 JavaScriptで記述している場合は、を使用できますArray#findIndex。

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

メソッドArray#findIndexは配列tokensを反復処理し、チェックしているトークンでinStr（現在の配列で）開始するかどうかをチェックできidxます。トークンの簡略化されたリストを使用して、次のようなことを行います（と仮定しますinStr.substr(idx)===”PRINT”）。

トークン	.startsWith（トークン）？	インデックス
CLS	false	0
印刷	true	1

注：indexOfJSと同様に、何も見つからない場合は、を取得し-1ます。

一致するものが見つかった場合は、返された配列にそのインデックスを保存できます。しかし、後でトークンとシンボルをどのように区別するのでしょうか。簡単：最上位ビットをオンにします。これは、トークン値に128を追加することで実行できます

（注：128より多くのトークンが必要な場合、一部のトークンでは2バイトを使用する必要があります。これは少し複雑になりますが、それほど複雑ではありません。 BASICの一部のバージョンは、たとえば、さまざまなMicrosoft BASICでこれ

を実行します。）JavaScriptは終了しましたが、アセンブリ言語でどのように実行しますか？

ほぼ同じであることがわかりますが、コードははるかに長くなります。

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

まあ、それほど悪くはないようです。アルゴリズムはほとんど同じですが、アセンブリ言語のトークンテーブルの構造が少し異なります。これは次のようになります。

CLS   00 80
PRINT 00 81
:     00 82

各キーワードは、nullバイトとそれに続くトークン番号で終了します。

ただし、ここでは重要なことが欠けています。この文字列の比較はどのように行われるのでしょうか。RetroputerのコアにSTRCMPは使用できる手順がありますが、どのように見えますか？

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
}

あなたのことはわかりませんが、String#startsWithJSメソッドがますます好きになり始めています。はい、同じことをしますが、すべての内部ロジックを記述する必要はありません！

可変処理

これでキーの圧縮が完了したので、終了できます。しかし、Retroputer BASICは、変数のトークン化という別の一歩を踏み出しました。メモリが限られている状況では有害である可能性があるため、80年代と90年代のBASICのいくつかのバージョンのみがこれを行ったように思われます。ただし、メモリが多い場合は、変数のトークン化によってパフォーマンスが向上します。

RetroputerBASICの機能は次のとおりです。

変数名の最初の2文字までを読み取ります。（これは、メモリの制約のために、当時のBASICバージョンの標準的な不便でした。）
これらの2つの文字から、変数のインデックスを決定します。「A」は変数0、「A0」は変数53などです。方程式は非常に単純ですが、今は興味がありません。
BASIC . , $ BASIC . .
BASIC , . !

（注：Retroputer BASICが変数にメモリを動的に割り当てることを学習すると、インデックスを変数へのポインターに置き換えます。ToDoリストの別の項目です！）

これにより、実行時に変数を非常に高速に見つけることができます。変数名を解析してインデックスを毎回計算する必要はありません。変数に出会ったとき。連続サイクルでは、大幅な節約になります。ただし、これにはコストがかかります。ポインタと変数名を一緒に格納する必要があるため、発生する変数ごとに、出力に4バイトを追加する必要があります。

それが価値があるかどうかを決めるのはあなた次第です。

とはいえ、JavaScriptでは、文字ストリームの残りの部分が変数であるかどうかを判断するのも簡単です。

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

Retroputerが変数をトークン化するために現在使用しているコードについては詳しく説明しません。冗長すぎます。変数に動的なメモリ割り当てを追加すると、それに戻ります。

トークン化が完了しました

JSでコードをテストすると、RetroputerBASICが内部で使用するものと同様のバイト配列が得られます。

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

うわー、数バイトを節約するのに何と大変な作業です。しかし、空きメモリが数キロバイトしかない場合は、それだけの価値があります。ただし、ユーザーが入力したテキストを圧縮する利点はこれだけではありません。プログラムの実行も高速化されます。

これが発生する理由を説明するには、Retroputerがコードを実行する方法を理解する必要があります。ここでは詳しく説明しませんが、簡単に言うと、コードを実行するには次のものが必要です。

メモリから1バイトを取得します
バイトの最上位ビットがオンになっている場合、それはトークンです。それ以外の場合は、構文エラー（またはNUL。いずれの場合も、これがプログラム行になります）です。
配列内のトークンハンドラーを探しています-この配列には、トークンを処理する関数自体へのポインターが含まれています
ハンドラーを呼び出します（引数などの受信を担当します）
もう一度繰り返します

これは、キーワードをトークン化するもう1つの理由です。キーワードのロジックを実行するのは簡単で、配列内のアドレスを見つけて呼び出すだけです。

トークン化はスペースを節約するために重要ですが、実行速度も向上することを強調したいと思います。

たとえば、JS実行ループは次のようになります。

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

もちろん、実際にはすべてがそれほど単純ではなく、はるかに単純ですが、これはすでに別の投稿のトピックです！

80年代スタイルのBASICインタープリターを書く

Retroputerの特性