2

问题陈述

假设我有两个解析器p，q并且像这样连接它们：

r = try p *> q

在 Parsec 中，其行为是：

  • 如果p在不消耗输入的情况下失败，则r在不消耗输入的情况下失败。
  • 如果p在消耗输入后r失败，则在不消耗输入的情况下失败。
  • 如果q在不消耗输入的情况下失败，则r在消费后失败p。
  • 如果q在消费输入后r失败，则在消费p和部分后失败q。

但是，我正在寻找的行为有点不寻常：

  • 如果p在不消耗输入的情况下失败，则r应该在不消耗输入的情况下失败。
  • 如果p在使用输入后失败，则r应该在不使用输入的情况下失败。
  • 如果q在不消耗输入的情况下失败，那么r 应该在不消耗输入的情况下失败。
  • 如果q在消费输入后失败，那么r在消费一些输入后应该会失败。

我似乎想不出一个干净的方法来做到这一点。

基本原理

原因是我有一个这样的解析器：

s = (:) <$> q <*> many r

q嵌入在解析器r中的解析器需要一种方法来发出信号：无效输入（在q消耗输入但失败时发生）或many循环结束（在q不消耗任何内容并失败时发生）。如果输入无效，它应该完全使解析器失败并向用户报告问题。如果没有更多输入要消耗，那么它应该结束many循环（不向用户报告解析器错误）。问题是输入可能以 a 结尾p但没有任何更有效的q的 's 可以使用，在这种情况下q会失败但不消耗任何输入。

所以我想知道是否有人有一个优雅的方法来解决这个问题？谢谢。

附录：示例

p = string "P"
q = (++) <$> try (string "xy") <*> string "z"

（假设的） parser 上的测试输入s，它是否按我想要的方式工作：

  1. xyz（接受）
  2. xyzP（接受；P仍未解析）
  3. xyzPx（接受；Px仍未解析；q失败但未消耗任何输入）
  4. xyzPxy（拒绝；解析器q使用xy但失败）
  5. xyzPxyz（接受）

在表单r = try p *> q中，s实际上会同时拒绝上面的案例#2 和案例#3。当然，可以通过编写来实现上述行为：

r = (++) <$> try (string "P" *> string "xy") <*> string "z"

但这不是适用于任何解析器p和q. （也许不存在通用解决方案？）

4

1 回答 1

1

我相信我找到了解决方案。这不是特别好，但似乎有效。至少要开始：

{-# LANGUAGE FlexibleContexts #-}
import Control.Applicative hiding (many, (<|>))
import Control.Monad (void)
import Control.Monad.Trans (lift)
import Control.Monad.Trans.Maybe
import Text.Parsec hiding (optional)
import Text.Parsec.Char
import Text.Parsec.String

rcomb ::  (Stream s m t) => ParsecT s u m a -> ParsecT s u m b -> ParsecT s u m b
rcomb p q = ((test $ opt p *> opt q) <|> pure (Just ()))
                >>= maybe empty (\_ -> p *> q)
  where
    -- | Converts failure to @MaybeT Nothing@:
    opt = MaybeT . optional -- optional from Control.Applicative!
    -- | Tests running a parser, returns Nothing if parsers failed consuming no
    -- input, Just () otherwise.
    test = lookAhead . try . runMaybeT . void

这是r您要的组合器。这个想法是我们首先在“测试”运行中执行解析器（使用lookAhead . try），如果其中任何一个在没有消耗输入的情况下失败，我们将其记录为Nothinginside MaybeT。这是通过 完成的opt，它将失败转换为Nothing并将其包装到MaybeT. 感谢MaybeT, 如果opt p返回Nothing,opt q被跳过。

如果两者都p成功q，则该test ..部分返回Just ()。如果其中一个消耗输入，则整个test ..失败。这样，我们区分了 3 种可能性：

  1. p失败，某些输入被or消耗q。
  2. 失败使得失败的部分不消耗输入。
  3. 成功。

在<|> pure (Just ())1. 和 3. 结果之后Just ()，而 2. 结果为 Nothing。最后，该maybe部分转换Nothing为非消耗性故障，并Just ()再次运行解析器，现在没有任何保护。这意味着 1. 再次失败并消耗了一些输入，而 3. 成功了。

测试：

samples =
    [ "xyz" -- (accept)
    , "xyzP" -- (accept; P remains unparsed)
    , "xyzPz" -- (accept; Pz remains unparsed)
    , "xyzPx" -- (accept; Px remains unparsed; q failed but did not consume any input)
    , "xyzPxy" -- (reject; parser q consumed xy but failed)
    , "xyzPxyz" -- (accept)
    ]

main = do
    -- Runs a parser and then accept anything, which shows what's left in the
    -- input buffer:
    let run p x = runP ((,) <$> p <*> many anyChar) () x x

    let p, q :: Parser String
        p = string "P"
        q = (++) <$> try (string "xy") <*> string "z"

    let parser = show <$> ((:) <$> q <*> many (rcomb p q))
    mapM_ (print . run parser) samples
于 2013-09-03T08:29:24.320 回答