设计并实现Tiny BASIC解释器的核心框架——词法分析器、表达式求值器和变量存储。BASIC是8位电脑的灵魂语言，从Altair BASIC到Commodore 64 BASIC，它让数以百万计的人第一次接触编程。今天，我们将亲手打造属于自己的BASIC。
解释器与编译器的根本区别：编译器将源代码一次性翻译为机器码，解释器则逐行读取并立即执行。BASIC是典型的解释型语言——这也解释了为什么它运行较慢但交互性极好。
我们实现的是Tiny BASIC——一个精简到极致的BASIC方言，最初由Li-Chen Wang在1976年实现，仅占用约2KB内存：
| 类别 | 项目 | 规格 |
|---|---|---|
| 变量 | A-Z | 26个16位有符号整数变量 |
| 常量 | 数字 | -32768到32767 |
| 运算 | 算术 | + - * / ( ) 整数运算 |
| 运算 | 比较 | = < > <= >= <> |
| 运算 | 逻辑 | AND OR NOT |
| 语句 | LET | LET var = expr |
| 语句 | PRINT expr [;expr...] [;] | |
| 语句 | INPUT | INPUT var |
| 语句 | GOTO | GOTO linenum |
| 语句 | GOSUB | GOSUB linenum |
| 语句 | RETURN | RETURN |
| 语句 | IF-THEN | IF expr THEN linenum |
| 语句 | FOR-NEXT | FOR var=expr TO expr [STEP expr] |
| 语句 | END | END |
| 命令 | RUN | 从最小行号开始执行 |
| 命令 | LIST | 列出程序 |
| 命令 | NEW | 清除程序 |
我们先用Python实现解释器原型——方便调试和验证，然后再移植到8位汇编：
import re
class TinyBasic:
"""Tiny BASIC解释器"""
def __init__(self):
self.variables = {} # A-Z 变量
self.program = {} # 行号 → 源代码行
self.running = False
self.current_line = 0
self.gosub_stack = [] # GOSUB返回栈
self.for_stack = [] # FOR循环栈
def tokenize(self, line):
"""词法分析：将源代码行拆分为token列表"""
tokens = []
i = 0
while i < len(line):
if line[i].isspace():
i += 1
continue
if line[i] == '"':
# 字符串字面量
j = i + 1
while j < len(line) and line[j] != '"':
j += 1
tokens.append(('STRING', line[i+1:j]))
i = j + 1
elif line[i].isdigit() or \
(line[i] == '-' and (not tokens or tokens[-1][0] in ('OP','LPAREN'))):
j = i + 1
while j < len(line) and line[j].isdigit():
j += 1
tokens.append(('NUMBER', int(line[i:j])))
i = j
elif line[i].isalpha():
j = i + 1
while j < len(line) and (line[j].isalnum() or line[j] == '_'):
j += 1
word = line[i:j].upper()
if word in ('LET','PRINT','INPUT','GOTO',
'GOSUB','RETURN','IF','THEN',
'FOR','TO','STEP','NEXT',
'END','RUN','LIST','NEW',
'AND','OR','NOT','RND'):
tokens.append(('KEYWORD', word))
elif len(word) == 1:
tokens.append(('VAR', word))
else:
tokens.append(('IDENT', word))
i = j
elif line[i:i+2] in ('<=','>=','<>'):
tokens.append(('OP', line[i:i+2]))
i += 2
elif line[i] in '+-*/=<>(),;':
tokens.append(('OP', line[i]))
i += 1
else:
i += 1 # 跳过未知字符
return tokens
def evaluate(self, tokens, pos=0):
"""表达式求值：递归下降解析器"""
val, pos = self._expr(tokens, pos)
return val
def _expr(self, tokens, pos):
"""加法/减法层"""
left, pos = self._term(tokens, pos)
while pos < len(tokens) and \
tokens[pos] == ('OP', '+') or \
tokens[pos] == ('OP', '-'):
op = tokens[pos][1]
pos += 1
right, pos = self._term(tokens, pos)
if op == '+':
left += right
else:
left -= right
return left, pos
def _term(self, tokens, pos):
"""乘法/除法层"""
left, pos = self._factor(tokens, pos)
while pos < len(tokens) and \
tokens[pos] == ('OP', '*') or \
tokens[pos] == ('OP', '/'):
op = tokens[pos][1]
pos += 1
right, pos = self._factor(tokens, pos)
if op == '*':
left *= right
else:
if right == 0:
raise ZeroDivisionError("Division by zero")
left = int(left / right)
return left, pos
def _factor(self, tokens, pos):
"""因子：数字、变量、括号表达式、一元运算"""
if pos >= len(tokens):
raise SyntaxError("Unexpected end of expression")
tok = tokens[pos]
# 一元负号
if tok == ('OP', '-'):
pos += 1
val, pos = self._factor(tokens, pos)
return -val, pos
# 括号
if tok == ('OP', '('):
pos += 1
val, pos = self._expr(tokens, pos)
if pos < len(tokens) and \
tokens[pos] == ('OP', ')'):
pos += 1
return val, pos
# 数字
if tok[0] == 'NUMBER':
return tok[1], pos + 1
# 变量
if tok[0] == 'VAR':
return self.variables.get(tok[1], 0), pos + 1
# RND函数
if tok == ('KEYWORD', 'RND'):
pos += 1
import random
return random.randint(0, 32767), pos
raise SyntaxError(f"Unexpected token: {tok}")
def execute_line(self, line):
"""执行一行BASIC代码"""
tokens = self.tokenize(line)
if not tokens:
return
# 检查是否以行号开头
if tokens[0][0] == 'NUMBER' and \
len(tokens) > 1 and tokens[0][1] >= 0:
line_num = tokens[0][1]
self.program[line_num] = line
return
# 直接执行命令
self._execute_tokens(tokens)
def _execute_tokens(self, tokens):
"""执行token列表"""
if not tokens:
return
kw = tokens[0][1] if tokens[0][0] == 'KEYWORD' else None
if kw == 'PRINT':
self._exec_print(tokens[1:])
elif kw == 'LET':
self._exec_let(tokens[1:])
elif kw == 'RUN':
self._exec_run()
elif kw == 'LIST':
self._exec_list()
elif kw == 'NEW':
self.program.clear()
elif kw == 'GOTO':
line_num = tokens[1][1]
self.current_line = line_num
elif kw == 'END':
self.running = False
def _exec_print(self, tokens):
"""PRINT语句执行"""
output = ""
i = 0
trailing_semi = False
while i < len(tokens):
if tokens[i] == ('OP', ';'):
trailing_semi = True
i += 1
continue
if tokens[i][0] == 'STRING':
output += tokens[i][1]
i += 1
else:
val, i = self._expr(tokens, i)
output += str(val)
trailing_semi = False
if trailing_semi:
print(output, end='')
else:
print(output)
def _exec_let(self, tokens):
"""LET语句执行"""
var_name = tokens[0][1]
if tokens[1] != ('OP', '='):
raise SyntaxError("Expected =")
val, _ = self._expr(tokens, 2)
self.variables[var_name] = val
def _exec_run(self):
"""RUN命令执行"""
self.running = True
lines = sorted(self.program.keys())
if not lines:
return
idx = 0
while self.running and idx < len(lines):
self.current_line = lines[idx]
line = self.program[self.current_line]
tokens = self.tokenize(line)
# 跳过行号token
self._execute_tokens(tokens[1:])
if self.current_line == lines[idx]:
idx += 1
else:
# GOTO改变了当前行
idx = lines.index(self.current_line) \
if self.current_line in lines \
else len(lines)
# 测试
if __name__ == '__main__':
basic = TinyBasic()
basic.execute_line('10 LET A = 5')
basic.execute_line('20 LET B = 3')
basic.execute_line('30 PRINT "A + B = "; A + B')
basic.execute_line('RUN')
# 输出: A + B = 8实现FOR-NEXT循环语句。FOR压入循环变量名、终止值、步长和返回行号到for_stack；NEXT弹出栈顶，递增循环变量，如果未超过终止值则跳回FOR的下一行。测试：FOR I=1 TO 10: PRINT I: NEXT I
实现子程序调用。GOSUB将当前行号压入gosub_stack，跳转到目标行号；RETURN弹出栈顶行号并跳回。测试：写一个计算阶乘的递归子程序。
扩展BASIC支持一维数组：DIM A(10)声明数组，A(I)访问元素。在8位实现中，数组存储在变量区之后的连续内存中。每个数组元素占2字节（16位整数）。
将Python解释器移植到8位CPU汇编语言。关键挑战：16位算术运算、字符串操作、内存管理。提示：先实现表达式求值器（使用操作数栈），再逐步添加语句。
你实现了Tiny BASIC解释器的核心！这包括：
BASIC让编程变得人人可及——你的8位电脑现在有了自己的编程语言！