Clever Geek Handbook

Menulis juru bahasa BASIC gaya 80-an





Selama beberapa tahun saya telah mengerjakan proyek pribadi untuk membuat (dan benar-benar meneliti) "emulator palsu", yaitu emulator yang ditulis dalam JavaScript untuk komputer yang tidak pernah ada. Mesin ini seharusnya menjadi penghormatan bagi komputer delapan dan enam belas-bit tahun 1980-an dan 90-an.



Namun, saya menyukai kerumitannya: mesin ini juga menggunakan serangkaian instruksi baru. Ini mirip dengan kit yang digunakan di era itu, tetapi sedikit lebih mudah untuk digunakan. Retroputer lahir . Selama bertahun-tahun, emulator telah berkembang dan meningkat, tetapi kemungkinan besar tidak akan pernah "selesai" (bagaimanapun juga, ini adalah proyek penelitian pribadi).



Saat @bbcmicrobot muncul, Saya ingin membuat sesuatu yang serupa untuk Retroputer. Keterampilan pengembangan JS saya sebagian besar terbatas pada front-end, jadi ini akan menjadi alasan yang bagus untuk mendapatkan pengalaman back-end. Hanya ada satu masalah: Retroputer hanya dapat memahami bahasa assemblynya sendiri. Itu belum memiliki dukungan BASIC.



Jadi saya datang dengan pembuatan juru bahasa BASIC dengan gaya tahun 80-an, yaitu, sepenuhnya dalam bahasa assembly, seperti yang kemudian ditulis. Saya memutuskan bahwa pekerjaan saya pantas dibagikan karena kami tidak sering harus menyelami area yang sangat jauh dari abstraksi biasanya. Alat keseharian saya (JavaScript) membuat banyak aspek menjadi sepele dan terkadang bahkan tampak seperti sihir. Memahami proses tingkat terendah sering membantu dalam memahami abstraksi ini.



Jadi mari kita mulai.



Karakteristik retroputer



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




Ketika saya menulis assembler untuk Retroputer, saya dapat menggunakan alat Pegjs yang sangat berguna. Ini menyediakan sintaks perakitan asli yang cepat, tetapi sayangnya tidak ada yang seperti ini untuk Retroputer ASM. Artinya, kita harus menempuh jalan yang sulit.



Penguraiannya sendiri dilakukan dalam beberapa tahap. Bahasa yang menggunakan kompilator mengurai kode menjadi pohon sintaksis abstrak (AST) (atau representasi lain), dan kemudian dapat menggunakan pohon ini untuk menghasilkan kode asli yang telah selesai. Oleh karena itu, program harus benar secara sintaksis agar kompilasi berhasil.



Beberapa penafsir modern memiliki konsep ini juga, karena seringkali berguna untuk menghasilkan AST perantara dan mengeksekusinya daripada kode sumber.



Namun untuk interpreter BASIC pada mesin dengan sumber daya terbatas, akan sangat efisien untuk mengurai dalam beberapa tahap, beberapa di antaranya terjadi pada waktu proses. Namun, ini berarti kesalahan sintaks tidak dapat dideteksi hingga Anda menjalankan program dan menavigasi ke area kode yang mengalami kesalahan.



Penguraian Retroputer BASIC terdiri dari tiga tahap:



  1. Mengonversi string
  2. Tokenisasi
  3. Pemeriksaan sintaks waktu proses


Dua tahap pertama terjadi ketika pengguna memasuki program (atau mendownloadnya). Yang terakhir terjadi selama eksekusi program. Pada dasarnya, dua yang pertama membuat badan pesawat pesawat, tapi tidak menjamin akan lepas landas. Kaki terakhir adalah pilot uji - kami berharap dia lepas landas, tetapi kami tidak yakin tentang itu sampai dia mencoba.



Catatan: Kode sumber BASIC Retroputer (dalam pengembangan) tersedia di GitHub .



Mengonversi string



Ini adalah bagian paling sederhana dari keseluruhan proses. String yang dimasukkan pengguna diubah menjadi huruf besar untuk menyederhanakan (dan mempercepat) proses selanjutnya. BASIC tidak peka huruf besar / kecil, jadi kami dapat memanfaatkannya. 



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


