4

问题

我正在为自学滚动一个不确定的解析器，它看起来像：

newtype Parser a b = P { runP :: [a] -> [(b, [a])] }

而且我希望能够放入一个可能 是形式的子例程：[a] -> [b]，它需要一个字符缓冲区并将其发送到结果列表。这里的诀窍是子例程本身是一个有状态的计算，它在每次成功调用时转换状态（将其视为有限状态机）。具体来说：

  1. 如果子例程输出空 list []，则解析器将再插入一个 char 到缓冲区中并将其交给子例程，该子例程再次运行。
  2. 如果子例程输出非空列表[b]，则首先刷新缓冲区，然后解析器再将一个字符插入缓冲区，将其交给子例程。[b]存储在某处
  3. 在达到逃生条件之前，步骤 1 和 2 会一遍又一遍地运行。所有中间结果都应该以某种方式组合起来。

  4. 一旦达到转义条件，子例程将结果bs返回给解析器，并将其与剩余的流结合起来，as如下所示：

    rs = fmap (flip (,) as) bs :: [(b,[a])]

从而满足签名runP

该函数可能具有以下签名：withf :: ([a] -> [b]) -> Parser a b

重要的是它withf g必须是一个解析器，所以我可以使用<*>. 注意函数签名Suggestg是一个纯函数，所以它不太可能是正确的。

尝试过的解决方案

我尝试使用各种协程包来实现这一点，但对我来说，lift将解析器放入协程计算上下文中更有意义，将它与也提升到上下文中的转换器组合在一起，这意味着它不再是解析器。

我还尝试将其实现withf为可以访问 Parser 值构造函数的原始函数。基本上将步骤 1..4 转换为代码。我这里最大的问题是谁负责什么信息：

  1. 缓冲区状态
  2. 中间结果的状态
  3. 如何组合中间结果的逻辑。
  4. 应该如何实现转义条件，或者更好地组合成withf

我还尝试了直接在解析器中烘焙的各种自制协程实现（因此不使用Parser上面定义的类型），但收效甚微。

任何能指出我正确方向的人都非常感谢。

4

2 回答 2

3

首先让我们在解析器中使用MonadPlus而不是。[]它将使它更通用并稍微澄清代码（我们不会有那么多嵌套[]的 s）：

newtype Parser a m b = P { runP :: [a] -> m (b, [a]) }

我建议您更改子例程的签名。你需要的是：

  • 子程序是否需要更多输入的信号，以及
  • 将状态保持在某个地方。

这可以通过这种类型签名轻松完成：

newtype Sub a b = Sub { runSub :: Either (a -> Sub a b) [b] }

一个子程序要么产生一个结果，要么请求一个新的输入并产生一个新的子程序。这样，您可以通过将其传递到返回的子例程来保持所需的任何状态。转换函数将如下所示：

withf :: (MonadPlus m) => Sub a b -> Parser a m b
withf start = P $ f (runSub start)
  where
    f (Right bs) xs   = msum [ return (b, xs) | b <- bs ]
    f (Left r)   []   = mzero    -- No more input, can't proceed.
    f (Left r) (x:xs) = f (runSub (r x)) xs

更新：我们可以采取的另一种方法是意识到解析器实际上是一个StateT转换器，其状态是[a]：

type Parser a m b = StateT [a] m b

runP :: (Monad m) => Parser a m b -> [a] -> m (b, [a])
runP = runStateT

确实，runP正是runStateT！

这样，我们就可以免费获得一个Monad实例Parser。现在我们可以将我们的任务分成更小的块。首先，我们创建一个解析器，它使用一个输入，或者失败：

receive :: (MonadPlus m) => Parser a m a
receive = get >>= f
  where
    f []        = mzero    -- No more input, can't proceed.
    f (x:xs)    = put xs >> return x

然后用它来描述withf：

withf :: (MonadPlus m) => Sub a b -> Parser a m b
withf start = f (runSub start)
  where
    f (Right bs) = msum (map return bs)
    f (Left r)   = receive >>= f . runSub . r

注意 ifm是 a MonadPlusthen 也是StateT s ma ，MonadPlus所以我们可以直接使用with 。mzeromsumParser

于 2013-08-02T07:31:07.153 回答
2

首先，让我们定义一个新的数据类型来表示解析的可能结果。

data Step r = Done | Fail | Succ r

解析器可以用 结束Done，用 指示解析失败或用成功Fail返回解析值。rSucc r

我们将使我们的数据类型成为类型类Step的实例Monoid

instance Monoid (Step r) where
    mempty = Done
    Done   `mappend` _ = Done
    Fail   `mappend` x = x
    Succ r `mappend` _ = Succ r

如果我们的解析器是Done，我们应该立即终止。AFail意味着我们应该检查下Step一个的结果是否可能成功。Succ r，当然，意味着我们已经成功地解析了一个值。

现在让我们为 a 定义一个类型同义词Parser。它需要能够累积解析结果（Writer）并保持表示尚未消费的输入的纯状态（State）。

{-# LANGUAGE FlexibleContexts #-}                                                                   

import Control.Monad.State
import Control.Monad.Writer
import Data.List
import Data.Foldable

type Parser w s = WriterT w (State s)

evalParser :: Parser w s r -> s -> w
evalParser = evalState . execWriterT

这是实际的解析器

parser :: (MonadState [s] m, MonadWriter [w] m) => ([s] -> Step [w]) -> m ()
parser sub = do
    bufs <- gets inits
    -- try our subroutine on increasingly long prefixes until we are done,
    -- or there is nothing left to parse, or we successfully parse something
    case foldMap sub bufs of
         Done   -> return ()
         Fail   -> return ()
         Succ r -> do
            -- record our parsed result
            tell r
            -- remove the parsed result from the state
            modify (drop $ length r) 
            -- parse some more
            parser sub

和一个简单的测试用例

test :: String
test = evalParser (parse sub) "aabbcdde"
    where sub "aabb" = Succ "aabb"
          sub "cdd"  = Succ "cdd"
          sub "e"    = Done
          sub _      = Fail

-- test == "aabbcdd"
于 2013-08-02T04:15:05.123 回答