👝 🙍🏻 🗂️ Escrevendo um intérprete BASIC no estilo dos anos 80 👩🏻‍🎓 🤲🏾 🤘🏽

Há vários anos venho trabalhando em um projeto pessoal de criar (e realmente pesquisar) um "emulador falso", ou seja, um emulador escrito em JavaScript para um computador que nunca existiu. Essa máquina deveria ser um tributo aos computadores de oito e dezesseis bits das décadas de 1980 e 1990.

No entanto, adoro a complexidade: esta máquina também usou um novo conjunto de instruções. É parecido com os kits usados naquela época, mas um pouco mais fácil de trabalhar. O Retroputer nasceu . Com o passar dos anos, o emulador foi se expandindo e melhorando, mas muito provavelmente nunca estará "concluído" (afinal, este é um projeto de pesquisa pessoal).

Quando @bbcmicrobot apareceu, Eu queria criar algo semelhante para o Retroputer. Minhas habilidades de desenvolvimento de JS eram limitadas principalmente ao front-end, então essa seria uma ótima desculpa para obter alguma experiência de back-end. Só há um problema: o Retroputer só pode entender sua própria linguagem assembly. Não tem suporte BASIC ainda.

Então eu vim com a criação do intérprete BASIC no estilo dos anos 80, ou seja, totalmente em linguagem assembly, como estava escrito na época. Decidi que valia a pena compartilhar meu trabalho porque não costumamos mergulhar em áreas que estão tão distantes das abstrações usuais. Minha ferramenta do dia-a-dia (JavaScript) torna muitos aspectos triviais e às vezes até parece mágica. Compreender o nível mais baixo de processos geralmente ajuda a compreender essas abstrações.

Então vamos começar.

Características do retroputador

16 ROM (KERNEL) c 1 (scratch space)

512 , 64

16- 6516, 512 4 64

4025, ,

1125

9800

Quando eu estava escrevendo assembler para Retroputer, eu podia usar a ferramenta Pegjs muito útil. Ele fornecia uma sintaxe de assembly nativa rápida, mas infelizmente nada como isso existe para o Retroputer ASM. Ou seja, teremos que seguir o caminho mais difícil.

A análise em si é realizada em vários estágios. Uma linguagem que usa um compilador analisa o código em uma árvore de sintaxe abstrata (AST) (ou outra representação) e pode usar essa árvore para gerar o código nativo finalizado. Portanto, o programa deve estar sintaticamente correto para uma compilação bem-sucedida.

Alguns interpretadores modernos também têm esse conceito, porque geralmente é útil gerar um AST intermediário e executá-lo em vez do código-fonte.

Mas para o interpretador BASIC em uma máquina com recursos limitados, será mais eficiente analisar em vários estágios, alguns dos quais ocorrem em tempo de execução. No entanto, isso significa que os erros de sintaxe não podem ser detectados até que você execute o programa e navegue até a área do código com o erro.

A análise retroputer BASIC consiste em três estágios:

Conversão de strings
Tokenização
Verificação de sintaxe de tempo de execução

As primeiras duas etapas ocorrem quando o usuário entra no programa (ou faz o download). O último ocorre durante a execução do programa. Basicamente, os dois primeiros criam a fuselagem da aeronave, mas não garantem que ela decolará. A última etapa é um piloto de teste - esperamos que ele decole, mas não temos certeza sobre isso até que ele tente.

Observação: o código-fonte do Retroputer BASIC (em desenvolvimento) está disponível no GitHub .

Conversão de strings

Esta é a parte mais simples de todo o processo. A string inserida pelo usuário é convertida em maiúsculas para simplificar (e acelerar) os processos subsequentes. O BASIC não faz distinção entre maiúsculas e minúsculas, então podemos tirar vantagem disso.

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

É muito fácil fazer isso em JavaScript, certo?

theLine = theLine.toUpperCase();

Mas em linguagem assembly, esse processo é mais detalhado. Precisamos ler o caractere, convertê-lo em maiúsculas e armazená-lo em algum lugar.

           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.

