在Haskell中从头开始编写解析器

Question

是否有从头开始为Haskell中的给定语法编写解析器的好教程？

我发现：

1. parsing expressions and statements (HaskellWiki)

2. Parsing a simple imperative language (HaskellWiki)

3. Using parsec (Real World Haskell)

但所有这些使用秒差距库，虽然这可能是有趣的INDUST rial应用程序我特别寻找不使用复杂库的'自下而上'的示例。

唯一一个我发现它使用“基本” Haskell是这样的：Parsing with Haskell 它使用了一些非常外来语法（这是很难区分什么程序的一部分，或者什么只有“伪”），而且也没有明确的语法定义。

任何建议，非常感谢！

Answer 1

从头开始构建Parsec实际上非常容易。实际的库代码本身是大量泛化和优化的，它扭曲了核心抽象，但是如果你只是从头开始构建一些东西来了解更多关于发生的事情，你可以用几行代码来编写它。下面我将构建一个稍微弱一点的Applicative解析器。

从本质上讲，我们要产生Applicative，Parser与原始解析器值

satisfy :: (Char -> Bool) -> Parser Char 

和try几个组合程序等，其中“撤消”沿着一个分析器，如果失败

try :: Parser a -> Parser a 

和orElse，如果第一个解析器失败，它允许我们继续使用第二个解析器。通常，这实际上是与缀组合子(<|>)

orElse, (<|>) :: Parser a -> Parser a -> Parser a 

书面自从我们Applicative需要跟踪当前流状态，并能够失败，我们将结合国家Applicative和Either应用性构建它。

type Error = String 
newtype Parser a = P { unP :: String -> (String, Either Error a) } 

instance Functor Parser where 
    fmap f (P st) = P $ \stream -> case st stream of 
    (res, Left err) -> (res, Left err) 
    (res, Right a) -> (res, Right (f a)) 

instance Applicative Parser where 
    pure a = P (\stream -> (stream, Right a)) 
    P ff <*> P xx = P $ \stream0 -> case ff stream0 of -- produce an f 
    (stream1, Left err) -> (stream1, Left err) 
    (stream1, Right f) -> case xx stream1 of   -- produce an x 
     (stream2, Left err) -> (stream2, Left err) 
     (stream2, Right x) -> (stream2, Right (f x)) -- return (f x) 

如果我们遵循Applicative实例(<*>)方法仔细我们可以看到，它只是通过流进f - 生产Parser，取结果流，如果成功，它传递到x - 生产Parser如果它们都成功，则返回其应用程序(f x)。这意味着，如果我们有一个函数产生解析器和参数产生的解析器，我们可以序列他们(<*>)

-- given 
parseChar :: Char -> Parser Char 

parseHi :: Parser (Char, Char) -- parses 'h' then 'i' 
parseHi = pure (,) <$> parseChar 'h' <*> parseChar 'i' 

我们可以使用这个Applicative的机制建设所需的组合程序也是如此。这里的satisfy

-- | Peek at the next character and return successfully if it satisfies a predicate 
satisfy :: (Char -> Bool) -> Parser Char 
satisfy f = P $ \stream -> case stream of 
    []     -> ([], Left "end of stream") 
    (c:cs) | f c  -> (cs, Right c) 
     | otherwise -> (cs, Left "did not satisfy") 

而这里的try

-- | Run a parser but if it fails revert the stream to it's original state 
try :: Parser a -> Parser a 
try (P f) = P $ \stream0 -> case f stream0 of 
    (_  , Left err) -> (stream0, Left err) 
    (stream1, Right a) -> (stream1, Right a) 

而这里的orElse

orElse :: Parser a -> Parser a -> Parser a 
orElse (P f1) (P f2) = P $ \stream0 -> case f1 stream0 of 
    (stream1, Left err) -> f2 stream1 
    (stream1, Right a) -> (stream1, Right a) 

通常在这一点上，我们也注意到，Parser形式的Alternative实例与orElse如果我们也立即提供失败的解析器，empty

instance Alternative Parser where 
    empty = P $ \stream -> (stream, Left "empty") 
    (<|>) = orElse 

    many = manyParser 
    some = someParser 

，我们可以写manyParser和someParser作为重复运行一个解析器组合。

-- | 0 or more 
manyParser :: Parser a -> Parser [a] 
manyParser (P f) = P go where 
    go stream = case f stream of 
    (_  , Left err) -> (stream, Right []) -- throws away the error 
    (stream', Right a) -> case go stream' of 
     (streamFin, Left err) -> (streamFin, Left err) 
     (streamFin, Right as) -> (streamFin, Right (a : as)) 

-- | 1 or more 
someParser :: Parser a -> Parser [a] 
someParser (P f) = P $ \stream -> case f stream of 
    (stream', Left err) -> (stream', Left err) 
    (stream', Right a) -> 
    let (P fmany) = manyParser (P f) 
    in case fmany stream' of 
     (stream'', Left err) -> (stream'', Left err) 
     (stream'', Right as) -> (stream'', Right (a:as)) 

从这里我们可以开始在更高层次的抽象工作。

char :: Char -> Parser Char 
char c = satisfy (== c) 

string :: String -> Parser String 
string []  = pure [] 
string (c:cs) = (:) <$> char c <*> string cs 

oneOf :: [Char] -> Parser Char 
oneOf cs = satisfy (`elem` cs) 

parens :: Parser a -> Parser a 
parens parseA = dropFirstAndLast <$> char '(' <*> parseA <*> char ')' 
    where 
    dropFirstAndLast _ a _ = a 

Answer 2

我真的很喜欢Graham Hutton的“Programming in Haskell”。它给monads和解析器组合器提供了一个温和的介绍。第八章构建一个基本的解析器库。

这里是链接to Programming in Haskell book site。您还可以找到解析器库和基本表达式解析器的链接。此外，如果您有兴趣，您还可以查看在乌得勒支大学开发的应用式样分析器组合器uu-parsinglib。