簡易計算欄位 - Parsing

在前一篇提到怎麼設計一個簡單的程式語言並求值。這篇會介紹一下怎麼用 JavaScript 生態系的工具來把原始碼 parse 成我們設計的 AST 。

這次選用的工具是 parsimmon ，他是一套 parser combinator 工具。不像 parser generator 會幫我們生出 parser 程式碼，它讓我們可以用小的 parser 組合出大的 parser ，所以才叫 combinator 。

Str, Num 和 Field parsers

先準備要用的 syntax node ：

import {
  Empty,
  Str,
  Num,
  Field,
  Binary,
} from './syntax';

再準備針對個別 node 的 parser ：

const Parser = P.createLanguage({
  str: () => string.map(Str),
  num: () => number.map(Num),
});

const string =
  token(P.regexp(/"((?:\\.|.)*?)"/, 1))
    .desc('string');

const number =
  token(P.regexp(/-?(0|[1-9][0-9]*)([.][0-9]+)?([eE][+-]?[0-9]+)?/))
    .map(Number)
    .desc('number');
    
function token(parser) {
  return parser.skip(P.optWhitespace);
}

這裡的 token 是個一產生新 parser 的小工具。他會產生一個「 parse 我們要的東西，並且忽略後面任意空白」的新 parser 。

接著處理欄位參考，參考欄位的語法是 {field} ：

const Parser = P.createLanguage({
  str: () => string.map(Str),
  num: () => number.map(Num),
  field: () =>
    lbrace
      .then(symbol)
      .skip(rbrace)
      .map(Field),
});

// 省略 string 和 number

const lbrace = word('{');

const rbrace = word('}');

const symbol =
  token(P.regexp(/[a-zA-Z_-][a-zA-Z0-9_-]*/))
    .desc('symbol');
    
function word(str) {
  return P.string(str).thru(token);
}

word 也是一個產生新 parser 的小工具，它產生一個「 parse 特定字串，再忽略後面任意數量的空白」的新 parser 。

lbrace.then(symbol).skip(rbrace).map(Field) 用中文講就是：「先拿一個左括號，接著拿一個 symbol （並且不要左括號，把 symbol 當成結果），再跳過一個右括號，最後把結果變成一個 Field node 」。

有了這些 parser 後，我們可以告訴 createLanguage 說，我們的 expression parser expr 是由 num, str 和 field 這三種 term parser 組出來的：

const Parser = P.createLanguage({
  expr: (r) =>
    P.alt(
      r.field,
      r.num,
      r.str,
    ).thru(parser => P.optWhitespace.then(parser)),
  str: () => string.map(Str),
  num: () => number.map(Num),
  field: () =>
    lbrace
      .then(symbol)
      .skip(rbrace)
      .map(Field),
});

用白話讀起來就是：「 expr 的開頭會有任意數量的空白，接著可能是 field, num, str 三種東西其中一種」。

Binary operator

binary operator 比較難處理，例如我們會希望可以做到「先乘除後加減」，同時又得知道遇上 str, num 或 field 時，就不用再看它們是不是一個有著 binary operator 的式子：

const Parser = P.createLanguage({
  expr: (r) =>
    P.alt(
      r.binary,
      r.field,
      r.num,
      r.str,
    ).thru(parser => P.optWhitespace.then(parser)),
  str: () => string.map(Str),
  num: () => number.map(Num),
  field: () =>
    lbrace
      .then(symbol)
      .skip(rbrace)
      .map(Field),
  binary: (r) => {
    const notBinary = P.alt(r.func, r.field, r.listField, r.num, r.str);
    const base = lparenthesis.then(r.binary).skip(rparenthesis).or(notBinary);
    return [
      [binaryLeft, [word('*'), word('/')]],
      [binaryLeft, [word('+'), word('-')]],
    ].reduce(
      (acc, [parser, ops]) => parser(P.alt(...ops), acc),
      base,
    );
  },
});

const lparenthesis = word('(');

const rparenthesis = word(')');

function binaryLeft(operator, operand) {
  return P.seqMap(
    operand,
    P.seq(operator, operand).many(),
    (first, rest) =>
      rest.reduce((left, [op, right]) => Binary(op, left, right), first),
  );
}

於是先準備一個 helper function binaryLeft ，它會幫我們產生「左結合的 binary operator parser 」。

接著再用 reduce 組合出：「先 parse 加減，再 parse 乘除，最後 parse 其他東西或者用 () 包起來的自己」這樣的 parser 。

這個順序是從外往內看，和一般講的「先乘除後加減」相反。但從 reduce 裡面看，可以看到我們是從 base 這個 parser 開始，先和乘除 parser 組合起來，再和加減 parser 組合起來，由內往外組合。

再把 r.binary 加到 expr parser 的最前面，希望我們的 parser 先試試看 binary operator parser 。

最後暴露一個 function parse 把 Parser 包裝起來，就能讓人使用我們的 parser 了：

export function parse(str) {
  return Parser.expr.tryParse(str);
}

小結

現在我們知道該怎麼用 parsimmon 組合出想要的 parser ，也知道怎麼從小 parser 組合出大 parser 了。