<p>It would appear that (context free) parsing <em>a la</em> <a href="http://en.wikipedia.org/wiki/Parsec_%28parser%29" rel="nofollow noreferrer">Parsec</a> is naturally expressed in terms of the <strong><a href="http://hackage.haskell.org/package/base-4.7.0.2/docs/Control-Applicative.html" rel="nofollow noreferrer">Applicative</a></strong> type class. In turn, this class is described well by so-called <strong>strong lax monoidal functors</strong>, which are mentioned in <a href="https://cstheory.stackexchange.com/questions/12412/explaining-applicative-functor-in-categorical-terms-monoidal-functors">this very nice cstheory question</a> and <a href="https://stackoverflow.com/questions/23316255/lax-monoidal-functors-with-a-different-monoidal-structure">this nice stackoverflow question</a>.</p>

<p>More generally, Parsec parsers are <strong>monads</strong>, that are so well known in both CS theory and category theory that I'm not going to give references unless asked.</p>

CC BY-SA 3.0
2015-03-16T18:22:58.580Z
Does it say much that a concept in computation is a monad? Almost everything
can be expressed as a monad.
Martin Berger
CC BY-SA 3.0
2015-03-17T12:45:18.323Z
Not much, I agree, but it does give an answer to the original request.
cody
CC BY-SA 3.0
2015-03-16T15:04:09.427Z
2015-03-16T15:04:09.427Z
2017-05-23T12:40:09.333Z
cody
<p>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". </p>

<p>In modern terms, Joachim Lambek invented <a href="http://en.wikipedia.org/wiki/Noncommutative_logic">noncommutative linear logic</a> 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). </p>

<p>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 <em>before</em> 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$. </p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/CYK_algorithm#Valiant.27s_algorithm">Valiant's presentation of CYK parsing via boolean matrix multiplication</a>, in categorical terms. As motivation, I quote from Lambek's 1958 paper <a href="http://dx.doi.org/10.2307%2F2310058"><em>The Mathematics of Sentence Structure</em></a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2015-03-17T11:35:50.973Z
Rephrasing Vailant's matrix-multiplication rendition of CFG- parsing in the language of Lambek grammars is probably more than just an exercise ...
Martin Berger
CC BY-SA 3.0
2015-03-17T12:06:34.417Z
@MartinBerger: is that better? :)
Neel Krishnaswami
CC BY-SA 3.0
2015-03-17T12:15:53.097Z
There is only one way to find out!
Martin Berger
CC BY-SA 3.0
2015-03-18T12:30:17.850Z
Umm, but "categorial grammar" refers to the *linguistic* notion of category (http://en.wikipedia.org/wiki/Syntactic_category), it does not involve mathematicians' category theory. So the answer has nothing to do with the question.
Emil Jeřábek
CC BY-SA 3.0
2015-03-18T13:38:42.463Z
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.
Neel Krishnaswami
CC BY-SA 3.0
2015-03-17T09:49:53.027Z
2015-03-17T12:06:21.273Z
2015-03-17T12:06:21.273Z
Neel Krishnaswami
<p>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.</p>

<p>Best,</p>

<reference-request><functional-programming><ct.category-theory><parsing>
Category theory and parsers --- references wanted
Rodrigo Ribeiro
# Category theory and parsers --- references wanted

(Asked by: username_0 on 2015-03-15)

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,

**Tags:** reference-request, functional-programming, ct.category-theory, parsing

---

## 2 answers

### Answer by username_3 on 2015-03-17. Score: 10 | Accepted answer

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](http://en.wikipedia.org/wiki/Noncommutative_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](http://en.wikipedia.org/wiki/CYK_algorithm#Valiant.27s_algorithm), in categorical terms. As motivation, I quote from Lambek's 1958 paper [*The Mathematics of Sentence Structure*](http://dx.doi.org/10.2307%2F2310058):

> 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.

> **Comments:**
> **username_2**: Rephrasing Vailant's matrix-multiplication rendition of CFG- parsing in the language of Lambek grammars is probably more than just an exercise ...  
> **username_3**: @MartinBerger: is that better? :)  
> **username_2**: There is only one way to find out!  
> **username_4**: Umm, but "categorial grammar" refers to the *linguistic* notion of category (http://en.wikipedia.org/wiki/Syntactic_category), it does not involve mathematicians' category theory. So the answer has nothing to do with the question.  
> **username_3**: 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.  

---

### Answer by username_1 on 2015-03-16. Score: 5

It would appear that (context free) parsing *a la* [Parsec](http://en.wikipedia.org/wiki/Parsec_%28parser%29) is naturally expressed in terms of the **[Applicative](http://hackage.haskell.org/package/base-4.7.0.2/docs/Control-Applicative.html)** 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](https://cstheory.stackexchange.com/questions/12412/explaining-applicative-functor-in-categorical-terms-monoidal-functors) and [this nice stackoverflow question](https://stackoverflow.com/questions/23316255/lax-monoidal-functors-with-a-different-monoidal-structure).

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.

> **Comments:**
> **username_2**: Does it say much that a concept in computation is a monad? Almost everything can be expressed as a monad.  
> **username_1**: Not much, I agree, but it does give an answer to the original request.  

---

