---
title: Semantic Parsing
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 13
order: 613
summary: >
  Turning a sentence into a structured, executable meaning, the grammar-based way.
  We take the logical forms defined earlier and build them compositionally: a
  rule-based parser that walks a syntax tree applying lambda terms, then Combinatory
  Categorial Grammar (CCG), which fuses syntax and semantics so one lexicalized
  derivation produces both — including supertagging and A* parsing. Learned and
  neural semantic parsers follow in the companion lesson.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "Ch. 12 — Constituency Grammars; §12.6 Lexicalized Grammars; §12.6.1 Combinatory Categorial Grammar"
  - book: Jurafsky
    ref: "Ch. 13 — Constituency Parsing; §13.6 CCG Parsing; §13.6.3 Supertagging; §13.6.4 CCG Parsing using the A* Algorithm"
  - book: Jurafsky
    ref: "Ch. 16 — Computational Semantics and Semantic Parsing"
---

The previous lesson on
[logical semantics](/natural-language-processing/linguistic-structure/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.[^jm-semparse]

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.

$$
% caption: The semantic-parsing task end to end: a natural-language question is
% mapped to a logical form (here a $\lambda$-term over predicates), which
% executes against a knowledge base to return a denotation — the answer.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum height=10mm, align=center, inner sep=3pt},
  lf/.style={draw, align=center, inner sep=4pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, minimum width=42mm] (q) at (0,0) {What states border Texas?};
  \node[lf, draw=acc, text=acc] (l) at (0,-1.9) {lambda x. state(x) and borders(x, texas)};
  \node[box, minimum width=30mm] (kb) at (0,-3.9) {knowledge base};
  \node[box, draw=acc, minimum width=42mm] (a) at (0,-5.7) {Louisiana, Arkansas,\\Oklahoma, New Mexico};
  \draw[->, acc, thick] (q) -- (l) node[midway, right, font=\scriptsize] {semantic parsing};
  \draw[->, thick] (l) -- (kb) node[midway, right, font=\scriptsize] {execute / query};
  \draw[->, acc, thick] (kb) -- (a) node[midway, right, font=\scriptsize] {denotation};
\end{tikzpicture}
$$

