如何限制单向变压器解析器组合器中的回溯

tl; dr，如何实现可以限制回溯的解析器，其中解析器是monad变换器堆栈？如何限制单向变压器解析器组合器中的回溯

我还没有找到任何文章，博客或这种方法的示例实现;似乎限制回溯的典型方法是带有附加构造函数的数据类型，或默认情况下回溯关闭的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'

来源

2012-12-06 Matt Fenwick

我可能会错过一些东西，但结果是你想要的结果还是你当前得到的结果。（如果是后者，你想得到什么结果？） – huon

@dbaupp both - 代码'现在'正在运行，但仅限于该特定monad堆栈。我的目标是找出这样做的“正确”方式，或者至少是一种更好/更清洁/更一般的方式。 –

的答案似乎是在MonadOr type class（这不幸的是，我是不是标准库的一部分）：

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

满足含半幺群and 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-07 20:47:01

如何限制单向变压器解析器组合器中的回溯

回答

相关问题