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

Question

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

我发现:

1. 解析表达式和语句(HaskellWiki)

2. 解析一个简单的命令式语言(HaskellWiki)

3. 使用parsec(真实世界Haskell)

但所有这些都使用了parsec库,虽然这可能对工业应用程序很有意思,但我特别在寻找没有使用复杂库的"自下而上"的例子.

我发现使用'基本'Haskell的唯一一个是: 使用一些非常外来的语法解析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递到-producing Parser,获取结果流,如果成功,则将其传递给x-producing 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”。它对 monad 和解析器组合器进行了温和的介绍。第八章构建了一个基本的解析器库。

这是在 Haskell 书籍站点中编程的链接。您还将找到解析器库和基本表达式解析器的链接。

此外，如果您有兴趣，还可以查看乌得勒支大学开发的uu-parsinglib applicative style parser combinators。