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

附录代码为 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 宏系统

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