《Crafting Interpreters》学习笔记 2——状态，控制流，函数，语义分析

对 AST，有各种各样的方式去料理它——编译到另一门高级语言，生成机器码，字节码……这里采取最直接的方式——直接执行它。

当前的实现中只支持表达式，因此执行代码就是去计算表达式，并产生一个值。为此，对表达式中的每种元素，字面量，操作符等，都需要知晓如何去计算它和产生结果。

该实现解释器了，该解释器直接遍历 AST 并产生一个结果，解释器仍旧是一个 Visitor，返回值是 Object，因为我们并不知道表达式具体会返回什么，是 Double 还是 String 还是 Boolean。

注意字面量和值的区别——字面量是 lexer 和 parser 的领域，而值是 interpreter，运行时的领域。

实现解释器当前是很简单的，语言中当前只有表达式，和四则运算一样简单，但有些东西需要注意：

  1. 不应该暴露底层的实现细节，应当妥善处理任何运行时异常，避免抽象泄漏，并且保证其行为最终和后面的 clox 一致。
  2. 始终关心 Java 和 Lox 的类型系统，变量生命周期之间的关系（虽然这玩意全让 JVM 操心去了，到 clox 后才对这玩意有完全的控制权）

总之这一章其实没多少需要做笔记的地方，直接进下一章。

语句

该让这玩意有点编程语言的样子了，为了让它真正能做点什么，不至于当一个计算器，命令式语言要能真正做什么需要引入什么东西？语句 Statement！先做什么后做什么。在大多数编程语言中，整个源代码是由一个个语句组成的。

为此，需要在语法中引入语句的概念，这里先从简单的开始，引入一个 expression 语句（即计算该表达式并利用它的副作用，但目前什么额外的操作都不能做）和一个 print 语句（没错，语句而非库函数，因为定义函数是后面的事情，现在要马上能看到效果）：

1
2
3
4
5
program   -> statement* EOF
statement -> exprStmt
          |  printStmt
exprStmt  -> expr ";"
printStmt -> "print" expr ";"

注意 program 规则最后的 EOF，这是为了避免解析器遗漏某些 token 没处理，在之前的四则运算的玩意里如果写一个 1 + 2 3 + 4，它处理完1 + 2就停了。

状态

这样就有点编程语言的样子了，但这里还欠缺一个要素——状态 State，离开了状态，那这些语句不过是一堆独立的个体，没有任何相互联系的地方。引入状态就是引入变量——绑定 binding 值到一个名字上。而这又引入一个问题——变量存在哪？这又引入一个概念——环境 Environment——关联变量和值的数据结构。

这里为了简化，不考虑作用域问题，把什么词法作用域啊函数作用域啊先留到将来，只考虑全局变量，这样，Environment 的实现就非常显然了——直接上哈希表就行。

为此，再次扩充变量定义语法（这里加个私货 VAL）：

1
2
3
4
5
6
7
program        → declaration* EOF 
declaration    → varDecl        # 这里的 varDecl 其实不太合适定义出来一个新的规则，其实 declaration 的实现中就需要根据第一个 token 是否是 var 来做操作。.
               |  statement 
statement      → exprStmt
               |  printStmt 
varDecl        → "var" IDENTIFIER ( "=" expression )? ";" 
valDecl        -> "val" IDENTIFIER "=" expression;

注意这里把语句做了一些分离，为了避免这样的代码：

1
2
if (true) 
    var a = 1;

这玩意在 java，kotlin，js，scala 中均不合法，提示需要一个表达式。为了和该行为保持一致，只要在后来实现 if 的时候让它只接受 statement 而非 declaration 即可。

以及，生成一个新的 AST 类 Stmt 表示语句，并定义其子类 Expression，Print，Var。

1
2
3
4
5
generate_ast 'Stmt', %/
  Expression : Expr expression
  Print      : Expr expression
  Var        : Token name, Expr initializer
/

另外，关于上一节中的错误处理，declaration 显然很适合作为同步点，因此 synchronize 方法放到这里。

