プログラミング言語などのコンピュータ言語を構文解析するパーサコンビネータを TypeScript で作ってみようと思います。既存のパーサライブラリは使用せず、すべて自作します。パーサコンビネータを実装した後、四則演算の式パーサや JSON パーサを作ってみます。

書いてみると、意外と簡単です。「関数型言語」という言葉に謎にビビっている人もレッツトライ。

パーサコンビネータとは

小さなパーサ関数を組み合わせる (コンビネーション) ことで、複雑な構文を解析することができます。

関数をゴリゴリ組み合わせて大きなパーサを組み立てます。プログラミング言語に、第一級関数 (関数本体を引数として渡したり、戻り値として返せる性質) のサポートがあるなら、パーサコンビネータで構文解析をすることができます。 JavaScript にはもちろん第一級関数のサポートがあります。

Haskell などの関数型言語を習得しておくと、より理解が深まると思います (楽しいですよ) 。

プロジェクトの構成

言語は TypeScript を使います。 TypeScript で書くので、型をなるべくガチガチに定義します。

また、本プロジェクトはテスト駆動開発で進めます。テストフレームワークとして、 Jest を使います。テストケースは使い方を記したドキュメントにもなります。テストを一旦飛ばして実装から先に見ても構いません。

プロジェクトの作成

早速プロジェクトを作りましょう。

$ mkdir parser-combinator
$ cd parser-combinator
$ npm init -y

TypeScript をインストールして設定します。

$ npm i -D typescript
$ npx tsc --init

tsconfig.json を編集して、 TypeScript コンパイラを設定しておきます。

tsconfig.json
{
  "compilerOptions": {
    // ...
    "target": "es2015",  // 今時 ES2015 に対応していないブラウザなんて無いと信じたい (青色の "e" の字を脳内に浮かべながら)
    "outDir": "./dist",  // 出力先ディレクトリ
    // ...
  }
}

続いて、 Jest をインストールして設定します。

$ npm i -D jest ts-jest @types/jest

package.json を編集して、 test スクリプトの設定と Jest の設定を追加します。

package.json
{
  // ...
  "scripts": {
    "test": "jest"
  },
  "jest": {
    "preset": "ts-jest",
    "testPathIgnorePatterns": ["<rootDir>/dist/"]
  },
  // ...
}

その他 Git や ESLint などの設定は各自で行ってください。

TypeScript のおさらい

JavaScript を使って開発をしているとき、こんなことを考えたことはありますでしょうか。

  • 「この関数は文字列を返してくるけど、 undefined を返してくる可能性もあったっけ。調べるの面倒だな」
  • 「このオブジェクトに必要なメンバは何だったっけ。調べるの面倒だな」
  • 「また TypeError: undefined is not a function だ。どこで undefined が紛れ込んだんだ。しんどい」

そんな人は TypeScript を使ったほうが良いです。筆者は、中規模以上の Web 開発で TypeScript は必須だと考えています。型をちゃんと付けておくことで、後々開発者が楽できる場面が多くなるからです。 IDE のサポートも最大限受けられます。

この節では、 TypeScript の重要な機能をおさらいします。ここでは簡易的な説明に留めておきますので、 TypeScript を詳しく理解するために各種ドキュメントを読むことをおすすめします。 TypeScript の型システムをよく理解している人はこの節をスキップしても OK です。

TypeScript は、 TS Playground を使うことで Web ブラウザ上で簡単に試すことができます。 TypeScript のトランスパイル結果をリアルタイムに確認することができます。 TS Playground のエディタは Visual Studio Code で使われている Monaco Editor であり、マウスカーソルを乗せるとツールチップが出て型を調べたりすることができます。

TypeScript の概要

TypeScript は、静的型付けできる JavaScript です。派生型は構造的部分型 (Structural Subtyping) の方式をとっています。 TypeScript ファイル *.ts をトランスパイル (コンパイル) して JavaScript ファイル *.js を生成します。本記事とは関係ありませんが、 React で使用される JSX 構文もサポートしています。

TypeScript は JavaScript のスーパーセットです。つまり、 JavaScript のコードはそのまま TypeScript のコードとすることができます。言い換えると、 TypeScript は JavaScript に静的型付け構文を追加した上位互換の言語となっています。

TypeScript のトランスパイル

TypeScript ファイルを JavaScript ファイルにトランスパイルするには、 typescript パッケージを npm なり yarn なりでインストールした後、 npx tscyarn tsc することで行うことができます。デフォルトでは、 *.ts ファイルは同じディレクトリの *.js ファイルへトランスパイルされます。 tsconfig.json ファイルを使用するか、コマンドラインオプションを指定することで、出力先ディレクトリを変更することができます。

TypeScript で型の検査に失敗してトランスパイルエラーとなっても、 JavaScript ファイルは構わず出力されます (出力は型情報を消し去るだけなので) 。

型を書く

以下のコードは、型を書いていない TypeScript コードです。 JavaScript コードでもあります。

const add_one = n => n + 1;
const ans = 42;

console.log(add_one(ans));

これに型の記述を追加すると、以下のようになります。

const add_one = (n: number): number => n + 1;
const ans: number = 42;

console.log(add_one(ans));

変数名や引数名の後に : と型を書きます。関数の戻り値は引数の ( ) の後に書きます。

以下のように、型が一致していない場合はトランスパイルエラーとなります (JavaScript ファイルは出力されます) 。

const ans: boolean = 42;

型を省略した場合、型が推論され自動的に適切な型になります。自動的に推論できない場合は、後述する any 型となります。

基本的な型

TypeScript の基本的な型を以下に示します。

プリミティブ

  • string: 文字列
  • number: 数値
  • boolean: 論理値

nullundefined

  • null: null
  • undefined: undefined

void

関数の戻り値がない場合は void 型を指定します。

配列

T[] もしくは Array<T> とすると、要素の型が T である配列の型を表します。

const array: number[] = [1, 2, 3, 4, 5];

// Type 'null' is not assignable to type 'string'.
// Type 'undefined' is not assignable to type 'string'.
const badArray: Array<string> = ['hoge', 'fuga', null, undefined];

タプル

配列の要素数と要素の型の位置が決まっている型をタプル型として定義することができます。

const numStrNum: [number, string, number] = [123, 'hello', 42];

値に過不足があってはいけませんし、値の型が不一致でもいけません。トランスパイルエラーとなります。

// Type 'number' is not assignable to type 'string'.
// Type 'string' is not assignable to type 'number'.
const numStrNum: [number, string, number] = [123, 42, 'hello'];

タプルの実態は配列ですが、配列よりも制約が厳しい型です。

any

any は何でも入る型です。 JavaScript との後方互換性のためにあるような型で、 TypeScript の利点をすべてぶっ壊してしまうので、基本的に使ってはいけません。後述する unknown 型をなるべく使うようにしましょう。 noImplicitAny (strict のうちの一部) オプションが有効の場合、暗黙的な any はトランスパイルエラーとなります。

オブジェクト

オブジェクトの型は、メンバ名とその型を {} で囲んで定義することができます。以下のように定義することができます。

const coord: { x: number; y: number; } = { x: 123, y: 42 };

この場合、 coordnumber 型の xnumber 型の y をメンバに持つオブジェクト型を表します。

interface を使うことで、オブジェクト型に名前をつけることができます。

interface Coordinate {
  x: number;
  y: number;
}

const coord: Coordinate = { x: 123, y: 42 };

関数型

関数の引数と戻り値の型を定義することができます。

const func: (a: number) => number = a => a * 42;

(a: number) => number の部分が関数型となります。 1 つの number 型引数をとり、 number 型の値を返す関数です。

type を使うことで、関数型に名前をつけることができます。

type MyFunc = (a: number) => number;
const func: MyFunc = a => a * 42;

列挙型

正直使わん。

高度な型

Intersection Types

複数の型のメンバを 1 つの型に統合することができます。

interface MyFirstType {
  x: string;
}
interface MySecondType {
  y: number;
}

const f = (obj: MyFirstType & MySecondType): void => {
  console.log(`x is ${obj.x}, y is ${obj.y}`);
};

T & U とすると、型 T と型 U の両方のメンバをもつ型とすることができます。

Union Types

複数の型のうちどれか 1 つの型であれば良い場合に使用します。

const printStrOrNum = (value: string | number): void => {
  console.log(value);
};

printStrOrNum('hello');
printStrOrNum(123);

// Argument of type 'boolean' is not assignable to parameter of type 'string | number'.
printStrOrNum(false);

T | U とすると、型 T もしくは型 U を受け入れます。

Union Types を使用する際、型を判別しなければならない場合があります。

const printStrOrNum = (value: string | number): void => {
  // Property 'toUpperCase' does not exist on type 'string | number'. Property 'toUpperCase' does not exist on type 'number'.
  console.log(value.toUpperCase());
};

typeof で判別する if 文などを書けば、自動的に型を絞り込むことができます。

const printStrOrNum = (value: string | number): void => {
  if (typeof value === 'string') {
    // ここで value は string 型
    console.log(value.toUpperCase());
  } else {
    // ここで value は number 型
    console.log(value);
  }
};

型を判別する関数 (User-Defined Type Guards) を自前で定義して、型を絞り込むこともできます。

型エイリアス

関数型の節で紹介しましたが、 type を使うことで型に別名をつけることができます。 C 言語でいう typedef です。

type StringOrNumber = string | number;

リテラル型

string 型と number 型と boolean 型に関して、リテラル型を定義することができます。リテラル型は、指定された値しか入らない型です。

const hellostr: 'hello' = 'hello';
const one: 1 = 1;

hellostr には 'hello' しか代入できないし、 one には 1 しか代入することができません。他の値は代入できません。

// Type '"world"' is not assignable to type '"hello"'.
const hellostr: 'hello' = 'world';

// Type '42' is not assignable to type '1'.
const one: 1 = 42;

リテラル型の使い方として、 string のリテラルを列挙型として使うことがよくあります。

type Direction = 'north' | 'south' | 'east' | 'west';

const d: Direction = 'north';

// Type '"hello"' is not assignable to type 'Direction'.
const bad: Direction = 'hello';

また、オブジェクト型と Union Types を合わせることで、タグ付き Union (判別共用体) を実現することができます。

interface SomeString {
  status: 'some';
  value: string;
}
interface None {
  status: 'none';
}
type OptionString = SomeString | None;

型の絞り込みもできます。

const optionStringOrDefault = (opt: OptionString, def: string): string => {
  if (opt.status === 'some') {
    return opt.value;
  } else {
    return def;
  }
}

never

ありえない状態での型は never 型となります。先程の OptionString 型での例を見てみます。

const optionStringOrDefault = (opt: OptionString, def: string): string => {
  if (opt.status === 'some') {
    return opt.value;
  } else if (opt.status === 'none') {
    return def;
  } else {
    // opt.status の全パターンが調べられているため、
    // ここに来ることはありえず、 opt は never 型となる
    // この関数の戻り値の型は string であるが、型エラーとならない
    return opt;
  }
}

特殊な型を扱うとき never 型を直接扱う場合があります。

unknown

unknown 型は any と同様何でも入る型ですが、型を絞り込まないと値を使うことができません。 any より型安全です。

const printType = (value: unknown) => {
  if (typeof value === 'string') {
    console.log('type of value is string');
    console.log(`upper case is ${value.toUpperCase()}`);
  } else if (typeof value === 'number') {
    console.log('type of value is number');
    console.log(`doubled value is ${value * 2}`);
  } else {
    console.log('other type');
  }
};

ジェネリクス

関数型やオブジェクト型などで型パラメータを定義することができます。デフォルトの型も指定できます。

interface GenericObject<T, U = number> {
  hoge: T;
  piyo: U;
  fuga: boolean;
}
type RepeatFunc<T> = (a: T) => [T, T];

extends を使用することで、型パラメータに制約を加えることができます。

type Duplicate<T extends string> = [T, T];

// MyType is ['hello', 'hello']
type MyType = Duplicate<'hello'>;

// Type 'number' does not satisfy the constraint 'string'.
type MyBadType = Duplicate<1>;

typeof

変数に対して typeof を使用すると、変数の型を取得することができます。

