Поскольку мне интересны парсеры (в основном грамматики выражений парсеров), мне интересно, есть ли какая-то работа, которая дает категорический подход к анализу. Любая ссылка на приложения теории категорий к синтаксическому анализу высоко ценится.
Одним из самых первых применений теории категорий к предмету вне алгебраической геометрии был анализ! Ключевые слова, которыми вы хотите руководствоваться при поиске, - это «исчисление Ламбека» и «категориальная грамматика».
В современных терминах Иоахим Ламбек изобрел некоммутативную линейную логику для моделирования структуры предложений. Основная идея заключается в том, что вы можете дать базовые части речи как имеющие типы, а затем (скажем) приписать английским прилагательным тип функции, переводя существительные фразы в именные. (например, «зеленый» рассматривается как функция, переводящая существительные в существительные, что означает, что «зеленые яйца» хорошо напечатаны, поскольку «яйца» являются существительными).
является типом фразы, которая имеет тип B , когда ей предшествует A слева и BA ∖ВВAB / AВAA ∗ BAВ
Оказывается, грамматики Ламбека эквивалентны контекстно-свободным языкам, хотя, по-видимому, это довольно сложный результат - показать, что CFG являются подмножеством грамматик Ламбека, легко, но другое направление было установлено только в 1991 году Пентусом.
Хорошее упражнение ^ H ^ H ^ Hp публикация для читателя (то есть я не пробовал его, но думаю, что было бы здорово попробовать) - использовать исчисление Ламбека, чтобы переформулировать представление Valiant о разборе CYK с помощью умножения логических матриц в категоричной форме. условия. В качестве мотивации я цитирую статью Ламбека 1958 года «Математика предложения» :
Представленное здесь исчисление формально совпадает с исчислением, построенным Г. Д. Финдли и настоящим автором для обсуждения канонических отображений в линейной и полилинейной алгебре.
Перефразирование выражения умножения матриц Вейлантом при разборе CFG на языке грамматик Ламбека, вероятно, больше, чем просто упражнение ...
Мартин Бергер
1
@MartinBerger: это лучше? :)
Нил Кришнасвами
Есть только один способ узнать!
Мартин Бергер
2
Ммм, но "категориальная грамматика" относится к лингвистической понятию категории ( en.wikipedia.org/wiki/Syntactic_category ), оно не затрагивает теорию категорий математиков. Таким образом, ответ не имеет ничего общего с вопросом.
Эмиль Йержабек 3
2
Исчисление Ламбека (которое является одним из основных формализмов для категориальной грамматики) действительно категорично в смысле теории категорий - это синтаксическая теория разделенных на две части моноидальных категорий, и Ламбек вполне осознавал этот факт. На языке теории доказательств категории лингвистики дают «атомарные суждения» исчисления Ламбека.
В более общем смысле парсеры Parsec - это монады , которые настолько хорошо известны как в теории CS, так и в теории категорий, что я не буду давать ссылки, если их не спросят.
Казалось бы, что (контекстно-свободный) парсинг а-ля parsec естественно выражается в терминах класса типов Applicative . В свою очередь, этот класс хорошо описывается так называемыми сильными слабыми моноидальными функторами , которые упоминаются в этом очень хорошем вопросе теории и этом хорошем вопросе о переполнении стека .
В более общем смысле парсеры Parsec - это монады , которые настолько хорошо известны как в теории CS, так и в теории категорий, что я не буду давать ссылки, если их не спросят.
источник