3

tl; dr、バックトラックを制限できるパーサーを実装するにはどうすればよいですか？パーサーはモナド変換子スタックです。

このアプローチの論文、ブログ、または実装例は見つかりませんでした。バックトラッキングを制限するための一般的なアプローチは、コンストラクターが追加されたデータ型、またはバックトラッキングがデフォルトでオフになっているParsecアプローチのようです。

私の現在の実装（commitコンビネータを使用、以下を参照）は間違っています。型、型クラスに属しているかどうかはわかりません。私のインスタンスは、本来あるべきと思われるほど一般的ではありません。

誰かがこれをきれいに行う方法を説明したり、私にリソースを教えてもらえますか？

現在のコードを以下に追加しました。投稿が長すぎてごめんなさい！

スタック：

StateT
MaybeT/ListT
Either e

意図は、バックトラッキングが中間層で動作することです-Nothingまたは空のリストは必ずしもエラーを生成しません、それは単に別のブランチを試す必要があることを意味します-一方、最下層はエラーのためのものです（いくつかの文脈で情報）解析をすぐに中止します。

{-# LANGUAGE NoMonomorphismRestriction, FunctionalDependencies, 
             FlexibleInstances, UndecidableInstances #-}

import Control.Monad.Trans.State   (StateT(..))
import Control.Monad.State.Class   (MonadState(..))
import Control.Monad.Trans.Maybe   (MaybeT(..))
import Control.Monad.Trans.List    (ListT(..))
import Control.Monad               (MonadPlus(..), guard)    

type Parser e t mm a = StateT [t] (mm (Either e)) a

newtype DParser e t a = 
    DParser {getDParser :: Parser e t MaybeT a}

instance Monad (DParser e t) where
  return = DParser . return
  (DParser d) >>= f = DParser (d >>= (getDParser . f))

instance MonadPlus (DParser e t) where
  mzero = DParser (StateT (const (MaybeT (Right Nothing))))
  mplus = undefined   -- will worry about later

instance MonadState [t] (DParser e t) where
  get = DParser get
  put = DParser . put

いくつかの構文解析クラス：

class (Monad m) => MonadParser t m n | m -> t, m -> n where
  item  :: m t
  parse :: m a -> [t] -> n (a, [t])

class (Monad m, MonadParser t m n) => CommitParser t m n where
  commit :: m a -> m a

それらのインスタンス：

instance MonadParser t (DParser e t) (MaybeT (Either e)) where
  item = 
      get >>= \xs -> case xs of
                          (y:ys) -> put ys >> return y;
                          []     -> mzero;
  parse = runStateT . getDParser

instance CommitParser t (DParser [t] t) (MaybeT (Either [t])) where
  commit p =
      DParser (
        StateT (\ts -> MaybeT $ case runMaybeT (parse p ts) of
                            Left e          ->  Left e;
                            Right Nothing   ->  Left ts;
                            Right (Just x)  ->  Right (Just x);))

そして、さらにいくつかのコンビネータ：

satisfy f = 
    item >>= \x ->
    guard (f x) >>
    return x

literal x = satisfy (== x)

次に、これらのパーサー：

ab = literal 'a' >> literal 'b'

ab' = literal 'a' >> commit (literal 'b')

これらの結果を与える：

> myParse ab "abcd"
Right (Just ('b',"cd"))  -- succeeds

> myParse ab' "abcd"
Right (Just ('b',"cd"))  -- 'commit' doesn't affect success

> myParse ab "acd"
Right Nothing       -- <== failure but not an error

> myParse ab' "acd"
Left "cd"           -- <== error b/c of 'commit'
4

1 に答える 1

2

答えはMonadOr型クラスにあるようです（残念ながら私にとっては標準ライブラリの一部ではありません）：

class MonadZero m => MonadOr m where   
  morelse :: m a -> m a -> m a

満足のいくモノイドと左キャッチ：

morelse mzero b = b 
morelse a mzero = a 
morelse (morelse a b) c = morelse a (morelse b c) 
morelse (return a) b = return a
于 2012-12-07T20:47:01.207 に答える