在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。