Skip to main content

katakomby

Текста-ориентированная коробочка для LL(k) парсеров.

Да, действительно, это стремненькая библиотечка парсеров комбинаторов с плохим выводом ошибок(его просто нет) и крайне медленной реализацией… Никому не советую и не рекомендую.

Используемый стек: Type Script и Deno(от него только название).

import { pipe } from "https://esm.sh/@mobily/ts-belt@3.13.1";
import { C, P, parse } from "https://deno.land/x/katakomby/mod.ts";

const { numeric, str, chain, any, lazy, between } = P;

const sum = (xs: number[]) => xs.reduce((acc, x) => acc + x);
const product = (xs: number[]) => xs.reduce((acc, x) => acc * x);

// term -> numeric | "(" expr ")"
function term(): P.Parser<number> {
  return any(
    between(str("("), lazy(expr), str(")")),
    numeric,
  );
}

// factor -> term ("*" term)*
function factor(): P.Parser<number> {
  return pipe(
    chain(term(), str("*")),
    C.map(product),
  );
}

// expr -> factor ("+" factor)*
function expr(): P.Parser<number> {
  return pipe(
    chain(factor(), str("+")),
    C.map(sum),
  );
}

console.log([
  parse(expr(), "2+2*2"),   // 6
  parse(expr(), "(2+2)*2"), // 8
  parse(expr(), "d2 2*2"),  // "Expted a numeric literal."
]);

Я потратил на написание пару дней aka небольшой спринт. До этого я переписывал всё три или четыре раза, так как выходила бяка, но это меня не спасло - вышло всё также, как и прошлые разы. В любом случае, получил опыт, своего рода удовлетворение, что родил хоть что-то. Библиотечку на практике использовать не буду, лучше взять готовые решения aka Ohm, но в быту пригодится: можно будет показывать шаражникам, знакомым, тем сем, поэтому и прикладываю мануальчик на потыкать.

Ничего не понял. Чё это?

Парсеры комбинаторы - это типичный LL(k) парсер, то есть нисходящий(слева-направо, сверху-вниз) парсером с шагом в k lookahead символом, то есть насколько символов надо заглянуть вперёд, чтобы распознать выражение. Если вы знакомы с методом рекурсивного спуска, то вот оно это и есть. Также парсеры комбинаторы зачастую scaner-less, то есть у нас отсутствует отдельный шаг лексического анализа(токенизации), так мы занимаемся этим на месте.

Парсеры комбинаторы пришли к на из ФП, поэтому и концепции те же, а именно композиция и ещё раз композиция. В ФП мы пишем кучу маленьких чистых функций, из композиции которых получаем программу. И в парсерах комбинаторах тоже самое - у нас есть куча маленьких парсеров, комбинируя которые мы можем разбирать более сложные конструкции. Всё это красиво и изящно.

Минусы тут заключаются в том, что для их реализации необходим более менее сносный ЯВУ с first-class функциями и ежи ими замыканиями, параметрическим полиморфизмом, и чтобы это всё было адекватно выполнено и не пришлось страдать. Также традиционно очень скудная работа с ошибками(но не всегда), которую очень легко запороть.

Соединяй и властвуй

Я предлагаю начать знакомство с парсерами комбинаторами с помощью этой библиотечки. Для большего фана будем учиться интерактивно, используя deno repl:

$ deno
Deno 1.26.2
exit using ctrl+d, ctrl+c, or close()
>

Импортируем библиотечку:

> import { P, C, parse } from "https://deno.land/x/katakomby/mod.ts"
  • P - это модуль со всеми парсерами;
  • C - это модуль с каррироваными парсерами;
  • parse - это функция принимает парсер и строку, и натравляет одно на другое;

Начнём с самого базового парсера, с str:

> const p = P.str("abc")

Суть этого парсера состоит в том, что он ожидает считать указанною строку(в нашем случае "abc"). 

> parse(p, "abc") 
{ success: true, context: { text: "abc", index: 3 }, value: "abc" }

Если мы чтение окажется успешным, то он просто вернёт эту строку(context.value). А если нет…

> parse(p, "a c")
{ success: false, context: { text: "a c", index: 0 }, expected: "abc" }

Получим ошибку! А теперь попробуйте запустит вот такой код:

> parse(p, "abcabc")
// ???

Ладно, я думаю, вы уяснили базовую механику, поэтому пробежимся по базовым парсерам.

// P.regexp
> parse(P.regexp(/\d+/y), "3223")
{ ..., value: "3223" }

// P.many - ноль или больше вхождений
> parse(P.many(P.str("a")), "aaaa")
{ ..., value: [ "a", "a", "a", "a"] }
> parse(P.many(P.str("a")), "")
{ ..., value: [] }

// P.many1 - одно или больше вхождений
> parse(P.many1(P.str("a")), "")
{ ..., expected: "a" }

