For any string $𝑤$, we can define a representable grammar $\lceil 𝑤\rceil$ which matches exactly the string $𝑤$ and nothing else. The parse trees for a representable grammar are proofs that the string is exactly equal to $𝑤$:

The first set ($\text{𝖥𝗂𝗋𝗌𝗍}(\cdot )$) of a grammar $𝐴$ are all the characters that may appear at the beginning of a word in the language of $𝐴$.

The first set of a grammar $𝐴$ may be captured in Lambek${\begin{array}{}\end{array}}^{𝙳}$ via the following proposition:

Or perhaps with ones of the grammars

The followlast set ($\text{𝖥𝖫𝖺𝗌𝗍}(\cdot )$) of a grammar $𝐴$ are all the characters that may follow a word in the language of $𝐴$ in a string that is in the language of $𝐴$.

The followlast set of a grammar $𝐴$ may be captured in Lambek${\begin{array}{}\end{array}}^{𝙳}$ via the following proposition:

Or perhaps with ones of the grammars

A context-free grammar satisfies the LL(1) condition if it satisfies the following three conditions:

• All of its productions have pairwise disjoint first sets
• If a concatenation of nonterminals $𝐴\otimes 𝐵$ appears in a production, then $𝐴$ has a disjoint followlast set from the first set of $𝐵$
• At most one production is nullable

This is essentially the type system of [1], which characterizes the LL(1) condition for context-free expressions.

Intutively, an LL(1) grammar can be parsed unambiguously, and without backtracking, by a predictive parser that only needs one token of lookahead.

The nullability ($\text{𝖭𝗎𝗅𝗅}(\cdot )$) of a grammar $𝐴$ may be captured in Lambek${\begin{array}{}\end{array}}^{𝙳}$ via the following proposition:

Or perhaps with one of the grammars

A grammar $𝐴$ is nullable if the empty string belongs to the language of $𝐴$.

Grammars $𝐴$ and $𝐵$ are sequentially unambiguous if the followlast set of $𝐴$ is disjoint from the first set of $𝐵$.

We can understand this intuitively by characterizing the behavior of a left-to-right parser of $𝐴\otimes 𝐵$. First it searches for a parse of $𝐴$, then upon finding a character that is not in $\text{𝖥𝖫𝖺𝗌𝗍}(𝐴)$ it may begin trying search for $𝐵$.

That is, there is a unique boundary between the $𝐴$-parse and the $𝐵$-parse.

Let $𝐶$ be a small monoidal category. Recall that for presheaves $𝐴,𝐵:{𝐶}^{\text{op}}\to \text{𝐒𝐞𝐭}$, the Day convolution provides a closed monoidal structure:

which forms an adjunction $𝐴\otimes -⊣𝐴⊸-$.

For covariant functors $𝐴:𝐶\to \text{𝐒𝐞𝐭}$ and presheaves $𝐵:{𝐶}^{\text{op}}\to \text{𝐒𝐞𝐭}$, we can define the quotient and its right adjoint, each of which is a presheaf on $𝐶$:

These form the adjunction ${𝐷}_{𝐴}⊣\sqrt[𝐴]{-}$.

The tensor of grammars,

is simply typed, so $𝐵$ cannot see what $𝐴$ matched.

Just as we have the generalization from the pair type $𝐴\times 𝐵$ to the dependent pair ${\mathrm{\Sigma }}_{𝑎:𝐴}𝐵𝑎$, we can define a dependent tensor operation. It is a $\mathrm{\Sigma }$-like generalization over the ordinary tensor, in which the second grammar depends on a parse tree of the first.

Write $\text{𝖳𝗋𝖾𝖾}(𝐴)={\sum }_{𝑤}𝐴(𝑤)$ for the type of parse trees of $𝐴$, each paired with the string it parses.

For a grammar $𝐴$ and a family of grammars $𝐵:\text{𝖳𝗋𝖾𝖾}(𝐴)\to \text{𝐆𝐫}$, the dependent tensor is:

We may also write it as $(𝑎\in 𝐴)\otimes 𝐵(𝑎)$.

When $𝐵$ is a constant family, the dependent tensor reduces to the ordinary tensor $𝐴\otimes 𝐵$.

Dependence runs left to right here, which fits left-to-right parsing. The other handedness, in which the first grammar depends on a parse of the second, is also definable.

For an alphabet $\mathrm{\Sigma }$, let ${\mathrm{\Sigma }}^{\ast }$ be the free monoid of strings over $\mathrm{\Sigma }$. A formal grammar $𝐴$ is a family of types indexed by strings:

