ハスケルのゼロからパーサーを書く

Question

ハスケルの与えられた文法のパーサーを一から書くための良いチュートリアルはありますか？

私が見つけた：

1. parsing expressions and statements (HaskellWiki)

2. Parsing a simple imperative language (HaskellWiki)

3. Using parsec (Real World Haskell)

が、これらのすべてはパーセクのライブラリを使用し、それがために面白いかもしれないがインダストリアルrialアプリケーション私は、洗練されたライブラリを使用せずに「ボトムアップ」している例を具体的に探しています。

「基本」はHaskellを使用して、私が見つけた唯一の一つがこれです：いくつかの非常に外国の構文を使用していますParsing with Haskell （それは区別することは非常に難しいいただきましたプログラムの一部またはいただきました！唯一の「擬似コード」）と明示的な文法定義はありません。

どのような提案も高く評価されています。

Answer 1

実際にParsecを最初から構築するのは驚くほど簡単です。実際のライブラリコード自体は大きく一般化され、最適化されてコア抽象化に矛盾しますが、何が起こっているかを理解するために何かを構築しているのであれば、ほんの数行のコードで書くことができます。私は少し弱いApplicativeパーサーを構築します。

基本的に、我々はプリミティブパーサ値

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

と、このようなことが

try :: Parser a -> Parser a 

を失敗した場合、パーサーを「取り消し」 try、など、いくつかコンビネータとともに Applicative、 Parserを生成したいです

とorElseを使用すると、最初のパーサーが失敗した場合に2番目のパーサーを続けることができます。通常、これは実際に私達が状態ApplicativeとEither応用的に組み合わせることで、それを構築します、現在のストリームの状態を追跡し、失敗することができるように私たちのApplicativeニーズので中置コンビネータ(<|>)

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

で書かれています。

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インスタンスで(<*>)方法に従った場合は、慎重に、我々はそれだけでParserを産生fにストリームを渡すことがわかり、結果ストリームを取り、、成功した場合、Parserを産生xに渡します両方とも成功した場合は、アプリケーション(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、我々はまた、我々はまた、すぐに提供する場合ParserはorElseでAlternativeインスタンスを形成していることに注意してください。この時点で、一般的に

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) 

だだです失敗したパーサー、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"が本当に好きです。それは、モナドとパーサーコンビネータを穏やかに紹介します。第8章では、基本的なパーサライブラリを作成します。

ここにリンクto Programming in Haskell book siteがあります。また、パーサライブラリと基本式パーサへのリンクもあります。

さらに興味のある方は、Utrecht Universityで開発されたuu-parsinglibアプリケーションスタイルパーサーコンビネータをご覧ください。