Sangat mudah untuk melakukan ini di JavaScript, bukan? 



theLine = theLine.toUpperCase();


Namun dalam bahasa assembly, proses ini lebih detail. Kita perlu membaca karakternya, mengubahnya menjadi huruf besar, dan kemudian menyimpannya di suatu tempat. 



           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.


Kode di atas tidak cukup cocok dengan semantik dari kode versi JavaScript. Perbedaan penting adalah bahwa saat ini kami menggunakan Unicode untuk bekerja dengan teks, jadi mengonversi masukan dari huruf kecil ke huruf besar seringkali lebih sulit, dan terkadang tidak mungkin (tergantung pada bahasanya). Retroputer hidup di dunia ASCII (lebih tepatnya, di dunia variasi ASCII-nya sendiri yang disebut RetSCII), yaitu, semua karakter yang didukung dikodekan dalam delapan bit. Untuk banyak bahasa, ini sama sekali tidak cukup, tetapi memenuhi kenyataan saat itu.



Ini juga berarti bahwa kita dapat menggunakan fitur ASCII yang lucu untuk mengonversi dari huruf kecil ke huruf besar. Huruf besar "A" diwakili dalam kode ASCII 65, dan huruf kecil "a" diwakili oleh kode97... Jika Anda terbiasa dengan kekuatan dua, maka Anda seharusnya memperhatikan perbedaan ini.



Jadi ternyata huruf kecil yang ditentukan dengan angka yang persis 32 lebih banyak dari jumlah huruf kecil. Jika kita tahu bahwa nilainya berada pada kisaran yang benar, kita hanya perlu mengurangi 32!



Pendekatan ini berhasil, tetapi kami hanya dapat memodifikasi sedikit. Dalam kasus Retroputer, ini tidak akan lebih cepat dari pengurangan, namun, jika tidak ada pengurangan, kita tidak perlu memperhatikan flag carry / pinjam selama perhitungan. Ternyata kita bisa menggunakan bitwise anduntuk mematikan bit di tempat nilai 32. 



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


Tapi ada satu kehalusan: tidak semuanya bisa diubah menjadi huruf besar. Misalnya, jika pengguna menambahkan string literal, maka kita perlu lebih berhati-hati, karena kita tidak ingin Retroputer BASIC terus-menerus meneriaki pengguna dengan huruf besar. (Sementara banyak komputer pada zaman itu tidak memiliki huruf kecil, Retroputer tidak.)



Misalnya: 



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


Ini berarti kita perlu melacak apakah kita berada di tengah string literal. Di BASIC, hanya ada satu sebutan untuk ini: tanda kutip ganda. Jika karakternya adalah tanda kutip ganda, kita dapat menyetel benderanya dan, bergantung pada nilai benderanya, ubah menjadi huruf besar atau biarkan apa adanya.



Ternyata JavaScript tidak memiliki fungsi bawaan untuk ini, tetapi kita dapat membuatnya sendiri: 



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


Sekarang logika di JS lebih cocok dengan versi assembler, meskipun kami sekali lagi menggunakan sedikit dukungan Unicode di JS.



Versi assembler terlihat seperti ini: 



           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.


Sejauh ini kami hanya melakukan konversi teks input menjadi huruf besar, tetapi Anda dapat menggunakan definisi string literal untuk kemungkinan lain. Kita bisa melakukan satu pemeriksaan sintaks lagi!



Jika pada akhir proses kita menemukan apa inStringyang masih benar ( bl = 0xFF), maka kita dapat mengembalikan kesalahan, karena itu berarti ada literal string yang tidak lengkap di suatu tempat dalam string.



Catatan: Ternyata banyak versi BASIC agak toleran karena kurangnya tanda kutip penutup pada string. Saya menemukan ini saat membuat penerjemah saya sendiri. Meskipun demikian, menurut saya itu tidak benar, jadi Retroputer BASIC tidak mengizinkannya.



Tokenisasi



Langkah selanjutnya dalam parsing adalah mengubah string input menjadi sesuatu yang lebih efisien untuk dijalankan oleh interpreter Retroputer BASIC. Kami mencoba sedekat mungkin dengan konsep pohon sintaks abstrak, tetapi hasilnya tetap bukan pohon. Tapi itu akan menjadi sesuatu yang bisa kita tangani dengan cepat saat runtime.



