Haskell的级联解析器

debugcn 发表于 Dev

托默

我的解析器类型是

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

我有两个解析器：

1）a = (satisfy isAlpha)知道如何匹配字符串中的第一个字母数字字符。

跑步parse a "k345"给Just ('k',"345")

2）b = many (satisfy isDigit)知道如何匹配任意数量的数字。跑步parse b "1234 abc"给Just ("1234"," abc")

现在，我想结合这两个解析器，并匹配一个单字母数字字符，后跟任意数量的数字。

我试过了：

parse (a *> b) "k1234 7"并得到了Just ("1234"," 7 ")。看起来'k'第一个解析器匹配的内容a从输出中消失了。我该如何解决这个问题？

谢谢！

对于玩具解析器，请查看以下代码：

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
module Parse where

import Data.Char
import Data.List

newtype Parser a = Parser 
  { parse :: String -> Maybe (a, String) }

satisfy :: (Char -> Bool) -> Parser Char
satisfy cond = Parser $ \s ->
   case s of 
     "" -> Nothing 
     (c:cs) -> if cond c then Just (c, cs) else Nothing

many :: Parser a -> Parser [a]
many p = Parser $ \s -> 
  case parse p s of 
    Nothing -> Just ([], s)
    Just (c, cs) -> let Just (cc, cs') = parse (many p) cs
                     in Just (c:cc, cs')

string :: String -> Parser String 
string str = Parser $ \s -> if isPrefixOf str s 
                               then Just (str, drop (length str) s)
                               else Nothing

instance Functor Parser where 
  fmap f (Parser g) = Parser $ \s -> 
    case g s of
      Nothing -> Nothing
      Just (r, remain) -> Just (f r, remain)

instance Applicative Parser where
  pure a = Parser $ \s -> Just (a, s)
  -- (<*>) :: f (a -> b) -> f a -> f b
  (Parser f) <*> (Parser g) = Parser $ \s -> 
    case f s of
      Nothing -> Nothing
      Just (ab, remain) -> case g remain of
                            Nothing -> Nothing
                            Just (r, remain1) -> Just (ab r, remain1)

instance Semigroup a => Semigroup (Parser a) where 
  (Parser p1) <> (Parser p2) = Parser $ \s -> 
    case p1 s of 
      Nothing -> Nothing 
      Just (r1, s1) -> case p2 s1 of 
                         Nothing -> Nothing 
                         Just (r2, s2) -> Just (r1 <> r2, s2)

instance (Monoid a, Semigroup (Parser a))=> Monoid (Parser a) where
  mempty = Parser $ \s -> Just (mempty, s)
  mappend = (<>)

a = satisfy isAlpha
b = many (satisfy isDigit)

λ> parse a "k345"
Just ('k',"345")
λ> parse b "12345 abc"
Just ("12345"," abc")
λ> parse (a *> b) "k1234 7"
Just ("1234"," 7")
λ> parse (string "k" <> b) "k1234 7"
Just ("k1234"," 7")

因此，也许你应该找到一些教程，并尝试熟悉Functor，Applicative和Monad。看，您可以Monoid为您的Parser类型实现a的实例，然后可以使用(<>)来将解析的结果组合在一起。