Parser 小學校：傳來傳去的一級公民

幾年前，科幻作家姜峯楠的短篇小說《你一生的故事》改編成了電影《異星入境》。故事中提到沙皮爾-沃爾夫假說，沙皮爾-沃爾夫假說認為，語言決定了人的世界觀與認知能力。

雖然假說終究是假說，但在寫程式時，用不同的方式描述問題，常常可以幫助我們改變看問題的角度。

大家老是說 JavaScript 的函數是一級函數 (first-class function) ，到底把函數傳來傳去，可以給我們怎樣的新觀點？

簡單的 CSV

今天有一張 CSV ，內容是：

Death Stranding, 1790, Kojima Productions
Grand Theft Auto V, 1299, Rockstart North
Valheim, 318, Iron Gate AB

我們可以很方便地用正規表達式 (regular expression) 一行一行處理：

const [, name, price, developer] =
  /s*([^,]*)\s*,\s*(\d*)\s*,\s*([^,]*)\s*/.exec(line);
const result = { name, price, developer };

但正規表達式常常得按需求重寫。有沒有什麼方法能做出一種可以組合的工具，來幫我們處理字串？

Parser ，處理字串的函數

如果我們只關心輸入和輸出，那一個 parser 可以簡單看成一個「吃字串、吐出結果和剩下的字串」的函數。

用 TypeScript 描述起來長這樣：

type Option<T> = T | undefined;
type Parser<T> = (input: string) => [Option<T>, string];

第一個 parser

我們可以這樣實作一個函數，幫我們生出「取得某個字串 s 的 parser 」：

const str
    : (s: string) => Parser<string>
    = (s) => (input) => {
        if (input.startsWith(s)) return [s, input.slice(s.length)];
        return [, input];
    };

要是成功看見了字串 s ，就會得到 s 和剩下來的字串。要是沒拿到 s ，則會得到 undefined 和原封不動的 input 。

用起來像這樣：

let result: Option<any>;
let rest: string = '';

const foo = str("foo");
[result, rest] = foo("foobar");
console.log(result, rest); // "foo", "bar"

字串與數字

為了要處理 "Death Stranding" 和 1790 這種字串，還得做出可以處理英文字的 parser 跟可以處理數字的 parser 。

先準備一個可以處理特定範圍內的字元的 range ：

const range
    : (begin: number, end: number) => Parser<string>
    = (begin, end) => (input) => {
        let i = 0;
        while(i < input.length) {
            const code = input.charCodeAt(i);
            if (code < begin || end < code) break;
            ++i;
        }
        if (i === 0) return [, input];
        return [input.slice(0, i), input.slice(i)];
    };

接著就能做出處理英文的 word parser 和處理數字的 digits parser ：

const word = range("A".charCodeAt(0), "z".charCodeAt(0));

[result, rest] = word("foobar2000");
console.log(result, rest); // "foobar", "2000"

const digits = range("0".charCodeAt(0), "9".charCodeAt(0));

[result, rest] = digits("1984DEC10");
console.log(result, rest); // "1984", "DEC10"

連接數個 parser

為了要處理任意數量的英文字，還需要一個「能串起數個 parser 」的 seq ：

const seq
    : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<[T, U]>
    = (pa, pb) => (input) => {
        const [a, rest0] = pa(input);
        if (a === undefined) return [, input];
        const [b, rest1] = pb(rest0);
        if (b === undefined) return [, input];
        return [[a, b], rest1];
    };

實作 seq 時，可以注意到，我們常常判斷 parser 跑完後的結果是成功還是失敗。

如果有一組函數，可以幫我們處理這件事，讓 parser 失敗時，自動傳回 [, input] ，其他時候再交給我們判斷，組合 parser 的時候就更輕鬆了。

這樣的一組函數通常叫做 pure 和 bind ：

const pure
    : <T>(x: T) => Parser<T>
    = (x) => (input) => [x, input];

const bind
    : <T, U>(pa: Parser<T>, f: (x: T) => Parser<U>) => Parser<U>
     = (pa, f) => (input) => {
         const [a, rest] = pa(input);
         if (a === undefined) return [, input];
         const pb = f(a);
         return pb(rest);
     };

接著可以用 pure 和 bind 做看看後面會用到的 seq3 和 seq5 ：

