让我们为APL构建一个简单的解释器

# 让我们构建一个简单的APL解释器 - 第一部分 来源：https://mathspp.com/blog/lsbasi-apl-part1 一张黑白涂鸦，画着一个人坐在电脑前。 ## 前言https://mathspp.com/blog/lsbasi-apl-part1#foreword 首先，我要感谢 Ruslan Spivak 的《让我们构建一个简单的解释器》（https://ruslanspivak.com/lsbasi-part1/）系列博文，该系列介绍了如何构建一个 Pascal 解释器。我几年前第一次阅读该系列的开头部分，最终创建了 Roj 编程语言（https://mathspp.com/blog/creating-programming-language-from-scratch）；这次我重新阅读该系列，但目的是为 APL 构建一个解释器，而 APL 与 Pascal 截然不同。 我正在编写一个 APL 解释器，并为此写下这篇文章，因为： - 这能帮助我学习 APL； - 我可以锻炼并提升我的 Python 技能； - 我可以记录下为了让代码运行所做的工作； - 如果你决定编写自己的 APL 解释器，这篇博文也能帮助你！ 对于那些了解 LSBASI 系列的人，我的 LSBASI 系列中的编号*不*会与 Spivak 的编号一致。这是因为在这个解释器中，我需要处理 Spivak 不需要处理的事情，反之亦然，因为 APL 和 Pascal 在某些方面有着截然不同的特性。另一方面，开头部分非常相似，本文将呈现的工作大致与 Spivak 在其第 8 篇博文（https://ruslanspivak.com/lsbasi-part8/）中完成到一半的工作相当。 ### 代码https://mathspp.com/blog/lsbasi-apl-part1#the-code [](https://github.com/RodrigoGiraoSerrao/RGSPL) 本项目的代码可在该 GitHub 仓库（https://github.com/RodrigoGiraoSerrao/RGSPL）中找到，快去加个星吧 ;) 本部分的源代码只是文件 `rgspl1.py`（https://github.com/RodrigoGiraoSerrao/RGSPL/releases/v0.1） ：你可以下载并尝试。 ## 我们的目标https://mathspp.com/blog/lsbasi-apl-part1#what-we-are-aiming-for 本系列博文将跟随我构建 APL 解释器的旅程，最终目标是：用 Python 编写一个功能完备的 APL 解释器！这将是一项艰巨的工作 ;) ## 今日目标https://mathspp.com/blog/lsbasi-apl-part1#today-s-goal 本文将介绍启动该项目的基础知识；具体来说，我们希望能够解析简单的 APL 语句，包括： 1. 浮点数和整数（正数和负数——在 APL 中，我们使用 `¯` 来表示负号（https://aplwiki.com/wiki/High_minus），例如 `¯3` 表示 \(-3\)）以及由它们组成的向量； 2. 函数 `+-×÷` 的单子（monadic）和双子（dyadic）版本； 3. 交换/反转运算符 `⍨`； 4. 带括号的表达式； ## 词法分析https://mathspp.com/blog/lsbasi-apl-part1#tokenizing 我们需要做的第一件事是获取一些 APL 源代码，将其拆分为 token（词法单元），去掉不需要的内容（如空白字符），并找出每个字符所代表的内容。例如，我们查找数字，判断它们是整数还是浮点数，或者查看 APL 字形并将它们与名称关联起来。 以下是 `Token` 类的代码，它定义了我们今天将使用的几种 token 类型： ``` class Token: """Represents a token parsed from the source code.""" INTEGER = "INTEGER" FLOAT = "FLOAT" PLUS = "PLUS" MINUS = "MINUS" TIMES = "TIMES" DIVIDE = "DIVIDE" NEGATE = "NEGATE" COMMUTE = "COMMUTE" LPARENS = "LPARENS" RPARENS = "RPARENS" EOF = "EOF" # Helpful lists of token types. FUNCTIONS = [PLUS, MINUS, TIMES, DIVIDE] MONADIC_OPS = [COMMUTE] # What You See Is What You Get characters that correspond to tokens. WYSIWYG = "+-×÷()⍨" # The mapping from characteres to token types. mapping = { "+": PLUS, "-": MINUS, "×": TIMES, "÷": DIVIDE, "(": LPARENS, ")": RPARENS, "⍨": COMMUTE, } def __init__(self, type_, value): self.type = type_ self.value = value def __str__(self): return f"Token({self.type}, {self.value})" def __repr__(self): return self.__str__() ``` 定义完这些 token 类型以及 `__str__` 和 `__repr__` 方法（允许我们以更友好的方式打印 token 实例）后，我们需要能够将像 `5 + 6` 这样的字符串转换为 token 列表 `[Token(EOF, None), Token(INTEGER, 5), Token(PLUS, +), Token(INTEGER, 6)]`。 注意 `EOF` token（文件结束 token）在列表中是第一个。这是因为我决定从右向左对 APL 源代码进行词法分析，这正是 APL 的执行顺序。希望这个决定不会在未来给我带来麻烦！ 顺便说一句，这可能是一个好时机，让你知道我也会犯错！很多错误！如果你在某个时刻有不同的想法，请*一定*尝试一下，然后在下面的评论中告诉我结果如何。 回到我们的程序，我们已经有了 `Token` 类，现在定义 `Tokenizer` 类，它接收一个字符串并构建 token 列表。这是类的开头部分： ``` class Tokenizer: """Class that tokenizes source code into tokens.""" def __init__(self, code): self.code = code self.pos = len(self.code) - 1 self.current_char = self.code[self.pos] def error(self, message): """Raises a Tokenizer error.""" raise Exception(f"TokenizerError: {message}") def advance(self): """Advances the cursor position and sets the current character.""" self.pos -= 1 self.current_char = None if self.pos < 0 else self.code[self.pos] # ... ``` 我们用包含 APL 代码的字符串实例化这个类，例如 `Tokenizer("5 + 6")`。`error` 函数是一个辅助函数，用于在 Tokenizer 出错时抛出异常。 最后，`advance` 函数是一个小的实用函数，它将 tokenizer 的“光标”向左移动，并重新定义保存 `current_char` 的辅助变量。当我们遍历完所有 APL 代码并到达字符串的末尾时（由于我们从右向左移动，这实际上是开头），我们将 `current_char` 设置为 `None`，表示没有更多内容需要处理。 有了这个骨架，下面是该类的其余部分： ``` class Tokenizer: # ... def skip_whitespace(self): """Skips all the whitespace in the source code.""" while self.current_char and self.current_char in " \t": self.advance() def get_integer(self): """Parses an integer from the source code.""" end_idx = self.pos while self.current_char and self.current_char.isdigit(): self.advance() return self.code[self.pos+1:end_idx+1] def get_number_token(self): """Parses a number token from the source code.""" parts = [self.get_integer()] # Check if we have a decimal number here. if self.current_char == ".": self.advance() parts.append(".") parts.append(self.get_integer()) # Check for a negation of the number. if self.current_char == "¯": self.advance() parts.append("-") num = "".join(parts[::-1]) if "." in num: return Token(Token.FLOAT, float(num)) else: return Token(Token.INTEGER, int(num)) def get_wysiwyg_token(self): """Retrieves a WYSIWYG token.""" char = self.current_char if char in Token.mapping: self.advance() return Token(Token.mapping[char], char) self.error("Could not parse WYSIWYG token.") def get_next_token(self): """Finds the next token in the source code.""" self.skip_whitespace() if not self.current_char: return Token(Token.EOF, None) if self.current_char in "0123456789": return self.get_number_token() if self.current_char in Token.WYSIWYG: return self.get_wysiwyg_token() self.error("Could not parse the next token...") def tokenize(self): """Returns the whole token list.""" tokens = [self.get_next_token()] while tokens[-1].type != Token.EOF: tokens.append(self.get_next_token()) return tokens[::-1] ``` 借助上面的代码，表达式 `5 -⍨ ¯2.3` 将被词法分析为 `[Token(EOF, None), Token(INTEGER, 5), Token(MINUS, -), Token(COMMUTE, ⍨), Token(FLOAT, -2.3)]`，如果我们运行 `print(Tokenizer("5 -⍨ ¯2.3").tokenize())` 的话。不信？只需复制表达式 `5 -⍨ ¯2.3`，然后粘贴到运行脚本时得到的读取-求值-打印循环中。 ## 在 `Token` 列表中找到结构https://mathspp.com/blog/lsbasi-apl-part1#finding-structure-in-the-token-list 现在我们已经拥有了所有 token，我们希望以更结构化的方式来表示它们。为此，我们将构建一个所谓的抽象语法树（请参阅 Spivak 的第 7 篇 LSBASI 博文（https://ruslanspivak.com/lsbasi-part7/））。 这个 AST 结构将使我们解释 APL 程序变得容易得多；代价是首先需要构建树，我们通过遍历 `Token` 列表（再次从右向左）并确定哪些是标量（https://aplwiki.com/wiki/Scalar），哪些是数组（https://aplwiki.com/wiki/Array），哪些是运算符（https://aplwiki.com/wiki/Operator），以及哪些是双子（https://aplwiki.com/wiki/Dyadic_function）/单子（https://aplwiki.com/wiki/Monadic_function）函数来完成。这就是我们的 AST 要做的工作。之后，解释程序就变得非常容易。 为了知道*如何*构建 AST，我首先为我想实现的 APL 语言子集制定了一个*语法*（https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form）。*语法*只是一种符号工具，用于指定语言中哪些类型的语句是有意义的。在我们的例子中，我们构建一个语法来指定 APL 中哪些类型的语句是有意义的。 经过一番苦思冥想，头都快撞裂了（一张黑白涂鸦，画着一个头撞在裂缝的墙上），在大量思考、多次草稿以及 APL Orchard（https://chat.stackexchange.com/rooms/52405/the-apl-orchard）中一些友好人士的帮助下，我制定了以下语法，该语法应从右向左阅读： ``` PROGRAM := EOF STATEMENT STATEMENT := ( ARRAY FUNCTION | FUNCTION )* ARRAY ARRAY := ( "(" STATEMENT ")" | SCALAR )+ SCALAR := INTEGER | FLOAT FUNCTION := F | FUNCTION "⍨" F := "+" | "-" | "×" | "÷" ``` 每一行代表一条规则，它可能依赖于下面的规则，直到我们到达像 `F` 或 `SCALAR` 这样的规则，这些规则可以通过仅仅查看我们手头的 token 来检查。这个语法的工作方式是（从上到下、从右向左阅读规则，因为这是 APL 解释程序的方式）： 1. 一个程序是一个*语句*后跟文件结束符； 2. 一个语句是一个数组，后跟 0 个或多个出现，可以是单个*函数*（这些将是单子函数）或一个*函数*后跟另一个*数组*（这些将是双子函数）； 3. 一个数组是 1 个或多个*标量*或带括号的*语句*； 4. 一个标量要么是整数 token，要么是浮点数 token； 5. 一个函数是一个交换运算符和一个*函数*，或者只是一个简单的*f*； 6. 一个*f*只是我们所知道的所有 APL 函数集合的简称：`+-×÷`。 注意规则之间如何相互引用，以及规则如何引用层级中更靠上的规则；这些自引用和递归丰富了我们的语法，但也使得 AST 的解析稍微困难一些。 我们将这些规则转化为代码来构建 AST 的方式很简单；首先，我们为 AST 将要拥有的不同节点定义类型，目前包括标量（https://aplwiki.com/wiki/Scalar）、数组（https://aplwiki.com/wiki/Array）、双子函数（https://aplwiki.com/wiki/Dyadic_function）、单子函数（https://aplwiki.com/wiki/Monadic_function）和运算符（https://aplwiki.com/wiki/Operator）： ``` class ASTNode: """Stub class to be inherited by the different types of AST nodes. The AST Nodes are used by the Parser instances to build an Abstract Syntax Tree out of the APL programs. These ASTs can then be traversed to interpret an APL program. """ class Scalar(ASTNode): """Node for a simple scalar like 3 or ¯4.2""" def __init__(self, token): self.token = token self.value = self.token.value def __str__(self): return f"S({self.value})" def __repr__(self): return self.__str__() class Array(ASTNode): """Node for an array of simple scalars, like 3 ¯4 5.6""" def __init__(self, children): self.children = children def __str__(self): return f"A({self.children})" def __repr__(self): return self.__str__() class MOp(ASTNode): """Node for monadic operators like ⍨""" def __init__(self, token, child): self.token = token self.child = child def __str__(self): return f"MOp({self.token.value} {self.child})" def __repr__(self): return self.__str__() class Monad(ASTNode): """Node for monadic functions.""" def __init__(self, token, child): self.token = token self.child = child def __str__(self): return f"Monad({self.token.value} {self.child})" def __repr__(self): return self.__str__() class Dyad(ASTNode): """Node for dyadic functions.""" def __init__(self, token, left, right): self.token = token self.left = left self.right = right def __str__(self): return f"Dyad({self.token.value} {self.left} {self.right})" def __repr__(self): return self.__str__() ``` 在我们确定了将拥有的节点类型之后，我们定义一个 `Parser` 类，它接收一个 `Tokenizer` 作为输入，并提供将 token 列表解析为 AST 的方法。 `Parser` 类的开头如下： ``` class Parser: """Implements a parser for a subset of the APL language. The grammar parsed is available at the module-level docstring. """ def __init__(self, tokenizer, debug=False): self.tokens = tokenizer.tokenize() self.pos = len(self.tokens) - 1 self.token_at = self.tokens[self.pos] self.debug_on = debug def debug(self, message): """If the debugging option is on, print a message.""" if self.debug_on: print(f"PD @ {message}") def error(self, message): """Throws a Parser-specific error message.""" raise Exception(f"Parser: {message}") def eat(self, token_type): """Checks if the current token matches the expected token type.""" if self.token_at.type != token_type: self.error(f"Expected {token_type} and got {self.token_at.type}.") else: self.pos -= 1 self.token_at = None if self.pos < 0 else self.tokens[self.pos] def peek(self): """Returns the next token type without consuming it.""" peek_at = self.pos - 1 return None if peek_at < 0 else self.tokens[peek_at].type ``` 我们的 `Parser` 实例接收一个关键字参数 `debug`（默认为 `False`），你可以用它来打印调试信息，例如当我们开始匹配上述语法中的每条规则时。与 `Tokenizer` 类似，我们也定义了一个 `error` 方法。 该类中新增的是辅助函数 `eat` 和 `peek`。`eat` 函数用于当我们*应该*看到一个给定的 token 类型并希望继续前进时。我们只需“吃掉”我们应该看到的 token 类型，如果正确，就继续移动；如果错误，则类抛出错误。 例如，我们有规则 `SCALAR`