Combinatory categorial grammar

Type-logical grammar lets logical rules determine how categories combine. What if we instead choose a small inventory of combinators explicitly? Combinatory categorial grammar (CCG) assigns complex categories to words and combines them with such an inventory (Steedman 2000; Steedman and Baldridge 2011). The lexicon specifies the local argument structure, while the combinators specify which compatible structures may combine.

NoteReading

Read Steedman and Baldridge (2011) on categories, application, composition, and type raising.

Categories and application

We use the same slash convention as in the type-logical grammar section:

• \(X/Y\) requires \(Y\) on the right;
• \(X\backslash Y\) requires \(Y\) on the left.

Thus chases may receive \((S\backslash NP)/NP\). The application rules are

\[ \frac{X/Y \qquad Y}{X} \quad > \qquad\qquad \frac{Y \qquad X\backslash Y}{X} \quad <. \]

Composition and type raising

CCG also permits selected composition and type-raising rules. Forward composition is

\[ \frac{X/Y \qquad Y/Z}{X/Z} \quad >B, \]

and forward type raising is

\[ \frac{X}{T/(T\backslash X)} \quad >T. \]

These rules license constituents that application alone would not produce. But the permitted directions, modalities, and composition degrees are part of the grammar definition. They cannot be added without affecting ambiguity, parsing complexity, and sometimes weak generative capacity.

NoteQuestion

What category results when \(S/VP\) combines with \(VP/NP\) by forward composition?

TipAnswer

Set \(X=S\), \(Y=VP\), and \(Z=NP\). Forward composition returns \(S/NP\).

A chart recognizer

The following recognizer implements application and first-degree harmonic composition. It intentionally omits type raising and crossed composition, so it recognizes only the fragment determined by these four rules.

from collections.abc import Callable, Mapping, Sequence
from dataclasses import dataclass
from typing import Literal


@dataclass(frozen=True, slots=True)
class AtomicCategory:
    name: str


@dataclass(frozen=True, slots=True)
class FunctorCategory:
    result: Category
    argument: Category
    direction: Literal["/", "\\"]


type Category = AtomicCategory | FunctorCategory
type Combinator = Callable[[Category, Category], Category | None]


def forward_application(left: Category, right: Category) -> Category | None:
    if (
        isinstance(left, FunctorCategory)
        and left.direction == "/"
        and left.argument == right
    ):
        return left.result
    return None


def backward_application(left: Category, right: Category) -> Category | None:
    if (
        isinstance(right, FunctorCategory)
        and right.direction == "\\"
        and right.argument == left
    ):
        return right.result
    return None


def forward_composition(left: Category, right: Category) -> Category | None:
    if (
        isinstance(left, FunctorCategory)
        and isinstance(right, FunctorCategory)
        and left.direction == right.direction == "/"
        and left.argument == right.result
    ):
        return FunctorCategory(left.result, right.argument, "/")
    return None


def backward_composition(left: Category, right: Category) -> Category | None:
    if (
        isinstance(left, FunctorCategory)
        and isinstance(right, FunctorCategory)
        and left.direction == right.direction == "\\"
        and right.argument == left.result
    ):
        return FunctorCategory(right.result, left.argument, "\\")
    return None


COMBINATORS: tuple[Combinator, ...] = (
    forward_application,
    backward_application,
    forward_composition,
    backward_composition,
)

type CCGChart = list[list[set[Category]]]


def ccg_chart(
    words: Sequence[str],
    lexicon: Mapping[str, Sequence[Category]],
) -> CCGChart:
    chart: CCGChart = [
        [set() for _ in range(len(words) + 1)]
        for _ in range(len(words) + 1)
    ]

    for left, word in enumerate(words):
        chart[left][left + 1].update(lexicon.get(word, ()))

    for width in range(2, len(words) + 1):
        for left in range(len(words) - width + 1):
            right = left + width
            for split in range(left + 1, right):
                for left_category in chart[left][split]:
                    for right_category in chart[split][right]:
                        for combine in COMBINATORS:
                            if result := combine(left_category, right_category):
                                chart[left][right].add(result)

    return chart


N = AtomicCategory("N")
NP = AtomicCategory("NP")
S = AtomicCategory("S")

lexicon: dict[str, tuple[Category, ...]] = {
    "greyhounds": (NP,),
    "chase": (FunctorCategory(FunctorCategory(S, NP, "\\"), NP, "/"),),
    "rabbits": (NP,),
}

words = ("greyhounds", "chase", "rabbits")
chart = ccg_chart(words, lexicon)
S in chart[0][len(words)]

Why the recognizer is correct for this fragment

The chart invariant is

\(C\) occurs in chart cell \([i,j]\) exactly when the lexical assignments and the four implemented combinators derive category \(C\) for words \(i\) through \(j-1\).

For soundness, a length-one category comes directly from the lexical entry for that word. A category added to a longer span is returned by one of the four combinators applied to categories already present on two adjacent subspans. By induction on span length, those child categories have derivations over their stated words. Adding the licensed combinator gives a derivation of the parent category over their concatenated span.

For completeness, take any derivation licensed by this fragment. A one-word derivation is entered during lexical initialization. A longer derivation ends with one of the four binary combinators. Its left and right subderivations cover adjacent, shorter spans. By the induction hypothesis, both child categories occur in their cells. The chart loop visits their split point and applies every implemented combinator, so it adds the parent category. Thus, the chart contains every derivable category.

The qualification “for this fragment” matters. The proof ranges over the lexical categories and four combinators in COMBINATORS. It does not establish completeness for a CCG that also licenses type raising, crossed composition, or higher-degree composition.

Formal position

Restricted CCGs with bounded-degree composition are weakly equivalent to TAG (Vijay-Shanker and Weir 1994). This result applies to a specified formal system, not to every grammar called CCG. Richer combinator inventories may change the result.

CCG is thus one route to the TAG-equivalent portion of the mildly context-sensitive formalisms. General multiple context-free grammars cover a larger family, while still admitting polynomial-time recognition for each fixed grammar. The equivalence-proof section uses the argument stack of a CCG category as the invariant in a slow translation through linear indexed grammar.

References

Steedman, Mark. 2000. The Syntactic Process. MIT Press.

Steedman, Mark, and Jason Baldridge. 2011. “Combinatory Categorial Grammar.” In Non-Transformational Syntax. Wiley-Blackwell.

Vijay-Shanker, K., and David J. Weir. 1994. “The Equivalence of Four Extensions of Context-Free Grammars.” Mathematical Systems Theory 27 (6): 511–46. https://doi.org/10.1007/BF01191624.