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

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

Парсинг — это процесс преобразования менее структурированного входа, например текста, в более структурированные данные, такие как объекты.

Многие знают о регулярных выражениях для парсинга, а некоторые слышали о tree-sitter — мощной парсерской библиотеке, которая питает подсветку синтаксиса в редакторах кода.

Но регулярные выражения становятся беспорядочными на сложных задачах, а tree-sitter часто избыточен — для этой золотой середины идеальны комбинаторы парсеров. О них знают немногие, поэтому позвольте показать!

Частичный парсер

Наименьшая единица парсинга, которую мы рассмотрим, — это частичный парсер. Он решает, где разрезать входную строку, а затем возвращает кортеж, состоящий из какого-угодно значения и остатка строки.

Это может быть любая функция, лишь бы она возвращала такой кортеж! Она даже может использовать внутри регулярные выражения.

const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

Цепочка

Один парсер сам по себе не многое сделает, но применяя несколько парсеров подряд, можно потребить весь вход шаг за шагом.

const pHello: Parser<string> = (input: string) => {
  if (!input.startsWith("Hello")) throw new Error();

  return ["Hello", input.substring(5)];
};

const pIgnoreWhitespace: Parser<null> = (input: string) => {
  const match = input.match(/^\s+/);
  if (match == null) throw new Error();

  const spaces = match[0];
  return [null, input.substring(spaces.length)];
};

const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

const [token1, input2] = pHello("Hello 100");
const [token2, input3] = pIgnoreWhitespace(input2);
const [token3, input4] = pInteger(input3);

console.log(token1, token2, token3); // "Hello", null, 100
console.log(input4); // empty!

Цепочка

Или, и здесь раскрывается настоящая мощь частичных парсеров: обернём цепочку в новый парсер.

const pHello100: Parser<[string, null, number]> = (input: string) => {
  const [hello, rest1] = pHello(input);
  const [space, rest2] = pIgnoreWhitespace(rest1);
  const [number, rest3] = pInteger(rest2);

  return [[hello, space, number], rest3];
};

pSeq

Или обобщим и предоставим функцию, которая делает цепочку! "Подать остаток строки в следующий парсер" — это очень универсальная операция, которая не зависит от того, что делает какой-то конкретный парсер.

Правильно выражать типы непросто, но TypeScript вполне способен выразить эти сложные вариативные типы.

type Parsers<T extends unknown[]> = { [K in keyof T]: Parser<T[K]> };

const pSeq = <T extends unknown[]>(...parsers: Parsers<T>): Parser<T> =>
  (input) => {
    const results = [] as unknown as T;
    let rest = input;
    for (const p of parsers) {
      const [val, next] = (p as Parser<unknown>)(rest);
      results.push(val);
      rest = next;
    }
    return [results, rest];
  };

Комбинаторы

Так как pSeq объединяет много парсеров в новый парсер, мы его называем комбинатором парсеров.

Внимательно посмотрите на функциональное безумие, которое здесь происходит: pSeq — это функция, которая принимает парсеры (которые тоже функции) и возвращает ещё один парсер (тоже функцию).

И только потом мы начинаем парсинг, вызывая полученную функцию с данными.

Это похоже на то, что мы строим вложенную конструкцию из функций, создавая сложную программу. Неплохо!

Кстати

Если разбиение строки на много токенов кажется вам как-то связано с .reduce, то вы чуете правильное направление. На самом деле, то, что мы здесь делаем, — это двойственная операция, которая в функциональных кругах называется unfold (разворот). reduce называется fold (сворот).

Сворот использует промежуточное состояние — аккумулятор — чтобы объединить список вещей в одно, а разворот использует промежуточное состояние, чтобы разбить одно на много.

Математика, ура!

Кортежи неудобны

Если цель парсинга — получить из сырых строк структурированные, часто удобочитаемые данные, то кортеж вроде ["Hello", null, 100] едва ли может быть конечной целью.

Конечно, можно отобразить результат, чтобы превратить его в более удобный вид.

const pHello100 = pSeq(...);
const [result, rest] = pHello100("Hello 100");

console.log(result); // ["Hello", null, 100]

const parsed = {
  greeting: result[0],
  who: result[2],
};

pMap

Но это не в духе комбинаторов парсеров! Как и раньше, можно обернуть преобразование в новый комбинатор парсеров.

pMap принимает парсер и функцию; функция будет применена к конечному результату после парсинга.

const pMap = <T, R>(parser: Parser<T>, fn: (value: T) => R): Parser<R> =>
  (input: string) => {
    const [value, rest] = parser(input);
    return [fn(value), rest];
  };

