Kinx ライブラリ - パーサ・コンビネータ（番外編）

# Kinx ライブラリ - パーサ・コンビネータ（番外編）

## はじめに

**「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」** でお届けしているスクリプト言語 [Kinx](https://github.com/Kray-G/kinx)。今回もパーサ・コンビネータです。

* 参考
    * 最初の動機 ... [スクリプト言語 KINX（ご紹介）](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76)
        * 個別記事へのリンクは全てここに集約してあります。
    * リポジトリ ... [https://github.com/Kray-G/kinx](https://github.com/Kray-G/kinx)
        * Pull Request 等お待ちしております。  

少し前に [Kinx ライブラリ - パーサ・コンビネータ（その2）](https://qiita.com/Kray-G/items/e2b9c99a5052423455ef) で実行まで行いました。さて今回は何でしょう。

そう、インターフェースのご紹介です。すみません、前回やり忘れました。

## Parsek

`Parsek` クラスのインスタンスには以下のメソッドがあります。文中の `$` はインスタンス化された実際の Parsek インスタンスを示します。

### 事前定義パーサー

`Parsek` クラスのインスタンスには、事前に定義された以下のパーサーが既に存在します。

| 事前定義パーサー |                                          内容                                          |
| ---------------- | -------------------------------------------------------------------------------------- |
| $.eof            | EOF である場合に成功するパーサー。                                                     |
| $.any            | 任意の 1 文字で成功するパーサー。                                                      |
| $.all            | 最後まで全て処理して成功するパーサー。                                                 |
| $.index          | 現在位置を返す（`{ offset, line, column}`）。offset は 0 起点、line/column は 1 起点。 |
| $.letter         | `$.regex(/[a-zA-Z]/)` と同じ。                                                         |
| $.letters        | `$.regex(/[a-zA-Z]*/)` と同じ。                                                        |
| $.digit          | `$.regex(/[0-9]/)` と同じ。                                                            |
| $.digits         | `$.regex(/[0-9]*/)` と同じ。                                                           |
| $.whitespace     | `$.regex(/\s+/)` と同じ。                                                              |
| $.optWhitespace  | `$.regex(/\s*/)` と同じ。                                                              |
| $.cr             | `$.string("\r")` と同じ。                                                              |
| $.lf             | `$.string("\n")` と同じ。                                                              |
| $.crlf           | `$.string("\r\n")` と同じ。                                                            |
| $.newline        | `$.alt($.crlf, $.lf, $.cr)` と同じ。                                                   |
| $.end            | `$.alt($.newline, $.eof)` と同じ。                                                     |

### パーサー生成関数

`Parsek` クラスのインスタンスには、以下のメソッドによってパーサーを生成する機能が存在します。

|       パーサー生成関数       |                                                                          内容                                                                          |
| ---------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------ |
| $.string(str)                | `str` で指定した文字列と一致した場合に成功するパーサーを作成する。                                                                                     |
| $.regex(re, groupIndex)      | `re` に指定した正規表現にマッチした場合に成功するパーサーを作成する。value には `groupIndex` で指定したグループのキャプチャ結果が入る。                |
| $.succeed(result)            | `result` を value に指定して必ず成功するパーサーを作成する。                                                                                           |
| $.fail(message)              | `message` をメッセージに残して失敗するパーサーを作成する。                                                                                             |
| $.oneOf(chars)               | `chars` に含まれる 1 文字にマッチしたら成功するパーサーを作成する。                                                                                    |
| $.noneOf(chars)              | `chars` に含まれる 1 文字にマッチしなかったら成功するパーサーを作成する。                                                                              |
| $.sepBy(content, separator)  | `content` でパース可能な文字列を `separator` にマッチした結果で分割した結果を返すパーサーを作成する。                                                  |
| $.sepBy1(content, separator) | `sepBy` は 0 個が許容されるが、`sepBy1` は少なくとも 1 つマッチしない場合失敗する。                                                                    |
| $.lazy(description, f)       | `f` にパーサーを返す関数を指定し、最初に使用されたときにパーサーを生成する。                                                                           |
| $.alt(...parsers)            | 指定された複数のパーサーのいずれかにマッチした場合に成功するパーサーを作成する。適用は指定された順に行われる。                                         |
| $.takeWhile(predicate)       | 次の文字が `predicate` で true である間成功し続けるパーサーを作成する。                                                                                |
| $.seq(...parsers)            | 指定された複数のパーサーに順にマッチした場合に成功するパーサーを作成する。結果は全ての結果の配列で返る。                                               |
| $.seqMap(...parsers, mapf)   | 指定された複数のパーサーに順にマッチした場合に成功するパーサーを作成する。結果は全ての結果の配列だが、それを mapf で指定された関数で返された値を返す。 |

## ParsekParser

`Parsek` クラスのメソッドで生成されたパーサーは、`ParsekParser` クラスのインスタンスです。このクラスには、パーサーをチェインさせるためのメソッドが定義されています。

### パースの実行

全てのパーサーが準備できたら、次のメソッドでパースを実行します。

|        メソッド         |                         内容                          |
| ----------------------- | ----------------------------------------------------- |
| parser.parseAll(target) | `target` に対して `parser` を使ってパースを実行する。 |

### パーサーの生成

|     パーサー生成関数     |                                                                               内容                                                                               |
| ------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| parser.desc(description) | `parser` によるパースが失敗した際に表示するメッセージを設定する。                                                                                                |
| parser.or(nextParser)    | `parser` によるパースに失敗した場合、`nextParser` を試みるパーサーを作成する。                                                                                   |
| parser.and(nextParser)   | `parser` によるパースに成功した場合、`nextParser` を実行するパーサーを作成する。結果は配列として返す。                                                           |
| parser.then(nextParser)  | `parser` によるパースに成功した場合、`nextParser` を実行するパーサーを作成する。結果は `nextParser` のものを返し、`parser` の結果は無視される。                  |
| parser.skip(nextParser)  | `parser` によるパースに成功した場合、`nextParser` を実行するパーサーを作成する。結果は `parser` のものを返し、`nextParser` の結果は無視される。                  |
| parser.many()            | `parser` が 0 回以上繰り返して出現することをパースするパーサーを作成する。                                                                                       |
| parser.many1()           | `parser` が 1 回以上繰り返して出現することをパースするパーサーを作成する。                                                                                       |
| parser.times(min, max)   | `parser` が `min` 回以上 `max` 回以下の回数繰り返して出現することをパースするパーサーを作成する。。`max` が省略された場合、ちょうど `min` 回数の場合に成功する。 |
| parser.sepBy(separator)  | `parser` でパース可能な文字列を `separator` にマッチした結果で分割した結果を返すパーサーを作成する。                                                             |
| parser.sepBy1(separator) | `sepBy` は 0 個が許容されるが、`sepBy1` は少なくとも 1 つマッチしない場合失敗する。                                                                              |
| parser.map(f)            | `parser` の結果を関数 f で変換したものを使うようにする。                                                                                                         |
| parser.chain(f)          | `parser` の結果を関数 f に渡し、f で返された新たなパーサーを次に続くパーサーとして利用するようにパーサーをつなぐ。                                               |
| parser./(nextParser)     | `parser.or(nextParser)` の別名。                                                                                                                                 |
| parser.+(nextParser)     | `nextParser` を指定せずに `parser.+()` として使うと `parser.many1()` の別名。`nextParser` を指定すると `parser.and(nextParser)` の別名。                         |
| parser.*()               | `parser.many()` の別名。                                                                                                                                         |

## Packrat Parsing

Packrat Parsing をサポートしています。

パーサー・コンビネータは通常バックトラックで解析を進めます。つまり、例えば `$.alt(a, b, c)` の場合、`a` のパーサーで失敗したら `b` というように進めるのですが、途中何度も同じパーサーを繰り返す可能性があります。

そこで、バックトラックした際、**同じ場所で同じ条件で解析した場合、同じ結果になる** という性質を利用して一部結果をキャッシュしておいて再利用することで性能向上が見込めます。メモ化ですね。

`Parsek` ではこの機能をサポートしています。ちなみに、`Parsek` インスタンスを作る際のコンストラクタに `{ disablePackratParsing: true }` を指定すると無効化することもできます。

ベンチマークでその性能を見てみましょう。[ここ](https://engineering.linecorp.com/ja/blog/peg-parser-generator-packrat-parser/) を参考に、ものすごい数のバックトラックが発生する文法を処理してみます。文法は以下です。

```peg
S <- A
A <- P "+" A / P "-" A / P
P <- "(" A ")" / "1"
```

これで以下の文字列をパースします。

```
(((((((((((((1)))))))))))))
```

説明も分かりやすいのでそのまま引用してしまいます。

> このルールと文字列の組み合わせの肝は、必ずすべてのAとPの組み合わせを経てから最終的にパースされることです。つまりバックトラックによる最悪のケースをほぼ再現できます。したがって愚直にバックトラックさせるならば、括弧の対応の数に応じて処理時間は指数関数的な増加をみせるはずです。

いやー、すごいですね。

では、ベンチマークのソースコードです。パーサー自体は同じなので、`{ disablePackratParsing: true }` の `$D` パーサーと、有効化した `$E` パーサーで同じテストを行うものです。

```javascript
using Parsek;

var $E = new Parsek();
var $D = new Parsek({ disablePackratParsing: true });
var tmr = new SystemTimer();

// rule:
//     S <- A
//     A <- P "+" A / P "-" A / P
//     P <- "(" A ")" / "1"
// input:
//     (((((((((((((1)))))))))))))

function generateParser($) {
    var S, A, P;
    S = $.lazy(&() => A);
    A = $.lazy(&() => $.alt($.seq(P, $.string('+'), A), $.seq(P, $.string('-'), A), P));
    P = $.alt($.seq($.string('('), A, $.string(')')), $.string('1'));
    return S;
}

function test($) {
    for (var i = 0; i <= 10; ++i) {
        tmr.restart();
        var r = generateParser($).parseAll(('(' * i) + '1' + (')' * i));
        var elapsed = tmr.elapsed();
        System.println(["%8.5f" % elapsed, r]);
    }
}

test($E);
test($D);
```

実行しましょう！

```:有効な場合
[" 0.00090", {"position":1,"status":1,"value":"1"}]
[" 0.00041", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00044", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00061", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.00083", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.00055", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.00061", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.00071", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00200", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00101", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00196", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
```

```:無効化した場合
[" 0.00022", {"position":1,"status":1,"value":"1"}]
[" 0.00034", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00097", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00353", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.01142", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.02686", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.09525", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.26821", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.72229", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 2.44629", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 7.48334", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
```

Packrat Parsing が有効な場合はカッコが 10 個になっても 2 ミリ秒以内で完了します。一方で、無効化した場合は最後のカッコが 10 個になった時点で 7.5 秒かかっています。

## おわりに

パーサー・コンビネータ、こうしてみると便利ですねー。あまり使ったことなかったけど、もうちょっと今後は活用してみようかな。正規表現では表現しきれない文字列のパースが簡単にできます。

言語処理系の作成に使ってもいいですね。Kinx は構文解析は yacc で字句解析は手書きなんですが。

本来、構文解析自体も手書きの再帰下降パーサーも好きなのですが、文法定義を変えるのが大変なのでもっぱら yacc を使ってます。んが、パーサー・コンビネータは字句解析も一緒にできるのでそれはそれで便利ですね。

ではまた！