O código acima não corresponde exatamente à semântica da versão JavaScript do código. Uma diferença importante é que hoje usamos Unicode para trabalhar com texto, portanto, converter a entrada de minúsculas em maiúsculas pode ser mais difícil e às vezes impossível (depende do idioma). O Retroputer vive no mundo ASCII (mais precisamente, no mundo de sua própria variação ASCII chamada RetSCII), ou seja, todos os caracteres suportados são codificados em oito bits. Para muitos idiomas, isso é completamente insuficiente, mas vai ao encontro da realidade da época.

Isso também significa que podemos usar um recurso ASCII atraente para converter de minúsculas para maiúsculas. O "A" maiúsculo é representado no código ASCII 65, e o "a" minúsculo é representado pelo código97... Se você está familiarizado com as potências de dois, deve ter notado essa diferença.

Portanto, verifica-se que as letras minúsculas são especificadas por um número que é exatamente 32 a mais que o número de letras minúsculas. Se sabemos que o valor está na faixa correta, só precisamos subtrair 32!

Essa abordagem funciona, mas podemos apenas modificar um pouco os bits. No caso do Retroputer, não será mais rápido do que a subtração, porém, na ausência de subtração, não teremos que prestar atenção ao sinalizador de transporte / empréstimo durante os cálculos. Acontece que podemos usar bit anda bit para desligar o bit no valor 32.

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

Mas há uma sutileza: nem tudo pode ser convertido em maiúsculas. Por exemplo, se o usuário adicionou uma string literal, então precisamos ser mais cuidadosos, porque não queremos que o Retroputer BASIC grite constantemente com o usuário com maiúsculas. (Embora muitos computadores da época não tivessem letras minúsculas, o Retroputer não tinha.)

Por exemplo:

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

Isso significa que precisamos controlar se estamos no meio de um literal de string. No BASIC, há apenas uma designação para isso: aspas duplas. Se o caractere for uma aspa dupla, podemos definir o sinalizador e, dependendo do valor do sinalizador, converter para maiúsculas ou deixar como está.

Acontece que JavaScript não tem funcionalidade integrada para isso, mas podemos criá-lo nós mesmos:

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

Agora, a lógica em JS corresponde mais de perto à versão do montador, embora façamos um pouco de uso do suporte Unicode em JS.

A versão do assembler se parece com isto:

           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.

Até agora, só fizemos a conversão do texto de entrada para maiúsculas, mas você pode usar a definição de um literal de string para outra possibilidade. Podemos fazer mais uma verificação de sintaxe!

Se no final do processo descobrirmos o que inStringainda é verdadeiro ( bl = 0xFF), podemos retornar um erro, porque isso significa que há uma string literal incompleta em algum lugar da string.

Nota: Acontece que muitas versões do BASIC são bastante tolerantes com a falta de aspas finais nas strings. Eu descobri isso ao criar meu próprio intérprete. Mesmo que seja, não parece certo para mim, então Retroputer BASIC não permite.

Tokenização

A próxima etapa da análise é transformar a string de entrada em algo mais eficiente para ser executado pelo interpretador Retroputer BASIC. Estamos tentando chegar o mais perto possível do conceito de uma árvore de sintaxe abstrata, mas o resultado ainda não será uma árvore. Mas será algo que podemos controlar rapidamente em tempo de execução.

Uma característica comum dos primeiros microcomputadores era a memória muito limitada. O Retroputer tem mais memória do que a maioria das máquinas padrão da época, mas ainda muito menos do que os computadores modernos. Portanto, programas BASIC longos podem facilmente ocupar muita memória se forem salvos durante a entrada do usuário.

Para economizar espaço, as palavras-chave são transformadas em tokens durante a entrada do programa na memória... Este processo converte palavras-chave em tokens de byte único. As palavras-chave têm sempre pelo menos dois bytes de comprimento, portanto, há mais economia à medida que você digita. Também significa que podemos usar a tabela de pesquisa em tempo de execução para chamar as rotinas de linguagem de montagem apropriadas.

