Haskell自定义解析器绑定与选择操作的输入解析状态问询

一、原始Parser定义与第一个问题 #

原始Parser代码 #

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'）。

疑问解答 #

第一个解析器确实已经运行：它成功消耗了输入字符串的第一个字符't'，得到剩余字符串"est"，并将这个剩余字符串传递给后续的char 't'解析器。但由于char 't'无法匹配"est"的第一个字符'e'，导致整个>>=组合的解析器返回Nothing。

因为runParser只返回解析结果（忽略剩余字符串），所以输出是Nothing。如果用能返回剩余字符串的runParser2测试，结果依然是Nothing——当后续解析失败时，整个组合解析器不会返回任何（剩余字符串+结果）的有效组合，相当于整个解析流程失败，不存在“剩余字符串”的有效输出。

二、新增Parser操作与第二个问题 #

新增Parser操作代码 #

(<|>) :: 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')

疑问解答 #

是的，(char 'w' >>= \a -> char 'o' >>= \b -> char 'r' >>= \c -> char 'l')被视为单个整体解析器：

1. 它内部的char 'w'和char 'o'确实成功消耗了输入的前两个字符，得到剩余字符串"qld"；
2. 但后续的char 'r'无法匹配"qld"的第一个字符'q'，导致整个组合解析器返回Nothing；
3. 由于<|>的逻辑是：如果第一个解析器失败，就回滚到原始输入字符串，再尝试第二个解析器；
4. 第二个解析器pure 'x'不会修改输入，直接返回原始输入"woqld"和结果'x'，所以最终输出是Just ("woqld",'x')。

内容的提问来源于stack exchange，提问作者user20102550