Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Kray-G

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

Last updated at Posted at 2020-07-19

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

はじめに

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

少し前に Kinx ライブラリ - パーサ・コンビネータ（その2） で実行まで行いました。さて今回は何でしょう。

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

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 } を指定すると無効化することもできます。

ベンチマークでその性能を見てみましょう。ここ を参考に、ものすごい数のバックトラックが発生する文法を処理してみます。文法は以下です。

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

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

(((((((((((((1)))))))))))))

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

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

いやー、すごいですね。

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

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 を使ってます。んが、パーサー・コンビネータは字句解析も一緒にできるのでそれはそれで便利ですね。

ではまた！

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?