构建80年代风格的BASIC解释器,第2部分

2020-08-10 07:50:30

如果您还记得本系列的第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。

哇-所以节省几个字节的成本需要做大量的工作。但如果你只有几个。

.