如何编写简单的parser（实践篇）

共计 8918 个字符，预计需要花费 23 分钟才能阅读完成。

上一篇（《如何编写简单的 parser（基础篇）》）中介绍了编写一个 parser 所需具备的基础知识，接下来，我们要动手实践一个简单的 parser，既然是“简单”的 parser，那么，我们就要为这个 parser 划定范围，否则，完整的 JavaScript 语言 parser 的复杂度就不是那么简单的了。
划定范围
基于能够编写简单实用的 JavaScript 程序和具备基础语法的解释能力这两点考虑，我们将 parser 的规则范围划分如下：

声明：变量声明 & 函数声明
赋值：赋值操作（& 左表达式）
加减乘除：加减操作 & 乘除操作
条件判断：if 语句

如果用一句话来划分的话，即一个能解析包括声明、赋值、加减乘除、条件判断的解析器。
功能划分
基于上一篇中介绍的 JavaScript 语言由词组（token）组成表达式（expression），由表达式组成语句（statement）的模式，我们将 parser 划分为——负责解析词法的 TokenSteam 模块，负责解析表达式和语句的 Parser，另外，负责记录读取代码位置的 InputSteam 模块。
这里，有两点需要进行说明：

由于我们这里包含的 expression 解析类型和 statement 的解析类型都不多，所以，我们使用一个 parser 模块来统一解析，但是在如 babel-parser 这类完整的 parser 中，是将 expression 和 statement 拆开进行解析的，这里的逻辑仅供参考；
另外，这里对词法的解析是逐字进行解析，并没有使用正则表达式进行匹配解析，因为在完整度高的 parser 中，使用正则匹配词法会提高整体的复杂度。

InputSteam
InputSteam 负责读取和记录当前代码的位置，并把读取到的代码交给 TokenSteam 处理，其意义在于，当传递给 TokenSteam 的代码需要进行判读猜测时，能够记录当前读取的位置，并在接下来的操作汇总回滚到之前的读取位置，也能在发生语法错误时，准确指出错误发生在代码段的第几行第几个字符。
该模块是功能最简洁的模块，我们只需创建一个类似“流”的对象即可，其中主要包含以下几个方法：

peek() —— 阅读下一个代码，但是不会将当前读取位置迁移，主要用于存在不确定性情况下的判读；

next() —— 阅读下一个代码，并移动读取位置到下一个代码，主要用于确定性的语法读取；

eof() —— 判断是否到当前代码的结束部分；

croak(msg) —— 抛出读取代码的错误。

接下来，我们看一下这几个方法的实现：
function InputStream(input) {
var pos = 0, line = 1, col = 0;
return {
next : next,
peek : peek,
eof : eof,
croak : croak,
};
function next() {
var ch = input.charAt(pos++);
if (ch == “\n”) line++, col = 0; else col++;
return ch;
}
function peek() {
return input.charAt(pos);
}
function eof() {
return peek() == “”;
}
function croak(msg) {
throw new Error(msg + ” (” + line + “:” + col + “)”);
}
}
TokenSteam
我们依据一开始划定的规则范围 —— 一个能解析包括声明、赋值、加减乘除、条件判断的解析器，来给 TokenSteam 划定词法解析的范围：

变量声明 & 函数声明：包含了变量、“var”关键字、“function”关键字、“{}”符号、“()”符号、“,”符号的识别；

赋值操作：包含了“=”操作符的识别；

加减操作 & 乘除操作：包含了“+”、“-”、“*”、“/”操作符的识别；

if 语句：包含了“if”关键字的识别；

字面量（毕竟没有字面量也没办法赋值）：包括了数字字面量和字符串字面量。