实现这些之后，又抛出另一个问题——在引用变量时，如果该变量找不着怎么办？有三种操作：

  1. 抛出编译期错误，这能实现当然是最好的，但会引入一些复杂度——比如编写两个共递归的函数，他们互相引用，这时如果要抛编译期错误就不允许函数这样定义了。这当然是能处理的，比如在处理出现在顶层的标识符时不把它们当作语句的序列，而是当它们是“同时”定义的，但实现这玩意对于这样一个 tree-walker 解释器来说不值得（就连 typescript 中，函数中引用的变量写在函数定义之后，调用该函数的代码之前（因此会抛运行时异常）这种情况也无法处理呢）
  2. 抛出运行时错误，许多脚本语言就是这样处理的，这里也这么处理
  3. 返回一个默认值比如 nil，不严格的 perl 是这么操作的，不应该这样搞，不然有了拼写错误都发现不了

这也是为啥这语言中不像 python，ruby 那样直接a = 1就定义变量了——要是有拼写错误就麻了，同时也避免像 python 那样引入智障的 global，nonlocal 关键字。

赋值表达式语法

上面说的是变量定义语句var variableName = initValue;，这里得研究一下变量赋值表达式，它的形式形如variableName = initValue。

这里有个非常有趣的点——在 js，c 的优先级表中，三目的优先级比赋值高，但 js 的行为和 c，java 的行为均不同，后两者的行为是符合其优先级的。js 的这个有点令人费解……不按 js 的来。

相应语法规则如下，注意赋值运算符是右结合的（如果把 ternary 的 body 里的 ternary 改成 assignment 应该就是 js 那种效果）：

1
2
3
4
5
6
7
8
9
10
11
expression -> assignment
assignment -> IDENTIFIER "=" assignment 
           |  ternary 
ternary    -> equality ("?" ternary ":" ternary)?
equality   -> comparison (("==" | "!=") comparsion)*
comparsion -> term ((">" | ">=" | "<" | "<=") term)*
term       -> factor (("-" | "+") factor)*
factor     -> unary (("*" | "/") unary)*
unary      -> ("!" | "-") unary | primary
primary    -> NUMBER | STRING | "true" | "false" | "nil" 
            | "(" expression ")"

虽然看上去轻松，但实现的时候还是有一些问题的，这关乎赋值语句本身的特性——左值和右值，在运行时，左值求的不是值，而是它对应的“地址”。如何保证等号左边是左值？这里的诀窍是退一步进两步——先放宽需求，这样去定义 assignment：

1
assignment -> ternary ("=" assignment)?

然后实际操作的时候，先获取一个 ternary，并检查下一个 token 是否是 EQUAL，若是就进入赋值表达式的逻辑，检查这里的 ternary 是否是 IDENTIFIER，如何检查呢？这里是个 Expr 啊？我们知道解析 IDENTIFIER 会解析成Expr.Variable，那就做个 instanceof 呗。这里实际上是一个把右值转换为左值的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private Expr assignment() {
    val res = ternary();
    if (match(EQUAL)) {
        val equal = previous();
        val value = assignment();
        // 后续可以进行更多处理，比如左边是 arr[i]，instance.field 等形式时
        // 左值不能当成普通表达式看待，需要特别的处理逻辑，比如 (a) = 1，即使看上去没啥问题，我们也不应当认为它合法
        if (res instanceof Expr.Variable) {
            return new Expr.Assign(((Expr.Variable) res).name, value);
        }
        error(equal, "Invalid assignment target"); // 非法的左值
        // 这里还是继续解析，这个错误不至于去进入 panic mode
    }
    return res;
}

这里如果直接尝试匹配一个 IDENTIFIER，再尝试匹配一个 EQUAL 来走到赋值表达式的逻辑如何呢？其实应该也是能做到的，但后续不好扩展。

在退一步时，可以退的更远，允许甚至不是表达式的东西出现在左边，只要保证退了后还能进就行，哈哈哈哈哈。

赋值表达式语义

这个倒简单——若先前存在该变量定义，就继续赋值操作，不然就报错说 undefined 的变量。

作用域