This definition views formal grammars directly as indexed families of types over strings (which equivalently form presheaves on the discrete category of strings). This view forms the central notion of the Dependent Lambek Calculus. For a given string $𝑤$, the type $𝐴(𝑤)$ represents the type of all valid parse trees for $𝑤$ according to the grammar $𝐴$. If the grammar cannot parse $𝑤$, then $𝐴(𝑤)$ is the empty type.

When a grammar quotient ${𝐷}_{𝐴}𝐵$ is taken with respect to a representable grammar $𝐴=\lceil 𝑤\rceil$ (matching exactly the string $𝑤$), it coincides with the residual $𝐴⊸𝐵$, as established by the Quotient and Residual Coincidence.

This special case is known as the Brzozowski derivative of $𝐵$ by the string $𝑤$, often written as ${𝜕}_{𝑤}𝐵$. We have the following coincidence:

Write $𝑢⊏𝑣$ when $𝑢$ is a proper suffix of $𝑣$, that is, $𝑣=𝑥\text{++}𝑢$ with $𝑥\ne 𝜀$. The later of a grammar $𝐴$ is

A parse of $▷𝐴$ over $𝑣$ is a parse of $𝐴$ over every proper suffix of $𝑣$. In particular $(▷𝐴)𝜀$ is a singleton.

This is later on families for strings under the proper-suffix order. That order is well-founded because it strictly decreases length, so it is a thin direct category. There is at most one map $𝑢\to 𝑣$, so the product over maps from the strict past has one factor per proper suffix. Guarded recursion is modelled by presheaves on $𝜔$, the topos of trees, and more generally by sheaves over a well-founded base [1]. Here the later acts on families, which is what grammars are, and there is no clock.

Later is the right adjoint of the proper-suffix derivative. Let $\text{𝖭𝖤𝖲}={⨁}_{𝑥\ne 𝜀}\lceil 𝑥\rceil$ be the grammar of non-empty strings. Then the derivative $({𝜕}_{\text{𝖭𝖤𝖲}}𝐵)𝑢\cong {\sum }_{𝑥\ne 𝜀}𝐵(𝑥\text{++}𝑢)$ has the right adjoint

so ${𝜕}_{\text{𝖭𝖤𝖲}}-⊣▷$. Splitting $\text{𝖭𝖤𝖲}$ into its summands gives the form of $▷$ that the calculus can define:

The component at $𝑤$ says: if the string begins with $𝑤$, then the rest parses as $𝐴$.

The restriction to non-empty $𝑤$ is what makes this a later. At $𝑤=𝜀$ the component is $\sqrt[\lceil 𝜀\rceil ]{𝐴}\cong 𝐴$. Including it would give a projection $▷𝐴⊢𝐴$, and Löb would then prove every grammar. For the same reason the later is a product over suffixes. A sum such as ${⨁}_{𝑐}\lceil 𝑐\rceil ⊸𝐴$ is empty at $𝜀$, and at $𝐴=\perp$ it is $\perp$. The identity step $\perp ⊢\perp$ would then give Löb a proof of $\top ⊢\perp$.

In the Agda this is ▷ in Grammar/Later/Base.agda, which is defined as the indexed conjunction of √l-string. The mirror image ▷r, over proper prefixes, is defined in the same way. See also the bilateral later and the later along an arbitrary well-founded order.

For every grammar $𝐴$ and every term $𝜑:▷𝐴⊢𝐴$, where $▷$ is the later on grammars, there is a unique global parse $\text{𝗅ö𝖻}𝜑:\top ⊢𝐴$ with

Here $\text{𝗇𝖾𝗑𝗍}𝑡:\top ⊢▷𝐴$ restricts a global parse $𝑡$ to every proper suffix.

The proof is recursion on the length of the string. At $𝑣$, the parses already built at the proper suffixes of $𝑣$ form an element of $(▷𝐴)𝑣$, and $𝜑$ turns it into a parse at $𝑣$. Uniqueness is Löb for families over the proper-suffix order. In the Agda, lob in Grammar/Later/Base.agda is this recursion, done by well-founded induction on length.

To prove an entailment $𝐵⊢𝐶$ this way, apply Löb to $𝐴=𝐵\Rightarrow 𝐶$. The hypothesis $▷(𝐵\Rightarrow 𝐶)$ is the induction hypothesis at every proper suffix. It becomes usable once a non-nullable grammar has been consumed. If $𝜀\&𝐵⊢\perp$, then

