Packrat Parserについて - Yet Another Ranha

この記事は、私が全くPackrat Parserが分からなかったにも関わらず、
Packrat Parser generatorを書こうとするうちに、
何故かPackrat Parserの事が分かってしまった様な気がしたので書くエントリ。

参考ページは
http://pdos.csail.mit.edu/~baford/packrat/icfp02/

上記ページでは非常に簡潔にしかし十分にPackrat Parserについて書かれている。
しかも分かりやすく、私の様な馬鹿にさえ理解されてしまう。

そもそもPackrat Parserとは何なのか

Packrat Parserはその名の通りparsingの技法である。

具体的にどういう事をしているのか、という事はFord先生のpaperでも触れられているが、
再帰下降パーザ(Recursive Descent Parsing)+Tabular Parsingの事である。
Tabularはピンと来る人には分かると思うが、テーブルを作るという事である。
簡単に言うと、parsingをDynamic Programmigっぽく行い、
無駄な計算をしないという事である。

ここまでの解説でちょっと分からない人はこの先を読んでも多分分からない程度にしか
私は書けないので戻るをした方が適切である。

なぜこの二つの手法を混ぜ合わせるのか、というのがPackrat Parserの
メリットを考える事とつながる。

Recursive Descent Parsingは、トップダウン的にgrammarをparseする手法である

さて、この方法だと何が悪いのか、という事であるが、ここで次の様なgrammarを考えて欲しい。

-- Parse an additive-precedence expression
pAdditive :: String -> Result Int
pAdditive s = alt1 where

    -- Additive <- Multitive '+' Additive
    alt1 = case pMultitive s of
	     Parsed vleft s' ->
	       case s' of
		 ('+':s'') ->
		   case pAdditive s'' of
		     Parsed vright s''' ->
		       Parsed (vleft + vright) s'''
		     _ -> alt2
		 _ -> alt2
	     _ -> alt2

    -- Additive <- Multitive
    alt2 = case pMultitive s of
	     Parsed v s' -> Parsed v s'
	     NoParse -> NoParse

例えば、これに対してinput "1"が渡されたとしよう。

最初にcase pMultitive sが行われ、
Parsedの結果が返ってくる。
しかしその次の case s'で失敗する為に、
処理はalt2に移り、またもpMultitiveが評価される。

これは明らかに無駄である。

ここで先程のTabular Parsingの話が出てくる。
予め実行しておいてテーブルを作っておけば(bottom-upで)、
無駄にparseする必要がなく成る、という事である。

如何にしてトップダウンのparsing手法にDPを組合せるかという事であるが、
ここでコンテストとか出てる人が思いつく方法として、memoizationがありますね！

上記論文ではHaskellを使う事によって、実に簡単にPackrat Parserを実装しています。

今回は要となる部分のコードだけ。
と言ってもHaskellを使う人にしてみれば当たり前ですが。

実際にコードを見ながら

論文に張られているコードと図を見ながらこの先を見てください。

基本的に書いている事を再び書き直しているだけですけど。

data Result v =
	  Parsed v Derivs
	| NoParse

data Derivs = Derivs {
		dvAdditive	:: Result Int,
		dvMultitive	:: Result Int,
		dvPrimary	:: Result Int,
		dvDecimal	:: Result Int,
		dvChar		:: Result Char
	}

Result型は、Parseした結果を取り扱うものです。
Parsed v Derivsは v = parseに成功した場合の値、 Derivsは読み残し、食い残しです。

Packrat ParserをHaskellで組み立てる時に重要になるのが、その次のDerivsです。
このDerivsの中には、"結果"が入ると思ってください。

要するにテーブルですね！Figure3のdvAdditive,dvMultitive,dvPrimary,dvDecimal,dvCharに直接対応しています。

さて、次はPackrat ParserのTabular parsing部分です。実際にテーブルを組み立ててみましょう。

parse :: String -> Derivs
parse s = d where
    d    = Derivs add mult prim dec chr
    add  = pAdditive d
    mult = pMultitive d
    prim = pPrimary d
    dec  = pDecimal d
    chr  = case s of
             (c:s') -> Parsed c (parse s')
             [] -> NoParse

parseはparseしたい文字列を受け取って、Derivsを返す関数で、中を見れば分かりますが2重再帰になっています。

