摘要：負(fù)責(zé)讀取和記錄當(dāng)前代碼的位置，并把讀取到的代碼交給處理，其意義在于，當(dāng)傳遞給的代碼需要進(jìn)行判讀猜測(cè)時(shí)，能夠記錄當(dāng)前讀取的位置，并在接下來的操作匯總回滾到之前的讀取位置，也能在發(fā)生語法錯(cuò)誤時(shí)，準(zhǔn)確指出錯(cuò)誤發(fā)生在代碼段的第幾行第幾個(gè)字符。

上一篇（《如何編寫簡(jiǎn)單的parser（基礎(chǔ)篇）》）中介紹了編寫一個(gè)parser所需具備的基礎(chǔ)知識(shí)，接下來，我們要?jiǎng)邮謱?shí)踐一個(gè)簡(jiǎn)單的parser，既然是“簡(jiǎn)單”的parser，那么，我們就要為這個(gè)parser劃定范圍，否則，完整的JavaScript語言parser的復(fù)雜度就不是那么簡(jiǎn)單的了。

基于能夠編寫簡(jiǎn)單實(shí)用的JavaScript程序和具備基礎(chǔ)語法的解釋能力這兩點(diǎn)考慮，我們將parser的規(guī)則范圍劃分如下：

聲明：變量聲明 & 函數(shù)聲明

賦值：賦值操作 （& 左表達(dá)式）

加減乘除：加減操作 & 乘除操作

條件判斷：if語句

如果用一句話來劃分的話，即一個(gè)能解析包括聲明、賦值、加減乘除、條件判斷的解析器。

基于上一篇中介紹的JavaScript語言由詞組（token）組成表達(dá)式（expression），由表達(dá)式組成語句（statement）的模式，我們將parser劃分為——負(fù)責(zé)解析詞法的TokenSteam模塊，負(fù)責(zé)解析表達(dá)式和語句的Parser，另外，負(fù)責(zé)記錄讀取代碼位置的InputSteam模塊。

這里，有兩點(diǎn)需要進(jìn)行說明：

由于我們這里包含的expression解析類型和statement的解析類型都不多，所以，我們使用一個(gè)parser模塊來統(tǒng)一解析，但是在如babel-parser這類完整的parser中，是將expression和statement拆開進(jìn)行解析的，這里的邏輯僅供參考；

另外，這里對(duì)詞法的解析是逐字進(jìn)行解析，并沒有使用正則表達(dá)式進(jìn)行匹配解析，因?yàn)樵谕暾雀叩膒arser中，使用正則匹配詞法會(huì)提高整體的復(fù)雜度。

InputSteam負(fù)責(zé)讀取和記錄當(dāng)前代碼的位置，并把讀取到的代碼交給TokenSteam處理，其意義在于，當(dāng)傳遞給TokenSteam的代碼需要進(jìn)行判讀猜測(cè)時(shí)，能夠記錄當(dāng)前讀取的位置，并在接下來的操作匯總回滾到之前的讀取位置，也能在發(fā)生語法錯(cuò)誤時(shí)，準(zhǔn)確指出錯(cuò)誤發(fā)生在代碼段的第幾行第幾個(gè)字符。

該模塊是功能最簡(jiǎn)潔的模塊，我們只需創(chuàng)建一個(gè)類似“流”的對(duì)象即可，其中主要包含以下幾個(gè)方法：

peek() —— 閱讀下一個(gè)代碼，但是不會(huì)將當(dāng)前讀取位置遷移，主要用于存在不確定性情況下的判讀；

next() —— 閱讀下一個(gè)代碼，并移動(dòng)讀取位置到下一個(gè)代碼，主要用于確定性的語法讀取；

eof() —— 判斷是否到當(dāng)前代碼的結(jié)束部分；

croak(msg) —— 拋出讀取代碼的錯(cuò)誤。

接下來，我們看一下這幾個(gè)方法的實(shí)現(xiàn)：

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 == "
") 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 + ")");
    }
}

我們依據(jù)一開始劃定的規(guī)則范圍 —— 一個(gè)能解析包括聲明、賦值、加減乘除、條件判斷的解析器，來給TokenSteam劃定詞法解析的范圍：

變量聲明 & 函數(shù)聲明：包含了變量、“var”關(guān)鍵字、“function”關(guān)鍵字、“{}”符號(hào)、“()”符號(hào)、“,”符號(hào)的識(shí)別；

賦值操作：包含了“=”操作符的識(shí)別；

加減操作 & 乘除操作：包含了“+”、“-”、“*”、“/”操作符的識(shí)別；

if語句：包含了“if”關(guān)鍵字的識(shí)別；

字面量（畢竟沒有字面量也沒辦法賦值）：包括了數(shù)字字面量和字符串字面量。