const hoge = 123 + 456;

// HogeType is number
type HogeType = typeof hoge;

keyof

オブジェクト型のキーを列挙して string のリテラル型 (と symbolnumber) の Union Types にしてしまう演算子です。

interface Point {
  x: number;
  y: number;
}

// PointKeys is 'x' | 'y'
type PointKeys = keyof Point;

Lookup Types

オブジェクト型の特定のメンバの型を取得することができます。

interface Item {
  name: string;
  price: number;
}

// ItemPrice is number
type ItemPrice = Item['price'];

// ItemNameOrPrice is string | number;
type ItemNameOrPrice = Item['name' | 'price']

Mapped Types

Union Types に対して map 関数的な処理を行い、新しい型を生成することができます。

interface Item {
  name: string;
  price: number;
}

// ItemKeys is 'name' | 'price'
type ItemKeys = keyof Item;

// StringifiedItem is { name: string; price: string; };
type StringifiedItem = { [K in ItemKeys]: string; };

Conditional Types

extends と三項演算子を使って型を分岐させることができます。

type IsString<T> = T extends string ? true : false;

// A is true
type A = IsString<string>;

// B is true
type B = IsString<'hello'>;

// C is false
type C = IsString<number>;

extends の条件に合う場合、 ? 直後の型に、条件に合わない場合は : 直後の型に分岐します。

infer

Conditional Types 中で infer キーワードを使うと、型をキャプチャして後で使うことができます。

interface Box<T> {
  value: T;
}
type BoxType<T> = T extends Box<infer U> ? U : never;

type BoxedString = Box<string>;

// A is string
type A = BoxType<BoxedString>;

// B is never
type B = BoxType<number>;

Variadic Tuple Types

タプル型に対してスプレッド構文を適用できます。

type RepeatTuple<T extends unknown[]> = [...T, ...T];

// A is [number, string, boolean, number, string, boolean]
type A = RepeatTuple<[number, string, boolean]>;

組み込みの型関数

上記の機能を活用した型が TypeScript に組み込まれています。その一部を紹介します。

lib.es5.d.ts
// Union Types である T から U を抽出する
type Extract<T, U> = T extends U ? T : never;

// Union Types である T から U を取り除く
type Exclude<T, U> = T extends U ? never : T;

// オブジェクト型 T からキー K であるものを抽出する
type Pick<T, K extends keyof T> = { [P in K]: T[P]; };

// オブジェクト型 T からキー K であるものを削除する
type Omit<T, K extends keyof any> = Pick<T, Exclude<keyof T, K>>;

// 関数型 T の引数の型をタプルとして取得する
type Parameters<T extends (...args: any) => any> = T extends (...args: infer P) => any ? P : never;

// 関数型 T の戻り値の型を取得する
type ReturnType<T extends (...args: any) => any> = T extends (...args: any) => infer R ? R : any;

他にも色々あります。

その他

最近 Template Literal Types が入り、文字列型に革命が起きました。この記事では使わないので説明は省略しますが、なかなかヤバい機能なのでぜひ調べてみてください。 SQL や GraphQL のクエリ文字列を表したリテラル型をパースして、クエリ結果の型安全なオブジェクト型を生成するといった試みがあります (ヤバい) 。

ちなみに TypeScript の型システムはチューリング完全らしいです。

関数のおさらい

パーサコンビネータを書くには、 JavaScript の関数の仕様や、カリー化と部分適用をしっかり理解している必要があります。理解が完璧な人はこの節をスキップしても OK です。

関数宣言と関数式

関数宣言で関数を作成するには、以下のように書きます。

function add_one(n: number): number {
  return n + 1;
}

関数宣言ではなく、関数式で関数を作成することもできます。

const add_one = function(n: number): number {
  return n + 1;
};

関数式では、名前の無い関数 (無名関数) を作成し、それを変数へ割り当てています。

どちらの場合も、以下のように呼び出すことができます。

add_one(42)  // => 43

関数宣言と関数式は、関数が巻き上げられる (Hoisting) かどうかが違います。

関数宣言は巻き上げられるため、宣言位置より前で使用できます。

hoisted(42)  // => 43

function hoisted(n: number): number {
  return n + 1;
}

一方、関数式は巻き上げられないため、宣言位置より前で使用できません。

notHoisted(42)  // ReferenceError: Cannot access 'notHoisted' before initialization

const notHoisted = function(n: number): number {
  return n + 1;
};

他の関数を相互に参照する場合 (相互再帰) などは、後に宣言された関数を使用するために関数宣言を使用する必要があります。

// 関数 a は関数宣言でも関数式でも良い
function a(x: number): number {
  if (x <= 1) return 1;
  return b(x + 2);      // 後に定義されている関数 b を参照
}

// 関数 b は後方参照されるため関数宣言である必要がある
function b(x: number): number {
  return a(x - 3) + 4;  // 前に定義されている関数 a を参照
}

関数式の書き方

関数式は、 2 通りの書き方があります。まずは function キーワードでの定義です。

const add_one = function(n: number): number {
  return n + 1;
};

add_one(42)  // => 43

もう一つはアロー関数です。

const add_one = (n: number): number => {
  return n + 1;
};

add_one(42)  // => 43

アロー関数が単一の式を返す場合、中括弧 { }return は省略可能です。

const add_one = (n: number): number => n + 1;

アロー関数は function と比べて

  • 関数式としてのみ書ける (無名関数のみ書ける)
  • 記述量が減る
  • this の束縛不可 (レキシカルスコープの this となる)

といった特徴があります。 Function.prototype.bind()this を変更されることが想定される場合は function を用いて関数定義する必要があります。 JavaScript を使う以上 this への理解はほぼ必須ですが、パーサコンビネータで this は使わないので今回はスルーで OK です。

関数に関数を渡す

関数の引数に、別の関数本体を渡すことができます。

const calc_two_values = (f: (a: number, b: number) => number): number => f(123, 456);

calc_two_values 関数では、引数 f を持っています。

f(a: number, b: number) => number 型です。これは、 number 型の引数を 2 つ持ち、 number 型を返す関数型です。この型に合致する関数は何でも渡すことができます。

この f123456 を渡した結果を calc_two_values 関数の最終的な戻り値として返しています。

では calc_two_values 関数を使ってみましょう。

const add = (a: number, b: number): number => a + b;

calc_two_values(add)  // => 579

関数 add を定義して、 calc_two_values に渡しています。結果、 123 + 456 が実行され、 579 が返ってきます。

通常は add なんかを別に定義せず、関数本体を直接書いてしまうことが多いです。

calc_two_values((a, b) => a + b)  // => 579

関数に関数を渡すことで、関数の挙動を外からカスタマイズすることができるようになります。今回は足し算する関数を渡しましたが、型が合っていれば引き算だろうと何だろうと任意の関数を渡してしまうことができます。

身近な例として、配列の filter 関数や sort 関数の挙動をカスタムするなどの使用例があります。

[1, 2, 3, 4, 5].filter(n => n % 2 === 0).sort((a, b) => b - a)  // => [4, 2]

関数から関数を返す

関数から、別の関数本体を返すことができます。

const logger = (): (str: string) => void => {
  return (str: string): void => console.log('[log] ' + str);
};

logger 関数は、「 string の値を渡すと、その値の前に [log] とつけて console.log する関数」を返す関数です。この字面だと分かりにくすぎるので、使用例を見てみましょう。

const mylog = logger();  // ここで mylog には関数が入っている
mylog('Hello');          // [log] Hello

logger 関数を呼び出して、返ってきた関数本体 (str: string): void => console.log('[log] ' + str)mylog に格納しています。これを呼ぶと [log] が先頭に付加されて console.log されます。

この例ではあまりうま味が無いですが、後述のカリー化の例でとってもおいしくなります。

カリー化

まず、 2 つの値を足し算する関数 add を考えましょう。普通に書いたらこうなります。

const add = (a: number, b: number): number => a + b;

引数を 2 つ取るシンプルな関数です。この関数の使い方は書くまでもありませんが、一応書いておきます。

add(1, 42)  // => 43

add 関数をカリー化した関数 cadd はこうなります。

const cadd = (a: number) => (b: number): number => a + b;

引数の書き方が変わりました。これが関数のカリー化です。一番右側の a + b の部分は変わっていません。

これをもう少し分かりやすく冗長に書くとこうなります。

const cadd = (a: number) => {
  return (b: number): number => {
    return a + b;
  };
};

cadd 関数を呼び出すと、関数が返ってきます。それをまた呼び出すと、加算された値が返ってきます。使い方は以下の通りです。

cadd(1)(42)  // => 43

呼び出し方が変わりました。何の意味があるのかこの時点では分からないと思いますが、次節の部分適用が容易になるという利点があります。

部分適用

add 関数では、呼び出し時に引数を 2 つ同時に指定しないといけません。

add(1, 42)  // 1 と 42 を同時に指定しなければいけない

引数の一部をあらかじめ指定しておきたいときは、新しい関数を書いてラップするか、 Function.prototype.bind() を使う必要があります。

const add_one = (b: number): number => add(1, b);

add_one(42)   // => 43
add_one(123)  // => 124

一方、カリー化した cadd 関数では、とても簡単に指定することができます。

const cadd_one = cadd(1);  // 最初の引数のみを指定し、 cadd_one 関数とする

cadd_one(42)   // => 43
cadd_one(123)  // => 124

引数の一部をあらかじめ指定しておく操作を部分適用と言います。なぜカリー化と部分適用を混同する人がいるのか

パーサコンビネータでは部分適用を頻繁に行うため、関数をカリー化しておくのが非常に有効です。

パーサ関数型の定義

すべての基礎となる、パーサ関数の型を定義しましょう。パーサ関数とは、文字列を入力し、入力の先頭から任意の長さの文字列を消費して、解析結果を出力する関数です。これはパーサコンビネータの重要な基礎です。

具体例を見てみましょう。整数を解析するパーサ関数を考えます。入力に 123456hoge という文字列を渡すと、先頭の 123456 を消費して、「データとして 123456 が取れました。残りは hoge です」という解析結果を出力します。

パーサ関数の型を定義するファイルを作っておきましょう。 src/types.ts に空のファイルを作っておきます。

$ mkdir src
$ touch src/types.ts

入力

まず、パーサの入力を具体的に定義しましょう。パーサに食わせるのは文字列になるわけですが、サロゲートなど JavaScript では文字列の扱いが少々厄介なので (そもそも厄介になったのは Unicode のせいですが) 、入力を単に string 型とするのはあまり良くないと思います。

"吉野家".length  // => 3
"𠮷野家".length  // => 4

文字列にスプレッド構文を適用して配列にすると、コードポイントごとに分割された配列が出来上がります。

[..."吉野家"]  // => ["吉", "野", "家"]
[..."𠮷野家"]  // => ["𠮷", "野", "家"]

これを入力の形式とした方がトラブりにくいと思いましたので、入力の型は string[] とします。 ParserInput 型として src/types.ts に定義しましょう。

src/types.ts
export type ParserInput = readonly string[];

出力

続いて出力です。解析結果が出力になるわけですが、まず解析が成功した場合と失敗した場合に分けて考えます。

解析が成功した場合、データ 1 つと、消費しきれなかった入力の残りの文字列が解析結果となります。データは string とは限りません。例えば、 truefalse という文字列の入力を解析して boolean 型をデータとするパーサ関数も考えられます。ですので、ジェネリクスを用いて定義することにします。

src/types.ts
interface ParseSuccess<T> {
  result: 'success';
  data: T;
  rest: ParserInput;
}

解析が失敗した場合、データもクソも無いので、シンプルな定義となります。

src/types.ts
interface ParseFail {
  result: 'fail';
}

これらを Union Types で合わせた ParserOutput を定義します。

src/types.ts
export type ParserOutput<T> = Readonly<ParseSuccess<T> | ParseFail>;

パーサ関数型

パーサ関数の型はこうなります。

src/types.ts
export type Parser<T> = (input: ParserInput) => ParserOutput<T>;

今後は、この型定義に従ってパーサ関数をどんどん書いていきます。

ユーティリティ型

