Semantic Parsing

The previous lesson on logical semantics argued that the meaning of a sentence can be written down as a formal object (a first-order-logic formula, a lambda term, a database query) that a machine can reason over and execute against a knowledge base. It defined what those meaning representations look like. It did not say how to get one out of a sentence. That is the job of semantic parsing: the process whereby a formal meaning representation is built and assigned to a linguistic input.¹

The target is not a tree of grammatical categories but a structure a program can run. For What states border Texas? the useful output is a query whose answer is a set of states, not a parse of the question. Semantic parsing maps the ambiguous surface of language to something with a denotation.

Two families of methods run across these two lessons. Compositional parsers build the meaning from the meanings of the parts, guided by syntax, so the logical form is guaranteed to be well-formed by construction. Neural parsers treat the logical form as a string and learn to generate it directly, trading the guarantee for the flexibility of a learned model. This lesson develops the grammar-based first family — syntax-driven lambda application and Combinatory Categorial Grammar, which fuses syntax and semantics so tightly that one derivation produces both. The learned and neural family, together with Abstract Meaning Representation and executable text-to-SQL, continues in learned and neural semantic parsing.

Compositional semantic parsing

The oldest and cleanest idea is the principle of compositionality: the meaning of a whole is a function of the meanings of its parts and the way they are combined. If we can attach a meaning to each word and a combination rule to each grammar rule, then parsing the sentence also parses its meaning — the two trees have the same shape.²

The mechanism is syntax-driven lambda application. Each lexical entry pairs a word with a lambda term; each phrase-structure rule says which child is the function and which is the argument, so the parent's meaning is the function applied to the argument. Recall from the logical-semantics lesson that a transitive verb denotes a two-place relation curried into nested lambdas, and a proper noun denotes an individual constant. Walk the tree bottom-up, applying at each internal node, and the root carries the meaning of the sentence.

The same derivation reads cleanly as a table walking the tree from the leaves up. Write $b$ for the two-place predicate $\text{borders}$, and carry the lambda terms explicitly:

The verb takes its object first (forming the VP meaning), then the whole VP is applied to the subject. Each step is a single beta-reduction — substitute the argument for the bound variable. The syntax tree and the semantic derivation are the same tree under different labels — the very correspondence compositionality promises.

Determiners and quantifiers are handled the same way with more elaborate lambda terms. Every state borders Texas needs the determiner every to denote a generalized quantifier, a function over two predicates — a restrictor and a scope — so that the subject NP's meaning outscopes the verb. The lexical entry is

where $P$ is filled by the noun (state) and $Q$ by the verb phrase. Walk the tree and the terms assemble as before, one application per rule:

The subject NP is now itself a function that takes the verb phrase as argument, the reverse of the plain proper-noun case, and applying it substitutes the VP's predicate in for $Q$. The machinery is heavier but the recipe is unchanged: one lambda term per lexical item, function application at each rule. The one thing this tree-walking cannot settle on its own is scope ambiguity. Every state borders a state has two readings — one border-partner shared by all states, or a possibly different partner per state — that share a single syntax tree, so a purely compositional parser must either commit to one reading or emit an underspecified form and defer the choice.

The weakness is brittleness. The approach needs a hand-built grammar, a hand-built lambda term for every word, and a clean syntactic parse to walk; ambiguity in the syntax multiplies into ambiguity in the semantics, and any construction the grammar does not cover produces no meaning at all. The rest of the lesson is a sequence of answers to that brittleness — first a grammar formalism built for composition, then learning, then dropping the grammar entirely.

Combinatory Categorial Grammar

Compositional parsing kept syntax and semantics in separate representations that happen to share a tree shape. Combinatory Categorial Grammar (CCG) fuses them. It is a heavily lexicalized grammar: almost all the grammatical information lives in the lexicon, and a tiny set of rules governs how entries combine. Because each lexical entry can carry a lambda term alongside its category, one CCG derivation produces the syntax and the meaning together.³

Categories

A CCG category is either atomic or a function. The atomic set is small — for English, essentially $S$ (sentence), $NP$ (noun phrase), $N$ (noun), and $PP$ (prepositional phrase). Everything else is a single-argument function written with a slash:

• $X/Y$ is a function that seeks an argument of type $Y$ to its right and returns an $X$.
• $X\backslash Y$ seeks a $Y$ to its left and returns an $X$.

The slash encodes the type of the expected argument, the direction it is found, and the type of the result. Subcategorization falls out for free: a transitive verb like borders is $(S\backslash NP)/NP$ — a function that first takes an $NP$ object on the right, yielding $S\backslash NP$, which then takes an $NP$ subject on the left, yielding $S$.

