---
tags: PLT
---
# Parser 小學校：傳來傳去的一級公民
幾年前，科幻作家姜峯楠的短篇小說《你一生的故事》改編成了電影《異星入境》。故事中提到沙皮爾-沃爾夫假說，沙皮爾-沃爾夫假說認為，語言決定了人的世界觀與認知能力。
雖然假說終究是假說，但在寫程式時，用不同的方式描述問題，常常可以幫助我們改變看問題的角度。
大家老是說 JavaScript 的函數是一級函數 (first-class function) ，到底把函數傳來傳去，可以給我們怎樣的新觀點？
## 簡單的 CSV
今天有一張 CSV ，內容是：
```csv=
Death Stranding, 1790, Kojima Productions
Grand Theft Auto V, 1299, Rockstart North
Valheim, 318, Iron Gate AB
```
我們可以很方便地用正規表達式 (regular expression) 一行一行處理：
```javascript=
const [, name, price, developer] =
/s*([^,]*)\s*,\s*(\d*)\s*,\s*([^,]*)\s*/.exec(line);
const result = { name, price, developer };
```
但正規表達式常常得按需求重寫。有沒有什麼方法能做出一種可以組合的工具，來幫我們處理字串？
## Parser ，處理字串的函數
如果我們只關心輸入和輸出，那一個 parser 可以簡單看成一個「吃字串、吐出結果和剩下的字串」的函數。
用 TypeScript 描述起來長這樣：
```typescript=
type Option<T> = T | undefined;
type Parser<T> = (input: string) => [Option<T>, string];
```
### 第一個 parser
我們可以這樣實作一個函數，幫我們生出「取得某個字串 `s` 的 parser 」：
```typescript=
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` 。
用起來像這樣：
```typescript=
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` ：
```typescript=
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 ：
```typescript=
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` ：
```typescript=
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` ：
```typescript=
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` ：
```typescript=
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` ：
```typescript=
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];
};
```
:::info
您能用 `bind` 實現更簡單的的 `map` 嗎？
:::
現在我們可以一次串起好幾個 parser 了：
```typescript=
const fullname = seq3(word, str(" "), word);
[result, rest] = fullname("Isaac Huang");
console.log(result, rest); // ["Isaac", " ", "Huang"], ""
```
### 不定數量的 parser
我們還需要一種用來取「零個或一個東西」的 parser ，才好做出組合任意數量 parser 的函數：
```typescript=
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` ：
```typescript=
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` ：
```typescript=
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
現在我們可以處理不定數量英文單字的產品名稱和開發商名稱了：
```typescript=
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"
```
也可以處理價格：
```typescript=
const price
: Parser<number>
= map(digits, (str) => parseInt(str, 10));
```
把這些 parser 串起來，就成了 `product` parser ：
```typescript=
const comma = skip(str(","), spaces);
const product = map(
seq5(productName, comma, price, comma, developerName),
([product, _, price, __, developer]) => ({ product, price, developer }),
);
```
再處理斷行：
```typescript=
const newline = str("\n");
const productList = sepBy(product, newline);
```
至此就完成了我們的 CSV parser ：
```typescript=
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 計算欄位時，我們還會看到它們的身影。
Sign in with Wallet
Connect another wallet