パーサ型からデータ型を簡単に取り出せるように、 ParserData 型を定義しておきます。後でパーサコンビネータを書くときに役立ちます。

src/types.ts
export type ParserData<P> = P extends Parser<infer T> ? T : never;

使い方は以下の通りです。

type P = Parser<number>;

// X is number
type X = ParserData<P>;

パーサプリミティブ

まずは最小限のパーサ関数を定義します。

パーサ関数を定義するファイルと、単体テストを定義するファイルを作っておきましょう。 src/primitives.tssrc/primitives.test.ts に空のファイルを作っておきます。

$ touch src/primitives.ts
$ touch src/primitives.test.ts

任意の 1 文字パーサ

何でも良い 1 文字をパースするパーサ関数 anyChar を作ります。これは簡単です。

テスト

まずは Jest でテストを書きましょう。入力が 0 文字の場合、 1 文字の場合、それよりも多い場合でのテストを書きます。

src/primitives.test.ts
import { anyChar } from './primitives';
import type { ParserOutput } from './types';

describe('anyChar', () => {
  const parser = anyChar;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('1 character input', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: 'a',
      rest: []
    });
  });

  test('Many characters input', () => {
    const input = [...'hoge'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: 'h',
      rest: [...'oge']
    });
  });
});

describe は、テストをグループ化します。 test で、テストケースを定義します。 expectanyChar 関数の結果を渡して、 toEqual でオブジェクトの一致を確認します。 toEqual は再帰的にオブジェクトの一致を確認します。

入力が 0 文字だった場合、パーサが失敗するように書きました。

テストが書けたので、実行します。まだ本体を書いていないので絶対失敗します。

$ npm test

> parser-combinator@1.0.0 test
> jest

FAIL src/primitives.test.ts
  ● Test suite failed to run

    Cannot find module './primitives' from 'src/primitives.test.ts'

    However, Jest was able to find:
    	'./primitives.test.ts'

    You might want to include a file extension in your import, or update your 'moduleFileExtensions', which is currently ['js', 'json', 'jsx', 'ts', 'tsx', 'node'].

    See https://jestjs.io/docs/en/configuration#modulefileextensions-arraystring

    > 1 | import { anyChar } from './primitives';
        | ^
      2 | import type { ParserOutput } from './types';
      3 |
      4 | describe('anyChar', () => {

      at Resolver.resolveModule (node_modules/jest-resolve/build/index.js:306:11)
      at Object.<anonymous> (src/primitives.test.ts:1:1)

Test Suites: 1 failed, 1 total
Tests:       0 total
Snapshots:   0 total
Time:        0.913 s
Ran all test suites.

実装

それでは、 anyChar 関数を書きます。パーサ関数は Parser<T> 型であり、今回 Tstring であるので、 Parser<string> 型の anyChar を書きます。

src/primitives.ts
import type { Parser } from './types';

export const anyChar: Parser<string> = input => {
  const [data, ...rest] = input;
  return {
    result: 'success',
    data,
    rest
  };
};

先頭から 1 文字取得するパーサなので、分割代入とスプレッド構文を使用して、入力の最初の文字と残りを分けています。あとは return して終わりです。

ここで一度テストを実行してみましょう。

$ npm test

> parser-combinator@1.0.0 test
> jest

FAIL src/primitives.test.ts
  anyChar
    ✕ Empty input (6 ms)
    ✓ 1 character input (1 ms)
    ✓ Many characters input

  ● anyChar › Empty input

    expect(received).toEqual(expected) // deep equality

    - Expected  - 1
    + Received  + 3

      Object {
    -   "result": "fail",
    +   "data": undefined,
    +   "rest": Array [],
    +   "result": "success",
      }

       8 |     const input = [] as const;
       9 |     const output = parser(input);
    > 10 |     expect(output).toEqual<ParserOutput<string>>({
         |                    ^
      11 |       result: 'fail'
      12 |     });

      at Object.<anonymous> (src/primitives.test.ts:9:20)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 2 passed, 3 total
Snapshots:   0 total
Time:        2.065 s
Ran all test suites.

入力が 0 文字のケースにおいて失敗してしまいました。入力が 0 文字のときパーサは解析失敗するはずなのに、そのことを anyChar 関数内で考慮するのを忘れていました。

anyChar 関数を修正し、テストを再実行しましょう。

src/primitives.ts
 import type { Parser } from './types';

 export const anyChar: Parser<string> = input => {
+  if (input.length > 0) {
     const [data, ...rest] = input;
     return {
       result: 'success',
       data,
       rest
     };
+  }
+  return { result: 'fail' };
 };
$ npm test

> parser-combinator@1.0.0 test
> jest

PASS src/primitives.test.ts
  anyChar
    ✓ Empty input (2 ms)
    ✓ 1 character input
    ✓ Many characters input (1 ms)

Test Suites: 1 passed, 1 total
Tests:       3 passed, 3 total
Snapshots:   0 total
Time:        0.898 s, estimated 1 s
Ran all test suites.

テストが通りました。 anyChar 関数の実装は完了です。テスト駆動開発の雰囲気はこんな感じです。

末尾パーサ

今度は、入力が 0 文字のときに解析成功し、それ以外の場合は失敗するパーサ関数 eof を作ります。 EOF は End-of-file の略です。

解析の結果、出てくるデータは特に何もないので、パーサ関数の型は Parser<null> とします。

テスト

src/primitives.test.ts
import { anyChar, eof } from './primitives';

// ...

describe('eof', () => {
  const parser = eof;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: []
    });
  });

  test('1 character input', () => {
    const input = [..."a"];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'fail'
    });
  });
});

実装

src/primitives.ts
export const eof: Parser<null> = input => {
  if (input.length === 0) {
    return {
      result: 'success',
      data: null,
      rest: []
    };
  }
  return { result: 'fail' };
};

テストを実行して表示が緑になることを確認してください。

パーサ関数を生成する関数

ここからがパーサコンビネータの本領です。今まで実装した anyChareof だけでは正直使い物になりませんが、これから実装する関数を実装していくことで複雑なパーサを組めるようになります。

特定の 1 文字のみのパーサ

anyChar はどのような文字でもパースします。しかし、特定の文字でないといけない構文というのはほとんどの言語で存在します。例えば、 JSON においてオブジェクトのキー名や文字列は " で囲わないといけない、などがあります。

そこで、特定の文字のみパース成功するパーサ関数を考えます。このパーサ関数は、入力の配列と、パース対象の文字を引数として指定します。

しかし、パーサ関数型は引数を 1 つしか取りません。パーサ関数型の定義をもう一度見てみましょう。

src/types.ts
export type ParserInput = readonly string[];
export type Parser<T> = (input: ParserInput) => ParserOutput<T>;

パース対象の文字を指定する術がありません。そこで、関数をカリー化し、パース対象の文字のみ部分適用することで、パーサ関数の型を合わせることができます。言い換えると、パース対象の文字を渡すことで、パーサ関数を生成する関数 char() を定義します。

テスト

最初にテストを書きます。 src/char.test.ts を作成します。

src/char.test.ts
import { char } from './char';
import type { ParserOutput } from './types';

describe('char("a")', () => {
  const parser = char('a');

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'a'>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'a'>>({
      result: 'success',
      data: 'a',
      rest: []
    });
  });

  test('Input "A"', () => {
    const input = [...'A'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'a'>>({
      result: 'fail'
    });
  });

  test('Input "hoge"', () => {
    const input = [...'hoge'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'a'>>({
      result: 'fail'
    });
  });
});

char() 関数に特定の文字を渡すことで、パーサ関数を取得できるようにします。今回は 'a' を指定したことで、文字 a をパースするパーサ関数を取得しています。この場合、 [...'a'][...'abc'] はパース成功し、 [...'A'][] はパース失敗となります。

実装

src/char.ts に実装を書きます。 anyChar を import して利用しています。

src/char.ts
import { anyChar } from './primitives';
import type { Parser, ParserInput } from './types';

type CharFunc = <T extends ParserInput[0]>(c: T) => Parser<T>;
export const char: CharFunc = c => input => {
  const r = anyChar(input);
  if (r.result === 'fail') return r;
  if (r.data !== c) return { result: 'fail' };
  return {
    result: 'success',
    data: c,
    rest: r.rest
  };
};

まず、 char() 関数の型を CharFunc として定義します。アロー関数を定義するときに型パラメータを定義することができないので、 type を使用して事前に定義しています。

型パラメータ TParserInput[0] のサブタイプとなるよう制約を加えています。配列型に [0] と指定することで、配列の要素の型を取得することができます。 ParserInput 型は readonly string[] なので、 ParserInput[0] 型は string となります。

あとは、 char() 関数を定義するだけです。引数はカリー化されていて、 c => input => { ... } となっています。 c がパース対象の文字、 input はパーサの入力です。関数の処理内容は見たまんまだと思うので解説は省略します。

条件を満たす 1 文字のパーサ

char() 関数を一般化した is() 関数を作ります。 char() 関数は文字を引数に取りましたが、 is() 関数は「文字が条件を満たすかどうか判定する関数」を引数に取るようにします。

テスト

src/char.test.ts
import { char, is } from './char';

// ...

describe('is()', () => {
 describe('is(c => c === "a")', () => {
   const parser = is((c): c is 'a' => c === 'a');

   test('Empty input', () => {
     const input = [] as const;
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'a'>>({
       result: 'fail'
     });
   });

   test('Input "a"', () => {
     const input = [...'a'];
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'a'>>({
       result: 'success',
       data: 'a',
       rest: []
     });
   });

   test('Input "A"', () => {
     const input = [...'A'];
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'a'>>({
       result: 'fail'
     });
   });
 });

 describe('is(c => c === "0" || c === "1")', () => {
   const parser = is((c): c is '0' | '1' => c === '0' || c === '1');

   test('Empty input', () => {
     const input = [] as const;
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'0' | '1'>>({
       result: 'fail'
     });
   });

   test('Input "0"', () => {
     const input = [...'0'];
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'0' | '1'>>({
       result: 'success',
       data: '0',
       rest: []
     });
   });

   test('Input "1"', () => {
     const input = [...'1'];
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'0' | '1'>>({
       result: 'success',
       data: '1',
       rest: []
     });
   });

   test('Input "A"', () => {
     const input = [...'A'];
     const output = parser(input);
     expect(output).toEqual<ParserOutput<'0' | '1'>>({
       result: 'fail'
     });
   });
 });
});

describe() をネストして、グループ化しています。

is() 関数に (c): c is 'a' => c === 'a' といった関数を渡しています。これは User-Defined Type Guards という関数です。この関数の戻り値の型は c is 'a' となっており、引数 c'a' 型であることをプログラマによって保証する関数です。実際の関数の処理は boolean を返しているだけです。

今回は c is 'a'c is '0' | '1' の 2 種類をテストしています。

実装

src/char.ts
type IsFunc = <T extends string>(f: (c: ParserInput[0]) => c is T) => Parser<T>;
export const is: IsFunc = f => input => {
  const r = anyChar(input);
  if (r.result === 'fail') return r;
  if (!f(r.data)) return { result: 'fail' };
  return {
    result: 'success',
    data: r.data,
    rest: r.rest
  };
};

char() 関数とほぼ同様の処理を行なっています。 r.dataf を用いて判定しています。

これで、 1 文字を任意の条件を指定して柔軟にパースすることができるようになりました。

パーサコンビネータ

ここが肝です。パーサ関数を引数にとり、パーサ関数を変形したり合成する関数を作ります。言い換えると、パーサ関数に対して演算子を適用する関数を作ります。

not 演算子

パーサ関数を変形する関数として、否定演算をする not() 関数を作ります。

テスト

テストファースト。 src/combinators.test.ts を作成します。

src/combinators.test.ts
import { not } from './combinators';
import { char } from './char';
import type { ParserOutput } from './types';

describe('not(char("a"))', () => {
  const parser = not(char('a'));

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: []
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'fail'
    });
  });

  test('Input "A"', () => {
    const input = [...'A'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: [...'A']
    });
  });

  test('Input "hoge"', () => {
    const input = [...'hoge'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: [...'hoge']
    });
  });
});

