| ClipArtMag Science Blog |

Free Cliparts

Пересматривание «Одноместного парсинга в Haskell»

Перевод статьи - Revisiting 'Monadic Parsing in Haskell'

Автор - Vaibhav Sagar

Источник оригинальной статьи:

http://vaibhavsagar.com/blog/2018/02/04/revisiting-monadic-parsing-haskell/

"Одноместный парсинг в Haskell" - это короткая статья, которая заложила основу для библиотек, таких как Parsec и Attoparsec. Хотя она была опубликована в 1998 году (почти 20 лет тому назад!), она изящно стареет но образцы кода будут работать практически без изменений. Тем не менее, уровень технологий продвинулась с тех пор и я думаю, что использование современного Haskell может сделать этот материал более простым в использовании и реализации.

Одноместный парсинг в Haskell - это то, что продало меня на всех трех. Перед Haskell мой опыт с синтаксическим анализом включали багги-регулярные выражения для лексер и инструментов для борьбы, таких как bison и flex, и хотя я слышал, что Haskell хорошо разбирался в разборе, я не мог понять, как это может быть, когда я не мог найти надежные библиотеки регулярных выражений! В некоторых документах я указал на Attoparsec и когда я увидел пример парсера RFC2616, это показалось мне волшебным трюком. Как это может быть так мало? Спустя несколько недель, я сам убедился, что никогда не оглядывался назад. Это было первое применение монадов, с которыми я столкнулся, что на самом деле упростило мою жизнь и я начал понимать, что монадов больше, чем самодовольства и недоступных для новичков.

Первое изменение я хочу сделать, это определение типа. В этом документе используется тип

newtype Parser a = Parser (String -> [(a,String)])

и хотя это достаточно известное определение, что у него есть своя рифма, я думаю, что гибкость списков здесь потрачена впустую. Авторы не используют его и вместо этого определяют оператор (+++) «детерминированный выбор» который дает не более одного результата и использует его везде. В Haskell уже есть идеальный тип данных для списков не более одного элемента. Возможно, поэтому я буду использовать это вместо []:

newtype Parser a = Parser (String -> Maybe (a, String))

Если мы переименуем String в s и, возможно, Maybe в m, появится более интересная картина:

newtype Parser s m a = Parser (s -> m (a, s))

Это StateT! Признание этого шаблона упрощает определение экземпляров, тем более проще, что GHC может сделать это для нас автоматически с -XGeneralizedNewtypeDeriving! Для полноты я буду сопротивляться искушению сделать это, но Вы можете попробовать его сами с

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Parser a = Parser (StateT String Maybe a)
deriving (Functor, Applicative, Alternative, Monad)

Второе изменение также для полноты: авторы переходят прямо в экземпляр Монады, не определяя сначала Functor и Applicative. Ради справедливости, Applicative абстракция еще не была обнаружена и это также причина по которой авторы определяют mzero и mplus (которые они называют (++)) вместо более общих Alternative методов empty и (<|>). Из-за нашего изменения Maybe, определяющего Alternative, мне не нужно беспокоиться о их (+++).

Наконец, я постараюсь избежать do-нотация, если это возможно, в пользу более подходящего стиля с использованием, например, <*> (который может быть объявлен «splat» если у вас пока нет имени для этого) потому что большинство этих парсеров этого не требуют.

Давайте начнем!

