构建80年代风格的BASIC解释器，第2部分
如果您还记得本系列的第1部分，我们实际上只深入研究了Retroputer Basic的第一阶段解析-即将输入的行转换为大写并检查引号是否正确匹配。(注意：应该指出的是，我们也可以在那里进行额外的检查-比如匹配圆括号，但我们目前不这样做。)。
我还提到，我想要解决的问题是，今天我们对非常有限的标准库(尤其是与JavaScript相关的库)有多么想当然。这里描述的没有什么是神奇的，但有时我们认为我们的工具是理所当然的，我发现了解引擎盖背后发生的事情是很有用的。
正如在上一篇文章中提到的，那个时代的基础人物常用的一种策略是标记化。为了节省空间和提高执行速度，关键字被“压缩”成单字节令牌(如果需要更多关键字，也可以是两个字节)。
假设您有一行简单的代码来清除屏幕并打印现在常见的问候语，如下所示。
虽然这本身并不占用大量内存，但如果您编写一个很长的程序，那么该程序中的很多单词都将是关键字。如果我们将它们压缩(标记化)，我们可以节省相当大的空间。例如，在标记化上面的行之后，您将在内存中看到更多类似于以下内容的内容：
这并不需要太多的努力就可以将其映射回我们最初的声明：
这可能看起来工作量很大，但节省的空间可能会很大。这在这里不是很多，但即便如此，您应该能够想象它是如何迅速积累起来的。在本例中，我们的压缩结果是19个字节。原始文本为26字节(算上终止NUL)。
如果您是在RAM非常有限的机器上运行的基本解释器，那么节省一些空间就很重要。一些基本的应用程序只有不到1千字节的RAM用于用户程序，因此这种处理确实非常重要，即使它没有带来额外的好处，也会很有吸引力。
好的-那么我们怎么才能把这样的东西标记化呢？起初，它在JavaScript中似乎相当微不足道。在给定字符串数组的情况下，您可以轻松地将每个关键字快速替换为相应的标记。对吗？
Const tokens=["；cls"；，"；print"；，"；："；]；函数tokenize(InStr){const newStr=inStr；tokens.forEach((Token，idx)=>；newStr=newStr.place(new RegExp(Token，"；g"；)，String.fromCharCode(128+idx))。
不幸的是，当您意识到我们不能着手替换字符串文字中的标记时，这一切都会崩溃。这意味着我们需要一个字符一个字符地处理，记住上下文，以避免处理实际上不是关键字的东西。
这个新算法与Retroputer中的汇编语言代码更加匹配-但是JS仍然使事情变得容易得多。下面是该JS代码的开始部分(我们将在整个帖子中填充它)：
Const toens=["；cls"；，"；print"；，"；："；]；函数tokenize(InStr){let out=[]；//返回值为"；crunked"；array let idx=0；//索引到inStr let ch="；"；//当前字符同时(idx<；inStr.length){ch=inStr.length。//获取当前字符编码//我们的逻辑将转到这里。push(Ch)；//现在按下字符idx++；//继续(Next Char)}out。ush(0)；//我们以NUL Return Out结束；}。
我们从一个非常简单的令牌列表开始，因为没有人希望看到这种格式的整个表(它很长，Retroputer实际上是从一个JS文件构建其令牌表！)，但是对于我们这里的目的来说，这应该已经足够了。这里的想法是，当我们看到令牌时，我们将在输出数组中记录它的索引。
此时，我们有一个函数，目前仅将字符串转换为其等效的字符代码。在这一点上，它没有多大用处，但可以作为有用的脚手架。
Do{call_get-source-index#get next character index(In Y)dl：=<；bp+source>；，y#从我们的源字符串(Ch)中读取下一个字符call_adv-source-index#前进我们的源索引call_get-target-index#获取目标中的位置("；out"；在JS中)<；bp+target>；，y：=dl#store to target(out[y]=ch)call_adv-。如果是，则中断}While！Z
我没有包括GET-SOURCE-INDEX或上面的其他函数，因为它们按照它们在TIN上说的做，只是获取、设置或推进我们的源索引和目标索引。值得注意的是，与JS不同的是，我们没有用汇编语言动态分配数组，因此该算法预先分配了一个合理大小的缓冲区。当我们遍历输入字符串时，我们必须知道将下一个令牌写入目标缓冲区的位置，这就是上面的目标索引正在做的事情。上面调用的每个函数都以y为单位返回索引。例如，_adv-target-index函数将目标索引前进一(相当于y++)。
我们应该注意的一件事是，字符串文字可能会混淆我们的记号赋值器-我们不能简单地将匹配关键字的每个字符串替换为记号的值。如果我们看到一个带有“cls”的字符串，我们不应该尝试对其进行标记化。它不应该是可执行的，如果我们将其打印为…。那么，我们将打印与令牌相对应的字节。不太可能是开发商想要的。
另一方面，数字文字应该不会有同样的问题，因为Basic没有任何数字作为关键字。即便如此，如果我们查看的是一个数字，那么进行关键字搜索是没有意义的--为什么要浪费时间呢？
因此，首先，让我们检查一下是否正在启动一个字符串-这在JS中并不太难做到：
If(ch=34){out.ush(0xFB)；//代码中的字符串令牌idx++；ch=inStr.charCodeAt(Idx)；//获取引号后的下一个字符，同时(ch！==34&；&；idx<；inStr.length){out.ush(Ch)；idx++；ch=inStr.charCodeAt(Idx)；}；idx++；//跳过引号。
双引号表示为字符代码34。其他编程语言可以识别更多的引号样式(如JS或C)，但是BASIC在这里很简单：双引号或断号。
一旦我们看到开始了一个字符串，我们可以简单地使用剩余的字符并将它们添加到我们的返回数组中，直到我们看到另一个引号。
当我们读入整个字符串时，我们需要添加一个NUL字节，因为Retroputer Basic使用C样式的字符串。如果我们想使用Pascal样式的字符串，我们可以维护一个计数器，并确保插入字符串文字的长度。不管怎样，都没什么大不了的。我使用NUL结尾字符串的唯一原因是因为这在汇编语言中非常容易处理，因为我们可以只与NUL字节进行比较，而不需要维护计数器。
好的，所以JavaScript并不太难。我认为，我们中的大多数人都会追求一些更抽象的东西，比如正则表达式。我认为，这让意图变得更明显了。
If(ch=34){out.ush(0xFB)；//代码中的字符串令牌Const字符串文字量=inStr.substr(idx+1).Match(/^[^"；]*/)[0]；idx+=字符串文字量.length+1；out.ush(...Array.from(字符串文字量，ch=>；ch.charCodeAt(0)；idx++；//跳过引号。
上面做的是非常相似的事情--但是我们不必逐个字符地检查字符，而是让JS用Match来做这件事。我们知道我们会得到一个匹配(我们是在一个字符串中)，所以我们甚至不需要费心检查我们是否得到了一个成功的匹配。然后，我们只需增加超过字符串长度的索引，并将字符复制到返回数组中。无论如何，对我来说，这要容易得多(但前提是您理解正则表达式以及一些ES6语法，如…。和箭头功能)。
当然，在汇编语言中，我们必须完成JS为我们所做的工作。这将产生与我们第一次JS尝试非常相似的结果：
Cmp dl，constants.QUOTE#dl是引号吗？Brs！z not-a-string#nope；not a string call_get-target-index#get next position in crash target dl：=brodata.TOK_code_string#"；string"；Token<；bp+target>；，y：=dl#将其存储到压缩目标call_adv-target-index-a-string：call_get-source-index dl：=<；bp+source>；，y#。如果Z{dl：=0}call_get-target-index<；bp+target>；，y：=dl#写入目标call_adv-target-index CMP dl，0#我们完成了吗？BRS！Z仍然是字符串#否，继续前进#下一步！不是字符串：
关于Retroputer的汇编语言解析器需要注意的一点是，它对更高级别的构造有一些非常基本的支持，比如块和循环。因此，如果Z{…。如果设置了零标志，}将执行块内的内容，并且Continue可用于分支回到块的顶部(Break也可用于退出块)。汇编程序会将其转换为各种比较和分支指令，因此CPU看不到任何高级位。但是它使编写代码变得更容易一些。
在我们的关键字列表中搜索我们的数字也是没有意义的，所以我们不妨跳过这些数字。大多数基本操作都会做一些与上面的字符串例程非常类似的事情-只要它读取的字符是一个数字，它就会连接到输出，然后处理程序就会继续进行。
Retroputer Basic(以及其他一些基础知识，如Atari Basic)更进一步：它将数字转换成相应的二进制格式。这非常容易做到-如果您看到一个数字，将累加器乘以10，然后将该数字相加，只要您看到一个数字，就重复这个过程。(然而，我应该注意到，Retroputer BASIC目前是一个仅限整数的事务。不过，添加浮点在待办事项列表上。)
(我应该注意到，Retroputer Basic当前在整数溢出(带符号或其他)方面没有任何作用。一旦我添加了浮点，Retroputer将改为转换为浮点表示。)。
Retroputer Basic还更进一步：它还将识别十六进制数字，并将它们转换为等价的二进制数字。它使用0x(就像JS一样)作为能指，并且有一些额外的逻辑来确保指定多个x字符被认为是错误的。
在汇编语言中，检查字符是否是数字并不难，但有点冗长，需要进行两次比较，以确定字符代码是否在0x30和0x39之间。(这些分别是“0”和“9”的字符代码。)。
一旦我们有了数字字符，我们就可以利用字符集的另一个精妙之处。0x30是“0”的字符代码，0x31是“1”的代码，依此类推。如果愿意，我们可以减去0x30，但我们有一个更简单的方法：只需去掉前四位：
不幸的是，如果我们需要处理十六进制数，则这不起作用。为此，我们可以减去，然后与10进行比较，如果大于10，则再次向下调整7(假设十六进制数字为大写“A”-“Z”)。
在JS中，我们可以再次使用正则表达式来查看是否正在查找一个数字，然后一旦有了匹配的数字，我们就可以调用number()，这也给我们带来了另一个好处：十六进制数的转换也很简单，因为如果数字以0x开头，number()会自动转换十六进制数。
If(ch&>；=48；&；&；ch<；=57){out.ush(0xFD)；//Number Token Const NumericalStr=inStr.substr(idx).match(/^[\d|A-F|a-f|x|X]+/)[0]；idx+=NumerWritalStr.Length；Const NumerWrital=Number(Number WritalStr)；Const Bytes=new Uint8Array(new Uint16Array([Numerical Writal]).Buffer)；out.Push(...Bytes)Continue；}。
正则表达式允许数字或十六进制数字的任意组合(加上x以进入十六进制模式)。这个表达式并不完美-例如，它将允许多个X，但就目前而言，它已经足够好了。
上述内容中令人惊讶的一点是将数字转换为字节。Number()完成了将数字字符串转换为JavaScript可以处理的数字的艰苦工作，但现在我们需要将其表示为一系列字节。我们可以使用一些数学运算来进行转换：
…。对于整数来说，这很容易做到。但是通过使用JS的类型化数组，我们可以跳过数学运算，并且还可以设置自己在将来处理浮点数(我们只需将Uint16Array替换为Float64Array。
实现这一点的汇编语言代码稍长一些，但它也需要做更多的工作。Retroputer进行了另一种优化：如果数字很小，则以较小的格式存储。这意味着0-255可以存储在一个字节中，而较大的数字会占用两个字节。
好的，我们已经做了很多工作，但是我们还没有找到一个关键字。嗯，去掉了数字和字符串，我们可以非常确定我们看到的不是关键字就是变量名。(它也可以是一个空格，但这很容易检查。)。
在BASIC中，关键字并不总是以字母字符开头-操作符和分隔符也算作标记。但变量也以字母字符开头。所以我们不能马上知道我们要处理的是一个关键字还是一个变量。没关系-如果我们在令牌列表中找不到匹配项，我们可以假定它是一个变量。
那么，我们如何实际检查我们的潜在关键字是否真的是一个关键字呢？如果我们在编写JavaScript，我们可能会使用Array#findIndex方法。
Const tokenMatch=tokens.findIndex(Token=>；inStr.substr(Idx).startsWith(Token))；if(tokenMatch>；-1){out.ush(tokenMatch+128)；idx+=tokens[tokenMatch].length；Continue；}。
Array#findIndex方法将迭代tokens数组，我们可以测试inStr(在当前idx)是否以我们正在检查的标记开始。使用简化的令牌列表，我们将执行如下操作(假设inStr.substr(Idx)=“print”：
注意：与JS中的indexOf一样，如果什么都没有找到，我们的问题会得到-1。
如果找到匹配项，则可以将索引存储在返回数组中。但是我们以后怎么知道代币和字符之间的区别呢？简单：打开高位，我们可以通过在令牌值上加128来实现这一点。
(注意：如果我们需要超过128个令牌，则某些令牌必须使用两个字节。这会让事情变得稍微复杂一些，但不会太复杂。有些Basic可以做到这一点-例如，各种风格的Microsoft Basic)。
所以，我们已经用JavaScript完成了这项工作，但是我们到底如何才能用汇编语言来完成这项工作呢？
嗯，事实证明，我们做的方式大致相同，但变得更冗长了。
搜索关键字：BL：=[d，x]#获取当前令牌CMP的第一个字符bl，constants.NUL#如果它是NUL，我们已经用尽了列表brs Z exit-keyword-search#，因此我们显然不是关键字CLR Z#比较字符串，而是使用部分相等调用[Vector tors.STRCMP]#，这样我们的源不需要#tokens；之间的NUL；c现在将是获得的字符数。前进到列表中的标记incx#逐个字符bl：=[d，x]#个标记以nuls cmp bl，constants.NUL#结尾。NUL#因此，如果我们看到它，我们可以停止}While！z incx#越过查找表BRS搜索关键字#中的标记#incx#，然后继续查找匹配项}clr c#找到匹配项！！z incx#转到查找表brs搜索关键字#中的标记#incx#并继续查找匹配项}clr c#找到匹配项！Add x，c#c是匹配Inc的长度x#超过NUL bl：=[d，x]#bl现在是令牌#call_get-target-index<；bp+target>；，y：=bl#写入令牌#call_adv-target-index call_get-source-index#前进超过源CLR中的令牌c add y，c#通过添加字符计数dec y#后退一(我们稍后将再次前进)。
好的，看起来还不错。除了汇编语言中的令牌表的结构略有不同之外，它几乎是完全相同的算法。也就是说，它看起来像这样：
不过，我们在这里遗漏了一些重要的东西-那就是，我们到底是如何进行字符串比较的？Retroputer的内核有一个我们可以使用的STRCMP例程，但是它是什么样子的呢？
Strcmp：{enter 0x00 Push a Push b Push d Push y Push f if Z{bl：=0x00#正在检查是否完全相等}否则{bl：=0x01#仅检查部分相等}_main：y：=0#字符串开头：cl：=[d，x，y]#字符串A al中的字符：=<；bp+4>；，y#字符串B中的字符CMP bl，0x01#如果正在执行完全相等，请检查是否正在执行完全相等操作。Re不是，所以检查字符串b brs Z string-are-equence#如果它是NUL，我们称它们为等于}CMP cl，al#检查字符if Z{CMP cl，0#EQUAL，但检查是否有NUL BRS Z字符串-Are-EQUAL#NUL ACTED，字符串等于包括y#下一个字符BRTOP#NOT NUL，因此请继续操作。}#如果在这里，如果N{popf#string小于set N clr Z brs_out}则字符串不相等，否则{popf#string大于clr N clr Z brs_out}string-are-等于：popf clr N#不小于set Z#但等于_out：C：=y#确保我们知道比较了多少个字符#POP D POP B POP A EXIT 0x00 ret}。
我不知道你怎么样，但是我越来越喜欢JS的string#startswith method。当然，它也做同样的事情，但是我不需要编写它的内部逻辑！
我们可以在这一点上完成-处理我们的关键字的工作已经完成。Retroputer BASIC做了更多的一步，那就是对变量进行标记化。我相信只有很少的80年代和90年代的基础知识做到了这一点，因为在有限的记忆条件下，它实际上可能会造成伤害。但是，如果您有大量内存，对变量进行标记化可以帮助提高性能。
它最多读取变量名的前两个字符。(由于内存限制，这是对当时基本知识的一种常见影响。)。
根据这两个字符，它确定一个变量索引。“A”是变量0，“A0”是变量53，依此类推。等式并不难，但不是这里的重点。
BASIC继续扫描变量的类型sigil。例如，在BASIC中，$表示字符串变量。变量类型存储在变量索引中较高的几位中。
然后，Basic将类型和索引写入输出，然后除了变量名本身之外还写入变量名的长度。这就是我们失去空间节约的地方！
(注：当Retroputer Basic可以动态分配变量时，索引将替换为指向变量的指针。待办事项清单上的另一件事！)
这使得在执行期间查找变量非常快：您不必在每次遇到变量时解析变量名并计算索引。在一个严密的循环中，节省的成本可以累积起来。但这也带来了巨大的代价：我们必须将指针和变量名存储在一起，因此我们在输出中为我们看到的每个变量增加了4个字节。
无论如何，在JavaScript中确定剩下的内容是否确实是字符流中的变量也很容易：
Const VariableMatch=inStr.substr(idx).match(/^[A-Z]+[A-Z0-9]*[\$]*/)；if(VariableMatch){const VariableName=VariableMatch[0]；idx+=VariableName.length；//tokenize(省略；这里没有新内容)继续；}。
我不打算深入Retroputer在这一点上对变量进行标记化的代码-它非常冗长，但不是特别有趣的…。现在还不行。当我添加动态变量分配时，我将重新考虑这一点。
现在，如果您测试我们的JS代码，您将得到一个与Retroputer Basic内部使用的字节数组类似的字节数组：
Console.log(toHex(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。
哇-所以节省几个字节的成本需要做大量的工作。但如果你只有几个。
.