Fitur umum dari mikrokomputer awal adalah memori yang sangat terbatas. Retroputer memiliki lebih banyak memori daripada kebanyakan mesin standar pada saat itu, tetapi masih jauh lebih sedikit daripada komputer modern. Oleh karena itu, program BASIC yang lama dapat dengan mudah menggunakan terlalu banyak memori jika disimpan selama input pengguna.



Untuk menghemat ruang, kata kunci diberi token selama program masuk ke dalam memori... Proses ini mengubah kata kunci menjadi token single-byte. Kata kunci selalu memiliki panjang setidaknya dua byte, jadi ada lebih banyak penghematan saat Anda mengetik. Ini juga berarti bahwa kita dapat menggunakan tabel pencarian saat runtime untuk memanggil rutinitas bahasa assembly yang sesuai.



Namun, Retroputer BASIC melangkah lebih jauh dari kebanyakan versi BASIC saat itu. Selain itu, ia mengubah angka menjadi bentuk biner, menandai string, menghitung referensi variabel, dan banyak lagi. Sejujurnya, ini membuang lebih banyak ruang, tetapi kecepatan (dan kemudahan penerapan) manfaatnya lebih besar daripada itu.



Jadi, langkah-langkah berikut digunakan di sini:







  1. , , . , , , , .




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



    , .




  3. , , , . JavaScript, !



    ( ). , PRINT !




  4. Retroputer BASIC ( ). . , , .



    Retroputer BASIC . , . , Retroputer BASIC.


Pada postingan saya tidak akan menjelaskan secara detail tentang implementasi tahap ini dalam bahasa assembly, saya akan tinggalkan untuk kedepannya. Tapi jangan khawatir, ada banyak kode di sana .



Memeriksa sintaks saat runtime



Last but not least, pemeriksaan sintaks runtime adalah. Setelah mengubah kode menjadi bentuk tokenized, cukup mudah untuk menerapkannya.



Pertama, saat runtime, BASIC memeriksa untuk melihat apakah saat ini memproses token. Semua token memiliki bit paling signifikan yang diaktifkan (yaitu, mereka memiliki nilai 128 dan lebih tinggi). Jika token ditemukan, maka kita dapat menentukan subrutin mana yang akan dipanggil dengan mencarinya di tabel vektor . Ini juga membuat tampilan kesalahan sintaks menjadi sepele - beberapa kata kunci tidak masuk akal sebagai operator, sehingga tabel vektor hanya menunjuk ke prosedur yang menghasilkan kesalahan sintaksis.



Setelah penangan token operator dipanggil, penangan melakukan semua pekerjaan penguraian tambahan. Untuk token dan dapat menggunakan transisi antara mereka gettok, gettok-raw,peektok dll Jika token adalah sesuatu yang tidak diharapkan oleh prosedur, maka prosedur akan mengembalikan kode kesalahan. Pada tahap inilah kesalahan sintaks dan kesalahan pencocokan jenis ditangkap.



Jika operator harus mengevaluasi ekspresi tersebut, tahap penguraian lainnya dilakukan. Saat mengurai ekspresi, tabel pemeta vektor lain digunakan , yaitu, kita dapat mencegat kata kunci yang tidak terkait dengan ekspresi matematika dan mengembalikan kesalahan yang sesuai. Misalnya, jika Anda mencoba masukPRINT 2+CLS, lalu kita mendapatkan kesalahan sintaks CLS( CLS- ini adalah singkatan dari "layar kosong").



Catatan: dari tabel ini, kita juga dapat menentukan prioritas operator matematika dan jumlah parameter yang dibutuhkan. Ini penting untuk evaluasi ekspresi yang sebenarnya, tetapi juga dapat digunakan untuk menangkap kasus di mana pengguna tidak memberikan cukup argumen.



Karena token memetakan langsung ke entri tabel pemeta vektor, program dapat dijalankan dengan cukup cepat dan dengan sedikit usaha. Tugas penguraian setiap jenis operator dipercayakan kepada penangan itu sendiri, dan secara umum hal ini tidak menimbulkan masalah tertentu. Mungkin yang paling sulit diurai adalah PRINTdanINPUT, tetapi di setiap langkah, satu token diambil pada satu waktu.



