language-design - BASIC，行是如何存储在内存中的？

Question

据我所知，BASIC 有行号，因为当时你必须使用行编辑器来输入你的程序。它允许你做这样的事情:

20 END
10 PRINT "HELLO WORLD"

这个程序会打印"HELLO WORLD"。我的问题是 BASIC 如何允许您以这种方式输入行？它们是如何存储在内存中的？我想这是一个行号和指向行本身的指针的映射，每次您输入一行时都会更新。但是在运行 LIST/RUN 命令之前必须对该映射进行排序。是这样吗？如果不是，那么 BASIC 究竟是如何在内存中存储命令的？

Answer 1

我想每个 Basic 实现都使用了特定的方法。

伴随我成长的 Basic 是在 MSX 计算机上运行的 Microsoft Basic。根据我当时如饥似渴地阅读的《The MSX Red Book》，MS-Basic实际上使用的是线性列表。

每个 Basic 行都存储为指向下一行的指针，后跟二进制形式的实际行号，然后是该行的标记化版本，再后跟一个空字符；像这样:

    Address  | Content
    8000     | 8009 -- next line
    8002     | 10   -- this line number
    8004     | .... -- opcodes for each instruction in the line
    ...      | ...
    8007     | ...
    8008     | Null -- terminator
    8009     | ...  -- the next line

尽管链表所在的行，Basic 解释器并没有利用它。每行都以线性连续的方式物理存储。

如您所想，在现有程序中间插入和删除行需要大量工作。如果在现有行之间插入新行，则后续行将在内存中向上移动以为新行腾出空间。同样，在程序中删除行会导致后续行在内存中向下移动以填充删除行留下的空间。这种在内存中上下移动意味着必须为移动的每一行更新所有这些链接。