dを定義したいのにそのdを呼び出すなんて、と思われるかもしれませんが、これはlazyな言語だと何らおかしな事はありません。
Derivsの中のdvAdditiveにpAdditive dを,dvMultitiveにpMultitive dを．．．としてDerivsを完成させて、それを返す関数です。

Haskellでプログラムを書く際には、"どうやって実行されていくのかを追う"のではなく、それを意味で捉える事が大事です。
この場合だと、Derivsの中に実行された結果が入っています。

こうやって作られたテーブルを如何にして使うか、という事に関しては、最初に出した関数のpackrat parser版を見ると分かります。

-- Parse an additive-precedence expression
pAdditive :: Derivs -> Result Int
pAdditive d = alt1 where

    -- Additive <- Multitive '+' Additive
    alt1 = case dvMultitive d of
	     Parsed vleft d' ->
	       case dvChar d' of
		 Parsed '+' d'' ->
		   case dvAdditive d'' of
		     Parsed vright d''' ->
		       Parsed (vleft + vright) d'''
		     _ -> alt2
		 _ -> alt2
	     _ -> alt2

    -- Additive <- Multitive
    alt2 = case dvMultitive d of
	     Parsed v d' -> Parsed v d'
	     NoParse -> NoParse

case dvMultitive d

ここで"テーブルの中から"pMultitiveを行った結果を返してもらっている訳です。ただ、最初に結果を貰おうにもその段階では実行されていないので、必要になって初めて実行されて、それでmemoizationされます。
ですからその結果を比較すると単純にそういうわけですね。

ここでピンと来ない人はstrictなプログラミング言語に慣れているので、実際にこう動いて・・・と頭の中で処理を行ってしまおうとする為にこんがらがってしまうのかもしれません。

もっと具体的に、如何にしてHaskellで勝手にメモ化が行われるかを示す例を考えてみます。

階乗計算をしよう！

{-
  本当にmemoizationが行われているかどうかを
  実験する。
-}

fact n = foldl (*) 1 [1..n]

data Memo = Memo { test::Integer }
gen n = Memo (fact n)

exe1 n = do mapM_ (\x -> print $ fact n) [0..99]
exe2 n = do mapM_ (\x -> print $ fact' n) [0..99]
    where m       = gen 10000
          fact' n = if n == 10000 then
                        (test m)
                    else
                        fact n

与えられた数の階乗を100回計算するHaskellのプログラムで、2タイプ書いてあります。

exe1では毎回fact関数を実行。exe2ではfact 10000だけをmemoizationし、そうで無い時は"gen 10000"だけを呼び出さない、という関数です。

実際に実行してみます。

main = exe1 10000

=> ./a.out  14.05s user 0.23s system 97% cpu 14.661 total

main = print $ exe2 10000

=> ./a.out  3.14s user 0.12s system 77% cpu 4.225 total

exe2では実質一度しか計算していないので流石に早いです。
この結果を疑問に思う人には

main = print $ fac 10000

=> ./a.out  0.14s user 0.01s system 96% cpu 0.159 total

ちょうどexe1が100倍になっているのが分かると思います。

次に

main = exe2 100

=> ./a.out  0.01s user 0.01s system 58% cpu 0.023 total

これで"本当に必要になるまでは計算されない(lazy)"とはどういう事かが分かったかと思われます。

こういう仕組みによって、自然にコードを書く(ちょっとテクニカルですが)だけでHaskellではpackrat parserを実現する事が出来るのです。

ポイント

1.必要になるまでは計算しない
2.そして必要になって計算した結果は、テーブルに保存しておく。

このたったの2つで達成する事が出来るのです。
Packrat Parserの技術はそれほど難しくは無いのでした。

やろうと思えば十分C++でも出来ると思います。
それこそmemoizationを行う為のデータ構造(mapやらhash)やらを作り、必要になった時に見に行き、存在しなかった場合は計算しておいてからその結果をぶち込めば良いのですから。

今度は

この論文の著者でもあるBryan Ford先生が書いたPappyの解説を行いたいと思います。

皆さんが、この機会に関数型言語が口だけの素晴らしさではなく、実際的な素晴らしさも伴っているのだという事をちょっとでも理解してくれると嬉しいです。