Haskell'de sıfırdan bir ayrıştırıcı yazma

Question

Haskell'de belirli bir dilbilgisi için bir ayrıştırıcıyı sıfırdan yazmak için iyi bir öğretici var mı?

buldum: bunun için ilginç olabilir iken

1. parsing expressions and statements (HaskellWiki)

2. Parsing a simple imperative language (HaskellWiki)

3. Using parsec (Real World Haskell)

fakat bunların hepsi parsekten kütüphane kullanın ve indust rial uygulamaları Özellikle sofistike kütüphaneler kullanılmadan 'aşağıdan yukarı' olan örnekleri arıyorum.

'temel' Haskell kullanan buldum tek şudur: bazı çok yabancı sözdizimi kullanır Parsing with Haskell (ayırt etmek çok zordur neyin programın parçası veya neyin Yalnızca 'yalancı kod') ve hiçbir açık dilbilgisi tanımı olmasa .

Her türlü öneri çok takdir edilmektedir!

Answer 1

Parsec'ten çizik yapmak aslında şaşırtıcı derecede kolaydır. Gerçek kütüphane kodunun kendisi, çekirdek soyutlamayı bozan, ağır bir şekilde genelleştirilmiş ve optimize edilmiştir, ancak bir şeyleri sıfırdan inşa ediyorsanız, neler olup bittiğini anlamak için sadece birkaç satırlık kod yazabilirsiniz. Aşağıda biraz daha zayıf bir Applicative ayrıştırıcısı inşa edeceğim.

Esasen, biz "undoes" ilkel ayrıştırıcı değeri

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

ve try gibi birkaç bağdaştırıcılarla ile birlikte bir Applicative, Parser üretmek isteyen bir çözümleyici

try :: Parser a -> Parser a 

başarısız olursa İlk ayrıştırıcı bozulursa ikinci bir ayrıştırıcıya devam etmemizi sağlayan

ve orElse. Genellikle bu aslında mevcut akış durumunu izlemek ve biz devlet Applicative ve Either uygulamalı birleştirerek inşa edeceğiz başarısız edebilmek için bizim Applicative ihtiyaçları yana infix combinator (<|>)

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

ile yazılmıştır.dikkatle sadece Parser üreten f içine akışı geçer görüyoruz biz Applicative durumda (<*>) yöntemi izlerseniz başarılı olursa

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) 

, xParser üreten geçirir, sonuç akımını alır ve ve ikisi de başarılı olursa, uygulamalarını (f x) döndürür. Bu, biz (<*>)

-- given 
parseChar :: Char -> Parser Char 

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

bir işlev üreten ayrıştırıcı ve biz bir argüman üreten ayrıştırıcı dizisi onlara sahip, biz de gerekli combinators oluşturmak için bu Applicative mekaniği kullanabileceği anlamına gelir. İşte 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") 

var Ve burada 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) 

var Ve burada da orElse ile Parser formları Alternative örneği de hemen temin eğer dikkat bu noktada Tipik 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) 

var başarısız ayrıştırıcı, empty

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

    many = manyParser 
    some = someParser 

Ve defalarca bir ayrıştırıcı çalıştırmak, bağdaştırıcılarla olarak manyParser ve someParser yazabilir.

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

Ve buradan çok daha yüksek soyutlama düzeylerinde çalışmaya başlayabiliriz.

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'un "Haskell'de Programlama" ya çok sevdim. Monad ve ayrıştırıcı kombinatorlere nazikçe giriş yapar. Sekizinci bölüm, temel ayrıştırıcı kitaplığı oluşturur.

İşte bağlantı to Programming in Haskell book site. Ayrıştırıcı kitaplığına ve temel ifade ayrıştırıcısına da bağlantı bulacaksınız.

Ayrıca, ilgileniyorsanız, Utrecht Üniversitesi'nde geliştirilen uu-parsinglib uygulama stili ayrıştırıcı kombinatorlerine de bakabilirsiniz.