char('a')not() で包んでいます。つまり、 a ではないなら成功するパーサ関数を作っています。

出力するデータは特に無いので、データ型は null です。また、入力の文字を 0 文字消費します。つまり、出力の残りは入力と一致します。

実装

src/combinators.ts に実装を書きます。

src/combinators.ts
import type { Parser } from './types'

type NotFunc = (p: Parser<unknown>) => Parser<null>;
export const not: NotFunc = p => input => {
  if (p(input).result === 'success') {
    return { result: 'fail' };
  } else {
    return { result: 'success', data: null, rest: input };
  }
};

not() 関数が受け取るパーサのデータ型は無視するので、 Parser<unknown> として引数を取るようにしています。 TypeScript を書くときは、可能なら any より unknown を使いましょう。

関数本体の処理は単純で、パーサ関数 p に入力を食わせて、成功と失敗を反転しています。三項演算子を使えば 1 つの式でも書けますが、見辛くなるので if 文を使用しています。

or 演算子

パーサ関数を合成する関数として、 or() 関数を作ります。この関数は、パーサ関数の配列を渡すと、それを先頭から順番に試し、最初に成功した結果を返す演算をします。

テスト

src/combinators.test.ts
import { not, or } from './combinators';

// ...

describe('or()', () => {
  describe('or([])', () => {
    const parser = or([]);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<unknown>>({
        result: 'fail'
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<unknown>>({
        result: 'fail'
      });
    });
  });

  describe('or([char("a"), char("b")])', () => {
    const parser = or([char('a'), char('b')]);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a' | 'b'>>({
        result: 'fail'
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a' | 'b'>>({
        result: 'success',
        data: 'a',
        rest: []
      });
    });

    test('Input "b"', () => {
      const input = [...'b'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a' | 'b'>>({
        result: 'success',
        data: 'b',
        rest: []
      });
    });

    test('Input "A"', () => {
      const input = [...'A'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a' | 'b'>>({
        result: 'fail'
      });
    });
  });
});

まず最初に or([]) として、パーサ関数を何も渡さなかった場合を定義しています。このような使い方はしないですが、テストケースとして書いておきます。この場合、パーサとしてはすべて失敗するように想定しています。出力するデータの型は unknown です。

次に、実用的な例をテストケースとしています。 char('a')char('b')or() で包んでいます。つまり、 a もしくは b の場合に成功するパーサ関数を作っています。出力するデータの型は 'a' | 'b' です。パーサ関数のデータ型の Union Types となります。

実装

src/combinators.ts
type OrFunc = <T>(ps: Parser<T>[]) => Parser<T>;
export const or: OrFunc = ps => input => {
  for (const p of ps) {
    const r = p(input);
    if (r.result === 'success') return r;
  }
  return { result: 'fail' };
};

素直に実装して終わりです。型はちゃんと推論されます。

連結演算子

これまでは 1 文字だけパースする関数のみを扱ってきました。 1 文字ずつ手動で順番に解析していくことは不可能では無いですがとてつもなく面倒なので、パーサ関数を連結してまとめて結果を返すような演算子を考えます。

例えば true という文字列を解析する場合、 char('t') char('r') char('u') char('e') というパーサ関数を用意し、先頭から 1 文字ずつ解析します。解析結果の rest フィールドを次のパーサの入力にしていくことで、連続した文字列の解析を行うことができます。これを簡単に行う関数 cat を作ります。名前の由来は、ファイルを連結 (concatenate) することができる cat コマンドから。

テスト

src/combinators.test.ts
import { not, or, cat } from './combinators';

// ...

describe('cat()', () => {
  describe('cat([])', () => {
    const parser = cat([]);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<[]>>({
        result: 'success',
        data: [],
        rest: []
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<[]>>({
        result: 'success',
        data: [],
        rest: [...'a']
      });
    });
  });

  describe('cat([char("a"), char("b")])', () => {
    const parser = cat([char('a'), char('b')]);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<['a', 'b']>>({
        result: 'fail'
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<['a', 'b']>>({
        result: 'fail'
      });
    });

    test('Input "abc"', () => {
      const input = [...'abc'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<['a', 'b']>>({
        result: 'success',
        data: ['a', 'b'],
        rest: [...'c']
      });
    });

    test('Input "A"', () => {
      const input = [...'A'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<['a', 'b']>>({
        result: 'fail'
      });
    });
  });
});

or のときと同様、パーサ関数を何も渡さなかった場合を定義しています。この場合、 0 文字のパーサを渡したとみなせるので、結果は成功と想定しています。

次に、 char('a') char('b') のパーサ関数を cat() で連結します。つまり、 ab という文字列をパースするパーサ関数を作っています。出力するデータの型は ['a', 'b'] です。これは配列型よりも制約が強いタプル型です。タプル型は、配列のそれぞれの位置の要素の型を個別に表現できる型です。

実装

src/combinators.ts
type CatFunc = <T extends Parser<unknown>[]>(ps: [...T]) => Parser<{ [K in keyof T]: ParserData<T[K]> }>;
export const cat: CatFunc = ps => input => {
  const rs = [];
  let i = input;
  for (const p of ps) {
    const r = p(i);
    if (r.result === 'fail') return r;
    rs.push(r.data);
    i = r.rest;
  }
  return {
    result: 'success',
    data: rs as ParserData<ReturnType<ReturnType<CatFunc>>>,
    rest: i
  };
};

CatFunc 型で、 Variadic Tuple Types を用いて引数を定義し、 Mapped Tuple Types を用いてパーサ関数型を定義しています。例として、 cat() 関数に [char('a'), char('b')] を渡すと、 Parser<['a', 'b']> 型のパーサを返すようになります。

Variadic Tuple Types を使用せず、引数を (ps: T) と定義してしまうと、 Mapped Tuple Types を使用してパーサ関数型を定義する際、タプルではなく Union Types の配列になってしまいます。つまり、 [char('a'), char('b')] を渡すと、 Parser<('a' | 'b')[]> 型のパーサを返すようになってしまいます。 Variadic Tuple Types を使用することで、しっかりと型制約を課すことができます。

あとは for 文で順番にパーサ関数を適用していくだけです。 rs が結果の配列となりますが、流石にここは型推論ができなかったので as を使用しています。

繰り返し演算子

パーサ関数を繰り返し適用する rep() 関数を作ります。パーサ関数を繰り返し適用することで、文字などの繰り返しを表現することができます。名前の由来は repeat から。

繰り返しの回数指定は、パラメータ n と m を用いて「 n 回以上 m 回以下繰り返す (n <= m) 」ことを想定してやればいいと思います。「必ず n 回繰り返す」といった要件に関しては n = m とすれば良いです。 n のデフォルト値は 0 、 m のデフォルト値は正の無限大にすることで、回数指定で楽ができます。

ということで rep() 関数は、繰り返し対象のパーサ関数、繰り返し回数の下限、繰り返し回数の上限の 3 つの引数を取れば良さそうです。

テスト

src/combinators.test.ts
import { not, or, cat, rep } from './combinators';

// ...

describe('rep()', () => {
  describe('rep(char("a"))', () => {
    const parser = rep(char('a'));

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: [],
        rest: []
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a'],
        rest: []
      });
    });

    test('Input "aa"', () => {
      const input = [...'aa'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: []
      });
    });

    test('Input "aab"', () => {
      const input = [...'aab'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: [...'b']
      });
    });
  });

  describe('rep(char("a"), 1)', () => {
    const parser = rep(char('a'), 1);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'fail'
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a'],
        rest: []
      });
    });

    test('Input "aa"', () => {
      const input = [...'aa'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: []
      });
    });

    test('Input "aab"', () => {
      const input = [...'aab'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: [...'b']
      });
    });
  });

  describe('rep(char("a"), 1, 2)', () => {
    const parser = rep(char('a'), 1, 2);

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'fail'
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a'],
        rest: []
      });
    });

    test('Input "aa"', () => {
      const input = [...'aa'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: []
      });
    });

    test('Input "aaa"', () => {
      const input = [...'aaa'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<'a'[]>>({
        result: 'success',
        data: ['a', 'a'],
        rest: [...'a']
      });
    });
  });
});

テストケース多めです。 char('a') を繰り返します。 0 回以上の繰り返し、 1 回以上の繰り返し、 1 回以上 2 回以下の繰り返しをテストします。

実装

src/combinators.ts
type RepFunc = <T>(p: Parser<T>, min?: number, max?: number) => Parser<T[]>;
export const rep: RepFunc = (p, min = 0, max = Number.POSITIVE_INFINITY) => input => {
  if (min > max) throw new Error('rep: min > max is not allowed.');
  if (min < 0) throw new Error('rep: negative min is not allowed.');
  if (max < 0) throw new Error('rep: negative max is not allowed.');

  const rs: ParserData<typeof p>[] = [];
  let i = input;
  for (let n = 0; n < max; n++) {
    const r = p(i);
    if (r.result === 'fail') break;
    rs.push(r.data);
    i = r.rest;
  }
  if (rs.length < min) return { result: 'fail' };
  return {
    result: 'success',
    data: rs,
    rest: i
  };
};

繰り返し上限に達するまで、入力に対して繰り返しパーサ関数を適用し、結果を返しています。繰り返し回数の下限に達していない場合は、解析失敗としています。

繰り返し回数の下限、繰り返し回数の上限はそれぞれデフォルト引数とし、省略可能にしています。

ユーティリティ

これで基本的なパーサ関数とパーサコンビネータは実装完了しました。ただ、これをそのまま使うのはちょっとキツいものもあるので、利便性が向上する便利なパーサをいくつか定義します。

アルファベットのパーサ

is() を使うか、 char()or() を使って、 or([char('a'), char('b'), ..., char('z')]) と定義すれば、小文字アルファベット 1 文字のパーサが出来上がりますが、記述量や計算量の観点から見て非効率すぎるので、あらかじめ効率的な実装で定義してしまいます。

大文字アルファベットの upperAlpha 、小文字アルファベットの lowerAlpha 、大文字小文字を区別しない alpha を定義します。

テスト

文字関連ということで src/char.test.ts にテストを書きます。

src/util.test.ts
import { char, is, upperAlpha, lowerAlpha, alpha } from './char';
import type { UpperAlphabet, LowerAlphabet, Alphabet } from './char';

// ...

describe('upperAlpha', () => {
  const parser = upperAlpha;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<UpperAlphabet>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<UpperAlphabet>>({
      result: 'fail'
    });
  });

  test('Input "A"', () => {
    const input = [...'A'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<UpperAlphabet>>({
      result: 'success',
      data: 'A',
      rest: []
    });
  });
});

describe('lowerAlpha', () => {
  const parser = lowerAlpha;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<LowerAlphabet>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<LowerAlphabet>>({
      result: 'success',
      data: 'a',
      rest: []
    });
  });

  test('Input "A"', () => {
    const input = [...'A'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<LowerAlphabet>>({
      result: 'fail'
    });
  });
});

describe('alpha', () => {
  const parser = alpha;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Alphabet>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Alphabet>>({
      result: 'success',
      data: 'a',
      rest: []
    });
  });

  test('Input "A"', () => {
    const input = [...'A'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Alphabet>>({
      result: 'success',
      data: 'A',
      rest: []
    });
  });

  test('Input "1"', () => {
    const input = [...'1'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Alphabet>>({
      result: 'fail'
    });
  });
});

アルファベットを表す UpperAlphabet LowerAlphabet Alphabet 型を新しく定義する予定です。

実装

src/char.ts
export type UpperAlphabet = 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z';
export type LowerAlphabet = Lowercase<UpperAlphabet>;
export type Alphabet = UpperAlphabet | LowerAlphabet;

export const upperAlpha: Parser<UpperAlphabet> = is((c): c is UpperAlphabet => /^[A-Z]$/.test(c));
export const lowerAlpha: Parser<LowerAlphabet> = is((c): c is LowerAlphabet => /^[a-z]$/.test(c));
export const alpha: Parser<Alphabet> = is((c): c is Alphabet => /^[A-Za-z]$/.test(c));

