Написание парсера с нуля на Хаскеле

Question

Есть ли хороший учебник для написания парсера для данной грамматики в Haskell с нуля?

Я нашел:

1. парсинг выражений и выражений (HaskellWiki)

2. Разбор простого императивного языка (HaskellWiki)

3. Использование parsec (Real World 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-продуцирующих 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

Мне очень понравилась "Программирование в Хаскеле" Грэма Хаттона. Это дает нежное введение в монады и парсер комбинаторы. Восьмая глава создает базовую библиотеку синтаксического анализатора.

Вот ссылка на Программирование на сайте книги Haskell. Вы также найдете ссылку на библиотеку парсера и парсер базовых выражений.

Кроме того, если вам интересно, вы также можете посмотреть на комбинаторы парсера аппликативного стиля uu-parsinglib, разработанные в Утрехтском университете.