接下來，TokenSteam主要使用InputSteam讀取并判讀代碼，將代碼段解析為符合ECMAScript標(biāo)準(zhǔn)的詞組流，返回的詞組流大致如下：

{ type: "punc", value: "(" }                   // 符號(hào)，包含了()、{}、,
{ type: "num", value: 5 }                      // 數(shù)字字面量
{ type: "str", value: "Hello World!" }         // 字符串字面量
{ type: "kw", value: "function" }            // 關(guān)鍵字，包含了function、var、if
{ type: "var", value: "a" }                    // 標(biāo)識(shí)符/變量
{ type: "op", value: "!=" }                    // 操作符，包含+、-、*、/、=

其中，不包含空白符和注釋，空白符用于分隔詞組，對(duì)于已經(jīng)解析了的詞組流來說并無意義，至于注釋，在我們簡(jiǎn)單的parser中，就不需要解析注釋來提高復(fù)雜度了。

有了需要判讀的詞組，我們只需根據(jù)ECMAScript標(biāo)準(zhǔn)的定義，進(jìn)行適當(dāng)?shù)暮?jiǎn)化，便能抽取出對(duì)應(yīng)詞組需要的判讀規(guī)則，大致邏輯如下：

首先，跳過空白符；

如果input.eof()返回true，則結(jié)束判讀；

如果input.peek()返回是一個(gè)“"”，接下來，讀取一個(gè)字符串字面量；

如果input.peek()返回是一個(gè)數(shù)字，接下來，讀取一個(gè)數(shù)字字面量；

如果input.peek()返回是一個(gè)字母，接下來，讀取的可能是一個(gè)標(biāo)識(shí)符，也可能是一個(gè)關(guān)鍵字；

如果input.peek()返回是標(biāo)點(diǎn)符號(hào)中的一個(gè)，接下來，讀取一個(gè)標(biāo)點(diǎn)符號(hào)；

如果input.peek()返回是操作符中的一個(gè)，接下來，讀取一個(gè)操作符；

如果沒有匹配以上的條件，則使用input.croak()拋出一個(gè)語法錯(cuò)誤。

以上的，即是TokenSteam工作的主要邏輯了，我們只需不斷重復(fù)以上的判斷，即能成功將一段代碼，解析成為詞組流了，將該邏輯整理為代碼如下：

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);
}

主邏輯類似于一個(gè)分發(fā)器（dispatcher），識(shí)別了接下來可能的工作之后，便將工作分發(fā)給對(duì)應(yīng)的處理函數(shù)如read_string、read_number等，處理完成后，便將返回結(jié)果吐出。

需要注意的是，我們并不需要一次將所有代碼全部解析完成，每次我們只需將一個(gè)詞組吐給parser模塊進(jìn)行處理即可，以避免還沒有解析完詞組，就出現(xiàn)了parser的錯(cuò)誤。

為了使大家更清晰的明確詞法解析器的工作，我們列出數(shù)字字面量的解析邏輯如下：

// 使用正則來判讀數(shù)字
function is_digit(ch) {
  return /[0-9]/i.test(ch);
}
// 讀取數(shù)字字面量
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函數(shù)在主邏輯和數(shù)字字面量中都出現(xiàn)了，該函數(shù)主要負(fù)責(zé)讀取符合格則的一系列代碼，該函數(shù)的代碼如下：

function read_while(predicate) {
  var str = "";
  while (!input.eof() && predicate(input.peek()))
    str += input.next();
  return str;
}

最后，TokenSteam需要將解析的詞組吐給Parser模塊進(jìn)行處理，我們通過next()方法，將讀取下一個(gè)詞組的功能暴露給parser模塊，另外，類似TokenSteam需要判讀下一個(gè)代碼的功能，parser模塊在解析表達(dá)式和語句的時(shí)候，也需要通過下一個(gè)詞組的類型來判讀解析表達(dá)式和語句的類型，我們將該方法也命名為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()函數(shù)中，需要注意的是，因?yàn)橛锌赡茉谥暗膒eek()判讀中，已經(jīng)調(diào)用read_next()來進(jìn)行判讀了，所以，需要用一個(gè)current變量來保存當(dāng)前正在讀的詞組，以便在調(diào)用next()的時(shí)候，將其吐出。

最后，在Parser模塊中，我們對(duì)TokenSteam模塊讀取的詞組進(jìn)行解析，這里，我們先講一下最后Parser模塊輸出的內(nèi)容，也就是上一篇當(dāng)中講到的抽象語法樹（AST），這里，我們依然參考babel-parser的AST語法標(biāo)準(zhǔn)，在該標(biāo)準(zhǔn)中，代碼段都是被包裹在Program節(jié)點(diǎn)中的（其實(shí)也是大部分AST標(biāo)準(zhǔn)的模式），這也為我們Parser模塊的工作指明了方向，即自頂向下的解析模式：