まず UpperAlphabet 型を定義します。これは完全にゴリ押しです。続いて LowerAlphabet 型ですが、これは UpperAlphabet 型に TypeScript 組み込みの Lowercase 型を適用して作っています。

Lowercase 型は

type Lowercase<S extends string> = intrinsic;

と定義されており、 intrinsic つまり TypeScript コンパイラの内部実装になっています。

大文字小文字を区別しない Alphabet 型は UpperAlphabetLowerAlphabet の Union Types で表現できます。

型の実装ができたので、次は関数の実装です。以前定義した is 関数を利用しています。文字の判定自体には正規表現を使用しています (溢れ出るチート感) 。他の実装方法としては、 String.prototype.codePointAt() を使用して Unicode コードポイントがアルファベットの範囲内に入っているか調べる方法があります。

また、 alpha 関数は

src/char.ts
import { or } from './combinators';

// ...

export const alpha: Parser<Alphabet> = or([upperAlpha, lowerAlpha]);

という風に実装することもできます。簡潔に表記できるコンビネータの強さがちょっと分かります。

数字のパーサ

アルファベットと同様に数字も使用頻度が高いので、こちらもあらかじめ定義しておきましょう。 digit を定義します。

テスト

src/char.test.ts
import { char, is, upperAlpha, lowerAlpha, alpha, digit } from './char';
import type { UpperAlphabet, LowerAlphabet, Alphabet, Digit } from './char';

// ...

describe('digit', () => {
  const parser = digit;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'fail'
    });
  });

  test('Input "5"', () => {
    const input = [...'5'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'success',
      data: '5',
      rest: []
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'fail'
    });
  });
});

数字を表す Digit 型を新しく定義する予定です。

実装

src/char.ts
export type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

export const digit: Parser<Digit> = is((c): c is Digit => /^\d$/.test(c));

アルファベットの時と同様、正規表現を使用しています。 \d は数字にマッチする文字クラスです。

解析結果の map

今までのパーサは、結果の型がすべて stringstring[] のサブタイプとなっていました。先ほど実装したパーサ関数 digit は数字 1 文字をパースしますが、結果の Digit 型は string のサブタイプである '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' であり、 number ではありません。数字 1 文字を number 型としてパースしたくなる時があるはずです。

そこで、解析結果を変換する map 関数を作ります。 Array.prototype.map() 関数と同様、結果の値を変換する関数を渡すことで、解析結果を変換します。

テスト

src/util.test.ts にテストを書きます。新しいファイルです。

src/util.test.ts
import { map } from './util';
import { digit } from './char';
import type { ParserOutput } from './types';

describe('map(digit, s => Number.parseInt(s, 10))', () => {
  const parser = map(digit, s => Number.parseInt(s, 10));

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "5"', () => {
    const input = [...'5'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 5,
      rest: []
    });
  });
});

map()digit パーサ関数と、結果を変換する関数を渡しています。 digit の結果は ParserOutput<Digit> ですが、この map() 関数で変換することで ParserOutput<number> となります。

変換する関数は s => Number.parseInt(s, 10) で、ここでは引数の型が Digit 、戻り値が number となっています。型はジェネリクスで推論されるので、任意の型から任意の型へ自由に変換することができます。意味は無いですが、 map() をネストしてさらに別の値や型へ変換することもできます。別の型でラップするといった用途にも使えます。

実装

src/util.ts に実装を書きます。

src/util.ts
import type { Parser } from './types'

type MapFunc = <T, U>(p: Parser<T>, f: (a: T) => U) => Parser<U>;
export const map: MapFunc = (p, f) => input => {
  const r = p(input);
  if (r.result === 'fail') return r;
  return {
    result: 'success',
    data: f(r.data),
    rest: r.rest
  };
};

型パラメータ T は変換前の型で、 U は変換後の型です。 map() 関数は変換前のパーサ関数 p と、変換関数 f を受け取り、 Parser<U> を返します。

文字列のパーサ

今までは「文字」に主眼を置いていました。「文字列」を扱うためには、連結演算子である cat() を使う必要がありましたが、これを直接使うのはあまりにもダルすぎます。

例えば、 true という文字列をパースするには

const parser = cat([char('t'), char('r'), char('u'), char('e')]);

と書く必要があります。しかも、解析結果の型は ['t', 'r', 'u', 'e'] となり更にダルいです。解析結果の型を 'true' にするには map() を使用して

const parser = map(
  cat([char('t'), char('r'), char('u'), char('e')]),
  a => 'true' as const  // or a.join('') as 'true'
);

とする必要があります。

そこで、文字列を直接指定してパースできる関数 str() を作ります。

テスト

src/util.test.ts にテストを書きます。

src/util.test.ts
import { map, str } from './util';

// ...

describe('str("true")', () => {
  const parser = str('true');

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'true'>>({
      result: 'fail'
    });
  });

  test('Input "true"', () => {
    const input = [...'true'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<'true'>>({
      result: 'success',
      data: 'true',
      rest: []
    });
  });
});

str()'true' を渡しています。これで文字列 true をパースする関数の完成です。結果も 'true' として返ってきます。

実装

src/util.ts
import { char } from './char';
import { cat } from './combinators';

// ...

type StrFunc = <T extends string>(s: T) => Parser<T>;
export const str: StrFunc = s => input => {
  const p = cat([...s].map(char));
  const r = p(input);
  if (r.result === 'fail') return r;
  return {
    result: 'success',
    data: s,
    rest: r.rest
  };
};

ジェネリクスを使用して、引数と戻り値の結果の型を一致させています。例えば、 T'true' の場合、 Parser<'true'> が返るようになります。

まず、受け取った文字列 s をスプレッド構文を用いて配列にバラします。それを char() へ map することで、 Parser<string> の配列を作ります。 .map(char).map(a => char(a)) と同じ意味です。そして、 Parser<string> の配列を cat() に渡して 1 つの Parser<string[]> にします。あとはそのパーサ関数に入力を食わせてやれば終わりです。データは s をそのまま返しています。

オプション演算子

繰り返し演算子に関連して、パースができてもできなくても良い opt() 関数を作ります。これは、パーサの 0 回以上 1 回以下の繰り返しと考えることができます。

オプション型の定義

テストを書く前に、 src/util.tsOption<T> 型を定義します。 Rust にある奴を TypeScript に持ってきました。

src/util.ts
interface Some<T> {
  status: 'some';
  value: T;
}
interface None {
  status: 'none';
}
export type Option<T> = Some<T> | None;

opt() 関数はパースした値が存在する場合と存在しない場合の 2 種類の値を返します。値が存在する場合は Some<T> を、 存在しない場合は None を保持することで、値が存在しているかどうかを確実に明示することができます。 Union Types なので、 status フィールドを見れば Some<T>None かが判定できます。

テスト

src/util.test.ts
import { map, opt, str } from './util';
import type { Option } from './util';
import { char, digit } from './char';

// ...

describe('opt()', () => {
  describe('opt(char("a"))', () => {
    const parser = opt(char('a'));

    test('Empty input', () => {
      const input = [] as const;
      const output = parser(input);
      expect(output).toEqual<ParserOutput<Option<'a'>>>({
        result: 'success',
        data: { status: 'none' },
        rest: []
      });
    });

    test('Input "a"', () => {
      const input = [...'a'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<Option<'a'>>>({
        result: 'success',
        data: { status: 'some', value: 'a' },
        rest: []
      });
    });

    test('Input "aa"', () => {
      const input = [...'aa'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<Option<'a'>>>({
        result: 'success',
        data: { status: 'some', value: 'a' },
        rest: [...'a']
      });
    });

    test('Input "b"', () => {
      const input = [...'b'];
      const output = parser(input);
      expect(output).toEqual<ParserOutput<Option<'a'>>>({
        result: 'success',
        data: { status: 'none' },
        rest: [...'b']
      });
    });
  });
});

char('a') があってもなくてもパース成功となります。 char('a') がパースできた場合、結果として { status: 'some', value: 'a' } が返され、パースできなかった場合は { status: 'none' } が返されます。

実装

src/util.ts
import { cat, rep } from './combinators';

// ...

type OptFunc = <T>(p: Parser<T>) => Parser<Option<T>>;
export const opt: OptFunc = p => input => {
  const r = rep(p, 0, 1)(input);
  if (r.result === 'fail') return r;
  return {
    result: 'success',
    data: r.data.length === 0 ? { status: 'none' } : { status: 'some', value: r.data[0] },
    rest: r.rest
  };
};

渡されたパーサ関数 prep() に渡して処理しています。 rep() が失敗することは無いのですが、 r.result === 'fail' のタイプガードを設けないと r.datar.rest に安全にアクセスできません。これは TypeScript の仕様です。自然と安全なコードが書けます。

rep() を使用しないコードも書けます。試してみてください。テストが通れば OK です。

差分演算子

「パーサ a でパースできるけど、パーサ b でパースできるものは含めたくない」といった時に使える diff() 関数を作ります。パーサ a とパーサ b の「差パーサ」を作ります。例えば、数字 (0 から 9) をパースする digit から '0' を除外したい、などの場合に使います。

テスト

src/util.test.ts
import { map, opt, str, diff } from './util';
import { char, Digit, digit } from './char';

// ...

describe('diff(digit, char("0"))', () => {
  const parser = diff(digit, char('0'));

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'fail'
    });
  });

  test('Input "0"', () => {
    const input = [...'0'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'fail'
    });
  });

  test('Input "5"', () => {
    const input = [...'5'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit>>({
      result: 'success',
      data: '5',
      rest: []
    });
  });
});

digit は数字のパースに成功しますが、 diff() を使うことで '0' のパースを失敗させます。

実装

src/util.ts
import { cat, not, rep } from './combinators';

// ...

type DiffFunc = <T, U>(p: Parser<T>, q: Parser<U>) => Parser<T>;
export const diff: DiffFunc = (p, q) => map(cat([not(q), p]), ([, r]) => r);

パーサ p からパーサ q を引き算しています。

ここで not() 関数の効果が発揮されます。 p から q を引くということは、 q のパースが成功せず、 p のパースが成功することと同義です。それを表現するために not(q)pcat() で連結しています。 not(q) が成功しても入力の消費は起こらないので、 cat() で連結しても成立します。

しかし、 not(p)null を結果として出力するので、 map() 関数で null を取り除いています。 ([, r]) => r とすることで、引数に渡ってくる配列の最初の要素を無視し、 2 番目の要素を取得しそのまま返しています。

リストパーサ

CSV (Comma-Separated Values) や配列など、カンマ区切りで値を並べる機会は多いと思うので、それを簡単にパースできるように list() 関数を作ります。例として、 digitchar(',') を組み合わせて 1,2,3,4,5 などをパースし、結果を Digit[] とするパーサを簡単に作れるようにします。

テスト

src/util.test.ts
import { map, opt, str, diff, list } from './util';

// ...