Karena banyak pemeriksaan tidak dilakukan hingga program dijalankan, ini berarti bahwa kami mungkin memiliki hasil parsial sebelum kesalahan terjadi. Misalnya: 



PRINT "Hello";CLS
Hello
?Syntax Error


Selain itu, ini berarti bahwa jika program meninggalkan layar dalam keadaan di mana kita tidak dapat melihat teksnya, maka kita mungkin mengalami masalah dengan penghapusan kesalahan. Jika kesalahan sintaks ditampilkan tetapi kami tidak melihatnya, apa yang harus kami lakukan?



Cara memeriksa sintaks ini tentu memiliki kekurangan, tetapi memungkinkan penerjemah yang cukup sederhana.



Tokenisasi masukan pengguna



Seperti yang disebutkan sebelumnya, itu umum untuk versi BASIC dari era itu menggunakan taktik tokenisasi. Untuk menghemat ruang dan meningkatkan kecepatan eksekusi, kata kunci "dikompresi" menjadi token byte tunggal (atau byte ganda, jika dibutuhkan lebih banyak kata kunci).



Mari kita anggap kita memiliki baris kode sederhana yang membersihkan layar dan mencetak salam standar: 



CLS: PRINT "Hello, World"


Meskipun ini sendiri tidak memakan banyak memori, jika Anda menulis program yang panjang, banyak kata dalam program itu yang akan menjadi kata kunci. Jika Anda mengompresnya (membuat token), Anda dapat menghemat sebagian kecil ruang. Misalnya, setelah tokenisasi baris yang ditunjukkan di atas, akan ada sesuatu seperti ini di memori: 



8A E3 B5 FC Hello, World 00 00


Seharusnya tidak terlalu sulit untuk mengubahnya kembali ke konstruksi asli:



Byte Kata kunci Catatan
8A

CLS

E3 ":" Akhir konstruksi
32 "" Kami menyimpan paling banyak satu ruang
B5

MENCETAK
FB Baris dalam kode Berikutnya adalah string literal
Halo, Dunia, 00 String dihentikan nol
00 Akhir baris kode Baris kode juga dibatalkan


Anda mungkin berpikir ini banyak pekerjaan, tetapi penghematan ruang bisa signifikan. Ini tidak terlalu terlihat dalam contoh, tetapi bahkan dari situ Anda dapat membayangkan seberapa cepat ruang yang dihemat dapat terakumulasi. Dalam kasus ini, hasil terkompresi adalah 19 byte. Teks sumber terdiri dari 26 byte (termasuk penghentian byte nol).



Menghemat ruang menjadi penting ketika datang ke juru bahasa BASIC yang berjalan pada mesin dengan RAM yang sangat sedikit untuk program pengguna. Oleh karena itu, kompresi seperti itu sangat penting dan menarik, meskipun tidak memiliki manfaat tambahan.



Jadi bagaimana kita membuat token seperti ini? Pada awalnya, JavaScript tampaknya cukup sepele untuk melakukan ini. Dengan larik string, Anda dapat dengan cepat mengganti setiap kata kunci dengan token yang sesuai. Benar?



Sepertinya ini pekerjaan untuk String#replace? Dengan pendekatan yang naif, Anda dapat mencoba sesuatu seperti ini: 



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


Sayangnya, kami segera menyadari bahwa kami tidak dapat mengganti literal string dengan token. Artinya Anda perlu melakukan pemrosesan karakter demi karakter, dengan memperhatikan konteksnya, agar tidak mengompres elemen yang bukan kata kunci.



Algoritme baru ini lebih dekat dengan kode bahasa assembly di Retroputer, tetapi JS masih membuatnya lebih mudah. Ini adalah awal dari kode JS (kami akan secara bertahap mengembangkannya di posting ini): 



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


Kami mulai dengan daftar token yang sangat disederhanakan, karena tidak ada yang ingin melihat seluruh tabel dalam format ini ( panjang, dan Retroputer benar-benar membuat tabel token dari file JS! ), Tapi untuk tujuan kami ini sudah cukup. Prinsipnya di sini adalah bahwa ketika kita melihat token, kita menulis indeksnya ke larik keluaran.