> **Definition (Semantic parsing).** The task of mapping a natural-language
> utterance to a meaning representation — a logical form, a query, or an
> executable program — that can be evaluated against a model of the world to
> produce a denotation. The enterprise of designing such representations and
> their parsers is called **computational semantics**.

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](/natural-language-processing/linguistic-structure/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.[^jm-compositional]

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.

$$
% caption: Syntax-driven lambda application for "Texas borders Louisiana": the
% syntax tree, with each node annotated by the meaning it carries. The verb's
% term applies to the object to build the VP meaning, and the VP's term applies
% to the subject to build the sentence meaning borders(texas, louisiana).
\begin{tikzpicture}[>=stealth, font=\footnotesize, level distance=13mm,
  every node/.style={inner sep=1.8pt, align=center},
  level 1/.style={sibling distance=54mm},
  level 2/.style={sibling distance=26mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] (s) {S\\ \footnotesize borders(texas, louisiana)}
    child { node {NP\\ \footnotesize texas}
      child { node {\textit{Texas}} } }
    child { node {VP\\ \footnotesize lam x. borders(x, louisiana)}
      child { node {V\\ \footnotesize lam y. lam x. borders(x, y)}
        child { node {\textit{borders}} } }
      child { node {NP\\ \footnotesize louisiana}
        child { node {\textit{Louisiana}} } } };
\end{tikzpicture}
$$

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

| Node | Rule | Meaning (lambda term) |
| --- | --- | --- |
| _Texas_ | lexical | $\texttt{texas}$ |
| _Louisiana_ | lexical | $\texttt{louisiana}$ |
| _borders_ | lexical | $\lambda y.\, \lambda x.\, b(x, y)$ |
| VP | VP $\to$ V NP | $(\lambda y.\lambda x.\, b(x,y))(\texttt{louisiana}) = \lambda x.\, b(x, \texttt{louisiana})$ |
| S | S $\to$ NP VP | $(\lambda x.\, b(x,\texttt{louisiana}))(\texttt{texas}) = b(\texttt{texas}, \texttt{louisiana})$ |

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

$$
\textit{every} \;:\; \lambda P.\, \lambda Q.\, \forall x\,\big[P(x) \Rightarrow Q(x)\big],
$$

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:

| Node | Meaning (lambda term) |
| --- | --- |
| _state_ | $\lambda x.\, \texttt{state}(x)$ |
| _every_ | $\lambda P.\lambda Q.\, \forall x[P(x) \Rightarrow Q(x)]$ |
| NP (_every state_) | $\lambda Q.\, \forall x[\texttt{state}(x) \Rightarrow Q(x)]$ |
| VP (_borders Texas_) | $\lambda z.\, b(z, \texttt{texas})$ |
| S | $\forall x[\texttt{state}(x) \Rightarrow b(x, \texttt{texas})]$ |

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.

> **Definition (Rule-to-rule hypothesis).** The assumption that each syntactic
> rule is paired with a fixed semantic rule specifying how the meanings of its
> children combine. Under this hypothesis the semantic derivation is isomorphic
> to the syntactic one, and a syntactic parse determines a compositional meaning.

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.[^jm-ccg]

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

$$
% caption: Reading the transitive-verb category (S\NP)/NP as a machine: consume
% the object NP on the right to get a verb-phrase function S\NP, then consume the
% subject NP on the left to get a complete sentence S.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cat/.style={draw, minimum width=26mm, minimum height=9mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cat, draw=acc, text=acc] (v)  at (0,0)    {(S{\char92}NP)/NP};
  \node[cat] (vp) at (0,-2)   {S{\char92}NP};
  \node[cat] (s)  at (0,-4)   {S};
  \node[align=left, font=\scriptsize] (o) at (5.2,0)  {+ object NP\\(to the right)};
  \node[align=left, font=\scriptsize] (u) at (5.2,-2) {+ subject NP\\(on the left)};
  \draw[->, acc, thick] (v)  -- (vp);
  \draw[->, acc, thick] (vp) -- (s);
  \draw[->, black] (o) -- (v);
  \draw[->, black] (u) -- (vp);
\end{tikzpicture}
$$

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:

$$
X/Y \quad Y \;\Rightarrow\; X \qquad (\text{forward, } >)
\qquad\qquad
Y \quad X\backslash Y \;\Rightarrow\; X \qquad (\text{backward, } <)
$$

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$:

$$
% caption: A CCG derivation for "United serves Miami" using only function
% application: forward application (>) combines serves with Miami into the
% verb-phrase category S\NP; backward application (<) combines that with the
% subject United into S.
\begin{tikzpicture}[>=stealth, font=\footnotesize, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % words
  \node (w1) at (0,0)   {United};
  \node (w2) at (3.0,0) {serves};
  \node (w3) at (6.0,0) {Miami};
  % categories
  \node (c1) at (0,-0.7)   {NP};
  \node (c2) at (3.0,-0.7) {(S{\char92}NP)/NP};
  \node (c3) at (6.0,-0.7) {NP};
  % forward application: serves + Miami
  \draw[thick] (2.0,-1.1) -- (6.8,-1.1) node[right, font=\scriptsize] {$>$};
  \node[text=acc] (vp) at (4.4,-1.55) {S{\char92}NP};
  % backward application: United + VP
  \draw[thick] (-0.5,-2.0) -- (6.0,-2.0) node[right, font=\scriptsize] {$<$};
  \node[text=acc] (s) at (2.75,-2.45) {S};
\end{tikzpicture}
$$

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:

$$
X/Y \quad Y/Z \;\Rightarrow\; X/Z \qquad (\text{forward composition, } >\!\mathbf{B})
$$

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 Z\;
X\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:

$$
X \;\Rightarrow\; T/(T\backslash X)
\qquad\qquad
X \;\Rightarrow\; T\backslash(T/X)
$$

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.

$$
% caption: The same sentence with type raising and forward composition. United is
% raised (>T) to S/(S\NP), then composed (>B) with serves to give S/NP — a
% "United serves" constituent still seeking its object — which finally applies to
% Miami. The intermediate S/NP is not a traditional constituent.
\begin{tikzpicture}[>=stealth, font=\footnotesize, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \node (w1) at (0,0)   {United};
  \node (w2) at (3.0,0) {serves};
  \node (w3) at (6.2,0) {Miami};
  \node (c1) at (0,-0.7)   {NP};
  \node (c2) at (3.0,-0.7) {(S{\char92}NP)/NP};
  \node (c3) at (6.2,-0.7) {NP};
  % type raise United
  \draw[thick] (-0.7,-1.1) -- (0.7,-1.1) node[right, font=\scriptsize] {$>$T};
  \node (tr) at (0,-1.55) {S/(S{\char92}NP)};
  % forward composition: United + serves
  \draw[thick] (-1.0,-2.0) -- (4.4,-2.0) node[right, font=\scriptsize] {$>$B};
  \node[text=acc] (comp) at (1.7,-2.45) {S/NP};
  % forward application to Miami
  \draw[thick] (-1.0,-2.9) -- (6.9,-2.9) node[right, font=\scriptsize] {$>$};
  \node[text=acc] (s) at (2.95,-3.35) {S};
\end{tikzpicture}
$$

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:

| Word | Category | Meaning |
| --- | --- | --- |
| _United_ | $NP$ | $\texttt{united}$ |
| _serves_ | $(S\backslash NP)/NP$ | $\lambda x.\, \lambda y.\, \texttt{serves}(y, x)$ |
| _Miami_ | $NP$ | $\texttt{miami}$ |

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 $\texttt{miami}$ for
$x$:

$$
\big(\lambda x.\lambda y.\, \texttt{serves}(y, x)\big)(\texttt{miami})
\;=\; \lambda y.\, \texttt{serves}(y, \texttt{miami}).
$$

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

$$
% caption: A CCG derivation with meaning in lockstep for "United serves Miami".
% Each cell carries a category over a lambda term; forward application (>) reduces
% serves applied to miami, backward application (<) reduces the verb phrase applied
% to united, so the category S and the logical form serves(united, miami) are built
% by the same two steps.
\begin{tikzpicture}[>=stealth, font=\footnotesize, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \node (w1) at (0,0)   {United};
  \node (w2) at (3.4,0) {serves};
  \node (w3) at (7.4,0) {Miami};
  \node[font=\scriptsize] (c1) at (0,-0.6)   {NP : united};
  \node[font=\scriptsize] (c2) at (3.4,-0.6) {(S{\char92}NP)/NP : lam x. lam y. serves(y,x)};
  \node[font=\scriptsize] (c3) at (7.4,-0.6) {NP : miami};
  \draw[thick] (2.1,-1.0) -- (8.4,-1.0) node[right, font=\scriptsize] {$>$};
  \node[text=acc, font=\scriptsize] (vp) at (5.2,-1.45) {S{\char92}NP : lam y. serves(y, miami)};
  \draw[thick] (-0.7,-1.9) -- (7.9,-1.9) node[right, font=\scriptsize] {$<$};
  \node[text=acc, font=\scriptsize] (s) at (3.5,-2.35) {S : serves(united, miami)};
\end{tikzpicture}
$$

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.[^jm-ccg]

$$
% caption: Supertagging as almost-parsing. A neural tagger scores CCG categories
% per word; keeping the top few per word (a beam) leaves a small search space of
% derivations. The word "serves" is ambiguous between a transitive category and an
% intransitive one, and the parser resolves it by which combination yields an S.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={font=\footnotesize},
  cat/.style={draw, minimum width=30mm, minimum height=6mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (w1) at (0,0) {United};
  \node[w] (w2) at (4.2,0) {serves};
  \node[w] (w3) at (8.4,0) {Miami};
  \node[cat] (a1) at (0,-1.0) {NP};
  \node[cat, draw=acc, text=acc] (b1) at (4.2,-1.0) {(S{\char92}NP)/NP  0.71};
  \node[cat] (b2) at (4.2,-1.8) {S{\char92}NP  0.19};
  \node[cat] (c1) at (8.4,-1.0) {NP};
  \draw[->, black] (w1) -- (a1);
  \draw[->, acc] (w2) -- (b1);
  \draw[->, black] (b1.south) -- (b2.north);
  \draw[->, black] (w3) -- (c1);
  \node[anchor=west, font=\scriptsize, text=acc] at (6.4,-1.8) {transitive tag wins:};
  \node[anchor=west, font=\scriptsize, text=acc] at (6.4,-2.2) {only it yields an S};
\end{tikzpicture}
$$

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.[^jm-ccg] 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](/natural-language-processing/linguistic-structure/neural-semantic-parsing).

[^jm-semparse]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 15 — Logical Representations of Sentence Meaning; Ch. 16 — Computational Semantics and Semantic Parsing: semantic parsing (semantic analysis) as the process that creates and assigns formal meaning representations to linguistic inputs, and the desiderata (verifiability, canonical form, inference) such representations must meet.
[^jm-compositional]: **Jurafsky & Martin**, Ch. 16 — Computational Semantics: the principle of compositionality and the rule-to-rule hypothesis, with syntax-driven semantic analysis walking a parse tree and combining child meanings by lambda application at each rule.
[^jm-ccg]: **Jurafsky & Martin**, §12.6.1 — Combinatory Categorial Grammar: categories as atomic elements or slash-typed single-argument functions, the lexicon as the locus of grammatical information, and the combinators (forward/backward application, composition, type raising) with worked derivations for coordination and long-distance dependencies.