describe('list(digit, char(","))', () => {
  const parser = list(digit, char(','));

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit[]>>({
      result: 'fail'
    });
  });

  test('Input "a"', () => {
    const input = [...'a'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit[]>>({
      result: 'fail'
    });
  });

  test('Input "1"', () => {
    const input = [...'1'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit[]>>({
      result: 'success',
      data: ['1'],
      rest: []
    });
  });

  test('Input "1,2,3,4,5"', () => {
    const input = [...'1,2,3,4,5'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<Digit[]>>({
      result: 'success',
      data: ['1', '2', '3', '4', '5'],
      rest: []
    });
  });
});

char(',') で区切られた digit のリストをパースします。要素数は 1 以上必要です。

実装

src/util.ts
type ListFunc = <T>(p: Parser<T>, delimiter: Parser<unknown>) => Parser<T[]>;
export const list: ListFunc = (p, delimiter) => map(cat([p, rep(cat([delimiter, p]))]), ([first, rest]) => [first, ...rest.map(([, r]) => r)]);

まず最初の要素は p としてパースします。 2 番目以降の要素は delimiterp を連結し cat([delimiter, p]) としたものを rep() で繰り返します。こうすることで、 delimiter で区切られた p のリストのパーサを表現できます。

このパーサの結果の型は [T, [unknown, T][]] となっているので、 map() で必要なものだけを取り出します。 型推論も完璧です。

list() 関数は要素数が 1 以上のリストを表しています。要素数が 0 以上のリストを表したいなら opt() 関数と組み合わせて使用することで実現できます。また、末尾の区切り文字 (いわゆるケツカンマ) も使えませんが、これも opt() 関数を使うことで許可できます。

作ったパーサとコンビネータまとめ

今まで小さな機能を持ったパーサやコンビネータをチマチマ作ってきました。複雑な文法をパースするのに必要な道具が結構揃いましたので、今まで作ってきたパーサ関数やパーサコンビネータをまとめます。一部型の表記は省略しています。

クリックして展開
パーサ 引数 パース結果型 説明
anyChar なし ParserInput[0] (string) 任意の 1 文字をパース
eof なし null 終端をパース
char() c: T extends ParserInput[0] T 文字 c をパース
is() f: (c: ParserInput[0] => c is T extends ParserInput[0]) T 関数 f を満たす文字 c をパース
not() p: Parser<unknown> null パーサ p が成功しないものをパース
or() ps: Parser<T>[] T パーサ配列 ps のうち最初に成功するものをパース
cat() ps: [Parser<T>, Parser<U>, ...] [T, U, ...] パーサ配列 ps を最後まで順次パース
rep() p: Parser<T>, min: number = 0, max: number = Number.POSITIVE_INFINITY T[] パーサ pmin 以上 max 以下の回数だけパース (最長一致)
alpha なし Alphabet アルファベット 1 文字をパース
upperAlpha なし UpperAlphabet 大文字アルファベット 1 文字をパース
lowerAlpha なし LowerAlphabet 小文字アルファベット 1 文字をパース
digit なし Digit 数字 1 文字をパース
map() p: Parser<T>, f: (a: T) => U U T 型のパース結果を U 型に変換
str() s: T extends string T 文字列 s をパース
opt() p: Parser<T> Option<T> パーサ p でのパースをオプション化
diff() p: Parser<T>, q: Parser<unknown> T パーサ p が成功するものからパーサ q が成功するものを除外
list() p: Parser<T>, delimiter: Parser<unknown> T[] パーサ delimiter を区切りとし、パーサ p のリストをパース (最低でも 1 件必要)

これだけあれば、かなり色々なことができます。次節から、これらのパーサを活用してもっと大きな構文をパースしていきます。

実践: boolean パーサ

実践編第一弾として、 boolean の値のパーサを作ります。

仕様

'true''false' という文字列をパースして、 boolean 型とするパーサ関数 bool を作ります。以上。

テスト

テスト駆動開発なのでテストから。 src ディレクトリの中に parsers ディレクトリを作り、 src/parsers/bool.test.ts に書きます。

src/parsers/bool.test.ts
import { bool } from './bool';
import type { ParserOutput } from '../types';

describe('bool', () => {
  const parser = bool;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<boolean>>({
      result: 'fail'
    });
  });

  test('Input "true"', () => {
    const input = [...'true'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<boolean>>({
      result: 'success',
      data: true,
      rest: []
    });
  });

  test('Input "false"', () => {
    const input = [...'false'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<boolean>>({
      result: 'success',
      data: false,
      rest: []
    });
  });

  test('Input "null"', () => {
    const input = [...'null'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<boolean>>({
      result: 'fail'
    });
  });
});

'true' から始まる文字列を渡したら true が返り、 'false' から始まる文字列を渡したら false が返ってきます。それ以外の場合はすべて失敗となります。使い方は至ってシンプルです。

実装

src/parsers/bool.ts に書きます。まずは 'true' をパースする parseTrue 関数を作ります。これは export してもしなくてもいいです。

src/parsers/bool.ts
import { map, str } from '../util';
import type { Parser } from '../types';

const parseTrue: Parser<true> = map(str('true'), () => true);

今まで mapstr をちゃんと作ってきたおかげで、超シンプルに書けました。マジでこれだけで 'true' はパースできます。

次は 'false' をパースする parseFalse 関数を作ります。

src/parsers/bool.ts
const parseFalse: Parser<false> = map(str('false'), () => false);

これで 'false' もパースできるようになりました。

あとは bool 関数を作って終わりです。

src/parsers/bool.ts
import { or } from '../combinators';

// ...

export const bool: Parser<boolean> = or([parseTrue, parseFalse]);

parseTrueparseFalseor() で包むだけ。以上です。 type boolean = true | false なので、型推論もバッチリです。

書く量があまりにも少なすぎて動くかどうか心配になりますが、遠慮なく npm test を実行しましょう。緑になるはずです。パーサコンビネータの強さを実感できたと思います。

実践: 整数パーサ

次は整数の値のパーサ int を作ります。

仕様

'42''-273' などの文字列をパースして、 nunber 型とするパーサ関数 int を作ります。

まずは負の整数を考えず、 0 以上の符号なし整数について考えます。

整数は、 0 のとき以外は先頭に「 0 」はつきません。例えば、 010 としては表せず、 10 と表す必要があります。このことを考えると、 0 以上の符号なし整数の定義は以下の BNF (Backus-Naur form) によって表すことができます。 BNF は文法 (文脈自由文法) を定義する言語です。なんとなくで見て OK です。

<non-zero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
         <digit> ::= "0" | <non-zero-digit>
        <number> ::= "0" | <non-zero-digit> <digit>*

TypeScript の型表記に結構似てるので分かりやすいと思います。 <digit>** は 0 回以上の繰り返しを表します。 0 以上の符号なし整数は、 0 とそれ以外とで場合分けすれば良さそうです。 BNF において < > で囲まれた記号をそのままパーサコンビネータとして実装すれば、パーサが書けてしまいます。

これで数値部分について定義できたので、あとは符号を定義すれば終了です。符号は +- のどちらかを取るか、そもそも符号を記載しない場合に分けられます。これに基づいてパーサを書けば符号パーサが出来上がります。

最終的に数値パーサと符号パーサを組み合わせれば、整数パーサが完成します。

テスト

src/parsers/int.test.ts に書きます。

src/parsers/int.test.ts
import { int } from './int';
import type { ParserOutput } from '../types';

describe('int', () => {
  const parser = int;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "true"', () => {
    const input = [...'true'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "0"', () => {
    const input = [...'0'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 0,
      rest: []
    });
  });

  test('Input "42"', () => {
    const input = [...'42'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 42,
      rest: []
    });
  });

  test('Input "-273"', () => {
    const input = [...'-273'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: -273,
      rest: []
    });
  });

  test('Input "+3735928559"', () => {
    const input = [...'+3735928559'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 3735928559,
      rest: []
    });
  });
});

適当な整数をテストケースにしています。

実装

src/parsers/int.ts に書きます。まずは符号を無視した数値部分をパースする numbers 関数を作ります。

その前に、非 0 の数字 1 文字をパースする nonZeroDigit を作りましょう。

src/parsers/int.ts
import type { Parser } from '../types';
import { char, digit, Digit } from '../char';
import { diff } from '../util';

const nonZeroDigit: Parser<Digit> = diff(digit, char('0'));

diff() を使えば超簡単。

先ほどの仕様セクションで、0 とそれ以外とで場合分けするように考えました。まずは '0' のパーサ zeroNumber を作りましょう。

src/parsers/int.ts
import { diff, map } from '../util';

// ..

const zeroNumber: Parser<0> = map(char('0'), () => 0);

これで OK です。何も難しくないと思います。

次に、 '0' 以外のパーサ nonZeroNumber を作ります。

src/parsers/int.ts
import { cat, rep } from '../combinators';

// ...

const nonZeroNumber: Parser<number> = map(cat([nonZeroDigit, rep(digit)]), ([first, rest]) => Number.parseInt([first, ...rest].join(''), 10));

まず、 cat([nonZeroDigit, rep(digit)]) とし、非 0 の数字と、数字の繰り返しを連結します。

これで得られた結果を map()number に変換しています。 nonZeroDigit の結果を firstrep(digit) の結果を rest で受け取り、スプレッド構文を使用して 1 つの配列にまとめた後、 join() して文字列として結合したところを Number.parseInt()number に変換しています。

これで、 zeroNumbernonZeroNumber が揃いました。これを or() で繋いでやれば numbers 関数の出来上がりです。これは次節でも使うので export しておきましょう。

src/parsers/int.ts
import { cat, or, rep } from '../combinators';

// ...

export const numbers: Parser<number> = or([zeroNumber, nonZeroNumber]);

数値部分の実装は意外と難しいかと思いきや割とあっけなく終わりました。

次は符号部分のパーサ sign を作ります。

src/parsers/int.ts
import { diff, map, opt } from '../util';

// ...

const sign: Parser<1 | -1> = map(opt(or([char('+'), char('-')])), s => s.status === 'some' ? s.value === '+' ? 1 : -1 : 1);

符号は '+''-' があるので、まず or([char('+'), char('-')]) というパーサを作ります。しかし、これらは省略可能なので、 opt() で包みます。そうすると、パーサの結果の型は Option<'+' | '-'> となります。

OptionNone であるか、 { value: '+' } の場合は正、 { value: '-' } の場合は負となります。 map() を使って、正の場合は 1 に、負の場合は -1 に変換しています。こうすることで、符号の値と数値の値の積を取れば、符号を考慮した値をすぐに計算することができます。

数値部分と符号部分が両方完成したので、あとはこれらをくっつけるだけです。 int 関数を作りましょう。

src/parsers/int.ts
export const int: Parser<number> = map(cat([sign, numbers]), ([s, n]) => s * n);

cat()signnumbers を連結して、 map() で数値を変換して、終わりです。テストを走らせましょう。全部緑になるはずです。

実践: 四則演算パーサ

四則演算のパーサを作ります。四則演算は加算、減算、乗算、除算に加えて、括弧による優先順位変更ができる数式です。 42+3*(2-5) のような数式をパースし、計算結果を取り出すことを目標にします。

仕様

式のパースでは抽象構文木 (AST: Abstract Syntax Tree) を作るのが普通ですが、今回は直接値を計算してしまうことにします。

四則演算の式は以下の BNF で表すことができます。

  <expr> ::= <term> [ ("+" | "-") <term> ]*
  <term> ::= <factor> [ ("*" | "/") <factor> ]*
<factor> ::= <number> | "(" <expr> ")"
<number> ::= 整数

BNF において [ ] で囲まれた部分はグループ化されています。四則演算は加減算より乗除算が優先され、乗除算より括弧が優先されます。この BNF では、下の行ほど優先度が高くなっています。

先程の整数パーサと同様、この BNF をそのままパーサコンビネータとして実装すれば、四則演算パーサの完成です。

テスト

src/parsers/expression.test.ts に書きます。

src/parsers/expression.test.ts
import { expr } from './expression';
import type { ParserOutput } from '../types';

describe('int', () => {
  const parser = expr;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "true"', () => {
    const input = [...'true'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "42"', () => {
    const input = [...'42'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 42,
      rest: []
    });
  });

  test('Input "1+2"', () => {
    const input = [...'1+2'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 1 + 2,
      rest: []
    });
  });

  test('Input "7-3"', () => {
    const input = [...'7-3'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 7 - 3,
      rest: []
    });
  });

  test('Input "8*16"', () => {
    const input = [...'8*16'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 8 * 16,
      rest: []
    });
  });

  test('Input "1024/16"', () => {
    const input = [...'1024/16'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 1024 / 16,
      rest: []
    });
  });

  test('Input "3*(5-2)"', () => {
    const input = [...'3*(5-2)'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 3 * (5 - 2),
      rest: []
    });
  });

  test('Input "42+3*(2-5)"', () => {
    const input = [...'42+3*(2-5)'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 42 + 3 * (2 - 5),
      rest: []
    });
  });
});

適当な数式をテストケースにしています。

実装

src/parsers/expression.ts に書きます。

四則演算の BNF を見ると、 <expr> の中で <term> が使われ、 <term> の中で <factor> が使われ、 <factor> の中で <expr> が使われていることが分かります。これは相互再帰になっており、パーサ関数の後方参照が必要になるため、パーサ関数は関数式ではなく関数宣言で書きます。