Nouns and proper nouns take atomic categories ($N$, $NP$), reflecting their role as arguments; verbs, determiners, and prepositions take functional categories. A ditransitive verb like give is $((S\backslash NP)/NP)/NP$: consume two objects on the right, then a subject on the left. The lexicon is where the grammar lives.

Combinators: application and composition

The rules that combine categories are the combinators. The first pair is function application, in the two directions:

A CCG derivation grows downward from the words: a horizontal line spans the combined elements, tagged at the right with the operation. Here is United serves Miami, with serves as the transitive verb $(S\backslash NP)/NP$:

Application alone gives no more power than a context-free grammar; it just moves information into the lexicon. The extra reach comes from function composition, which combines two functions without an intervening argument:

The first constituent seeks a $Y$ to its right; the second provides a $Y$ but is itself still waiting on a $Z$. Composition fuses them into one function of type $X/Z$ that skips the missing middle. There is a backward version $Y\backslash ZX\backslash Y\Rightarrow X\backslash Z$; both are signalled by a $\mathbf{B}$ in derivations, with $<$ or $>$ for direction.

The third operator is type raising, which turns a plain argument into a function that takes its own function as argument:

Type-raising a subject $NP$ to $S/(S\backslash NP)$ lets it compose forward with the verb before the object arrives, giving a strictly left-to-right, word-by-word derivation — one reason CCG is a good model of how humans process language incrementally.

Composition and type raising handle constructions that plain CFGs cannot: coordinating non-constituents (flew IcelandAir to Geneva and SwissAir to London), and long-distance dependencies. For the relative clause the flight that United diverted, the word that gets the lexical category $(NP\backslash NP)/(S/NP)$ — it seeks a sentence missing an object on its right, and turns it into a noun-phrase modifier. Type-raising United and composing it with the transitive verb diverted produces exactly that $S/NP$, so the gap where the object should be is threaded through the derivation without any movement machinery.

Semantics in lockstep

For semantic parsing, each combinator has a semantic counterpart. Pair every lexical category with a lambda term, and function application on the categories is beta-reduction on the terms; forward composition is function composition on the terms. The derivation that assembles the category $S$ simultaneously assembles the logical form. There is no separate semantic pass — syntax and meaning are built by the same rules at the same time.

For example, give each word an entry of the form category $:$ lambda term, and run the United serves Miami derivation on both halves at once:

Forward application combines serves with Miami. On the categories, $(S\backslash NP)/NP$ consumes the right-hand $NP$ to give $S\backslash NP$; on the terms, the very same step is a beta-reduction that substitutes $\text{miami}$ for $x$:

Backward application then combines United with that verb phrase — category $NPS\backslash NP\Rightarrow S$, term $(\lambda y.\text{serves}(y,\text{miami}))(\text{united})=\text{serves}(\text{united},\text{miami})$. The category $S$ and the closed formula $\text{serves}(\text{united},\text{miami})$ pop out of the same two rule applications.

This lockstep is why CCG is a common substrate for learned semantic parsers, covered in the next lesson.

Parsing CCG: supertagging and A*

A CCG grammar says how categories combine; a CCG parser has to find the derivation for a given sentence. The hard part is that the lexicon is enormous and ambiguous. CCGbank, the CCG treebank derived from the Penn Treebank, uses over a thousand distinct categories, and a common word can carry dozens of them. Assigning the right category to each word — its supertag — is therefore called supertagging, and it is almost parsing: once every word has its category, only a few ways remain to combine them.³

A modern supertagger is a neural sequence model (a biLSTM or transformer) that emits, for each word, a probability distribution over categories. Keeping only the few highest-scoring categories per word — a per-word beam — shrinks the parse search to something small. The combination step then searches for the highest-scoring derivation, and because each category has a probability, the search is naturally an A* search: expand partial derivations in order of a score that adds the categories committed so far to an admissible upper bound on the categories still to come, so the first complete parse pulled off the agenda is provably the best-scoring one.³ Supertag-then-combine is what makes CCG parsing fast enough to be practical despite the size of the category set.

Where this continues

The grammar-based route builds meaning by construction. A syntax-driven parser walks the tree applying one lambda term per word and one application per rule, so the semantic derivation is isomorphic to the syntactic one; CCG folds the two into a single heavily lexicalized formalism, where each combinator (application, composition, type raising) has a semantic counterpart and one derivation yields both the category $S$ and the logical form. Supertagging plus A* search makes that derivation findable despite a thousand-category lexicon.

The weakness throughout is brittleness: a hand-built grammar and a hand-built lambda term for every word. Replacing that hand labor with learning — inducing the lexicon and scoring model from data, dropping the grammar for a neural sequence-to-sequence decoder, and the Abstract Meaning Representation and text-to-SQL that come with it — continues in learned and neural semantic parsing.