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))
. Или что-то около того.
Дальше мне лень писать… проще апишку посмотреть.