function parse_toplevel() {
  var prog = [];
  while (!input.eof()) {
    prog.push(parse_statement());
  }
  return { type: "prog", prog: prog };
}

該parse_toplevel函數(shù)，即是Parser模塊的主邏輯了，邏輯也很簡(jiǎn)單，代碼段既然是有語句（statements）組成的，那么我們就不停地將詞組流解析為語句即可。

和TokenSteam類似的是，parse_statement也是一個(gè)類似于分發(fā)器（dispatcher）的函數(shù)，我們根據(jù)一個(gè)詞組來判讀接下來的工作：

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();
}

當(dāng)然，這樣的分發(fā)模式，也是只限定于我們?cè)谧铋_始劃定的規(guī)則范圍，得益于規(guī)則范圍小的優(yōu)勢(shì)，parse_statement函數(shù)的邏輯得以簡(jiǎn)化，另外，雖然語句(statements)是由表達(dá)式(expressions)組成的，但是，表達(dá)式（expression）依然能多帶帶存在于代碼塊中，所以，在parse_statement的最后，不符合所有語句條件的情況，我們還是以表達(dá)式進(jìn)行解析。

在語句的解析中，我們拿函數(shù)的的解析來作一個(gè)例子，依據(jù)AST標(biāo)準(zhǔn)的定義以及ECMAScript標(biāo)準(zhǔn)的定義，函數(shù)的解析規(guī)則變得很簡(jiǎn)單：

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()
  };
}

對(duì)于函數(shù)的定義：

首先一定是以關(guān)鍵字“function”開頭；

其后，若是匿名函數(shù)，則沒有函數(shù)名標(biāo)識(shí)符，否則，則解析一個(gè)標(biāo)識(shí)符；

接下來，則是函數(shù)的參數(shù)，包含在一對(duì)“()”中，以“,”間隔；

最后，即是函數(shù)的函數(shù)體。

在代碼中，解析參數(shù)的函數(shù)delimited是依據(jù)傳入規(guī)則，在起始符與結(jié)束符之間，以間隔符隔斷的代碼段來進(jìn)行解析的函數(shù)，其代碼如下：

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;
}

至于函數(shù)體的解析，就比較簡(jiǎn)單了，因?yàn)楹瘮?shù)體即是多段語句，和程序體的解析是一致的，ECMAScript標(biāo)準(zhǔn)的定義也很清晰：

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
  }
}

接下來，語句的解析能力具備了，該輪到解析表達(dá)式了，這部分，也是整個(gè)Parser比較難理解的一部分，這也是為什么將這部分放到最后的原因。因?yàn)樵诮馕霰磉_(dá)式的時(shí)候，會(huì)遇到一些不確定的過程，比如以下的代碼：

（function(a){return a;}）(a)

當(dāng)我們解析完成第一對(duì)“()”中的函數(shù)表達(dá)式后，如果此時(shí)直接返回一個(gè)函數(shù)表達(dá)式，那么后面的一對(duì)括號(hào)，則會(huì)被解析為多帶帶的標(biāo)識(shí)符。顯然這樣的解析模式是不符合JavaScript語言的解析模式的，這時(shí)，往往我們需要在解析完一個(gè)表達(dá)式后，繼續(xù)往后進(jìn)行嘗試性的解析。這一點(diǎn)，在parse_atom和parse_expression中都有所體現(xiàn)。

回到正題，parse_atom也是一個(gè)分發(fā)器（dispatcher），主要負(fù)責(zé)表達(dá)式層面上的解析分發(fā)，主要邏輯如下：

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();
  });
}

該函數(shù)一開頭便是以一個(gè)猜測(cè)性的maybe_call函數(shù)開頭，正如上我們解釋的原因，maybe_call主要是對(duì)于調(diào)用表達(dá)式的一個(gè)猜測(cè)，一會(huì)我們?cè)趤砜催@個(gè)maybe_call的實(shí)現(xiàn)。parse_atom識(shí)別了位于“()”符號(hào)中的表達(dá)式、函數(shù)表達(dá)式、標(biāo)識(shí)符、數(shù)字和字符串字面量，若都不符合以上要求，則會(huì)拋出一個(gè)語法錯(cuò)誤。

parse_expression的實(shí)現(xiàn)，主要處理了我們?cè)谧铋_始規(guī)則中定義的加減乘除操作的規(guī)則，具體實(shí)現(xiàn)如下：

function parse_expression() {
  return maybe_call(function(){
    return maybe_binary(parse_atom(), 0);
  });
}

這里又出現(xiàn)了一個(gè)maybe_binary的函數(shù)，該函數(shù)主要處理了加減乘除的操作，這里看到maybe開頭，便能知道，這里也有不確定的判斷因素，所以，接下來，我們統(tǒng)一講一下這些maybe開頭的函數(shù)。