接下来，TokenSteam 主要使用 InputSteam 读取并判读代码，将代码段解析为符合 ECMAScript 标准的词组流，返回的词组流大致如下：
{type: “punc”, value: “(”} // 符号，包含了()、{}、,
{type: “num”, value: 5} // 数字字面量
{type: “str”, value: “Hello World!”} // 字符串字面量
{type: “kw”, value: “function”} // 关键字，包含了 function、var、if
{type: “var”, value: “a”} // 标识符 / 变量
{type: “op”, value: “!=”} // 操作符，包含 +、-、*、/、=
其中，不包含空白符和注释，空白符用于分隔词组，对于已经解析了的词组流来说并无意义，至于注释，在我们简单的 parser 中，就不需要解析注释来提高复杂度了。
有了需要判读的词组，我们只需根据 ECMAScript 标准的定义，进行适当的简化，便能抽取出对应词组需要的判读规则，大致逻辑如下：

首先，跳过空白符；
如果 input.eof()返回 true，则结束判读；
如果 input.peek()返回是一个“””，接下来，读取一个字符串字面量；
如果 input.peek()返回是一个数字，接下来，读取一个数字字面量；
如果 input.peek()返回是一个字母，接下来，读取的可能是一个标识符，也可能是一个关键字；
如果 input.peek()返回是标点符号中的一个，接下来，读取一个标点符号；
如果 input.peek()返回是操作符中的一个，接下来，读取一个操作符；
如果没有匹配以上的条件，则使用 input.croak()抛出一个语法错误。

以上的，即是 TokenSteam 工作的主要逻辑了，我们只需不断重复以上的判断，即能成功将一段代码，解析成为词组流了，将该逻辑整理为代码如下：
function read_next() {
read_while(is_whitespace);
if (input.eof()) return null;
var ch = input.peek();
if (ch == ‘”‘) return read_string();
if (is_digit(ch)) return read_number();
if (is_id_start(ch)) return read_ident();
if (is_punc(ch)) return {
type : “punc”,
value : input.next()
};
if (is_op_char(ch)) return {
type : “op”,
value : read_while(is_op_char)
};
input.croak(“Can’t handle character: ” + ch);
}
主逻辑类似于一个分发器（dispatcher），识别了接下来可能的工作之后，便将工作分发给对应的处理函数如 read_string、read_number 等，处理完成后，便将返回结果吐出。
需要注意的是，我们并不需要一次将所有代码全部解析完成，每次我们只需将一个词组吐给 parser 模块进行处理即可，以避免还没有解析完词组，就出现了 parser 的错误。
为了使大家更清晰的明确词法解析器的工作，我们列出数字字面量的解析逻辑如下：
// 使用正则来判读数字
function is_digit(ch) {
return /[0-9]/i.test(ch);
}
// 读取数字字面量
function read_number() {
var has_dot = false;
var number = read_while(function(ch){
if (ch == “.”) {
if (has_dot) return false;
has_dot = true;
return true;
}
return is_digit(ch);
});
return {type: “num”, value: parseFloat(number) };
}
其中 read_while 函数在主逻辑和数字字面量中都出现了，该函数主要负责读取符合格则的一系列代码，该函数的代码如下：
function read_while(predicate) {
var str = “”;
while (!input.eof() && predicate(input.peek()))
str += input.next();
return str;
}
最后，TokenSteam 需要将解析的词组吐给 Parser 模块进行处理，我们通过 next()方法，将读取下一个词组的功能暴露给 parser 模块，另外，类似 TokenSteam 需要判读下一个代码的功能，parser 模块在解析表达式和语句的时候，也需要通过下一个词组的类型来判读解析表达式和语句的类型，我们将该方法也命名为 peek()。
function TokenStream(input) {
var current = null;
function peek() {
return current || (current = read_next());
}
function next() {
var tok = current;
current = null;
return tok || read_next();
}
function eof() {
return peek() == null;
}
// 主代码逻辑
function read_next() {
//….
}
// …
return {
next : next,
peek : peek,
eof : eof,
croak : input.croak
};
}
在 next()函数中，需要注意的是，因为有可能在之前的 peek()判读中，已经调用 read_next()来进行判读了，所以，需要用一个 current 变量来保存当前正在读的词组，以便在调用 next()的时候，将其吐出。
Parser
最后，在 Parser 模块中，我们对 TokenSteam 模块读取的词组进行解析，这里，我们先讲一下最后 Parser 模块输出的内容，也就是上一篇当中讲到的抽象语法树（AST），这里，我们依然参考 babel-parser 的 AST 语法标准，在该标准中，代码段都是被包裹在 Program 节点中的（其实也是大部分 AST 标准的模式），这也为我们 Parser 模块的工作指明了方向，即自顶向下的解析模式：
function parse_toplevel() {
var prog = [];
while (!input.eof()) {
prog.push(parse_statement());
}
return {type: “prog”, prog: prog};
}
该 parse_toplevel 函数，即是 Parser 模块的主逻辑了，逻辑也很简单，代码段既然是有语句（statements）组成的，那么我们就不停地将词组流解析为语句即可。
parse_statement
和 TokenSteam 类似的是，parse_statement 也是一个类似于分发器（dispatcher）的函数，我们根据一个词组来判读接下来的工作：
function parse_statement() {
if(is_punc(“;”)) skip_punc(“;”);
else if (is_punc(“{“)) return parse_block();
else if (is_kw(“var”)) return parse_var_statement();
else if (is_kw(“if”)) return parse_if_statement();
else if (is_kw(“function”)) return parse_func_statement();
else if (is_kw(“return”)) return parse_ret_statement();
else return parse_expression();
}
当然，这样的分发模式，也是只限定于我们在最开始划定的规则范围，得益于规则范围小的优势，parse_statement 函数的逻辑得以简化，另外，虽然语句 (statements) 是由表达式 (expressions) 组成的，但是，表达式（expression）依然能单独存在于代码块中，所以，在 parse_statement 的最后，不符合所有语句条件的情况，我们还是以表达式进行解析。
parse_function
在语句的解析中，我们拿函数的的解析来作一个例子，依据 AST 标准的定义以及 ECMAScript 标准的定义，函数的解析规则变得很简单：
function parse_function(isExpression) {
skip_kw(“function”);

return {
type: isExpression?”FunctionExpression”:”FunctionDeclaration”,
id: is_punc(“(“)?null:parse_identifier(),
params: delimited(“(“, “)”, “,”, parse_identifier),
body: parse_block()
};
}
对于函数的定义：

首先一定是以关键字“function”开头；
其后，若是匿名函数，则没有函数名标识符，否则，则解析一个标识符；
接下来，则是函数的参数，包含在一对“()”中，以“,”间隔；
最后，即是函数的函数体。

在代码中，解析参数的函数 delimited 是依据传入规则，在起始符与结束符之间，以间隔符隔断的代码段来进行解析的函数，其代码如下：
function delimited(start, stop, separator, parser) {
var res = [], first = true;
skip_punc(start);
while (!input.eof()) {
if (is_punc(stop)) break;
if (first) first = false; else skip_punc(separator);
if (is_punc(stop)) break;
res.push(parser());
}
skip_punc(stop);
return res;
}
至于函数体的解析，就比较简单了，因为函数体即是多段语句，和程序体的解析是一致的，ECMAScript 标准的定义也很清晰：
function parse_block() {
var body = [];
skip_punc(“{“);

while (!is_punc(“}”)) {
var sts = parse_statement()
sts && body.push(sts);
}
skip_punc(“}”);
return {
type: “BlockStatement”,
body: body
}
}
parse_atom & parse_expression
接下来，语句的解析能力具备了，该轮到解析表达式了，这部分，也是整个 Parser 比较难理解的一部分，这也是为什么将这部分放到最后的原因。因为在解析表达式的时候，会遇到一些不确定的过程，比如以下的代码：
（function(a){return a;}）(a)
当我们解析完成第一对“()”中的函数表达式后，如果此时直接返回一个函数表达式，那么后面的一对括号，则会被解析为单独的标识符。显然这样的解析模式是不符合 JavaScript 语言的解析模式的，这时，往往我们需要在解析完一个表达式后，继续往后进行尝试性的解析。这一点，在 parse_atom 和 parse_expression 中都有所体现。
回到正题，parse_atom 也是一个分发器（dispatcher），主要负责表达式层面上的解析分发，主要逻辑如下：
function parse_atom() {
return maybe_call(function(){
if (is_punc(“(“)) {
input.next();
var exp = parse_expression();
skip_punc(“)”);
return exp;
}
if (is_kw(“function”)) return parse_function(true)

《How to implement a programming language in JavaScript》（http://lisperator.net/pltut/）
《Parsing in JavaScript: Tools and Libraries》（https://tomassetti.me/parsing…）

标准以及文献：

《ECMAScript® 2016 Language Specification》（http://www.ecma-international…）
the core @babel/parser (babylon) AST node types（https://github.com/babel/babe…）

如何编写简单的parser（实践篇）

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）