{-# LANGUAGE InstanceSigs #-}

import Control.Applicative (Alternative(..))
import Control.Monad.Trans.State.Strict
import Control.Monad (guard)
import Data.Char (isSpace, isDigit, ord)

Для удобства я определил unParser, который разворачивает Parser a в его базовую строку StateT String Maybe a.

newtype Parser a = Parser { unParser :: StateT String Maybe a }
runParser = runStateT . unParser

fmap так же просто как разворачивание Parser и использование fmap основного StateT.

instance Functor Parser where
    fmap :: (a -> b) -> Parser a -> Parser b
    fmap f p = Parser $ f <$> unParser p

Больше разворачивается для Applicative и Alternative.

Alternative тип-класс позволяет нам выразить идею запуска одного парсера или другого, в результате чего получается первый успешный синтаксический анализ. empty обрабатывает случай, когда оба парсера терпят неудачу и (<|>) (который может быть произнесен «alt») выполняет чередование. Это достаточно удобно для себя, но Alternative также предоставляет many и some, которые точно соответствуют many и many1 из статьи:

-- many v = some v <|> pure []
-- some v = (:) <$> v <*> many v

но только после замены [] с помощью Maybe, как я сделал здесь (<|>) соответствует (+++).

instance Applicative Parser where
    pure :: a -> Parser a
    pure a = Parser $ pure a
    (<*>) :: Parser (a -> b) -> Parser a -> Parser b
    f <*> a = Parser $ unParser f <*> unParser a

instance Alternative Parser where
    empty :: Parser a
    empty = Parser empty
    (<|>) :: Parser a -> Parser a -> Parser a
    a <|> b = Parser $ unParser a <|> unParser b

Определение Monad немного интереснее, потому что мы должны вручную построить значение StateT, но это также сводится к разворачиванию и переделке.

instance Monad Parser where
    (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    a >>= f = Parser $ StateT $ \s -> do
        (a', s') <- runParser a s
        runParser (f a') s'

Обратите внимание, что anyChar является единственной функцией ниже, которая вручную создается Parser и удовлетворить это единственное, что требует интерфейса Monad.

anyChar :: Parser Char
anyChar = Parser . StateT $ \s -> case s of
    [] -> empty
    (c:cs) -> pure (c, cs)

satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = do
    c <- anyChar
    guard $ pred c
    pure c

char :: Char -> Parser Char
char = satisfy . (==)

string :: String -> Parser String
string [] = pure []
string (c:cs) = (:) <$> char c <*> string cs

Опять же, many и many1 не нужно определять, потому что они вначале предоставляются!

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy p sep = (p `sepBy1` sep) <|> pure []

sepBy1 :: Parser a -> Parser b -> Parser [a]
sepBy1 p sep = (:) <$> p <*> many (sep *> p)

Они почти идентичны определениям в документе. Я включил chainr для полноты.

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) <|> pure a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = p >>= rest
    where
        rest a = (do
            f <- op
            b <- p
            rest (f a b)) <|> pure a

chainr :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainr p op a = (p `chainr1` op) <|> pure a

chainr1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainr1 p op = scan
    where
        scan = p >>= rest
        rest a = (do
            f <- op
            b <- scan
            rest (f a b)) <|> pure a

Единственное различие здесь заключается в замене (>>) на (*>). Они имеют тот же эффект, за исключением того, что последний работает на Applicatives, а также поставляется с аналогами (<*). При написании парсеров я считаю их особенно полезными, потому что они позволяют мне объединять несколько парсеров вместе, когда я забочусь только о выходе одного из них, например. ignored *> ignored *> value <* ignored. В примере калькулятора, это используется в коэффициенте.

space :: Parser String
space = many (satisfy isSpace)

token :: Parser a -> Parser a
token p = p <* space

symbol :: String -> Parser String
symbol = token . string

apply :: Parser a -> String -> Maybe (a, String)
apply p = runParser (space *> p)

Пример калькулятора почти не изменился.

expr, term, factor, digit :: Parser Int
expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = digit <|> (symbol "(" *> expr <* symbol ")")
digit = subtract (ord '0') . ord <$> token (satisfy isDigit)

addop, mulop :: Parser (Int -> Int -> Int)
addop = (symbol "+" *> pure (+)) <|> (symbol "-" *> pure (-))
mulop = (symbol "*" *> pure (*)) <|> (symbol "/" *> pure (div))

Наконец, выплата!

runParser expr "(1 + 2 * 4) / 3 + 5"

Просто (8, "")
Что мы получили за 20 лет? При незначительных изменениях код более сложный и использует более мелкие абстракции. Например, если мы передумаем о замене [] на Maybe, мы можем переключить его обратно и а потом только обновить типа apply:

apply :: Parser a -> String -> [(a, String)]
apply p = runParser (space *> p) -- the implementation stays the same!

Если мы хотим получить более качественные сообщения об ошибках, мы можем использовать тип «Either String», чтобы отслеживать местоположения и сообщения об ошибках. Библиотека yoctoparsec принимает это еще больше, позволяя вам выбрать свой собственный тип потока.

Еще одно большое различие - это Applicative семейство функций, которое мы можем использовать, когда нам не нужно разветвляться на ранее проанализированном значении (который оказывается удивительно часто). Я большой поклонник x <$> y <*> z и ignored *> value <* ignored идиом, и я думаю, что это полезно, чтобы анализировать этот путь.

Иначе коде - в основном то же самое, и я думаю, что довольно невероятно, что так мало изменилось за 20 лет! Этот код доступен как IHaskell notebook, если вы хотите поэкспериментировать с ним самостоятельно.

Редактирование: я только что нашел «От моноид до почти полуколец: сущность MonadPlus и Alternative», в котором демонстрируется, как мой парсер, основанный на Maybe, не строго соблюдает Alternative законы. Что-то нужно иметь в виду, если вы планируете использовать его или что-то в этом роде!

Спасибо Alan O’Donnell, Andrey Mokhov, Annie Cherkaev, Julia Evans, and Noah Luck Easterly за комментарии и отзывы!