作用域，即能看到映射到特定名字的特定实体的地方。词法作用域是一种特殊的作用域，即仅通过程序的源代码便能够看出作用域的开始和结束位置。大多数现代语言中，变量都是词法作用域的（不全是，ruby 和 python 的变量没有词法作用域，只有函数作用域）。

而在 lox 中，方法，字段是动态作用域的——直到运行时，你才知道特定对象是否包含该方法、字段。

要引入词法作用域，只使用哈希表来作存储是不够的——需要考虑作用域遮蔽的情况，即内层作用域的变量遮蔽外层作用域的同名变量，而离开内层作用域之后，外层作用域的同名变量变得又能访问到了。

为此，Environment 需要是某种嵌套结构——在进入一个词法块的时候，创建一个新的 Environment，该 Environment 需要引用包围它的 Environment，定义变量时在该 Environment 中定义，查询时先查询该 Environment，再递归查询包围它的 Environment，如果不存在包围它的 Environment 再认为是 undefined 的变量。

离开词法块的时候，设定当前 Environment 为包围它的 Environment 即可。这里并不需要整出来个树结构，实际上链表即可。

另外，需要引入块：

1
2
3
4
statement → exprStmt
          |  printStmt 
          |  block
block     → "{" declaration* "}" ;

控制流

后面只记一些最值得记的地方，感觉并不需要跟着书见到啥记啥，又不是学马哲，没必要啥东西都抓，整点实用主义。

控制流最基本来说，只有两种类型：条件和循环。实现了这俩，那语言就图灵完备了。

if

if 的语法如下：

1
2
3
4
5
statement → exprStmt
          |  printStmt 
          |  block
          |  ifStmt
ifStmt    -> "if" "(" expression ")" statement ("else" statement)?

处理 if 时，有个经典的问题：对下面的代码，else 对应的是哪个 if？

1
2
3
if (first)
  if (second) {/*...*/}
else {/*...*/}

一些语言为了避免这个问题，直接为 else if 去提供新的关键字，这里直接走最自然的逻辑——让 else 匹配最近的 if，这正好和解析器的工作方式相吻合——在解析内层的 if 的时候，它会贪婪地把 else 子句马上消费掉。

条件表达式

条件表达式，注意 or 的优先级更低，就像一堵高墙把不同的 and 隔离开来。同时注意条件表达式计算时有短路操作，所以值得为条件表达式新增对应的语法树节点类型。

while，for

没啥好说的。关于 for，书中提了语法糖的概念，即不引入新的语法树节点，对于语法糖，手动去把它 desugar 成已有的语法树节点。

考虑到实现 for 有点蛋疼，书中的 for 限制颇多，这里干脆不要 for 了。

函数

最激动人心的时刻——函数。有了函数，就有了过程抽象的能力。

函数调用的语法如下：

1
2
call      ->  primary ("(" arguments? ")")*
arguments -> expression ("," expression)*

注意函数调用是左结合，因此它的实现类似中缀操作符。

函数定义的语法如下：

1
2
fnStmt -> "FUN" IDENTIFIER "(" parameters? ")" block
parameters -> IDENTIFIER ("," IDENTIFIER)*

注意这里的命名——argument 和 parameter。

闭包

关于函数，实际上有两个作用域和它相关——函数定义时的作用域，函数调用时的作用域，前者用于创建闭包（这玩意好像本身就叫闭包？），后者……或许可以在像 scala 之类的语言中传递隐式参数之类的玩意？

要实现闭包，只需要让函数记住函数定义时的作用域即可。

变量获取和绑定

上面的作用域的实现是有问题的——函数创建时，保存函数当前的环境，在获取变量时，它跟随着作用域链一层层往上找，找到最近的该变量。问题是，环境是可变的，在变量定义后，如果在比原所捕获变量的作用域更深的作用域下再次定义同名变量，函数再次调用后找到的变量和函数想要找到的变量就不同了。这是不符合直觉的：

1
2
3
4
5
6
7
8
9
10
val a = "global";
{
  fun showA() {
    print a;
  }

  showA(); // global
  val a = "block";
  showA(); // block
}

