PHPでパーサーコンビネーターを書いた

経緯

PHPでHTMLを真面目に解析したい。
よし、ならばParsecだ。

ちょっと探したけど、どれも中途半端な感じ。
自由に拡張できるParserを目指して作ることにした。

プログラム

https://github.com/nishimura/laiz-parsec
ここに置いた。

以前書いたPHPを関数型のようにするライブラリを利用している。

以下のような感じで使える。

<?php

require 'vendor/autoload.php';

use Laiz\Parsec;
use function Laiz\Parsec\parse;
use function Laiz\Parsec\parserReturn;
use function Laiz\Parsec\str;
use function Laiz\Parsec\many1;
use function Laiz\Func\Monoid\mappend;

Parsec\Char\load();

// (1)
$abc = str('abc');
$ret = parse($abc, "Test", "abcdef");
var_dump($ret);
// Right abc

Parsec\Combinator\load();

// (2)
$manyAbc = many1($abc);
$ret = parse($manyAbc, "Test", "abcabcabcdef");
var_dump($ret);
// Right ["abc", "abc", "abc"]

// (3)
$def = str('def');
$ret = parse(mappend($abc, $def), "Test", "abcdefabcdef");
var_dump($ret);
// Right "abcdef"

// (4)
$ret = parse($abc->const2($def), "Test", "abcdefabcdef");
var_dump($ret);
// Right "def"

// (5)
$p3 = $abc->aor($def)->aor(str('ghi'));
$ret = parse($p3, "Test", "abcdef");
var_dump($ret); // Right abc
$ret = parse($p3, "Test", "defghi");
var_dump($ret); // Right def
$ret = parse($p3, "Test", "ghiabc");
var_dump($ret); // Right ghi

// (6)
$parser = $abc->bind(function($a) use ($def){
    return $def->bind(function($b) use ($a){
        return parserReturn([strtoupper($a), $b]);
    });
});
$ret = parse($parser, "Test", "abcdefabc");
var_dump($ret);
// Right ["ABC", "def"]

パーサーの型は

data Parser s u a = Parser { unParser :: forall b .
                             State s u
                             -> (a -> State s u -> ParseError -> b) -- consumed ok
                             -> (ParseError -> b)                   -- consumed err
                             -> (a -> State s u -> ParseError -> b) -- empty ok
                             -> (ParseError -> b)                   -- empty err
                             -> b
                           }

こんな感じで、ほぼ Haskell の Parsec の移植。
Parsec3 のように Parser s u m a ではない。MonadTrans は作ってないので。

問題点

見づらい

(3) の p1 `mappend` p2 が mappend($p1, $p2) になるのは良いとして、(4) の p1 *> p2 が $p1->const2($p2) になることや、(5) の p1 <|> p2 が $p1->aor($p2) になるのがつらい。

(6) の

p :: (Stream s t) => Parser s u a -> Parser s u a -> Parser s u [a]
p p1 p2 = do x <- p1
             y <- p2
             return [x,y]

これが

$p = $p1->bind(function($x) use ($p2){
    return $p2->bind(function($y) use ($x){
        return parserReturn([$x, $y]);
    });
});

こう。関数の入れ子と二重の return つらい。
bind を fmap で書きなおせば (6) の

$parser = $abc->bind(function($a) use ($def){
    return $def->bind(function($b) use ($a){
        return parserReturn([strtoupper($a), $b]);
    });
});

これはもちろん

$parser = $abc->bind(function($a) use ($def){
    $f = function($b) use ($a){
        return [strtoupper($a), $b];
    };
    return fmap($f, $def);
});

こう書けるので、少しマシ。

重い、遅い

これが致命的で実用に耐えない。

追記 >>>： こちらで解決した。
今は

parse()
 │ 
 │ 0.025 s
 │ 66.94 KiB, 1.29 MiB

のような結果。
<<< 追記

https://github.com/nishimura/laiz-parsec/tree/v0.0.1
ここのREADMEのHTML Parserが

PHP Fatal error:  Maximum function nesting level of '1000' reached, aborting! in /tmp/php-test-parsec/vendor/
laiz/laiz-monad/src/Laiz/Func/CurryTrait.php on line 9

xdebugの xdebug.max_nesting_level = 1000 に引っかかる。つらい。

nesting_level を 1500 にして geekality/timer で測ると

parse()
 │ 
 │ 0.237 s
 │ 4.04 MiB, 9.62 MiB

重過ぎる。

よく考えれば当然で、for文の代わりに関数呼び出してるんだからループの数だけ再帰、しかも手続き型言語なので末尾呼出の最適化なしなので、スタックあふれるよね…。

それに加えて、Maybe などの 単純な値のコンテナと違って Parser は Writer系と同じく関数のコンテナになる。
そうすると何らかの操作でパーサーを組み合わせるたびに再帰が深くなっていくという。

関数呼び出しをgotoに変えて手動最適化するか、forループで書くか、何らかの別のやり方にしないと現状では使えない。

パーサーの振る舞いとしてはほぼ完成してるんだけどどうしたもんかな。