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

Question

问题

我正在滚动一个非确定性解析器进行自学，它看起来像:

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

我希望能够插入一个可能形式的子例程:[a] -> [b] ，它获取字符缓冲区并将其发送到结果列表。这里的技巧是子例程本身是一个有状态计算，并且它在每次成功调用时在状态之间转换(将其视为有限状态机)。具体来说:

1. 如果子例程输出空列表[] ，解析器会在缓冲区中再插入一个字符，并将其交给子例程，该子例程再次运行。
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必须是一个解析器，所以我可以使用 <*> 构建更大的解析器。注意函数签名建议 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 的 Monad 实例。现在我们可以将任务分成更小的 block 。首先，我们创建一个解析器，它消耗一个输入，否则就会失败:

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。