const seq3
    : <T, U, V>(pa: Parser<T>, pb: Parser<U>, pc: Parser<V>) => Parser<[T, U, V]>
    = (pa, pb, pc) =>
        bind(pa, (a) =>
          bind(pb, (b) =>
            bind(pc, (c) => pure([a, b, c]))));

const seq5
    : <T, U, V, W, X>(pa: Parser<T>, pb: Parser<U>, pc: Parser<V>, pd: Parser<W>, pe: Parser<X>) => Parser<[T, U, V, W, X]>
    = (pa, pb, pc, pd, pe) =>
        bind(seq3(pa, pb, pc), ([a, b, c]) =>
            bind(seq(pd, pe), ([d, e]) => pure([a, b, c, d, e])));

有時候我們也想直接替換結果，所以我們還會準備一個給 parser 用的 map ：

const map
    : <T, U>(pa: Parser<T>, f: (x: T) => U) => Parser<U>
    = (pa, f) => (input) => {
        const [a, rest] = pa(input);
        if (a === undefined) return [, input];
        return [f(a), rest];
    };

您能用 bind 實現更簡單的的 map 嗎？

現在我們可以一次串起好幾個 parser 了：

const fullname = seq3(word, str(" "), word);

[result, rest] = fullname("Isaac Huang");
console.log(result, rest); // ["Isaac", " ", "Huang"], ""

不定數量的 parser

我們還需要一種用來取「零個或一個東西」的 parser ，才好做出組合任意數量 parser 的函數：

const zeroOrOne
    : <T>(pa: Parser<T>) => Parser<[] | [T]>
    = (pa) => (input) => {
        const [a, rest] = pa(input);
        if (a === undefined) return [[], input];
        return [[a], rest];
    };

接著就能做出將一個 parser 重複很多次的 many ：

const many
    : <T>(pa: Parser<T>) => Parser<T[]>
    = (pa) => bind(zeroOrOne(pa), (xs) =>
        xs.length === 0
            ? pure(xs)
            : bind(many(pa), (ys) => pure([...xs, ...ys])));

還有靠一個 parser 分隔另外一個 parser 的 sepBy ：

const skip
    : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<T>
    = (pa, pb) => bind(pa, (a) => bind(pb, (_) => pure(a)));

const skipFirst
    : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<U>
    = (pa, pb) => bind(pa, (_) => bind(pb, (b) => pure(b)));

const sepBy
    : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<T[]>
    = (pa, pb) => bind(zeroOrOne(pa), (xs) =>
        xs.length === 0
            ? pure(xs)
            : bind(many(skipFirst(pb, pa)), (ys) => pure([...xs, ...ys])));

CSV parser

現在我們可以處理不定數量英文單字的產品名稱和開發商名稱了：

const concat = (xs: string[]) => xs.join("");
const spaces = map(many(str(" ")), concat);
const productName = map(sepBy(word, spaces), (xs) => xs.join(" "));
const developerName = productName;

[result, rest] = productName("Valheim, 318");
console.log(result, rest); // "Valheim", ", 318"
[result, rest] = productName("Death Stranding, 1790");
console.log(result, rest); // "Death Stranding", ", 1790"

也可以處理價格：

const price
    : Parser<number>
    = map(digits, (str) => parseInt(str, 10));

把這些 parser 串起來，就成了 product parser ：

const comma = skip(str(","), spaces);
const product = map(
    seq5(productName, comma, price, comma, developerName),
    ([product, _, price, __, developer]) => ({ product, price, developer }),
);

再處理斷行：

const newline = str("\n");
const productList = sepBy(product, newline);

至此就完成了我們的 CSV parser ：

const csv = `Death Stranding, 1790, Kojima Productions
Grand Theft Auto V, 1299, Rockstart North
Valheim, 318, Iron Gate AB`;

[result, rest] = productList(csv);
console.table(result);

小結

弄了半天，竟然只能做到幾行正規表達式就能做的事！

但在過程中，我們可以看見怎樣靠型別來描述複雜的行為，也見識到怎麼組合小工具來做出更複雜的工具。

這些製作 parser 的函數，都是一個個「靠自己的參數，就能把事情做完」的函數，像這樣不捕捉外界其他值的函數，又被稱為組合子 (combinator) ，本文正是帶大家實作了簡單的 parser combinator 。

未來有機會介紹 FormEditor 計算欄位時，我們還會看到它們的身影。