src/parsers/expression.ts
import { char } from '../char';
import { numbers } from './int';
import { cat, or, rep } from '../combinators';
import { map } from '../util';
import type { ParserInput, ParserOutput } from '../types';

export function expr(input: ParserInput): ParserOutput<number> {
  return map(cat([term, rep(cat([or([char('+'), char('-')]), term]))]), ([first, rest]) => {
    return rest.reduce((lhs, [op, rhs]) => {
      if (op === '+') return lhs + rhs;
      return lhs - rhs;
    }, first);
  })(input);
}

function term(input: ParserInput): ParserOutput<number> {
  return map(cat([factor, rep(cat([or([char('*'), char('/')]), factor]))]), ([first, rest]) => {
    return rest.reduce((lhs, [op, rhs]) => {
      if (op === '*') return lhs * rhs;
      return lhs / rhs;
    }, first);
  })(input);
}

function factor(input: ParserInput): ParserOutput<number> {
  return or([numbers, map(cat([char('('), expr, char(')')]), ([,n,]) => n)])(input);
}

まずは、 BNF 表記のものを愚直にパーサコンビネータで書きます。まずは expr から。

cat([term, rep(cat([or([char('+'), char('-')]), term]))])

これを map() で数値に変換します。 [first, rest] で分割しています。 first にあたるパーサが term で、 rest にあたるパーサが rep(cat([or([char('+'), char('-')]), term])) となります。 ['+' | '-', number][] 型の rest に対し reduce() 関数で畳み込み演算をします。畳み込み演算の初期値 first で、 reducer 関数のアキュムレータを lhs 、 配列の要素を [op, rhs] として分割し、演算子の種類によって計算を切り替えています。

あとは引数 input を適用して expr パーサは完成です。 termexpr とほぼ同じです。

factornumberscat([char('('), expr, char(')')]) のどちらかとなるので、 or() で包んでいます。 cat([char('('), expr, char(')')])['(', number, ')'] 型のパーサなので、 map()number の部分のみを取り出しています。

テストを実行し、緑になることを確認してください。テストが通ることに感動を覚えるはずです。

実践: JSON パーサ

最後の実践プロジェクトは JSON (JavaScript Object Notation) パーサです。この記事を見ている人なら、 JSON がどういうものか絶対知っているはずだと思いますので JSON 自体の説明は省略します。

この記事の執筆時点では、本家 JSON から一部仕様を省略した簡易 JSON パーサを作ろうと考えていましたが、フル規格でも全然実装できそうだったのでマジの JSON パーサを作ります。

仕様

JSON の仕様は ECMA International の ECMA-404 で見ることができます。また、 JSON 公式サイト にも分かりやすく示されています。この仕様通りに JSON パーサを実装し、オブジェクトを復元できたら完成です。

JSON は、必要となるパーサは大きく分けて

  • オブジェクト
  • 配列
  • 文字列
  • 数値
  • 空白

があります。簡単なものから実装していきましょう。

ディレクトリ src/parsers/json を作っておきます。

$ mkdir src/parsers/json

空白パーサ

JSON では改行やインデントなど、無視される空白文字があります。これは、人間が読みやすくするために必要です。空白文字の一覧は以下の通りです。

コード 文字名 説明 エスケープシーケンス
U+0009 CHARACTER TABULATION 水平タブ \t
U+000A LINE FEED 改行 \n
U+000D CARRIAGE RETURN 復帰 \r
U+0020 SPACE スペース

これらの 0 回以上の繰り返しが無視されます。

テスト

src/parsers/json/whitespace.test.ts に書きます。

src/parsers/json/whitespace.test.ts
import { whitespace } from './whitespace';
import type { ParserOutput } from '../../types';

describe('whitespace', () => {
  const parser = whitespace;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: []
    });
  });

  test('Input "abc"', () => {
    const input = [...'abc'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: [...'abc']
    });
  });

  test('Input "\\t\\n\\r hoge"', () => {
    const input = [...'\t\n\r hoge'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<null>>({
      result: 'success',
      data: null,
      rest: [...'hoge']
    });
  });
});

空白文字は JSON にとって必要とされていないので、解析結果の型は一律で null とします。

実装

src/parsers/json/whitespace.ts に書きます。

src/parsers/json/whitespace.ts
import { char } from '../../char';
import { or, rep } from '../../combinators';
import { map } from '../../util';
import type { Parser } from '../../types';

export const whitespace: Parser<null> = map(rep(or([...'\t\n\r '].map(char))), () => null);

[...'\t\n\r '].map(char) とすると、 [char('\t'), char('\n'), char('\r'), char(' ')] ができあがります。あとは or()rep() で包んで map()null にしてしまえば終了です。

数値パーサ

先程は整数のパーサを作りましたが、今度は小数も表現できる必要があるため、新しく作ります。

JSON では先頭での + の符号は許可されていません。また、省略可能な小数部と指数部が必要となります。小数部は . で始まり、その後に 1 桁以上の数字が並びます。指数部は e もしくは E で始まり、その後に省略可能な符号 (+ もしくは -) 、1 桁以上の数字が並びます。

テスト

src/parsers/json/number.test.ts に書きます。

src/parsers/json/number.test.ts
import { number } from './number';
import type { ParserOutput } from '../../types';

describe('number', () => {
  const parser = number;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "+1"', () => {
    const input = [...'+1'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'fail'
    });
  });

  test('Input "42"', () => {
    const input = [...'42'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: 42,
      rest: []
    });
  });

  test('Input "-273.15"', () => {
    const input = [...'-273.15'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: -273.15,
      rest: []
    });
  });

  test('Input "-1.125e+2"', () => {
    const input = [...'-1.125e+2'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<number>>({
      result: 'success',
      data: -1.125e+2,
      rest: []
    });
  });
});

適当な数値をテストケースにしています。 '+1' はパース失敗となることに注意してください。

実装

src/parsers/json/number.ts に書きます。

符号部 sign 、実数部 integer 、小数部 fraction 、指数部 exponent の 4 つに分けてパーサを書きます。

src/parsers/json/number.ts
import { char, digit } from '../../char';
import { cat, or, rep } from '../../combinators';
import { diff, map, opt } from '../../util';
import type { Parser } from '../../types';
import type { Option } from '../../util';

const sign: Parser<'-'> = char('-');
const integer: Parser<string> = or([char('0'), map(cat([diff(digit, char('0')), rep(digit)]), ([first, rest]) => [first, ...rest].join(''))]);
const fraction: Parser<string> = map(cat([char('.'), rep(digit, 1)]), ([dot, digits]) => [dot, ...digits].join(''));
const exponent: Parser<string> = map(cat([or([char('E'), char('e')]), opt(or([char('+'), char('-')])), rep(digit, 1)]), ([e, sign, digits]) => [e, sign.status === 'some' ? sign.value : '', ...digits].join(''));

export const number: Parser<number> = map(cat([opt(sign), integer, opt(fraction), opt(exponent)]), ([sign, integer, fraction, exponent]) => {
  const optOrEmpty = (opt: Option<string>) => opt.status === 'some' ? opt.value : '';
  const numberString = [optOrEmpty(sign), integer, optOrEmpty(fraction), optOrEmpty(exponent)].join('');
  return Number.parseFloat(numberString);
});

signintegerfractionexponent のパーサを仕様通りに定義して、 string 型として結果を生成しています。

これらを number パーサ関数で結合しています。符号部 sign 、小数部 fraction 、指数部 exponent は任意なので、 opt() で包んでから cat() で結合し、再び string にしてから Number.parseFloat()number にしています。

文字列パーサ

文字列は " で囲まれた文字列を値とするものです。 JSON では、文字列中に制御文字があってはならないし、エスケープするべき文字もあります。まずはそれらのパーサを定義してから文字列パーサを書くことになります。

文字列中に存在してはならない制御文字は U+0000 から U+001F の範囲の文字です。

エスケープシーケンスの一覧は以下の通りです。

コード 文字名 説明 エスケープシーケンス
U+0008 BACKSPACE 後退 \b
U+0009 CHARACTER TABULATION 水平タブ \t
U+000A LINE FEED 改行 \n
U+000C FORM FEED 書式送り \f
U+000D CARRIAGE RETURN 復帰 \r
U+0022 QUOTATION MARK 引用符 \"
U+002F SOLIDUS スラッシュ \/
U+005C REVERSE SOLIDUS バックスラッシュ \\

これらに加えて、 \uXXXX 形式で Unicode コードポイントを直接指定することができます。 XXXX の部分は 4 桁の 16 進数で、大文字小文字の区別はありません。

/\/\u002F\u002f は同じ文字になります。

テスト

src/parsers/json/string.test.ts に書きます。

src/parsers/json/string.test.ts
import { string } from './string';
import type { ParserOutput } from '../../types';

describe('string', () => {
  const parser = string;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('Input "hello"', () => {
    const input = [...'hello'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('Input "\'hello\'"', () => {
    const input = [...'\'hello\''];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('Input ""hoge\tfuga""', () => {
    const input = [...'"hoge\tfuga"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('Input ""hello""', () => {
    const input = [...'"hello"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: 'hello',
      rest: []
    });
  });

  test('Input ""\\a""', () => {
    const input = [...'"\\a"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'fail'
    });
  });

  test('Input ""\\b\\t\\n\\f\\r\\"\\/\\\\""', () => {
    const input = [...'"\\b\\t\\n\\f\\r\\"\\/\\\\"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: '\b\t\n\f\r"/\\',
      rest: []
    });
  });

  test('Input ""[/\\/\\u002F\\u002f]""', () => {
    const input = [...'"[/\\/\\u002F\\u002f]"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: '[////]',
      rest: []
    });
  });

  test('Input ""\\ud83c\\udf63""', () => {
    const input = [...'"\\ud83c\\udf63"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<string>>({
      result: 'success',
      data: '🍣',
      rest: []
    });
  });
});

" で括っているかのテストと、エスケープシーケンスのテストを重点的に行っています。

実装

src/parsers/json/string.ts に書きます。

まず、制御文字 cntrl 、エスケープシーケンス escape のパーサを定義します。 escape を定義するために、 16 進数をパースする hex や、 \uXXXX 形式の文字をパースする codePoint も定義します。 " で括る中身を stringContent として定義し、最終的に " で括った形式である string を組み立てます。

src/parsers/json/string.ts
import { anyChar } from '../../primitives';
import { char, digit, is } from '../../char';
import { cat, or, rep } from '../../combinators';
import { diff, map, str } from '../../util';
import type { Digit } from '../../char';
import type { Parser } from '../../types';

const cntrl: Parser<string> = is((c): c is string => (c.codePointAt(0) || 0) <= 0x1f);

type HexUpperAlpha = 'A' | 'B' | 'C' | 'D' | 'E' | 'F';
type HexLowerAlpha = Lowercase<HexUpperAlpha>;
type HexAlpha = HexUpperAlpha | HexLowerAlpha;
type HexDigit = Digit | HexAlpha;
const hex: Parser<HexDigit> = or([digit, is((c): c is HexAlpha => /^[A-Fa-f]$/.test(c))]);
const codePoint: Parser<string> = map(cat([str('\\u'), rep(hex, 4, 4)]), ([, code]) => String.fromCodePoint(Number.parseInt(code.join(''), 16)));

const escape: Parser<string> = or([
  map(str('\\b'), () => '\b'),
  map(str('\\t'), () => '\t'),
  map(str('\\n'), () => '\n'),
  map(str('\\f'), () => '\f'),
  map(str('\\r'), () => '\r'),
  map(str('\\"'), () => '"'),
  map(str('\\/'), () => '/'),
  map(str('\\\\'), () => '\\'),
  codePoint
]);

const stringContent: Parser<string> = map(rep(or([
  diff(anyChar, or([char('"'), char('\\'), cntrl])),
  escape
])), strs => strs.join(''));
export const string: Parser<string> = map(cat([char('"'), stringContent, char('"')]), ([, s, ]) => s);

まず、制御文字をパースする cntrl を定義しています。 is() 関数を使用して、 String.prototype.codePointAt() 関数の戻り値を判定することで制御文字かどうかを判定しています。

次に、 \uXXXX 形式のパーサ codePoint を定義しています。 16 進数 1 桁をパースする hex を定義し、それをちょうど 4 回繰り返すよう rep() 関数を使用しています。 16 進数 4 桁をパースしたら、 map() 関数で実際の文字へ変換しています。 Number.parseInt() では 16 進数であることを指定しています。

codePoint を使用して、エスケープシーケンスのパーサ escape を定義しています。

stringContent パーサで、文字列の内容を定義しています。これは、 JSON の仕様通りに実装するだけです。 map() 関数で、バラバラの文字を join() して連結しています。

あとは、 " で括った string を定義して終わりです。これも map() 関数を使用して、文字列の中身だけをパース結果として返しています。

値パーサ

JSON における値とは、文字列、数値、 truefalsenull 、オブジェクト、配列です。

このうち、文字列、数値は先ほど実装しました。 truefalse については、以前作成した boolean パーサをそのまま使えます。 null についてはすぐに実装できます。オブジェクトと配列は今後実装します。

ひとまず、オブジェクトと配列以外をサポートする値パーサを作ります。値の両端の空白は無視する必要があります。

テスト

src/parsers/json/value.test.ts に書きます。

src/parsers/json/value.test.ts
import { value } from './value';
import type { ValueType } from './value';
import type { ParserOutput } from '../../types';

describe('value', () => {
  const parser = value;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'fail'
    });
  });

  test('Input "hello"', () => {
    const input = [...'hello'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'fail'
    });
  });

  test('Input ""hello""', () => {
    const input = [...'"hello"'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: 'hello',
      rest: []
    });
  });

  test('Input "\t"hello"\t"', () => {
    const input = [...'\t"hello"\t'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: 'hello',
      rest: []
    });
  });

  test('Input "42"', () => {
    const input = [...'42'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: 42,
      rest: []
    });
  });

  test('Input "true"', () => {
    const input = [...'true'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: true,
      rest: []
    });
  });

  test('Input "false"', () => {
    const input = [...'false'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: false,
      rest: []
    });
  });

  test('Input "null"', () => {
    const input = [...'null'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: null,
      rest: []
    });
  });

  // TODO: Test object and array
});

