プログラミング言語などのコンピュータ言語を構文解析するパーサコンビネータを 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 コンパイラを設定しておきます。

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

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

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

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

{
  // ...
  "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 tsc や yarn 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: 論理値

null と undefined

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

この場合、 coord は number 型の x と number 型の 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 のリテラル型 (と symbol や number) の 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 に組み込まれています。その一部を紹介します。

// 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 型を返す関数型です。この型に合致する関数は何でも渡すことができます。

この f に 123 と 456 を渡した結果を 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 に定義しましょう。

export type ParserInput = readonly string[];

出力

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

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

interface ParseSuccess<T> {
  result: 'success';
  data: T;
  rest: ParserInput;
}

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

interface ParseFail {
  result: 'fail';
}

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

export type ParserOutput<T> = Readonly<ParseSuccess<T> | ParseFail>;

パーサ関数型

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

export type Parser<T> = (input: ParserInput) => ParserOutput<T>;

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

ユーティリティ型

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

export type ParserData<P> = P extends Parser<infer T> ? T : never;

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

type P = Parser<number>;

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

パーサプリミティブ

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

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

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

任意の 1 文字パーサ

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

テスト

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

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 で、テストケースを定義します。 expect へ anyChar 関数の結果を渡して、 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> 型であり、今回 T は string であるので、 Parser<string> 型の anyChar を書きます。

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 関数を修正し、テストを再実行しましょう。

 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> とします。

テスト

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

実装

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

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

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

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

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

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

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

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

export type ParserInput = readonly string[];
export type Parser<T> = (input: ParserInput) => ParserOutput<T>;

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

テスト

最初にテストを書きます。 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 して利用しています。

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 を使用して事前に定義しています。

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

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

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

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

テスト

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 種類をテストしています。

実装

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.data を f を用いて判定しています。

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

パーサコンビネータ

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

not 演算子

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

テスト

テストファースト。 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 に実装を書きます。

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() 関数を作ります。この関数は、パーサ関数の配列を渡すと、それを先頭から順番に試し、最初に成功した結果を返す演算をします。

テスト

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 となります。

実装

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 コマンドから。

テスト

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'] です。これは配列型よりも制約が強いタプル型です。タプル型は、配列のそれぞれの位置の要素の型を個別に表現できる型です。

実装

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 つの引数を取れば良さそうです。

テスト

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 回以下の繰り返しをテストします。

実装

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 にテストを書きます。

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 型を新しく定義する予定です。

実装

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 型は UpperAlphabet と LowerAlphabet の Union Types で表現できます。

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

また、 alpha 関数は

import { or } from './combinators';

// ...

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

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

数字のパーサ

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

テスト

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 型を新しく定義する予定です。

実装

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

今までのパーサは、結果の型がすべて string や string[] のサブタイプとなっていました。先ほど実装したパーサ関数 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 にテストを書きます。新しいファイルです。

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: []
    });
  });
});