如何限制單向變壓器解析器組合器中的回溯

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

如何限制單向變壓器解析器組合器中的回溯

回答

相關問題