« HTML + CSS で数式組版 (その16) | トップページ | Packrat Parsing を調べてみる (その2) »

2009年4月 4日 (土)

Packrat Parsing を調べてみる

このペーパーです。

Bryan Ford Packrat Parsing: Simple, Powerful, Lazy, Linear Time (PDF). ICFP, October 2002.

Haskell の実装例が載っているのですが、これがよくわからない。

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

なんじゃこりゃ?

どう評価されるんだろ? d のところの動きが謎ですね。

ペーパーには、以下のコードが載っています:

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

data Result v = Parsed v Derivs | NoParse

pAdditive :: Derivs -> Result Int
pMultitive :: Derivs -> Result Int
pPrimary :: Derivs -> Result Int
pDecimal :: Derivs -> Result Int

pAdditive d = alt1 where
  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

  alt2 = dvMultitive d

この続きを書いてみる。

pMultitive d = alt1 where
  alt1 = case dvPrimary d of
    Parsed vleft d' ->
      case dvChar d' of
        Parsed '*' d'' ->
          case dvPrimary d'' of
            Parsed vright d''' ->
              Parsed (vleft * vright) d'''
            _ -> alt2
        _ -> alt2
    _ -> alt2

  alt2 = dvPrimary d

pPrimary d = alt1 where
  alt1 = case dvChar d of
    Parsed '(' d' ->
      case dvAdditive d' of
        Parsed v d'' ->
          case dvChar d'' of
            Parsed ')' d''' ->
              Parsed v d'''
            _ -> alt2
        _ -> alt2
    _ -> alt2

  alt2 = dvDecimal d

pDecimal d = pDi where
  pDi = case pDs "" d of
    Parsed "" d' -> NoParse
    Parsed v d' -> Parsed (read v) d'
    _ -> NoParse
  pDs cs d = case dvChar d of
    Parsed c d' ->
      if isD c
      then pDs (cs ++ [c]) d'
      else Parsed cs d
    _ -> Parsed cs d
  isD c = c `elem` "0123456789"

とりあえず。

>ghci
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.2, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Prelude> :load packrat1.hs
Compiling Main             ( packrat1.hs, interpreted )
Ok, modules loaded: Main.
*Main> parse "2*(3+4)"

Top level:
    No instance for (Show Derivs)
      arising from use of `print' at Top level
    Probable fix: add an instance declaration for (Show Derivs)
    In a 'do' expression: print it

Show の instance がないと表示できません、か。

Haskell Hierarchical Libraries > Prelude > Converting to String (haskell.org)

を参考にして、 Show の instance を書きます。

instance (Show a) => Show (Result a) where
  showsPrec prec (Parsed v d) =
    showParen (prec > app_prec) $
      showString "Parsed " .
      showsPrec (app_prec + 1) v .
      showsPrec (app_prec + 1) d
    where app_prec = 10
  showsPrec prec NoParse =
    showParen (prec > app_prec) $
      showString "NoParse"
    where app_prec = 10

instance Show Derivs where
  showsPrec prec (Derivs add mult prim dec chr) =
    showParen (prec > app_prec) $
      showString "Derivs " .
      showsPrec (app_prec + 1) add .
      showsPrec (app_prec + 1) mult .
      showsPrec (app_prec + 1) prim .
      showsPrec (app_prec + 1) dec .
      showsPrec (app_prec + 1) chr
    where app_prec = 10

こんなんで良いのでしょうか。

*Main> parse "2*(3+4)"
Derivs (Parsed 14(Derivs (NoParse)(NoParse)(NoParse)(NoParse)(NoParse)))(Parsed
14(Derivs (NoParse)(NoParse)(NoParse)(NoParse)(NoParse)))(Parsed 2(Derivs (NoPar
se)(NoParse)(NoParse)(NoParse)(Parsed '*'(Derivs (Parsed 7(Derivs (NoParse)(NoPa
rse)(NoParse)(NoParse)(NoParse)))(Parsed 7(Derivs (NoParse)(NoParse)(NoParse)(No
... まだまだいっぱい。

うへえ。括弧地獄。

でも、一応 14 って答えが出てますね。

|

« HTML + CSS で数式組版 (その16) | トップページ | Packrat Parsing を調べてみる (その2) »

コメント

コメントを書く



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


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



トラックバック

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

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

« HTML + CSS で数式組版 (その16) | トップページ | Packrat Parsing を調べてみる (その2) »