値の型を ValueType 型として定義する予定です。オブジェクトと配列のテストは今後書くことにします。

実装

src/parsers/json/value.ts に書きます。

新しく null のパーサを parseNull として実装しています。値の両端の空白文字を除いた部分のパーサを valueContent として定義し、最終的に空白文字を両端に持った value パーサを組み立てます。

src/parsers/json/value.ts
import { cat, or } from '../../combinators';
import { map, str } from '../../util';
import { bool } from '../bool';
import { number } from './number';
import { string } from './string';
import { whitespace } from './whitespace';
import type { Parser, ParserInput, ParserOutput } from '../../types';

export type ValueType = string | number | boolean | null;

const parseNull: Parser<null> = map(str('null'), () => null);

const valueContent: Parser<ValueType> = or<ValueType>([
  string, number, bool, parseNull
]);
export function value(input: ParserInput): ParserOutput<ValueType> {
  return map(cat([whitespace, valueContent, whitespace]), ([, v, ]) => v)(input);
}

ValueType 型を Union Types で定義しています。 valueContent パーサで or() を使っています。ここでは型推論がうまく動かず、 or() に型パラメータを明示的に指定しないと、型でエラーが起きてしまいました。

また、 value は関数宣言で書いています。 value は配列やオブジェクトと相互再帰するためです。

仮の状態ですが、値パーサは一旦完成とします。

配列パーサ

配列は [] で囲まれ、 0 個以上の値を , 区切りで持つ値です。以前に list() パーサを実装しているので、簡単に実装できます。

テスト

値と同じく src/parsers/json/value.test.ts に書きます。

src/parsers/json/array.test.ts
import { value, array } from './value';

// ...

describe('array', () => {
  const parser = array;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType[]>>({
      result: 'fail'
    });
  });

  test('Input "hello"', () => {
    const input = [...'hello'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType[]>>({
      result: 'fail'
    });
  });

  test('Input "[]"', () => {
    const input = [...'[]'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType[]>>({
      result: 'success',
      data: [],
      rest: []
    });
  });

  test('Input "[1]"', () => {
    const input = [...'[1]'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType[]>>({
      result: 'success',
      data: [1],
      rest: []
    });
  });

  test('Input "[1, "2", false, null]"', () => {
    const input = [...'[1, "2", false, null]'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType[]>>({
      result: 'success',
      data: [1, '2', false, null],
      rest: []
    });
  });
});

配列の型は ValueType[] となります。数値や文字列などのスカラ値でテストしています。

実装

src/parsers/json/value.ts に書きます。

string パーサと同様、 [] の中身のパーサを arrayContent として定義し、 [] で括ったパーサを array として定義します。

src/parsers/json/array.ts
import { char } from '../../char';
import { list, map, str } from '../../util';

// ...

const arrayContent: Parser<ValueType[]> = map(or([list(value, char(',')), whitespace]), a => a ?? []);
export function array(input: ParserInput): ParserOutput<ValueType[]> {
  return map(cat([char('['), arrayContent, char(']')]), ([, a, ]) => a)(input);
}

arrayContentmap()a => a ?? [] を渡しています。これは Null 合体演算子で、 anull または undefined の場合、 ?? の右の値を返し、それ以外の場合は ?? の左の値を返します。

array も相互再帰するので、関数宣言です。

配列パーサを値パーサへ追加

配列も値の一種であるので、 value パーサを配列に対応させます。まずテストを追加します。

src/parsers/json/value.test.ts
// ...

describe('value', () => {
  // ...

  test('Input "[1, 2, 3]"', () => {
    const input = [...'[1, 2, 3]'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: [1, 2, 3],
      rest: []
    });
  });

  // TODO: Test object
});

value の実装に array を追加します。 ValueType 型も更新します。

src/parsers/json/value.ts
// ...

export type ValueType = string | number | boolean | null | ValueType[];

// ...

const valueContent: Parser<ValueType> = or<ValueType>([
  string, number, bool, parseNull, array
]);

// ...

書き終わったらテストを実行します。 value パーサで配列をパースできたら OK です。

オブジェクトパーサ

オブジェクトは {} で囲まれ、 0 個以上のキーバリューペアを , 区切りで持つ値です。キーは文字列、バリューは任意の値で、 : で区切られています。これも list() パーサがあるので簡単に実装できます。

テスト

src/parsers/json/value.test.ts に書きます。

src/parsers/json/value.test.ts
import { value, array, object } from './value';
import type { ValueType, ObjectType } from './value';

// ...

describe('object', () => {
  const parser = object;

  test('Empty input', () => {
    const input = [] as const;
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ObjectType>>({
      result: 'fail'
    });
  });

  test('Input "hello"', () => {
    const input = [...'hello'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ObjectType>>({
      result: 'fail'
    });
  });

  test('Input "{}"', () => {
    const input = [...'{}'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ObjectType>>({
      result: 'success',
      data: {},
      rest: []
    });
  });

  test('Input "{ "answer-to-the-ultimate-question": 42 }"', () => {
    const input = [...'{ "answer-to-the-ultimate-question": 42 }'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ObjectType>>({
      result: 'success',
      data: { "answer-to-the-ultimate-question": 42 },
      rest: []
    });
  });

  test('Input "{ "number": 1, "string": "hello", "boolean": true, "null": null }"', () => {
    const input = [...'{ "number": 1, "string": "hello", "boolean": true, "null": null }'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ObjectType>>({
      result: 'success',
      data: { number: 1, string: 'hello', boolean: true, null: null },
      rest: []
    });
  });
});

オブジェクトの型は ObjectType です。後ほど定義します。

実装

src/parsers/json/value.ts に書きます。

array パーサと同様、 {} の中身のパーサを objectContent として定義し、 {} で括ったパーサを object として定義します。キーバリューペアを objectKeyValue として事前に定義しておきます。

src/parsers/json/value.ts
export type ObjectType = { [key: string]: ValueType; };
const objectKeyValue: Parser<ObjectType> = map(cat([whitespace, string, whitespace, char(':'), value]), ([, k, , , v]) => ({ [k]: v }));
const objectContent: Parser<ObjectType> = map(or([list(objectKeyValue, char(',')), whitespace]), a => (a ?? []).reduce((obj, kv) => ({ ...obj, ...kv }), {}));
export function object(input: ParserInput): ParserOutput<ObjectType> {
  return map(cat([char('{'), objectContent, char('}')]), ([, o, ]) => o)(input);
}

ObjectType 型を定義しています。内容は { [key: string]: ValueType } となっており、キーが string 、バリューが ValueType であるオブジェクトを表しています。

objectKeyValue パーサでキーバリューペア 1 件をパースし、 ObjectType 型としています。 objectContent パーサで ObjectType[] を取得し、 reduce() とスプレッド構文で 1 つのオブジェクトにまとめています。

object パーサも相互再帰します。

オブジェクトパーサを値パーサへ追加

オブジェクトも値の一種であるので、 value パーサをオブジェクトに対応させます。まずテスト。

src/parsers/json/value.test.ts
// ...

describe('value', () => {
  // ...

  test('Input "{ "answer": 42, "absolute-zero": -273.15 }"', () => {
    const input = [...'{ "answer": 42, "absolute-zero": -273.15 }'];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<ValueType>>({
      result: 'success',
      data: { answer: 42, 'absolute-zero': -273.15 },
      rest: []
    });
  });
});

// ...

value の実装に object を追加します。 ValueType 型も更新します。

src/parsers/json/value.ts
// ...

export type ValueType = string | number | boolean | null | ValueType[] | ObjectType;

// ...

const valueContent: Parser<ValueType> = or<ValueType>([
  string, number, bool, parseNull, array, object
]);

// ...

書き終わったらテストを実行します。 value パーサでオブジェクトをパースできたら OK です。

完成

これで JSON パーサは完成しました。 JSON は、ルートがオブジェクトや配列である必要はありません。 value パーサそのものが JSON パーサとなります。このままだとちょっと分かりにくいので、 src/parsers/json/index.tsjson として再 export しておきましょう。 ValueType 型も JsonType として再 export します。

src/parsers/json/index.ts
export { value as json } from './value';
export type { ValueType as JsonType } from './value';

最終テスト

JSON パーサの最後のテストとして、このプロジェクトの package.json をパースしてみようと思います。

JSON ファイルを import するために、 TypeScript の設定 tsconfig.json を少し変更します。

tsconfig.json
{
  "compilerOptions": {
    // ...

    "resolveJsonModule": true
  }
}

src/parsers/json/index.test.ts にテストを書きます。

src/parsers/json/index.test.ts
import package_json from '../../../package.json';
import { json } from '.';
import type { JsonType } from '.';
import type { ParserOutput } from '../../types';

describe('json', () => {
  const parser = json;

  test('package.json', () => {
    const jsonstr = JSON.stringify(package_json, null, 2);
    const input = [...jsonstr];
    const output = parser(input);
    expect(output).toEqual<ParserOutput<JsonType>>({
      result: 'success',
      data: package_json,
      rest: []
    });
  });
});

package.json を import してオブジェクトとして取得し、 JSON.stringify() で JSON 文字列に戻しています。これを自作の JSON パーサに食わせ、パース結果を import したオブジェクトと比較します。オブジェクトが一致していれば、正常にパースできていることになります。

他の JSON ファイルでも試したい場合は、自由にテストを追加してみてください。

おわり

お疲れ様でした。

今回は TypeScript で実装しましたが、第一級関数をサポートする言語ならなんでもパーサコンビネータを作ることができます。

また、今回はパーサの入力を文字列に限定していましたが、文字列ではなく 1 byte 単位のバイト列とすることで、バイナリファイルの解析をすることもできます。

tsconfig.json などで用いられている JSON with Comments では、 JavaScript スタイルのコメントを書くことができます。今回作成した JSON パーサを拡張して、コメントをつけられるようにしてみるのも面白いと思います。

もちろん自作のドメイン固有言語 (DSL: Domain-Specific Language) を作って遊ぶのもよし、プログラミング言語を作って遊ぶのもよしです。