Pada titik ini, kami memiliki fungsi yang, untuk saat ini, cukup mengubah string menjadi kode karakter yang setara. Meskipun tidak terlalu berguna, ini dapat berfungsi sebagai kerangka kerja yang nyaman.



Versi bahasa assembly sangat mirip dengan yang ditunjukkan di atas. 



  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


Saya belum memasukkan dalam contoh di atas _get-source-indexatau fungsi lainnya, karena tugas mereka jelas dari namanya: mereka hanya mendapatkan, mengatur indeks sumber dan target, dan juga menavigasi melalui mereka. Perlu dicatat bahwa tidak seperti JS, tidak ada array yang dialokasikan secara dinamis dalam bahasa assembly, jadi algoritme ini mengalokasikan buffer dengan ukuran yang memadai. Saat kita menavigasi baris input, kita perlu tahu di mana harus menulis token berikutnya di buffer target, dan apa yang dilakukan indeks target di atas. Masing-masing fungsi di atas mengembalikan indeks dalam Y. Misalnya, fungsi _adv-target-indexmenambah indeks target sebesar satu (setara y++).



Hati-hati dengan literal



Kita perlu berhati-hati: string literal bisa membingungkan tokenizer - kita tidak bisa begitu saja mengganti setiap string karakter yang cocok dengan kata kunci dengan nilai token. Jika kita melihat literal string yang memiliki "CLS" di dalamnya, maka kita tidak boleh mencoba membuat tokenisasi. Seharusnya tidak dapat dieksekusi, dan jika kita mengeluarkannya ... maka alih-alih kita mengeluarkan byte yang sesuai dengan token. Ini kemungkinan besar bukan yang dimaksud pengembang.



Di sisi lain, literal numerik seharusnya tidak mengalami masalah ini, karena BASIC tidak memiliki kata kunci numerik. Meski begitu, tidak ada gunanya mencari kata kunci saat dihadapkan dengan angka - mengapa membuang waktu?



Tokenisasi string literal



Jadi, pertama-tama mari kita periksa apakah garisnya dimulai - di JS, ini tidak terlalu sulit: 



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


Tanda kutip ganda diwakili oleh kode karakter 34. Bahasa pemrograman lain dapat mengenali lebih banyak gaya tanda kutip (seperti JS atau C), tetapi dengan BASIC itu sederhana: baik tanda kutip ganda, atau tidak sama sekali.



Ketika kita melihat bahwa sebuah string dimulai, kita cukup mengambil karakter yang tersisa dan menambahkan ke larik keluaran sampai kita menemukan kutipan lain.



Setelah membaca seluruh string, kita perlu menambahkan byte nol karena Retroputer BASIC menggunakan string gaya C. Jika kita ingin menggunakan string gaya Pascal, kita dapat menyimpan counter dan memasukkan panjang string literal. Bagaimanapun, ini tidak menimbulkan masalah khusus. Satu-satunya alasan saya menggunakan string yang diakhiri dengan null adalah karena string tersebut sangat mudah digunakan dalam bahasa assembly - kita hanya perlu membandingkannya dengan byte null, bukan menyimpan penghitung.



Jadi JavaScript tidak terlalu sulit. Saya rasa sebagian besar dari Anda akan memutuskan untuk menggunakan sesuatu yang lebih abstrak, seperti ekspresi reguler. Saya pikir kode ini akan membuat niat kita lebih jelas. 



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


Kode di atas kurang lebih sama, tetapi alih-alih validasi karakter-demi-karakter, kami membiarkan JS dijalankan begitu saja match. Kami tahu kami akan mendapatkan kecocokan (kami dalam satu string), jadi kami bahkan tidak perlu memeriksa apakah pertandingan itu berhasil. Kami kemudian menambah indeks dengan panjang string dan menyalin karakter ke dalam larik keluaran. Menurut pendapat saya, kode ini jauh lebih mudah dipahami (namun, ini menyiratkan pemahaman tentang ekspresi reguler, serta kekhasan sintaks ES6, misalnya, …dan fungsi panah).



