4
4

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 5 years have passed since last update.

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

Last updated at Posted at 2016-07-07

経緯

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` p2mappend($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 つらい。
bindfmap で書きなおせば (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ループで書くか、何らかの別のやり方にしないと現状では使えない。

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

4
4
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
4
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?