将子例程放入解析器中的优雅方法是什么？

Question

问题

我正在推出一个用于自我教育的非确定性解析器，它看起来像是：

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

我希望能够插入一个子例程，可能是的形式：[a] -> [b]，它接受字符的缓冲区并将其发送到结果列表。这里的诀窍是，子例程本身是一个有状态的计算，每次调用成功时，它都会通过状态转换(把它看作是一个有限状态机)。具体地说：

1. 如果子例程输出空列表[]，解析器将再向缓冲区插入一个字符并将其生成给子例程，该子例程将再次运行。
2. 如果子例程输出非空列表[b]，则首先刷新缓冲区，解析器再向缓冲区插入一个字符，使其生成子例程。[b]存储在某个地方
3. 在达到转义条件之前，步骤1和步骤2会一次又一次地运行。所有中间结果都应以某种方式结合起来。
4. 一旦达到转义条件，子例程将结果bs返回给解析器，并将其与剩余的as流组合，如下所示： rs = fmap (倒装(，) as) bs :：[(b，a)]

从而满足runP的签名

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

重要的是，withf g必须是一个解析器，所以我可以使用<*>构建更大的解析器。注意，函数签名表明g是一个纯函数，因此不太可能是正确的。

试用解决方案

我试着使用各种协同器包来实现这一点，但对我来说，将解析器lift为协同计算上下文更有意义，它使用一个转换器组成，换能器也被提升到上下文中，这意味着它不再是一个解析器。

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

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

我还尝试了在解析器中直接使用各种家庭酿协同器实现(所以不使用上面定义的Parser类型)，但没有取得什么成功。

任何能为我指明正确方向的人都会受到极大的赞赏。

Answer 1

首先，让我们在解析器中使用MonadPlus而不是[]。它将使它更加通用，并澄清一些代码(我们不会有那么多嵌套的[])：

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！

这样，我们就可以免费获得Parser的一个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

注意，如果m是一个MonadPlus，那么StateT s m也是一个MonadPlus，所以我们可以在Parser中直接使用mzero和msum。

Answer 2

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

data Step r = Done | Fail | Succ r

解析器可以用Done完成，用Fail指示失败的解析，也可以用Succ r成功地返回已解析的值r。

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

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

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

现在，让我们定义一个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"