Tentu saja, dalam bahasa assembly, kita harus melakukan semua pekerjaan yang dilakukan JS secara manual. Hasilnya sangat mirip dengan percobaan pertama kami dalam menulis kode 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:


Perlu menambahkan catatan tentang parser bahasa assembly Retroputer - ia memiliki dukungan dasar untuk konstruksi tingkat tinggi seperti blok dan loop. Oleh karena itu, ia if Z {…}akan mengeksekusi konten di dalam blok ketika bendera nol disetel, dan continuedapat digunakan untuk bercabang kembali ke awal blok ( breakjuga digunakan untuk keluar dari blok). Assembler menerjemahkan ini ke dalam berbagai perbandingan dan instruksi percabangan, jadi CPU tidak melihat bagian kode tingkat tinggi, tetapi membuat kode sedikit lebih mudah untuk ditulis.



Tokenizing number



Juga, tidak masuk akal untuk mencoba mencari daftar kata kunci untuk angka, jadi kita bisa melewatkannya. Sebagian besar versi BASIC melakukan sesuatu yang mirip dengan pemrosesan string yang ditunjukkan di atas - jika karakter yang dibaca adalah digit, itu akan digabungkan ke keluaran, setelah itu kompresor akan mengambil alih.



Retroputer BASIC (dan beberapa versi BASIC lainnya, seperti Atari BASIC) melangkah lebih jauh: ia mengonversi angka ke format biner yang sesuai. Sangat mudah untuk melakukan ini - jika kita bertemu dengan sebuah digit, lalu kita mengalikan akumulator dengan 10 dan menjumlahkan digit tersebut, terus berlanjut selama digit tersebut terus muncul. (Perlu dicatat, meskipun, bahwa meskipun Retroputer BASIC hanya berfungsi dengan nilai integer, menambahkan angka floating point sudah ada dalam daftar todo saya.)



(Saya harus mengatakan bahwa saat ini Retroputer BASIC tidak melakukan apa - apa ketika terjadi overflow integer, baik ditandatangani atau tidak. Ketika saya menambahkan nomor floating point, Retroputer akan mengkonversi ke floating point juga.)



Retroputer BASIC melangkah lebih jauh. : ia juga mengenali bilangan heksadesimal dan mengubahnya menjadi padanan binernya. Ini digunakan sebagai sebutan untuk angka-angka tersebut 0x(seperti di JS), dan bahasanya sendiri memiliki logika tambahan untuk memastikan bahwa kesalahan dikembalikan jika beberapa karakter ditentukan x.



Dalam bahasa assembly, memeriksa apakah suatu karakter berupa digit tidaklah sulit, tetapi memerlukan beberapa perbandingan: Anda perlu memastikan bahwa kode karakter berada di antara 0x30dan0x39... (Ini adalah kode karakter "0" dan "9".)



Setelah menerima digit-karakter, kita dapat menggunakan properti lain dari himpunan karakter. 0x30- ini adalah kode karakter "0", 0x31- kode "1", dan seterusnya. Kita bisa mengurangi jika kita mau 0x30, tetapi ada cara yang lebih sederhana: buang saja empat bit paling signifikan: 



and dl, 0b0000_1111


Sayangnya ini tidak akan berfungsi jika kita perlu menangani nomor hex. Dalam kasus ini, Anda dapat mengurangi lalu membandingkan dengan 10, lalu menguranginya lagi dengan 7 jika kode lebih besar dari 10 (mengingat bilangan heksadesimal adalah "A" - "Z" dalam huruf besar).



Di JS, Anda dapat menggunakan ekspresi reguler lagi, dan kemudian ketika kami mendapatkan kecocokan untuk nomor tersebut, Anda dapat memanggil Number(), yang memberi kami keuntungan lain: bilangan heksadesimal juga dikonversi secara sepele, karena ini Number()melakukan ini secara otomatis jika nomor diawali dengan 0x.



Bagaimana tampilannya di 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;
}


Ekspresi reguler memungkinkan Anda menggunakan kombinasi angka atau digit heksadesimal (plus xuntuk beralih ke mode heksadesimal). Ekspresi tersebut tidak ideal, misalnya, Anda dapat menggunakan beberapa x, tetapi untuk sekarang ini sudah cukup.



