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

# 経緯

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


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


# プログラム

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

[以前書いた](http://qiita.com/nishimura/items/f78c64b2c86c82a4af08)PHPを関数型のようにするライブラリを利用している。

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

```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"]
```

パーサーの型は

```hs
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) の

```hs
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]
```

これが

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

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

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

これはもちろん

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

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


## 重い、遅い

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


**追記 >>>**： [こちら](http://qiita.com/nishimura/items/c42af4070124d28bd670)で解決した。
今は

```
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ループで書くか、何らかの別のやり方にしないと現状では使えない。


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