経緯
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ループで書くか、何らかの別のやり方にしないと現状では使えない。
パーサーの振る舞いとしてはほぼ完成してるんだけどどうしたもんかな。