Парсер-комбинаторы: парсер как монада, декларативный DSL поверх

В уроке 12 мы построили recursive descent для арифметики: набор взаимно рекурсивных функций, по одной на нетерминал, плюс цикл для левой ассоциативности. Подход рабочий, но даже на крошечной грамматике ушло за сотню строк, и каждый новый оператор требует либо новой функции, либо новой ветки.

Сегодня поднимем парсер на уровень выше. Заметим, что парсер сам по себе обычное значение, и тогда map, flatMap, alt из урока 07 превращаются из теории в инструмент. На нём весь парсер собирается за двадцать строк ядра плюс одна таблица комбинаторов. Под конец посмотрим в другую сторону, на декларативные генераторы парсеров в духе Instaparse, где грамматика сама становится данными.

После урока ты прочитаешь любую библиотеку парсер-комбинаторов (parsimmon, arcsecond, parser-ts, fp-ts/Parser, parsec и megaparsec в Haskell, spec-tools в Clojure), узнаешь в ней знакомые конструкции и сможешь осознанно выбирать между декларативной и комбинаторной формой.

Парсер это значение

В уроке 12 парсер был набором функций, которые делили общее изменяемое состояние (pos, tokens). Теперь парсер станет значением с явной сигнатурой.

type ParseSuccess<A> = { ok: true; value: A; rest: string };
type ParseFailure = { ok: false; error: string; rest: string };
type ParseResult<A> = ParseSuccess<A> | ParseFailure;

type Parser<A> = (input: string) => ParseResult<A>;

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

Сигнатура напрямую соответствует определению Хаттона и Майера из статьи 1998 года “Monadic Parsing in Haskell”:

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

Список пар у Хаттона позволяет описывать неоднозначные парсеры. В TypeScript мы упрощаем до Result: теряем неоднозначность, но получаем явные ошибки. Для большинства задач этого достаточно.

Двухслойная архитектура: примитивы и комбинаторы

В реализациях, которые хорошо ложатся в голову, ядро делят на два слоя:

• Примитивы, внутренний слой. Это несколько функций, лежащих ниже всех абстракций: pure, satisfy, eof. Они работают с сырой сигнатурой Parser<A>.
• Комбинаторы, внешний слой. Всё остальное собирается из примитивов и из других комбинаторов: map, flatMap, alt, many, sep, between, str, regex. Наружу библиотека показывает именно их.

Такой приём встречается во всех серьёзных реализациях. В Clojure внутренние функции пишут с префиксом _, внешние с префиксом +. В Haskell внутренние не экспортируют, внешние ре-экспортируются из Text.Parsec. В TypeScript обычно одно пространство имён, но дисциплина та же: сначала ядро, потом всё остальное.

Примитивы

// pure: всегда успех с заданным значением, ничего не потребляет
const pure = <A>(value: A): Parser<A> => (input) => ({
  ok: true,
  value,
  rest: input,
});

// fail: всегда неудача с заданным сообщением
const fail = <A = never>(message: string): Parser<A> => (input) => ({
  ok: false,
  error: message,
  rest: input,
});

// satisfy: один символ, который проходит предикат
const satisfy = (
  predicate: (c: string) => boolean,
  description: string,
): Parser<string> =>
  (input) =>
    input.length === 0
      ? { ok: false, error: `expected ${description}, got EOF`, rest: input }
      : predicate(input[0]!)
        ? { ok: true, value: input[0]!, rest: input.slice(1) }
        : { ok: false, error: `expected ${description}, got "${input[0]!}"`, rest: input };

// eof: успех только если строка пуста
const eof: Parser<null> = (input) =>
  input.length === 0
    ? { ok: true, value: null, rest: input }
    : { ok: false, error: `expected EOF, got "${input[0]!}"`, rest: input };

Четыре функции, около двадцати строк. Это всё ядро, дальше только композиция.

Комбинаторы первого порядка

const map = <A, B>(p: Parser<A>, f: (a: A) => B): Parser<B> => (input) => {
  const r = p(input);
  return r.ok ? { ok: true, value: f(r.value), rest: r.rest } : r;
};

const flatMap = <A, B>(p: Parser<A>, f: (a: A) => Parser<B>): Parser<B> =>
  (input) => {
    const r = p(input);
    return r.ok ? f(r.value)(r.rest) : r;
  };

const alt = <A>(p: Parser<A>, q: Parser<A>): Parser<A> => (input) => {
  const r = p(input);
  return r.ok ? r : q(input);
};

const ap = <A, B>(pf: Parser<(a: A) => B>, pa: Parser<A>): Parser<B> =>
  flatMap(pf, (f) => map(pa, f));

Узнаёшь? Это Functor, Applicative и Monad из урока 07. Парсер удовлетворяет всем трём контрактам и соответствующим законам.

alt это alt: попробуй первый парсер, и если он упал, попробуй второй. По умолчанию в большинстве библиотек этот выбор фиксируется на первом парсере: если он что-то прочитал, а потом всё равно упал, второй вариант не пробуется. Это поведение называют committed choice. В parsec для возврата к началу есть отдельные try/attempt.

