《用GO语言自制解释器》读书笔记

Published by 雪夜不下雪 on 共 2540 个字

附录代码为 Javascript 版本。

前言

  • 解释器种类很多，一个共同的功能是将源代码作为输入并求值，中途不会生成任何可见且之后还能再次运行的中间结果。
  • 编译器则是将源代码转换成底层系统可以理解的另一种语言。
  • 本书实现的解释器为树遍历（tree-walking）解释器：解析源代码，构建抽象语法树，然后对这棵树求值。
  • 我们将构建词法分析器、语法分析器、树表示形式和求值器（evaluator），其中涉及词法单元（token）、抽象语法树、如何构建抽象语法树、如何求值，以及如何使用新的数据结构和内置函数扩展所用的编程语言。

Monkey 编程语言和解释器

  • 本书设计的 Monkey 语言具有以下特征：
    • 类 C 语法
    • 变量绑定
    • 整形和布尔型
    • 算术表达式
    • 内置函数
    • 头等函数和高阶函数
    • 闭包
    • 字符串数据结构
    • 数组数据结构
    • 哈希数据结构
  • 解释器包含以下几个主要部分：
    • 词法分析器
    • 语法分析器
    • 抽象语法树
    • 内部对象系统
    • 求值器

第1章 词法分析

1.1 词法分析

  • 为了解释源代码，需要将其转换成其他易于处理的形式。源代码->词法单元->抽象语法树。
    • 第一次是用词法分析器将源代码转换为词法单元，这个过程称为词法分析。词法分析器有时也称词法单元生成器（tokenizer）或扫描器（scanner）。词法单元本身是短小、易于分类的数据结构。它会被传给语法分析器。
    • 在第二次转换中，语法分析器会将词法单元转换成抽象语法树。

1.2 定义词法单元

定义部分词法单元类型

1.3 词法分析器

  • 词法分析器将源代码作为输入，并输出对应的词法单元。词法分析器会遍历输入的字符，然后逐个输出识别出的词法单元。

1.5 编写REPL

  • REPL 是指Read-Eval-Print Loop（读取（求值求打印循环），读者可能从其他语言中对此有所了解，Python有REPL，Ruby有，每个JavaScript运行时也有，大多数Lisp和许多其他语言也有 REPL。有时 REPL 被称为控制台或交互模式，不过概念是相同的。REPL 读取输入，将其发送到解释器进行求值，然后打印解释器的输出，最后重新开始，重复“读取读求值求打印”这个循环。

第2章 语法分析

2.1 语法分析器

  • 语法分析器是一个软件组件，用于将输入的数据（通常是文本）构建成一个数据结构，通常是某种解析树、抽象语法树或其他层次结构。也就是说，它将输入的内容以结构化形式表示，并在此过程中检查语法是否正确……语法分析器通常位于词法分析器之后，而词法分析器会根据输入的字符序列创建词法单元。
  • 在大多数解释器和编译器中，用于源代码内部表示的数据结构称为“语法树”或“抽象语法树”（Abstract Syntax Tree，AST）。“抽象”是指AST中省略了源代码中可见的某些细节。比如分号、换行符、空格、注释、花括号、方括号和括号等信息不会出现在AST中，它们只是用来指导语法分析器如何构造AST。当然，各个语言和语法分析器具体省略的内容有所区别。需要注意的是，并没有一个通用的AST格式可供所有语法分析器使用。各个AST的实现都非常相似，它们在概念上相同，但是细节上略有区别。具体的实现取决于所解析的编程语言。

2.2 为什么不用语法分析器生成器

  • 语法分析器生成器是一种工具，只要为其提供语言的正式描述，它就能生成对应的语法分析器。
  • 只有编写了自己的语法分析器或至少尝试过之后，才能明白语法分析器生成器的优缺点，以及其所能解决的问题。

2.3 为 Monkey 语言编写语法分析器

  • 对编程语言进行语法分析时，主要有两种策略：自上而下的分析或自下而上的分析。每种策略都有很多变体。例如递归下降分析、Earley分析、预测分析，这些都是自上而下分析的变体。
  • 递归下降语法分析器。具体来说，它是基于自上而下的运算符优先级分析法的语法分析器。因为发明人是沃恩·普拉特（Vaughan Pratt），所以有时它也称为普拉特语法分析器。
  • 自上而下的语法分析器和自下而上的语法分析器的区别。前者从构造AST的根节点开始，然后下降；而后者则以相反的方式进行构造。对于新手来说，通常建议使用自上而下进行构造的递归下降语法分析器，因为这种方式更加接近我们对AST的认知及AST的构造方式。

2.4 语法分析器的第一步：解析 let 语句

  • AST需要两种不同类型的节点：表达式和语句。

2.6 解析表达式

2.6.2 自上而下的运算符优先级分析（也称普拉特解析法）

  • 普拉特解析法与其他语法分析方法的主要区别在于，普拉特没有将解析函数（回想一下parseLetStatement方法）与语法规则（在BNF或EBNF中定义）相关联，而是将这些函数（他称为语义代码，semantic code）与单个词法单元类型相关联。这个想法的关键是，每种词法单元类型都可以具有两个与之相关联的解析函数，具体取决于词法单元的位置，比如是中缀还是前缀。

2.6.3 术语

  • 前缀运算符是位于操作数（operand）前面的运算符。例如：–5
  • 后缀运算符是位于操作数后面的运算符。例如：foobar++
  • 中缀运算符位于两个操作数之间。例如：5 * 8。中缀运算符出现在二元表达式中，即有两个操作数的表达式。
  • 运算符优先级这个术语也可以称为运算顺序。它表示不同运算符的重要程度，能让运算符优先级更加直观。

2.6.6 标识符

  • 标识符无论是在单个表达式语句中，还是在其他上下文中，都是表达式。

第3章

3.1 为符号赋予含义

  • REPL 中的 E 表示“求值”，是解释器处理源代码过程的最后一步。代码经过求值后才会变得有意义。如果不进行求值，那么类似1 + 2的表达式转换后也只是一组字符、一组词法单元或一个树结构，并没有含义。

3.3 树遍历解释器

  • 我们将要构建一个树遍历解释器。也就是说，我们会使用语法分析器构建的AST，直接解释它，不经过任何预处理或编译步骤。

3.4 表示对象

  • 对象系统也可以称为“值系统”或“对象表示方法”。这里的重点是，需要为eval函数所返回的内容添加一个定义。也就是说，我们需要一个系统，用来表示AST的值或表示在内存中对AST求值时生成的值。

遗失的篇章：Monkey 的宏系统

5.1 宏系统

  • 宏系统是指与宏有关的编程语言特性，包括宏的定义、访问、求值，以及宏本身如何工作。宏可以分为两大类：文本替换宏系统和语法宏系统。在我看来，它们分别相当于搜索替换和代码即数据两个类别。
code下载