如何用JavaScript实现一门编程语言 - AST

[llwanghong]

整篇译文的目录章节如下：

• 前言
• λanguage描述
• 写一个解析器（Parser）
  • 字符流（Character Stream）
  • 标记流（Token Stream）
  • AST
  • 解析器
• 简单的解释器（Interpreter）
  • 我们得到了什么
  • 增加新的结构
  • 我们有多快？
• CPS求值器（CPS Evaluator）
  • 保护堆栈
  • Continuations
  • Yield进阶
• 编译成JS
  • JS代码生成器
  • CPS转换器
  • 示例及改进
  • 优化器
• 总结
• 真实示例

AST

正如前面所描述的，解析器将会构建出一个能准确表达程序语义的数据结构。一个AST节点就是一个普通的JavaScript对象，该对象有一个指定节点类型的type属性和依赖具体节点类型的额外信息。

简而言之：

• num { type: "num", value: NUMBER } // 数字型变量节点
• str { type: "str", value: STRING } // 字符串型变量节点
• bool { type: "bool", value: true or false } // 布尔型变量节点
• var { type: "var", value: NAME } // 标识符节点
• lambda { type: "lambda", vars: [ NAME... ], body: AST } // 函数声明节点
• call { type: "call", func: AST, args: [ AST... ] } // 函数调用节点
• if { type: "if", cond: AST, then: AST, else: AST } // 条件节点
• assign { type: "assign", operator: "=", left: AST, right: AST } // 赋值节点
• binary { type: "binary", operator: OPERATOR, left: AST, right: AST } // 二元表达式节点
• prog { type: "prog", prog: [ AST... ] } // 表达式序列节点

---

• let { type: "let", vars: [ VARS... ], body: AST } // 块级作用于变量节点

示例：

数字型变量Numbers("num")

字符串型变量Strings("str")

布尔型变量Booleans("bool")

标识符Identifiers("var")

函数声明Functions("lambda")

函数调用Function calls("call")

条件Conditionals("if")

else分支是可选的：

赋值Assignment("assign")

二元表达式Binary expressions("binary")

表达式序列Sequences("prog")

块级作用域变量Block scoped variables("let")