Dalam kode di atas, mengubah angka menjadi byte bisa dipertanyakan. Number()melakukan semua kerja keras untuk mengubah string angka menjadi angka yang dapat digunakan JavaScript, tetapi sekarang kita perlu merepresentasikannya sebagai urutan byte. Anda dapat menggunakan matematika untuk melakukan ini: 



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


... dan itu mudah dilakukan untuk integer. Namun berkat penggunaan array bertipe JS, Anda dapat menghindari semua penghitungan ini, tetapi pada saat yang sama bersiap untuk menangani bilangan floating point di masa mendatang (kami akan menggantinya Uint16Arraydengan Float64Array).



Kode bahasa assembly untuk tugas ini sedikit lebih panjang , tetapi berfungsi sedikit lebih banyak. Retroputer menggunakan satu optimasi lagi: jika angkanya kecil, maka disimpan dalam format yang lebih kecil. Ini berarti 0-255 dapat disimpan dalam satu byte, sedangkan nomor yang lebih panjang membutuhkan dua.



Cari kata kunci



Jadi kami telah melakukan cukup banyak pekerjaan, tetapi sejauh ini kami belum mengompresi satu kata kunci. Setelah berurusan dengan angka dan string literal, kita dapat yakin bahwa yang lainnya adalah kata kunci atau nama variabel. (Atau spasi, tetapi mudah untuk diperiksa.)



Dalam BASIC, kata kunci tidak selalu dimulai dengan karakter abjad; operator dan pembatas juga dianggap sebagai token. Tetapi variabel juga dimulai dengan karakter alfabet. Jadi kami tidak dapat langsung menentukan apakah kami akan mengompresi kata kunci atau variabel. Ini cocok untuk kami - jika kami tidak menemukan kecocokan dalam daftar token, kami akan menganggap bahwa ini adalah variabel.



Jadi bagaimana kita memverifikasi bahwa kata kunci potensial memang merupakan kata kunci? Jika kami menulis dalam JavaScript, kami dapat menggunakan Array#findIndex. 



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


Metode Array#findIndexiterasi atas array tokensdan kita dapat memeriksa apakah itu dimulai inStr(oleh yang sekarang idx) dengan token yang kita periksa. Bekerja dengan daftar token kami yang disederhanakan, kami akan melakukan sesuatu seperti (asumsikan bahwa inStr.substr(idx)===”PRINT”):



token .startsWith (token)? Indeks
CLS Salah 0
MENCETAK benar 1


Catatan: seperti indexOfJS, jika tidak ada yang ditemukan, kami dapatkan -1.



Jika kecocokan ditemukan, Anda dapat menyimpan indeksnya dalam array yang dikembalikan. Tetapi bagaimana kita kemudian membedakan token dari simbol? Mudah: aktifkan bit paling signifikan, yang dapat dilakukan dengan menambahkan 128 ke nilai token.



(Catatan: jika kita membutuhkan token lebih dari 128, maka untuk beberapa token kita harus menggunakan dua byte. Ini sedikit memperumit, tetapi tidak terlalu banyak. Beberapa versi BASIC melakukan ini, misalnya, di berbagai BASIC Microsoft.)



Kita sudah selesai dengan JavaScript, tetapi bagaimana kita melakukannya dalam bahasa assembly?



Ternyata hampir sama, tapi kodenya akan lebih panjang. 



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


Tidak terlalu buruk. Algoritmanya hampir sama, hanya tabel token bahasa assembly yang memiliki struktur sedikit berbeda. Ini terlihat seperti ini: 



CLS   00 80
PRINT 00 81
:     00 82


Setiap kata kunci diakhiri dengan byte nol diikuti dengan nomor token.



Namun, kami kehilangan sesuatu yang penting di sini - bagaimana perbandingan string ini dilakukan? Ada prosedur inti dari Retroputer STRCMPyang bisa kita gunakan, tapi seperti apa tampilannya? 



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
}


Saya tidak tahu tentang Anda, tapi saya mulai semakin menyukai metode String#startsWithdari JS. Ya, itu melakukan hal yang sama, tetapi kita tidak harus menulis semua logika internal!



Penanganan variabel