because a parse of $𝐵\otimes \top$ over $𝑣$ splits $𝑣=𝑥\text{++}𝑢$ with $𝑥$ non-empty, so $𝑢⊏𝑣$. This is ▷-app-NE in Grammar/Later/Properties.agda. Induction on a Kleene star is the standard use.

For presheaves, $\text{𝗇𝖾𝗑𝗍}:𝑃\to ▷𝑃$ restricts along the strict past, as in later on presheaves. A grammar is only a family over strings, so a map $\text{𝗇𝖾𝗑𝗍}:𝐴⊢▷𝐴$ into the later on grammars is extra data. It sends a parse over $𝑣$ to parses over every proper suffix of $𝑣$.

Let $\square 𝐴=𝐴\&▷𝐴$, so that $(\square 𝐴)𝑣\cong {\prod }_{𝑢⊑𝑣}𝐴𝑢$. This is the comonad $𝑈\circ \text{Cofree}$ for the suffix order, and presheaves are comonadic over families. The counit law forces the first component of a coalgebra $𝐴⊢\square 𝐴$ to be the identity. Hence:

• a presheaf on strings under the suffix order is the same as a grammar $𝐴$ with a map $\text{𝗇𝖾𝗑𝗍}:𝐴⊢▷𝐴$ that satisfies coassociativity. Restricting to $𝑢\prime$ and then to $𝑢⊏𝑢\prime$ must agree with restricting to $𝑢$ directly;
• for a proposition-valued grammar (a language), coassociativity is automatic, and $\text{𝗇𝖾𝗑𝗍}$ exists exactly when the language is closed under suffixes. For example, $\top$ has one, but $\lceil 𝑎\rceil$ does not, since $(▷\lceil 𝑎\rceil )𝑎\cong \lceil 𝑎\rceil 𝜀$ is empty.

Löb does not need $\text{𝗇𝖾𝗑𝗍}$ on $𝐴$. The fixed-point equation only restricts a global parse $\top ⊢𝐴$, and a global parse can always be restricted. In the Agda, the grammar-level IsCoalgebra record, with only the field next, is in Grammar/Later/Coalgebra.agda on the guarded branch.

On presheaves the strict downset of $𝑐\text{++}𝑡$ is represented by $𝑡$, because every proper suffix of $𝑐\text{++}𝑡$ is a suffix of $𝑡$. So predecessors simplify later to $(▷𝑃)(𝑐\text{++}𝑡)\cong 𝑃𝑡$. On grammars there is no such simplification, since the factors at different suffixes are unrelated.

For formal grammars $𝐴$ and $𝐵$, the quotient of $𝐵$ by $𝐴$ is the grammar of what is left of $𝐵$ once an $𝐴$ has been read off the front:

A parse of the quotient consists of an $𝐴$-parses at prefix $𝑢$ and a $𝐵$-parse of the full string $𝑢·𝑣$.

This operation has a right adjoint:

Intuitively, $\sqrt[𝐴]{𝐶}$ parses $𝑤$ if: for all splittings of $𝑤$ into a prefix and suffix, if the prefix matches $𝐴$ then the suffix must match $𝐶$.

Together, these form the adjunction:

This is an instance of the Day quotient over the discrete monoidal category of strings.

For formal grammars $𝐴$ and $𝐵$, the residual $𝐴⊸𝐵$ (sometimes called the lollipop or linear implication) is the right adjoint to the grammar tensor $𝐴\otimes 𝐵$. It describes strings that, when prefixed by a string matching $𝐴$, will match $𝐵$.

Formally, it is defined as:

Intuitively, a parse of $𝐴⊸𝐵$ at a string $𝑣$ is a function that takes any prefix string $𝑢$ and a parse of $𝑢$ in $𝐴$, and produces a parse of the full concatenated string $𝑢·𝑣$ in $𝐵$.

For formal grammars $𝐴$ and $𝐵$, their tensor $𝐴\otimes 𝐵$ represents the concatenation of the languages they describe. A parse for $𝐴\otimes 𝐵$ at a string $𝑤$ consists of a splitting of $𝑤$ into a prefix $𝑢$ and suffix $𝑣$, along with a parse of $𝑢$ in $𝐴$ and a parse of $𝑣$ in $𝐵$.

Formally, it is defined as:

This operation is exactly the Day convolution of $𝐴$ and $𝐵$, where we view formal grammars as presheaves over the monoid of strings.