Since I'm interested in parsers (mainly in parser expression grammars), I'm wondering if there's some work that gives a categorical treatment of parsing. Any reference on applications of category theory to parsing is highly appreciated.
Best,
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
One of the very first applications of category theory to a subject outside of algebraic geometry was to parsing! The keywords you want to guide your search are "Lambek calculus" and "categorial grammar".
In modern terms, Joachim Lambek invented noncommutative linear logic in order to model sentence structure. The basic idea is that you can give basic parts of speech as having types, and then (say) ascribe English adjectives a function type taking noun phrases to noun phrases. (eg, "green" is viewed as function taking nouns to nouns, which means that "green eggs" is well-typed, since "eggs" is a noun).
Linearity arises from the fact that an adjective takes exactly one noun phrase as an argument, and the noncommutativity arises from the fact that the order of words in sentences matters. For example, an adjective's noun argument comes after the adjective ("green eggs"), whereas a prepositional phrase's noun phrase comes before the prepositional phrases ("green eggs with ketchup"). In categorical terms, you want a (non-symmetric) monoidal category which is closed on the left and the right. So the type $A\setminus{}B$ is the type of a phrase which has type $B$, when it is preceded by an $A$ on the left, and $B/A$ is the type of a phrase which has type $B$ when succeeded by $A$ on the right, and the type $A \ast B$ is the type of a phrase made by concatenating something of type $A$ with something of type $B$.
It turns out that Lambek grammars are equivalent to context free languages, though apparently this quite a difficult result -- showing CFGs are a subset of Lambek grammars is easy, but the other direction was only established in 1991 by Pentus.
A good exercise^H^H^Hpublication for the reader (ie, I haven't tried it, but think it would be cool to try) is to use Lambek calculus to reformulate Valiant's presentation of CYK parsing via boolean matrix multiplication, in categorical terms. As motivation, I quote from Lambek's 1958 paper The Mathematics of Sentence Structure:
The calculus presented here is formally identical with a calculus constructed by G.D. Findlay and the present author for a discussion of canonical mappings in linear and multilinear algebra.
answered Mar 17, 2015 at 9:49
-
1$\begingroup$ Rephrasing Vailant's matrix-multiplication rendition of CFG- parsing in the language of Lambek grammars is probably more than just an exercise ... $\endgroup$ Mar 17, 2015 at 11:35
-
1$\begingroup$ @MartinBerger: is that better? :) $\endgroup$ Mar 17, 2015 at 12:06
-
-
3$\begingroup$ Umm, but "categorial grammar" refers to the linguistic notion of category (en.wikipedia.org/wiki/Syntactic_category), it does not involve mathematicians' category theory. So the answer has nothing to do with the question. $\endgroup$ Mar 18, 2015 at 12:30
-
3$\begingroup$ The Lambek calculus (which is one of the principal formalisms for categorial grammar) is indeed categorical in the sense of category theory -- it is the syntactic theory of biclosed monoidal categories, and Lambek was quite conscious of this fact. In the language of proof theory, the categories of linguistics give the "atomic propositions" of the Lambek calculus. $\endgroup$ Mar 18, 2015 at 13:38
$\begingroup$
$\endgroup$
2
It would appear that (context free) parsing a la Parsec is naturally expressed in terms of the Applicative type class. In turn, this class is described well by so-called strong lax monoidal functors, which are mentioned in this very nice cstheory question and this nice stackoverflow question.
More generally, Parsec parsers are monads, that are so well known in both CS theory and category theory that I'm not going to give references unless asked.
-
4$\begingroup$ Does it say much that a concept in computation is a monad? Almost everything can be expressed as a monad. $\endgroup$ Mar 16, 2015 at 18:22
-
$\begingroup$ Not much, I agree, but it does give an answer to the original request. $\endgroup$– codyMar 17, 2015 at 12:45