« Packrat Parsing を調べてみる | トップページ | Float 遊び »

2009年4月 7日 (火)

Packrat Parsing を調べてみる (その2)

遅延評価だから、一部が自分自身によって構築されるデータを、関数に渡しても無問題である、ということですかね。かつ、必要なデータは、その都度、芋づる式に評価されて構築されていくと。

例でいえば、最初に評価されるもの、”トリガー”になるのは、 先頭の dvAdditive でしょう。

つまり:

calc :: String -> Int
calc s = g $ parse s where
  g d = case dvAdditive d of
    Parsed v d' -> v

などとして:

*Main> calc "2*(3+4)"
14

これで、 parse 関数の、 add = pAdditive d の評価が開始します。

parse s = d
d = Derivs add mult prim dec chr
add = pAdditive d

pAdditive の中に入って、 dvMultitive d の評価が開始します。

add = pAdditive d
dvMultitive d

dvMultitive d は、 mult = pMultitive d ですから、 pMultitive の中にはいって、 dvPrimary d の評価が開始します。

add = pAdditive d
dvMultitive d
dvPrimary d

同様に、 dvDecimal d の評価が開始します。

add = pAdditive d
dvMultitive d
dvPrimary d
dvDecimal d

ここまでで、 dvChar d が 2文字分評価されて:

dvChar d = Parsed '2' d'
dvChar d' = Parsed '*' d''
dvDecimal d = Parsed 2 d'
dvPrimary d = Parsed 2 d'

pMultitive まで戻って、 ”2 *” までが読み込まれ、 再び pPrimary へ:

pMultitive d
dvPrimary d'' = pPrimary d''

ここで、 dvChar d'' が評価されて、 pAdditive へ:

dvChar d'' = Parsed '(' d'''
dvAdditive d''' = pAdditive d'''

再び pAdditive からの評価を通って:

dvChar d''' = Parsed '3' d''''
dvChar d'''' = Parsed '+' d'''''
dvDecimal d''' = Parsed 3 d''''
dvPrimary d''' = Parsed 3 d''''
dvMultitive d''' = Parsed 3 d''''
dvChar d''''' = Parsed '4' d''''''
dvDecimal d''''' = Parsed 4 d''''''
dvPrimary d''''' = Parsed 4 d''''''
dvMultitive d''''' = Parsed 4 d''''''
dvAdditive d''' = Parsed 7 d''''''

pPrimary まで戻って:

dvChar d'''''' = Parsed ')' d'''''''
dvPrimary d'' = Parsed 7 d'''''''

pMultitive まで戻って:

dvMultitive d = Parsed 14 d'''''''

最初の pAdditive まで戻る:

dvAdditive d = Parsed 14 d'''''''

なるほど〜。巧妙ですねえ。

|

« Packrat Parsing を調べてみる | トップページ | Float 遊び »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/80472/28999638

この記事へのトラックバック一覧です: Packrat Parsing を調べてみる (その2):

« Packrat Parsing を調べてみる | トップページ | Float 遊び »