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

满足 Monoid 和 Left Catch：

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 回答