Комбинаторы повтора

const many = <A>(p: Parser<A>): Parser<A[]> => (input) => {
  const out: A[] = [];
  let rest = input;
  while (true) {
    const r = p(rest);
    if (!r.ok) return { ok: true, value: out, rest };
    if (r.rest.length === rest.length) {
      // защита от бесконечного цикла на парсерах, которые ничего не потребляют
      return {
        ok: false,
        error: 'many: парсер успешен, но не двигает позицию',
        rest,
      };
    }
    out.push(r.value);
    rest = r.rest;
  }
};

const many1 = <A>(p: Parser<A>): Parser<A[]> =>
  flatMap(p, (head) => map(many(p), (tail) => [head, ...tail]));

const sepBy1 = <A, S>(p: Parser<A>, sep: Parser<S>): Parser<A[]> =>
  flatMap(p, (head) =>
    map(many(flatMap(sep, () => p)), (tail) => [head, ...tail]),
  );

const sepBy = <A, S>(p: Parser<A>, sep: Parser<S>): Parser<A[]> =>
  alt(sepBy1(p, sep), pure<A[]>([]));

const between = <O, A, C>(
  open: Parser<O>,
  p: Parser<A>,
  close: Parser<C>,
): Parser<A> =>
  flatMap(open, () => flatMap(p, (a) => map(close, () => a)));

Обрати внимание: many1, sepBy1 и between собраны из flatMap, map и соседних комбинаторов. Ни один из них не лезет в сырое определение Parser. Так и устроена настоящая библиотека: тонкое ядро плюс много декларативных производных.

Удобные обёртки

const char = (c: string): Parser<string> =>
  satisfy((x) => x === c, `'${c}'`);

const str = (s: string): Parser<string> => (input) =>
  input.startsWith(s)
    ? { ok: true, value: s, rest: input.slice(s.length) }
    : {
        ok: false,
        error: `expected "${s}", got "${input.slice(0, Math.min(s.length, 8))}"`,
        rest: input,
      };

const regex = (re: RegExp, description: string): Parser<string> => {
  const anchored = new RegExp('^(?:' + re.source + ')', re.flags.replace('g', ''));
  return (input) => {
    const m = anchored.exec(input);
    return m === null
      ? { ok: false, error: `expected ${description}`, rest: input }
      : { ok: true, value: m[0], rest: input.slice(m[0].length) };
  };
};

const ws: Parser<string> = regex(/\s*/, 'whitespace');

const lexeme = <A>(p: Parser<A>): Parser<A> =>
  flatMap(p, (a) => map(ws, () => a));

// runner
const run = <A>(p: Parser<A>, input: string): A => {
  const r = flatMap(ws, () => flatMap(p, (a) => map(eof, () => a)))(input);
  if (!r.ok) {
    throw new Error(`parse error at "${r.rest.slice(0, 20)}": ${r.error}`);
  }
  return r.value;
};

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

Прежде чем разбирать JSON, собери язык поменьше. Ядро комбинаторов в задаче уже готово, твоя работа начинается на слое, где из них складывается конкретная грамматика.

Сквозной пример: JSON-парсер на комбинаторах

Соберём подмножество JSON: числа, строки, булевы значения, null, массивы и объекты. На тех же комбинаторах, что и выше.

type JsonValue =
  | null
  | boolean
  | number
  | string
  | JsonValue[]
  | { [key: string]: JsonValue };

const numberLit: Parser<number> = map(
  regex(/-?\d+(?:\.\d+)?(?:[eE][+-]?\d+)?/, 'number'),
  Number,
);

const stringLit: Parser<string> = map(
  regex(/"(?:[^"\\]|\\.)*"/, 'string literal'),
  (raw) => JSON.parse(raw) as string,
);

const trueLit: Parser<true> = map(str('true'), () => true);
const falseLit: Parser<false> = map(str('false'), () => false);
const nullLit: Parser<null> = map(str('null'), () => null);

// рекурсия через ленивый референс
let valueRef: Parser<JsonValue> = (input) => valueImpl(input);

const value: Parser<JsonValue> = lexeme(
  alt(
    alt(alt(alt(alt(nullLit, trueLit), falseLit), stringLit), numberLit),
    alt(
      // array
      between(
        lexeme(char('[')),
        sepBy(valueRef, lexeme(char(','))),
        char(']'),
      ),
      // object
      map(
        between(
          lexeme(char('{')),
          sepBy(
            flatMap(lexeme(stringLit), (key) =>
              flatMap(lexeme(char(':')), () => map(valueRef, (v) => [key, v] as const)),
            ),
            lexeme(char(',')),
          ),
          char('}'),
        ),
        (pairs) => Object.fromEntries(pairs),
      ),
    ),
  ),
);

const valueImpl = value;

// готовый парсер
const parseJson = (input: string): JsonValue => run(value, input);

Около пятидесяти строк, и перед нами полный JSON-парсер. Recursive descent из урока 12 на сопоставимый язык занял бы вдвое больше. Каждая часть грамматики становится одной декларацией: array это between плюс sepBy плюс value, точка в точку как в EBNF.