上一篇（《如何编写简单的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中，使用正则匹配词法会提高整体的复杂度。InputSteamInputSteam负责读取和记录当前代码的位置，并把读取到的代码交给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) var tok = input.next(); if (tok.type == “var” || tok.type == “num” || tok.type == “str”) return tok; unexpected(); });}该函数一开头便是以一个猜测性的maybe_call函数开头，正如上我们解释的原因，maybe_call主要是对于调用表达式的一个猜测，一会我们在来看这个maybe_call的实现。parse_atom识别了位于“()”符号中的表达式、函数表达式、标识符、数字和字符串字面量，若都不符合以上要求，则会抛出一个语法错误。parse_expression的实现，主要处理了我们在最开始规则中定义的加减乘除操作的规则，具体实现如下：function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); });}这里又出现了一个maybe_binary的函数，该函数主要处理了加减乘除的操作，这里看到maybe开头，便能知道，这里也有不确定的判断因素，所以，接下来，我们统一讲一下这些maybe开头的函数。maybe_这些以maybe开头的函数，如我们以上讲的，为了处理表达式的不确定性，需要向表达式后续的语法进行试探性的解析。maybe_call函数的处理非常简单，它接收一个用于解析当前表达式的函数，并对该表达式后续词组进行判读，如果后续词组是一个“(”符号词组，那么该表达式一定是一个调用表达式（CallExpression），那么，我们就将其交给parse_call函数来进行处理，这里，我们又用到之前分隔解析的函数delimited。// 推测表达式是否为调用表达式function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr;}// 解析调用表达式function parse_call(func) { return { type: “call”, func: func, args: delimited("(", “)”, “,”, parse_expression), };}由于解析加、减、乘、除操作时，涉及到不同操作符的优先级，不能使用正常的从左至右进行解析，使用了一种二元表达式的模式进行解析，一个二元表达式包含了一个左值，一个右值，一个操作符，其中，左右值可以为其他的表达式，在后续的解析中，我们就能根据操作符的优先级，来决定二元的树状结构，而二元的树状结构，就决定了操作的优先级，具体的优先级和maybe_binary的代码如下：// 操作符的优先级，值越大，优先级越高var PRECEDENCE = { “=”: 1, “||”: 2, “&&”: 3, “<”: 7, “>”: 7, “<=”: 7, “>=”: 7, “==”: 7, “!=”: 7, “+”: 10, “-”: 10, “”: 20, “/”: 20, “%”: 20,};// 推测是否是二元表达式，即看该左值接下来是否是操作符function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); return maybe_binary({ type : tok.value == “=” ? “assign” : “binary”, operator : tok.value, left : left, right : maybe_binary(parse_atom(), his_prec) }, my_prec); } } return left;}需要注意的是，maybe_binary是一个递归处理的函数，在返回之前，需要将当前的表达式以当前操作符的优先级进行二元表达式的解析，以便包含在另一个优先级较高的二元表达式中。为了让大家更方便理解二元的树状结构如何决定优先级，这里举两个例子：// 表达式一1+23// 表达式二12+3这两段加法乘法表达式使用上面的方法解析后，分别得到如下的AST：// 表达式一{ type : “binary”, operator : “+”, left : 1, right : { type: “binary”, operator: “”, left: 2, // 这里简化了左右值的结构 right: 3 }}// 表达式二{ type : “binary”, operator : “+”, left : { type : “binary”, operator : “”, left : 1, right : 2 }, right : 3}可以看到，经过优先级的处理后，优先级较为低的操作都被处理到了外层，而优先级高的部分，则被处理到了内部，如果你还感到迷惑的话，可以试着自己拿几个表达式进行处理，然后一步一步的追踪代码的执行过程，便能明白了。总结其实，说到底，简单的parser复杂度远比完整版的parser低很多，如果想要更进一步的话，可以尝试去阅读babel-parser的源码，相信，有了这两篇文章的铺垫，babel的源码阅读起来也会轻松不少。另外，在文章的最后，附上该篇文章的demo。参考几篇可以参考的原文，推荐大伙看看：《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…）
...