Парсер-комбинаторы с нуля, потом megaparsec

Чтобы read из прошлого урока перестал быть заглушкой, нужен парсер. Сначала напишем парсер-комбинаторы своими руками: newtype Parser как функция от входа в Either, инстансы Functor, Applicative, Monad, Alternative, примитив satisfy и из него char, string, many, some, choice, between, sepBy, token. Когда станет понятно, как это устроено изнутри, перепишем то же самое на megaparsec и дальше в проекте пользуемся ей.

Идея

Что вообще такое парсер? Самое полезное определение тут не “программа, которая читает текст”, а вот это: парсер это функция, которая откусывает начало входа и возвращает либо разобранное значение вместе с остатком, либо ошибку. Запиши это типом:

String -> Either String (a, String)
--  ^вход         ^ошибка   ^значение и непрочитанный хвост

Дай этой функции на вход "abc", попроси откусить одну букву, и получишь Right ('a', "bc"): значение 'a' и остаток "bc". Передай остаток дальше другому парсеру, и так по кусочку разбери всю строку. Из этой простой идеи растёт всё остальное.

Комбинатор это функция, которая из маленьких парсеров собирает большой: many p повторяет p, p <|> q пробует сначала p, потом q, between open close p снимает обёртку. Самое красивое тут в том, что весь словарь комбинаторов это не новая теория, а ровно та иерархия абстракций, которую ты уже прошёл:

• Functor через fmap меняет разобранное значение, не трогая разбор: fmap (:[]) (char 'a') разберёт ту же букву, но вернёт строку, а не символ.
• Applicative секвенсит: (,) <$> p <*> q запустит p, потом q на остатке, и склеит результаты в пару.
• Alternative даёт выбор <|> и из него повтор many (ноль и больше) и some (один и больше).
• Monad через >>= позволяет грамматике ветвиться по уже прочитанному.

Поэтому сначала мы напишем Parser своими руками с этими четырьмя инстансами, увидим, что магии нет, а потом возьмём megaparsec, у которой ровно те же инстансы плюс хорошие сообщения об ошибках.

Прежде чем писать код, прогони комбинаторы в голове по шагам. Виджет ползёт по ленте входа слева направо: всё слева от курсора это consumed, всё справа это remaining. Посмотри, как many повторяет шаг до первого несовпадения, как <|> при неудаче первой альтернативы восстанавливает вход и пробует вторую, и как between снимает рамку и оставляет только середину.

Свой Parser

Оборачиваем функцию-парсер в newtype, чтобы повесить на неё инстансы. Заведи модуль Lishp.Parser.Combinators:

newtype Parser a = Parser {runParser :: String -> Either String (a, String)}

runParser это просто аксессор, который достаёт функцию обратно. Теперь четыре инстанса. Читай их как определения: каждый говорит, что значит скомбинировать парсеры этим способом.

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input ->
    case p input of
      Left err        -> Left err            -- ошибка проходит насквозь
      Right (a, rest) -> Right (f a, rest)   -- меняем значение, остаток как был

instance Applicative Parser where
  pure x = Parser $ \input -> Right (x, input)   -- ничего не съесть, вернуть x
  Parser pf <*> Parser px = Parser $ \input ->
    case pf input of
      Left err        -> Left err
      Right (f, rest) ->                          -- первый дал функцию и остаток
        case px rest of                           -- второй идёт по остатку
          Left err         -> Left err
          Right (x, rest') -> Right (f x, rest')

instance Monad Parser where
  Parser p >>= f = Parser $ \input ->
    case p input of
      Left err        -> Left err
      Right (a, rest) -> runParser (f a) rest     -- f a зависит от a, что и нужно

instance Alternative Parser where
  empty = Parser $ \_ -> Left "empty: no parse"   -- всегда неудача
  Parser p <|> Parser q = Parser $ \input ->
    case p input of
      Left _  -> q input                          -- p не вышел, пробуем q
      success -> success                          -- p вышел, берём его

Вся идея в том, как Applicative и Monad протаскивают остаток: первый парсер съел кусок и вернул хвост, второй стартует с этого хвоста. Так последовательный разбор получается сам собой, без явного индекса и цикла. Alternative ловит ошибку и пробует запасной вариант, это и есть выбор грамматики.