No entanto, Retroputer BASIC foi um pouco mais longe do que a maioria das versões BASIC da época. Além disso, ele converte números em forma binária, marca strings, calcula referências de variáveis e muito mais. Para ser honesto, isso está desperdiçando mais espaço, mas os benefícios de velocidade (e facilidade de implementação) superam isso.

Portanto, as seguintes etapas são usadas aqui:

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

, .
, , , . JavaScript, !

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

Retroputer BASIC . , . , Retroputer BASIC.

No post não entrarei em detalhes sobre a implementação dessa etapa em linguagem assembly, deixarei para o futuro. Mas não se preocupe, há muito código aí .

Verificando a sintaxe em tempo de execução

Por último, mas não menos importante, a verificação de sintaxe do tempo de execução é. Depois de converter o código para a forma tokenizada, é muito fácil implementá-lo.

Primeiro, em tempo de execução, o BASIC verifica se está processando um token no momento. Todos os tokens têm o bit mais significativo ativado (ou seja, eles têm um valor de 128 e superior). Se um token for encontrado, podemos determinar qual sub-rotina chamar, encontrando-a na tabela de vetores . Também torna trivial exibir erros de sintaxe - algumas palavras-chave não fazem sentido como operadores, então a tabela de vetores simplesmente aponta para o procedimento que gera o erro de sintaxe.

Depois que o manipulador de token do operador é chamado, ele assume todo o trabalho de análise adicional. Por fichas e pode usar a transição entre eles gettok, gettok-raw,peektok etc. Se o token não for esperado pelo procedimento, o procedimento simplesmente retornará um código de erro. É nesse estágio que os erros de sintaxe e os erros de correspondência de tipo são detectados.

Se o operador deve avaliar a expressão, então outro estágio de análise é executado. Ao analisar uma expressão, outra tabela de pesquisa vetorial é usada , ou seja, podemos interceptar palavras-chave que não estão relacionadas a uma expressão matemática e retornar os erros correspondentes. Por exemplo, se você tentar inserirPRINT 2+CLS, então obteremos um erro de sintaxe em CLS( CLS- esta é a abreviação para "limpar tela").

Nota: a partir desta tabela, também podemos determinar a prioridade dos operadores matemáticos e o número de parâmetros necessários. Isso é importante para a avaliação real da expressão, mas também pode ser usado para capturar casos em que o usuário não forneceu argumentos suficientes.

Como o token é mapeado diretamente para a entrada da tabela de pesquisa de vetor, o programa pode ser executado com bastante rapidez e esforço mínimo. A tarefa de analisar cada tipo de operador é confiada ao próprio manipulador e, em geral, isso não causa problemas específicos. Provavelmente, os mais difíceis de analisar são PRINTeINPUT, mas em cada etapa, um token é obtido por vez.

Como muitas das verificações não são realizadas até o tempo de execução do programa, isso significa que podemos ter resultados parciais antes que o erro ocorra. Por exemplo:

PRINT "Hello";CLS
Hello
?Syntax Error

Além disso, isso significa que se o programa sair da tela em um estado em que não possamos ver o texto, poderemos ter problemas com a eliminação de erros. Se um erro de sintaxe for exibido, mas não o virmos, o que devemos fazer?

Essa forma de verificar a sintaxe certamente tem suas desvantagens, mas permite um interpretador bastante simples.

Tokenizando a entrada do usuário

Conforme mencionado anteriormente, era comum que as versões do BASIC daquela época usassem táticas de tokenização. Para economizar espaço e aumentar a velocidade de execução, as palavras-chave foram "compactadas" em tokens de byte único (ou byte duplo, se mais palavras-chave forem necessárias).

Vamos fingir que temos uma linha de código simples que limpa a tela e imprime uma saudação padrão:

CLS: PRINT "Hello, World"

Embora isso por si só não ocupe muita memória, se você escrever um programa longo, muitas palavras nesse programa serão palavras-chave. Se você compactá-los (tokenizar), poderá salvar uma fração sólida do espaço. Por exemplo, após a tokenização da linha mostrada acima, haverá algo assim na memória:

8A E3 B5 FC Hello, World 00 00

Não deve ser muito difícil convertê-lo de volta à construção original:

Byte	Palavra-chave	Notas
8A	CLS
E3	":"	Fim da construção
32	""	Nós armazenamos no máximo um espaço
B5	IMPRESSÃO
FB	Linha no código	Em seguida, vem o literal de string
Olá, mundo, 00		Strings são terminados em null
00	Fim da linha de código	Linhas de código também têm terminação nula

Você pode achar que isso dá muito trabalho, mas a economia de espaço pode ser significativa. Isso não é particularmente notável no exemplo, mas mesmo a partir dele você pode imaginar a rapidez com que o espaço economizado pode se acumular. Nesse caso, o resultado compactado é 19 bytes. O texto de origem consiste em 26 bytes (incluindo o byte nulo de terminação).

Economizar espaço se torna importante quando se trata do interpretador BASIC rodando em uma máquina com muito pouca RAM para programas do usuário. Portanto, essa compressão é muito importante e atrativa, mesmo que não tenha benefícios adicionais.

Então, como simbolizamos algo assim? A princípio, parece que JavaScript é bem trivial para fazer isso. Com uma matriz de strings, você pode substituir rapidamente cada palavra-chave pelo token correspondente. Verdade?

Parece que isso é um trabalho para String#replace? Com uma abordagem ingênua, você pode tentar algo assim:

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

Infelizmente, logo percebemos que não podemos substituir literais de string por tokens. Isso significa que você precisa fazer o processamento caractere por caractere, levando em consideração o contexto, para não comprimir elementos que não sejam palavras-chave.

Esse novo algoritmo está mais próximo do código da linguagem assembly no Retroputer, mas o JS ainda torna as coisas muito mais fáceis. Aqui está o início do código JS (vamos expandi-lo gradualmente nesta postagem):

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

Começamos com uma lista muito simplificada de tokens, porque ninguém quer ver a tabela inteira neste formato ( é longo, e o Retroputer na verdade cria tabelas de tokens a partir de um arquivo JS! ), Mas para nossos propósitos isso será suficiente. O princípio aqui é que, quando vemos um token, escrevemos seu índice no array de saída.

Neste ponto, temos uma função que, por enquanto, simplesmente converte a string em seus códigos de caracteres equivalentes. Embora não seja particularmente útil, pode servir como uma estrutura conveniente.

A versão em assembly é bastante semelhante à mostrada acima.

  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

Não incluí no exemplo acima _get-source-indexou em outras funções, porque suas tarefas são claras a partir do nome: eles simplesmente obtêm, definem os índices de origem e destino e também navegam por eles. É importante notar que, ao contrário do JS, não há arrays alocados dinamicamente na linguagem assembly, portanto, esse algoritmo aloca um buffer de tamanho suficiente. Conforme avançamos na linha de entrada, precisamos saber onde escrever o próximo token no buffer de destino e o que o índice de destino está fazendo acima. Cada uma das funções acima retorna um índice em Y. Por exemplo, a função _adv-target-indexincrementa o índice de destino em um (equivalente y++).

Cuidado com os literais

Precisamos ter cuidado: literais de string podem ser confusos para o tokenizer - não podemos simplesmente substituir cada string de caractere que corresponde a uma palavra-chave por um valor de token. Se virmos um literal de string com "CLS", não devemos tentar tokenizá-lo. Ele não deve ser executável e, se o enviarmos ... então, em vez dele, exibiremos o byte correspondente ao token. Provavelmente, não foi isso que o desenvolvedor quis dizer.

Por outro lado, literais numéricos não deveriam ter esse problema, porque BASIC não possui palavras-chave numéricas. Mesmo assim, não adianta procurar uma palavra-chave quando se depara com um número - por que perder tempo?

Literais de string de tokenização

Então, vamos primeiro verificar se a linha começa - em JS, isso não é particularmente difícil:

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