這些以maybe開頭的函數(shù)，如我們以上講的，為了處理表達(dá)式的不確定性，需要向表達(dá)式后續(xù)的語法進(jìn)行試探性的解析。

maybe_call函數(shù)的處理非常簡(jiǎn)單，它接收一個(gè)用于解析當(dāng)前表達(dá)式的函數(shù)，并對(duì)該表達(dá)式后續(xù)詞組進(jìn)行判讀，如果后續(xù)詞組是一個(gè)“(”符號(hào)詞組，那么該表達(dá)式一定是一個(gè)調(diào)用表達(dá)式（CallExpression），那么，我們就將其交給parse_call函數(shù)來進(jìn)行處理，這里，我們又用到之前分隔解析的函數(shù)delimited。

// 推測(cè)表達(dá)式是否為調(diào)用表達(dá)式
function maybe_call(expr) {
  expr = expr();
  return is_punc("(") ? parse_call(expr) : expr;
}
// 解析調(diào)用表達(dá)式
function parse_call(func) {
  return {
    type: "call",
    func: func,
    args: delimited("(", ")", ",", parse_expression),
  };
}

由于解析加、減、乘、除操作時(shí)，涉及到不同操作符的優(yōu)先級(jí)，不能使用正常的從左至右進(jìn)行解析，使用了一種二元表達(dá)式的模式進(jìn)行解析，一個(gè)二元表達(dá)式包含了一個(gè)左值，一個(gè)右值，一個(gè)操作符，其中，左右值可以為其他的表達(dá)式，在后續(xù)的解析中，我們就能根據(jù)操作符的優(yōu)先級(jí)，來決定二元的樹狀結(jié)構(gòu)，而二元的樹狀結(jié)構(gòu)，就決定了操作的優(yōu)先級(jí)，具體的優(yōu)先級(jí)和maybe_binary的代碼如下：

// 操作符的優(yōu)先級(jí)，值越大，優(yōu)先級(jí)越高
var PRECEDENCE = {
  "=": 1,
  "||": 2,
  "&&": 3,
  "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
  "+": 10, "-": 10,
  "*": 20, "/": 20, "%": 20,
};
// 推測(cè)是否是二元表達(dá)式，即看該左值接下來是否是操作符
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是一個(gè)遞歸處理的函數(shù)，在返回之前，需要將當(dāng)前的表達(dá)式以當(dāng)前操作符的優(yōu)先級(jí)進(jìn)行二元表達(dá)式的解析，以便包含在另一個(gè)優(yōu)先級(jí)較高的二元表達(dá)式中。

為了讓大家更方便理解二元的樹狀結(jié)構(gòu)如何決定優(yōu)先級(jí)，這里舉兩個(gè)例子：

// 表達(dá)式一
1+2*3
// 表達(dá)式二
1*2+3

這兩段加法乘法表達(dá)式使用上面的方法解析后，分別得到如下的AST：

// 表達(dá)式一
{
  type     : "binary",
  operator : "+",
  left     : 1,
  right    : {
    type: "binary",
    operator: "*",
    left: 2, // 這里簡(jiǎn)化了左右值的結(jié)構(gòu)
    right: 3
  }
}
// 表達(dá)式二
{
  type     : "binary",
  operator : "+",
  left     : {
    type     : "binary",
    operator : "*",
    left     : 1,
    right    : 2
  },
  right    : 3
}

可以看到，經(jīng)過優(yōu)先級(jí)的處理后，優(yōu)先級(jí)較為低的操作都被處理到了外層，而優(yōu)先級(jí)高的部分，則被處理到了內(nèi)部，如果你還感到迷惑的話，可以試著自己拿幾個(gè)表達(dá)式進(jìn)行處理，然后一步一步的追蹤代碼的執(zhí)行過程，便能明白了。

其實(shí)，說到底，簡(jiǎn)單的parser復(fù)雜度遠(yuǎn)比完整版的parser低很多，如果想要更進(jìn)一步的話，可以嘗試去閱讀babel-parser的源碼，相信，有了這兩篇文章的鋪墊，babel的源碼閱讀起來也會(huì)輕松不少。另外，在文章的最后，附上該篇文章的demo。

幾篇可以參考的原文，推薦大伙看看：

《How to implement a programming language in JavaScript》（http://lisperator.net/pltut/）

《Parsing in JavaScript: Tools and Libraries》（https://tomassetti.me/parsing...）

標(biāo)準(zhǔn)以及文獻(xiàn)：

《ECMAScript? 2016 Language Specification》（http://www.ecma-international...）

the core @babel/parser (babylon) AST node types（https://github.com/babel/babe...）