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,
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityOne 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.
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.