Einen Parser von Grund auf in Haskell schreiben

Question

Gibt es ein gutes Tutorial, um einen Parser für eine gegebene Grammatik in Haskell von Grund auf neu zu schreiben?

ich gefunden:

1. parsing expressions and statements (HaskellWiki)

2. Parsing a simple imperative language (HaskellWiki)

3. Using parsec (Real World Haskell)

aber alle diese die Parsec-Bibliothek verwenden, und während die für interessant sein kann Indust rial-Anwendungen Ich suche gezielt nach Beispielen, die ohne den Einsatz von hochentwickelten Bibliotheken "von unten" funktionieren.

Die einzige, die ich gefunden, die ‚Basis‘ Haskell verwendet, ist dies: Parsing with Haskell , die einige sehr fremden Syntax verwendet (es ist sehr schwer zu unterscheiden, was von dem Programm oder was nur ‚Pseudo-Code‘) und es gibt keine explizite Grammatikdefinition .

Alle Vorschläge werden sehr geschätzt!

Answer 1

Es ist erstaunlich einfach, Parsec von Grund auf neu zu erstellen. Der eigentliche Bibliothekscode selbst ist stark verallgemeinert und optimiert, was die Kernabstraktion verzerrt, aber wenn Sie nur Dinge von Grund auf neu erstellen, um mehr darüber zu verstehen, was vor sich geht, können Sie es in ein paar Zeilen Code schreiben. Ich werde einen etwas schwächeren Parser unten erstellen.

Im Wesentlichen haben wir eine Applicative, Parser zusammen mit einem primitiven Parser Wert

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

und ein paar combinators wie try produzieren wollen, die "rückgängig gemacht" ein Parser, wenn es fehlschlägt

try :: Parser a -> Parser a 

und orElse, was es uns ermöglicht, mit einem zweiten Parser fortzufahren, wenn der erste Parser fehlschlägt. Normalerweise ist dies tatsächlich mit dem Infix combinator geschrieben (<|>)

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

Da unsere Applicative Bedürfnisse Spur des aktuellen Stream Zustand zu halten und in der Lage zu scheitern, werden wir es bauen durch die Kombination der Staat Applicative und die Either applicative.

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) 

Wenn wir die (<*>) Methode in der Applicative Beispiel folgen sorgfältig sehen wir, dass es geht nur um den Strom in den f produzierenden Parser, führt den Ergebnisstrom und, falls erfolgreich, übergibt sie an die x -produzierenden Parser und wenn beide erfolgreich sind, gibt sie ihre Anwendung (f x) zurück. Das bedeutet, dass, wenn wir eine Funktion produzierenden Parser und ein Argument produzierenden Parser haben wir können Sequenz sie mit (<*>)

-- given 
parseChar :: Char -> Parser Char 

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

Wir haben die Mechanik dieser Applicative können die benötigten combinators auch zu bauen. Hier ist 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") 

Und hier ist 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) 

Und hier ist 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) 

Typisch an dieser Stelle auch wir fest, dass Parser bildet eine Alternative Instanz mit orElse, wenn wir auch eine sofort zur Verfügung stellen fehlender Parser, empty

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

    many = manyParser 
    some = someParser 

Und wir können manyParser und someParser als combinators schreiben, die immer wieder einen Parser ausgeführt werden.

-- | 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)) 

Und von hier aus können wir anfangen, auf viel höheren Abstraktionsebenen zu arbeiten.

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

Ich mochte Graham Huttons "Programmierung in Haskell" wirklich. Es gibt eine sanfte Einführung in Monaden und Parser-Kombinatoren. Das achte Kapitel baut eine grundlegende Parser-Bibliothek.

Hier ist der Link to Programming in Haskell book site. Sie finden auch einen Link zur Parser-Bibliothek und zum grundlegenden Ausdrucksparser.

Weiter, wenn Sie interessiert sind, können Sie auch auf uu-parsinglib Anwendung Stil Parser Kombinator an der Universität Utrecht entwickelt.