Теория категорий и парсеры - нужны ссылки

13

Поскольку мне интересны парсеры (в основном грамматики выражений парсеров), мне интересно, есть ли какая-то работа, которая дает категорический подход к анализу. Любая ссылка на приложения теории категорий к синтаксическому анализу высоко ценится.

Лучший,

Родриго Рибейро
источник

Ответы:

9

Одним из самых первых применений теории категорий к предмету вне алгебраической геометрии был анализ! Ключевые слова, которыми вы хотите руководствоваться при поиске, - это «исчисление Ламбека» и «категориальная грамматика».

В современных терминах Иоахим Ламбек изобрел некоммутативную линейную логику для моделирования структуры предложений. Основная идея заключается в том, что вы можете дать базовые части речи как имеющие типы, а затем (скажем) приписать английским прилагательным тип функции, переводя существительные фразы в именные. (например, «зеленый» рассматривается как функция, переводящая существительные в существительные, что означает, что «зеленые яйца» хорошо напечатаны, поскольку «яйца» являются существительными).

является типом фразы, которая имеет тип B , когда ей предшествует A слева и BAВВAВ/AВAA*ВAВ

Оказывается, грамматики Ламбека эквивалентны контекстно-свободным языкам, хотя, по-видимому, это довольно сложный результат - показать, что CFG являются подмножеством грамматик Ламбека, легко, но другое направление было установлено только в 1991 году Пентусом.

Хорошее упражнение ^ H ^ H ^ Hp публикация для читателя (то есть я не пробовал его, но думаю, что было бы здорово попробовать) - использовать исчисление Ламбека, чтобы переформулировать представление Valiant о разборе CYK с помощью умножения логических матриц в категоричной форме. условия. В качестве мотивации я цитирую статью Ламбека 1958 года «Математика предложения» :

Представленное здесь исчисление формально совпадает с исчислением, построенным Г. Д. Финдли и настоящим автором для обсуждения канонических отображений в линейной и полилинейной алгебре.

Нил Кришнасвами
источник
1
Перефразирование выражения умножения матриц Вейлантом при разборе CFG на языке грамматик Ламбека, вероятно, больше, чем просто упражнение ...
Мартин Бергер
1
@MartinBerger: это лучше? :)
Нил Кришнасвами
Есть только один способ узнать!
Мартин Бергер
2
Ммм, но "категориальная грамматика" относится к лингвистической понятию категории ( en.wikipedia.org/wiki/Syntactic_category ), оно не затрагивает теорию категорий математиков. Таким образом, ответ не имеет ничего общего с вопросом.
Эмиль Йержабек 3
2
Исчисление Ламбека (которое является одним из основных формализмов для категориальной грамматики) действительно категорично в смысле теории категорий - это синтаксическая теория разделенных на две части моноидальных категорий, и Ламбек вполне осознавал этот факт. На языке теории доказательств категории лингвистики дают «атомарные суждения» исчисления Ламбека.
Нил Кришнасвами
4

Казалось бы, что (контекстно-свободный) парсинг а-ля parsec естественно выражается в терминах класса типов Applicative . В свою очередь, этот класс хорошо описывается так называемыми сильными слабыми моноидальными функторами , которые упоминаются в этом очень хорошем вопросе теории и этом хорошем вопросе о переполнении стека .

В более общем смысле парсеры Parsec - это монады , которые настолько хорошо известны как в теории CS, так и в теории категорий, что я не буду давать ссылки, если их не спросят.

Коди
источник
3
Много ли говорит о том, что концепция в вычислениях является монадой? Почти все можно выразить как монаду.
Мартин Бергер
Не очень, я согласен, но он дает ответ на первоначальный запрос.
Коди