代码之家 › 专栏 › 技术社区 › user20102550

如果我们绑定两个解析器,而第二个解析器失败,字符串会被解析一次吗?

functional-programming haskell

user20102550 · 技术社区 · 10 月前

假设这是一个解析器:

data Parser a = MkParser (String -> Maybe (String, a))


runParser :: Parser a -> String -> Maybe a
runParser (MkParser sf) inp = case sf inp of
                                Nothing -> Nothing
                                Just (_, a) -> Just a


unParser :: Parser a -> String -> Maybe (String, a)
unParser (MkParser sf1) = sf1

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
-- takes a parser, and a second parser (second parser takes a char)
-- parses `a`, then feeds `a` to second parser...
MkParser pa >>= k = MkParser sf
    where
        sf inp = case pa inp of
            Nothing -> Nothing
            Just (as, a) -> unParser (k a) as
-- Question: If the second parser fails, does the first
-- parser still parse? What string does it return?
-- as or inp?

-- parses any char
anyChar :: Parser Char
anyChar = MkParser sf
  where
    sf "" = Nothing
    sf (c:cs) = Just (cs, c)

-- parses the char we want
char :: Char -> Parser Char
char wanted = MkParser sf
  where
    sf (c:cs) | c == wanted = Just (cs, c)
    sf _ = Nothing

假设我这样做

secondFail = anyChar >>= \c -> char c
runParser secondFail "test"

这给了 Nothing 因为 \c -> char c 失败( e 不是 t ).

我的问题是,第一个解析器运行了吗?输入字符串是否被解析了1次?是“est”还是因为第二个解析器失败,整个事情都失败了,字符串也没有被解析?

我不确定如何编写代码来测试输出,因为输出只是 没有什么 .

编辑:我想我回答了我自己的问题。我添加了这个函数(基本上,如果第一个解析器成功,什么都不做,但如果第一个分析器失败,运行第二个解析器:

(<|>) :: Parser a -> Parser a -> Parser a
-- Choice / Backtrack.
-- takes two parsers
-- tries one parse
-- pa1 stringInput
-- saves the location
-- if it fales, reverts back,
-- gives stringInput (no change) to 
-- pa2.
MkParser pa1 <|> pa2 = MkParser sf
    where
        sf inp = case pa1 inp of
            Nothing -> unParser pa2 inp
            j -> j

-- I want to be able to produce a parser that gives exactly what I want and
-- doesn't change the input string at all, doesn't touch it
pure :: a -> Parser a
pure a = MkParser (\inp -> Just (inp, a))

添加了以下内容来运行解析器:

runParser2 :: Parser a -> String -> Maybe (String, a)
runParser2 (MkParser pa) inp = pa inp

然后我做了这个:

secondFail = (char 'w' >>= \a -> char 'o' >>= \b -> char 'r'  >>= \c -> char 'l') <|> pure 'x'

然后运行它:

runParser2 secondFail "woqld"

这给了

Just ("woqld",'x')

它能给吗 Just ("woqld",'x') 因为 (char 'w' >>= \a -> char 'o' >>= \b -> char 'r' >>= \c -> char 'l') 被视为一个解析器?尽管 w 和 o 解析器成功,此后整个解析器失败 r 失败?因此,它恢复到原始输入并将其提供给 pure 'x' ?

1 回复 | 直到 10 月前

Noughtmare 10 月前

对于第二个解析器 char c 为了能够启动它,必须首先赋予它以下字符 anyChar 返回。因此,如果第二个解析器失败,则第一个解析器必须成功。

你可以这样测试它:

import Debug.Trace

traceCurrentString :: Parser ()
traceCurrentString = MkParser (\s -> traceShow s (Just (s, ())))

secondFail = anyChar >>= \c -> traceCurrentString >>= \() -> char c

那么 secondFail 产生以下输出:

ghci> runParser secondFail "test"
"est"
Nothing

请注意,这样的跟踪是不可靠的,可能会受到优化的影响,因此您应该只将其用于调试,即使这样,您也应该对结果持怀疑态度。

编辑:关于你的编辑,你应该使用这样的解析器:

secondFail =
  char 'w' >>= (\a ->
    char 'o' >>= (\b ->
      char 'r'  >>= (\c -> char 'l' <|> pure '4')
        <|> pure '3')
    <|> pure '2')
  <|> pure '1'

然后,您将看到预期的结果:

ghci> runParser2 secondFail "woqld"
Just ("qld",'3')