Kompresi kunci sekarang sudah selesai, jadi kita bisa menyelesaikannya. Tapi Retroputer BASIC mengambil langkah maju - variabel tokenisasi. Menurut saya hanya beberapa versi BASIC dari tahun 80-an dan 90-an yang melakukan ini, karena dalam kondisi memori yang terbatas dapat berbahaya. Tetapi jika ada banyak memori, maka tokenisasi variabel membantu meningkatkan kinerja.



Inilah yang dilakukan Retroputer BASIC:



  • Itu membaca hingga dua karakter pertama dari nama variabel. (Ini adalah ketidaknyamanan standar dari versi BASIC era karena kendala memori.)
  • Dari kedua karakter ini, menentukan indeks variabel. "A" adalah variabel 0, "A0" adalah variabel 53, dan seterusnya. Persamaannya cukup sederhana, tetapi itu tidak menarik minat kita sekarang.
  • BASIC . , $ BASIC . .
  • BASIC , . !


(Catatan: ketika Retroputer BASIC belajar mengalokasikan memori untuk variabel secara dinamis, kami akan mengganti indeks dengan pointer ke variabel. Item lain dalam daftar rencana!)



Hal ini membuat pencarian variabel menjadi sangat cepat pada waktu proses: kita tidak perlu mengurai nama variabel dan menghitung indeks setiap saat ketika kita bertemu variabel. Dalam siklus berkelanjutan, penghematan bisa sangat besar. Tetapi ini harus dibayar mahal: kita perlu menyimpan penunjuk dan nama variabel bersama-sama, jadi untuk setiap variabel yang kita temui, kita perlu menambahkan empat byte tambahan ke keluaran.



Terserah Anda untuk memutuskan apakah itu sepadan.



Namun, dalam JavaScript juga mudah untuk menentukan apakah sisa aliran karakter adalah variabel: 



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


Saya tidak akan menjelaskan secara rinci kode yang saat ini digunakan oleh Retroputer untuk membuat token variabel, itu terlalu bertele-tele. Kami akan kembali ke sana ketika saya menambahkan alokasi memori dinamis untuk variabel.



Tokenisasi selesai



Jika sekarang kita menguji kode kita di JS, kita mendapatkan array byte yang mirip dengan yang digunakan Retroputer BASIC secara internal: 



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, kerja keras untuk menghemat beberapa byte. Tetapi jika hanya ada beberapa kilobyte memori yang bebas, itu sepadan! Tetapi ini bukan satu - satunya keuntungan dari mengompresi teks yang dimasukkan oleh pengguna, kami juga mempercepat eksekusi program.



Untuk menjelaskan mengapa ini terjadi, kita perlu memahami bagaimana Retroputer mengeksekusi kode tersebut. Saya tidak akan membahas detailnya untuk saat ini, tetapi secara singkat, berikut ini diperlukan untuk menjalankan kode:



  • Dapatkan satu byte dari memori
  • Jika sebuah byte memiliki bit paling signifikan yang dihidupkan, maka itu adalah token, jika tidak maka itu adalah kesalahan sintaksis (atau NUL; dalam hal apa pun, di sinilah kita berakhir dengan jalur program)
  • Kami mencari penangan token dalam larik - larik ini berisi penunjuk ke fungsi itu sendiri yang memproses token
  • Kami memanggil penangan (bertanggung jawab untuk menerima argumen dan sejenisnya)
  • Kami ulangi lagi


Ini adalah alasan lain untuk membuat tokenizing kata kunci - menjalankan logika kata kunci menjadi sepele, cukup temukan alamatnya dalam array dan panggil.



Saya ingin menekankan bahwa meskipun tokenisasi penting untuk menghemat ruang, ini juga meningkatkan kecepatan eksekusi.



Misalnya, run loop JS mungkin terlihat seperti ini: 



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


Tentu saja, pada kenyataannya semuanya tidak sesederhana itu, itu lebih dari itu, tetapi ini sudah menjadi topik untuk posting lain!



Sumber daya







Periklanan



VPS bertenaga dengan perlindungan DDoS dan perangkat keras terbaru. Semua ini tentang server epik kami . Konfigurasi maksimum adalah 128 core CPU, RAM 512 GB, NVMe 4000 GB.





More articles:


All Articles