const pGreeting = pMap(
  pHello100,
  ([greeting, _, who]) => ({ greeting, who }),
);

const [parsed, rest] = pGreeting("Hello 100");

console.log(parsed); // { greeting: "Hello", who: 100 }

pRepeat

Перед тем как перейти к практическому примеру, покажу третий фундаментальный комбинатор парсеров: pRepeat — он принимает парсер и применяет его снова и снова, пока не сможет.

Это * из регулярных выражений, только как комбинатор!

const pRepeat = <T>(parser: Parser<T>): Parser<T[]> =>
  (input: string) => {
    const values: T[] = [];
    let rest = input;
    while (true) {
      try {
        const [value, next] = parser(rest);
        values.push(value);
        rest = next;
      } catch {
        return [values, rest];
      }
    }
  };

const pNumber: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

const pSemicolon: Parser<string> = (input: string) => {
  if (!input.startsWith(";")) throw new Error();

  return [";", input.substring(1)];
};

const pNumberCsv = pRepeat(pSeq(pNumber, pSemicolon));

pNumberCsv("10;20;30;");
// [[[10, ";"], [20, ";"], [30, ";"]], ""]

Построим парсер!

Теперь у нас есть инструменты, чтобы начать парсить настоящие, реальные данные!

Выше — пример вывода, когда я пингую Cloudflare. Там множество полезной информации, поэтому давайте её спарсим в структурированные данные.

type PingResult = {
  header: PingHeader;
  packets: IcmpPacket[];
  statistics: PingStatistics;
};

type IcmpPacket = {
  byteCount: number; from: string;
  seq: number; ttl: number; time: number;
};

type PingHeader = {
  targetIp: string;        // 1.1.1.1
  resolvedIp: string;      // 1.1.1.1 в скобках
  icmpPayloadSize: number; // 56
  totalPacketSize: number; // 84
};

type PingStatistics = {
  packetsTransmitted: number; packetsReceived: number;
  packetLoss: number; time: number;
  rtt: { min: number; avg: number; max: number; mdev: number };
};

Кусочки и кое-что

В этом выводе есть повторяющиеся элементы вроде десятичных чисел или IP-адресов. Давайте их сначала подготовим.

// Точный текст, вроде "PING"
const pString = (text: string): Parser<string> => (input: string) => {
  if (!input.startsWith(text)) throw new Error();

  return [text, input.substring(text.length)];
};

// Целые числа, вроде 64
const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

// Числа с опциональной дробной частью, вроде 68.7
const pDecimal: Parser<number> = (input: string) => {
  const match = input.match(/^\d+(\.\d+)?/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

// Четыре байта и три точки, вроде 1.1.1.1
const pByte = pMap(pInteger, (n) => {
  if (n > 255) throw new Error();
  return n;
});

const pDot = pString(".");

const pIpV4Address = pMap(
  pSeq(pByte, pDot, pByte, pDot, pByte, pDot, pByte),
  ([a, _1, b, _2, c, _3, d]) => `${a}.${b}.${c}.${d}`,
);

// Минимум одно пространство
const pWhitespace: Parser<null> = (input: string) => {
  const match = input.match(/^\s+/);
  if (match == null) throw new Error();

  return [null, input.substring(match[0].length)];
};

Заголовок

Первую строку должно быть легко парсить, это просто pSeq парсеров и потом pMap, чтобы придать форму PingHeader.

const pPingHeaderParts = pSeq(
  pString("PING"), pWhitespace, pIpV4Address, pWhitespace,
  pString("("), pIpV4Address, pString(")"), pWhitespace,
  pInteger, pString("("), pInteger, pString(")"),
  pString(" bytes of data."),
);

const pPingHeader = pMap(
  pPingHeaderParts,
  ([a, b, c, d, e, f, g, h, i, j, k, l, m]) => ({
    targetIp: c,
    resolvedIp: f,
    icmpPayloadSize: i,
    totalPacketSize: k,
  }),
);

Пакет

Пакеты — это тоже pSeq парсеров, за которым идёт pMap. Это парсинг точно простой!

const pIcmpPacketParts = pSeq(
  pInteger, pString(" bytes from "), pIpV4Address,
  pString(": icmp_seq="), pInteger,
  pString(" ttl="), pInteger,
  pString(" time="), pDecimal, pString(" ms"),
);

const pIcmpPacket = pMap(
  pIcmpPacketParts,
  ([a, b, c, d, e, f, g, h, i, j]) => ({
    byteCount: a, from: c, seq: e, ttl: g, time: i,
  }),
);