// P.manyN - N или больше вхождений
> parse(P.manyN(P.str("a"), 3), "aaaa")
{ ..., value: [ "a", "a", "a", "a" ] }
> parse(P.manyN(P.str("a"), 3), "aa")
{ ..., expected: "a" }

// P.sequence
> parse(P.sequence(P.str("a"), P.str("b")), "ab")
{ ..., value: [ "a", "b" ] }
> parse(P.sequence(P.str("a"), P.str("b")), "ac")
{ ..., expected: "b" }

// P.any
> parse(P.any(P.str("a"), P.str("b")), "c")
{ ..., expected: "b" }
> parse(P.any(P.str("a"), P.str("b")), "b")
{ ..., value: "b" }
> parse(P.any(P.str("a"), P.str("b")), "a")
{ ..., value: "a" }

// P.map
> const numeric = P.map(P.regexp(/\d+/y), Number.parseInt)
> parse(numeric, "323")
{ ..., value: 323 }
> parse(numeric, "x")
{ ..., expected: "\\d+" }

// P.left(parserA, parserB) => parserA
> parse(P.left(P.str("a"), P.str("b")), "ab")
{ ..., value: "a" }
> parse(P.left(P.str("a"), P.str("b")), "a")
{ ..., expected: "b" }

// P.right
> parse(P.right(P.str("a"), P.str("b")), "a")
{ ..., expected: "b" }
> parse(P.right(P.str("a"), P.str("b")), "ab")
{ ..., value: "b" }

Float

Теперь, имея базовые представления, давайте напишем парсер чисел с плавающей запятой, то есть мы хотим, что "25.1" распарисилась в кортеж из двух элементов [25, 1].

Тут мы сразу видим, что нам потребуется P.regexp, P.str и парсеры, чтобы склеить это всё. Мы, конечно, могли бы воспользоваться только P.regexp, но тогда бы не было истории.

> type Float = [number, number]
> const numeric = P.map(
    P.regexp(/\d+/y),
    Number.parseInt
)
> const dot = P.str(".")
> const float: P.Parser<Float> = 
    P.sequence(numeric, P.right(dot, numeric))

> parse(float, "11.5")
{ ..., value: [ 11, 5 ] }
> parse(float, "11.")
{ ..., expected: "\\d+" }

Всё круто, всё работает, но….

Повышаем уровень дискуссии в восточной Европе

Мы научились сочетать парсеры, но выглядит это слишком многословно, а также нам хотелось бы заменять expected: "\\d+" на что-то более внятное. Здесь нам помогут каррированные парсеры, а также пара дополнительных парсеров. Для удобный работы с каррироваными функциями вам потребуется pipe, вы можете взять любой, я возьму из ts-belt. В самой библиотечке всё обходится без него. 

> import { pipe } from "https://esm.sh/@mobily/ts-belt@3.13.1";

Начнём менять numeric. 

const numeric: P.Parser<number> = pipe(
    P.regexp(/\d+/y),
    C.map(Number.parseInt),
)

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

const numeric: P.Parser<number> = pipe(
    P.regexp(/\d+/y),
    C.map(Number.parseInt),
    C.mapError("Numeric token expected."),
)
> parse(float, "11.")
{
  success: false,
  context: { text: "11.", index: 3 },
  expected: "Numeric token expected."
}

Проделаем всё тоже самое со всем кодом.

const numeric: P.Parser<number> = pipe(
    P.regexp(/\d+/y),
    C.map(Number.parseInt),
    C.mapError("Numeric token expected."),
)

const dot = P.mapError(P.str("."), "Dot character expected.")

const float: P.Parser<Float> = 
    P.sequence(numeric, P.right(dot, numeric))

Вложенность во float можно убрать за счёт удаление P.right, тут на ваше усмотрение:

const float: P.Parser<Float> = pipe(
    P.sequenceT(numeric, dot, numeric),
    C.map(([x, _, y]) => [x, y]),
)

Rule

Тут бы его описать, но не лень. Если кратко, то rule работает почти как sequenceT, но имеет ещё функциональность P.lazy, P.str. 

const float: P.Parser<Float> = pipe(
    P.rule(numeric, ".", numeric),
    C.map(([x, _, y]) => [x, y]),
)

Рекурсия

Иногда потребуется рекурсивно вызывать парсеры, что может поставить в тупик, поэтому рассмотрим пример. Более интересный пример с S-выражениями можете найти тут. 

S -> "a" S | ξ
function S(xs: "a"[] = []): P.Parser<"a"[]> {
    return P.any(
        pipe(
            P.str("a"), 
            C.bind(_ => S(["a"].concat(xs)))
        ),
        P.map(P.eos, _ => xs)
    )
}

> parse(S(), "aaaaξ")
{ ..., value: [ "a", "a", "a", "a" ] }

Если бы функция S не принимала бы аргументов, то можно было использовать rule: rule("a", S). Или P.lazy: P.sequence2(a, P.lazy(S)). Или что-то около того.

Дальше мне лень писать… проще апишку посмотреть.