这里的问题在于，在函数定义的该层环境中，又定义了同名变量 a，函数往外找变量 a 时，先找到了同层的这个 a，即使它是在函数定义后才定义的。词法作用域是静态语义，函数捕获的变量应当是比它先定义的，最深的变量。这里没有给变量 a 重新赋值，因此函数的输出结果不同绝对是哪里出现了问题。

这里有两个概念——静态的作用域和动态的环境，需要保证它们正确地同步。大多数时候同步是得到保障的——进入新作用域时创建新环境，离开该作用域时丢掉环境。变量定义时，把变量绑定到环境上。

错误来自于一个前提——我们假设块中的每一行语句都在同一个作用域中。根据该前提，这里使用单个环境去表达作用域。新增变量时，不是创建新作用域，而是把变量绑定在现有的这个作用域上，即不断地修改这个作用域。函数需要看到的，是函数定义时的作用域的一个不变的快照。

要处理这个问题，最明显的方案是丢掉这个前提，每次新增一个变量，也要新创建一个 Environment，保证运行时的行为和静态语义完全一致，但要实现这个估计会很痛苦且低效。考虑到只有对函数才有这种情况，可以在定义函数时把整个作用域完全拷贝一次。

但这里使用更直接的方案——进行语义分析，在函数定义时直接“烘培”函数中引用的外部变量。

语义分析

resolve——遇到标识符时，找到相应的变量定义。每次遇到带变量的表达式就要进行这一过程。考虑到对静态作用域，每一个用到的变量，都能唯一地找到它的变量定义，没必要在运行时才去一层一层地去找，而是只找一次，找一次就固化它（我是说，烘培 lol）。

为此，需要进行一次语义分析，在解析完 token 序列之后，真正执行代码之前；类型分析，优化通常在此时执行。一般来说，一切不依赖运行时状态的工作都可以在这里完成。

这里，需要根据每个标识符去找到对应的变量定义，因此所有和变量（标识符）以及块相关的语句和表达式需要处理，其他的节点就直接继续遍历它的子节点：

  1. 块
  2. 函数定义
  3. 变量定义
  4. 变量引用和赋值表达式

在进行语义分析时，遇到变量和函数的定义时，记录定义位置（以作用域为单位）；遇到引用变量和函数的地方时，检查当前以及定义位置之间差了多少层作用域，并让这个信息被解释器知晓。

这里定义一个 Resolver 用来进行变量的获取，它要维护一个作用域栈，栈中元素为哈希表，保存当前作用域下定义的变量。该哈希表的类型为Map<String, Boolean>，key 为标识符名称，至于 value……要考虑一个边缘情况：

1
2
3
4
val a = 1;
{
  val a = a;
}

这认为是不合法的，要报错Cannot access 'a' before initialization。为了能区分这种情况，不能直接用集合去保存当前作用域，这里的 value 表示变量是否“准备完毕”，这里先把 a 先“声明”，处理完右值后，再把 a 去“定义”；在获取变量时，如果发现变量“声明”了但没“定义”就报错。（如果没有找到变量，就认为变量是在顶层作用域，因为顶层作用域是非常灵活的，这里不报错）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 下面是这两个过程的伪代码描述
def resolve(node: ASTNode):
    if node is VAR_STMT:
        declare node
        resolve node.initializer 
        define node
    elif node is FUNCTION:
        declare_and_define node
        with_new_scope:
            declare_and_define params
            resolve for node.body
    elif node is BLOCK:
        with_new_scope:
            resolve for node.stmts
    elif node is VARIABLE:
        var_stmt, depth = find_define_location node
        assert var_stmt is defined
        interpreter.resolveLocal node, depth
    else:
        resolve for node.childrens

如何让解析器保存该信息？增加一个哈希表字段，映射相应 AST 节点（必将是Variable或Assign类型，即赋值和取值）到其和其定义位置的距离。使用IdentityHashMap以使能够利用到节点本身的唯一标识符——地址。

之后，修改解释器对赋值和变量的处理，直接根据该哈希表去找到相应字段所在的 Environment，如果没找到，则默认是在全局作用域中。

这一趟语义分析也可以干点其他的，比如，检查变量是否在同一个作用域被重复定义了，检查 return 时是否在函数内，检查 return 后是否还有不可到达的代码…