As aspas duplas são representadas pelo código de caractere 34. Outras linguagens de programação podem reconhecer muito mais estilos de aspas (como JS ou C), mas com BASIC é simples: aspas duplas ou nada.

Quando vemos que uma string começa, podemos simplesmente pegar os caracteres restantes e adicioná-los ao array de saída até encontrar outra citação.

Depois de ler a string inteira, precisamos adicionar um byte zero porque o Retroputer BASIC usa strings no estilo C. Se quiséssemos usar strings no estilo Pascal, poderíamos armazenar um contador e inserir o comprimento do literal da string. Em qualquer caso, isso não representa nenhum problema particular. O único motivo pelo qual usei strings terminadas em nulo é porque elas são muito fáceis de trabalhar em linguagem assembly - só precisamos comparar com um byte nulo, não armazenar um contador.

Portanto, o JavaScript não era particularmente difícil. Acho que a maioria de vocês decidiria usar algo mais abstrato, como uma expressão regular. Acho que este código tornará nossas intenções mais óbvias.

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

O código acima é praticamente o mesmo, mas em vez da validação caractere por caractere, deixamos o JS apenas executar match. Sabemos que obteremos uma correspondência (estamos em uma string), então nem precisamos verificar se a correspondência foi bem-sucedida. Em seguida, incrementamos o índice pelo comprimento da string e copiamos os caracteres no array de saída. Na minha opinião, este código é muito mais fácil de entender (no entanto, implica no entendimento de expressões regulares, bem como das peculiaridades da sintaxe ES6, por exemplo, …e das funções de seta).

Claro, em linguagem assembly, temos que fazer manualmente todo o trabalho que JS faz. O resultado é muito semelhante à nossa primeira tentativa de escrever código 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:

Vale a pena adicionar uma observação sobre o analisador de linguagem assembly Retroputer - ele tem suporte básico para construções de alto nível, como blocos e loops. Portanto, ele if Z {…}executará o conteúdo dentro do bloco quando o sinalizador zero for definido e continuepode ser usado para desviar para o início do bloco ( breaktambém usado para sair do bloco). O assembler traduz isso em várias instruções de comparação e ramificação, de forma que a CPU não veja as partes de alto nível do código, mas torna o código um pouco mais fácil de escrever.

Números de tokenização

Além disso, não faz sentido tentar pesquisar números na lista de palavras-chave, portanto, podemos simplesmente ignorá-los. A maioria das versões do BASIC faz algo semelhante à manipulação de string mostrada acima - se o caractere lido for um dígito, ele será concatenado à saída, após o qual o compressor assumirá o controle.

Retroputer BASIC (e algumas outras versões do BASIC, como Atari BASIC) vai um passo adiante: ele converte um número para o formato binário apropriado. Isso é muito fácil de fazer - se encontrarmos um dígito, então multiplicamos o acumulador por 10 e adicionamos o dígito, continuando dessa forma enquanto os dígitos continuarem a ocorrer. (É importante notar, porém, que embora o Retroputer BASIC funcione apenas com valores inteiros, adicionar números de ponto flutuante já está na minha lista de tarefas.)

(Devo dizer que atualmente o Retroputer BASIC não faz nada quando ocorre um estouro de inteiro, seja com ou sem sinal. Quando eu adiciono números de ponto flutuante, o Retroputer irá converter para ponto flutuante também.) O

Retroputer BASIC vai um passo adiante. : também reconhece números hexadecimais e os converte em seus equivalentes binários. É usado como uma designação para esses números 0x(como em JS), e a própria linguagem tem uma lógica adicional para garantir que um erro seja retornado se vários caracteres forem especificados x.

Em linguagem assembly, verificar se um caractere é um dígito não é tão difícil, mas requer algumas comparações: você precisa ter certeza de que o código do caractere está entre 0x30e0x39... (Estes são códigos de caracteres "0" e "9".)

Tendo recebido um dígito de caractere, podemos usar outra propriedade conveniente do conjunto de caracteres. 0x30- este é o código de caractere "0", 0x31- o código "1" e assim por diante. Poderíamos subtrair se quiséssemos 0x30, mas há uma maneira mais simples: basta descartar os quatro bits mais significativos:

and dl, 0b0000_1111

Infelizmente, isso não funcionará se precisarmos lidar com números hexadecimais. Nesse caso, você pode subtrair e comparar com 10 e, em seguida, diminuí-lo em 7 novamente se o código for maior que 10 (dado que os números hexadecimais são "A" - "Z" em maiúsculas).

Em JS, você pode usar expressões regulares novamente, e então quando temos um jogo para o número, você pode chamar Number(), que nos dá uma outra vantagem: números hexadecimais também são convertidos trivialmente, porque ele Number()faz isso automaticamente se o número começa com 0x.

Como fica em 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;
}

A expressão regular permite que você use qualquer combinação de números ou dígitos hexadecimais (mais xpara mudar para o modo hexadecimal). A expressão não é ideal, por exemplo, permite usar vários x, mas por enquanto é o suficiente.

No código acima, a conversão de números em bytes pode ser questionável. Number()fez todo o trabalho árduo de transformar uma string de números em um número com o qual o JavaScript possa trabalhar, mas agora precisamos representá-lo como uma sequência de bytes. Você pode usar a matemática para fazer isso:

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

... e é fácil de fazer para um número inteiro. Mas, graças ao uso de matrizes digitadas em JS, você pode evitar todos esses cálculos, mas ao mesmo tempo se preparar para lidar com números de ponto flutuante no futuro (iremos simplesmente substituir Uint16Arraypor Float64Array).

O código da linguagem assembly para esta tarefa é um pouco mais longo , mas faz um pouco mais. O Retroputer usa mais uma otimização: se o número for pequeno, ele é salvo em um formato menor. Isso significa que 0-255 pode ser armazenado em um byte, enquanto números mais longos ocupam dois.

Pesquisar palavras-chave

Então, nós trabalhamos bastante, mas até agora não comprimimos uma única palavra-chave. Tendo lidado com números e literais de string, podemos ter certeza de que todo o resto é uma palavra-chave ou um nome de variável. (Ou um espaço, mas isso é fácil de verificar.)

No BASIC, as palavras-chave nem sempre começam com um caractere alfabético; operadores e delimitadores também são considerados tokens. Mas as variáveis também começam com um caractere alfabético. Portanto, não podemos determinar imediatamente se vamos compactar uma palavra-chave ou uma variável. Isso nos convém - se não encontrarmos uma correspondência na lista de tokens, assumiremos que se trata de uma variável.

Então, como verificamos se uma palavra-chave potencial é realmente uma palavra-chave? Se estivéssemos escrevendo em JavaScript, poderíamos usar o Array#findIndex.

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

O método Array#findIndexitera sobre o array tokense podemos verificar se ele começa inStr(pelo atual idx) com o token que estamos verificando. Trabalhando com nossa lista simplificada de tokens, faremos algo como (suponha que inStr.substr(idx)===”PRINT”):

símbolo	.startsWith (token)?	Índice
CLS	falso	0
IMPRESSÃO	verdade	1

Nota: como indexOfcom JS, se nada for encontrado, obtemos -1.

Se uma correspondência for encontrada, você pode armazenar seu índice na matriz retornada. Mas como podemos distinguir posteriormente um token de um símbolo? Fácil: ative o bit mais significativo, o que pode ser feito adicionando 128 ao valor do token.

(Observação: se precisarmos de mais tokens do que 128, para alguns tokens teremos que usar dois bytes. Isso complica um pouco as coisas, mas não tanto. Algumas versões do BASIC fazem isso, por exemplo, vários BASICs da Microsoft.)

Concluímos o trabalho em JavaScript, mas como fazemos isso em linguagem assembly?

Acontece que é quase o mesmo, mas o código será muito mais longo.

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

Bem, não parece tão ruim. O algoritmo é quase o mesmo, apenas a tabela de tokens da linguagem assembly é estruturada de maneira ligeiramente diferente. É mais ou menos assim:

CLS   00 80
PRINT 00 81
:     00 82

Cada palavra-chave é encerrada com um byte nulo seguido por um número de token.

No entanto, estamos perdendo algo importante aqui - como essa comparação de strings é feita? Existe um procedimento no núcleo do Retroputer STRCMPque podemos usar, mas como ele se parece?

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
}

Não sei sobre você, mas estou começando a amar o método String#startsWithdo JS cada vez mais . Sim, faz a mesma coisa, mas não temos que escrever toda a lógica interna!

Manipulação de variável

A compressão da chave agora está completa, então podemos terminar. Mas o Retroputer BASIC dá outro passo à frente - tokenizando variáveis. Parece-me que apenas algumas versões do BASIC dos anos 80 e 90 o fizeram, porque em condições de memória limitada pode ser prejudicial. Mas se houver muita memória, a tokenização de variáveis ajuda a melhorar o desempenho.

Aqui está o que Retroputer BASIC faz:

Ele lê até os dois primeiros caracteres do nome da variável. (Este era um inconveniente padrão das versões BASIC da época devido às restrições de memória.)
A partir desses dois caracteres, ele determina o índice da variável. "A" é a variável 0, "A0" é a variável 53 e assim por diante. A equação é muito simples, mas não nos interessa agora.
BASIC . , $ BASIC . .
BASIC , . !

(Observação: quando o Retroputer BASIC aprende a alocar memória dinamicamente para variáveis, substituiremos o índice por um ponteiro para uma variável. Outro item na lista de tarefas!)

Isso torna a localização de variáveis incrivelmente rápida em tempo de execução: não temos que analisar o nome da variável e calcular o índice todas as vezes quando encontramos uma variável. Em ciclos contínuos, a economia pode ser substancial. Mas isso tem um custo alto: precisamos armazenar o ponteiro e o nome da variável juntos, portanto, para cada variável que encontrarmos, precisamos adicionar quatro bytes extras à saída.

Cabe a você decidir se vale a pena.

Seja como for, em JavaScript também é fácil determinar se o restante do fluxo de caracteres é uma variável:

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

Não vou descrever em detalhes o código que o Retroputer usa atualmente para tokenizar variáveis, é muito prolixo. Voltaremos a ele quando adicionar a alocação de memória dinâmica para variáveis.

Tokenização concluída

Se agora testarmos nosso código em JS, obteremos uma matriz de bytes semelhante àquela que o Retroputer BASIC usa internamente:

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

Uau, que trabalho demais para economizar alguns bytes. Mas quando há apenas alguns kilobytes de memória livre, vale a pena! Mas esta não é a única vantagem de comprimir o texto digitado pelo usuário, também agilizamos a execução do programa.

Para explicar por que isso acontece, precisamos entender como o Retroputer executa o código. Não vou entrar em detalhes por agora, mas em poucas palavras, o seguinte é necessário para executar o código:

Pegue um byte da memória
Se o byte tem o bit mais significativo ativado, então este é um token, caso contrário, é um erro de sintaxe (ou NUL; em qualquer caso, é aqui que terminamos de trabalhar com a linha do programa)
Estamos procurando um manipulador de token em uma matriz - esta matriz contém ponteiros para as próprias funções que processam o token
Chamamos o manipulador (é responsável por receber argumentos e similares)
Repetimos tudo de novo

Este é outro motivo para tokenizar palavras-chave - executar a lógica da palavra-chave torna-se trivial, basta encontrar o endereço em uma matriz e chamá-lo.

Gostaria de enfatizar que, embora a tokenização seja importante para economizar espaço, ela também melhora a velocidade de execução.

Por exemplo, um loop de execução JS pode ser parecido com isto:

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

Claro que na realidade nem tudo é tão simples, é muito mais, mas isso já é assunto para outro post!

Recursos

O código JavaScript completo para esta postagem
Código-fonte Retroputer (atualmente em desenvolvimento)
Lista de recursos usados para este projeto

Escrevendo um intérprete BASIC no estilo dos anos 80

Características do retroputador