Semantic Parsing and Meaning Representations

A language model can answer a question in fluent English. But sometimes the useful output is not another sentence. It is a database query, a logical formula, a graph, or a program that a machine can check, execute, or reason over. If you ask, "Which departments have more than two enrolled students?", a helpful answer might be a list of department names. A more useful and inspectable answer might be a SQL query that computes that list from your actual database.

A stored answer may become stale when the database changes. A query records a procedure that can be executed against a new snapshot and checked against expected rows. Producing that query separates the interpretation of the question from the computation of the answer.

Semantic parsing is the task of turning natural language into a formal meaning representation. The representation might be first-order logic, a lambda-calculus expression, an Abstract Meaning Representation (AMR) graph, a SQL query, a regular expression, or a sequence of API calls. What ties these together is that the output has a syntax and a semantics. The syntax tells you what expressions are well formed. The semantics tells you what those expressions mean. For example, a formula can denote a truth value, a SQL query a result table, and an executed program an output.

The phrase "meaning representation" is deliberately broad. The target depends on the task. Formal-semantic analyses can use logical formulas and model-theoretic truth; computational-linguistic meaning representations include AMR graphs, frame-based structures, and logical forms. Database interfaces can target SQL, task-oriented assistants can produce API calls, and planning systems can use action sequences and state transitions. These targets have explicit formation rules and an intended interpretation. Executable representations additionally specify how to evaluate or run the structured object.

This chapter builds on the semantic ideas from Part VIII: Semantics and Information Extraction. Earlier, we treated word senses, sentence meaning, semantic roles, relations, events, and entity linking as separate problems. Here we connect them. A semantic parser must decide what the words mean, how they combine, what entities and relations they refer to, and what formal object the whole utterance denotes. The chapter also builds on tokenization from Part V: Subword Tokenization and syntax from Part VII: Linguistic Form: Morphology and Syntax. Formal representations do not remove the need for linguistic analysis. They make the analysis explicit.

Designing a parser raises some of the same questions as semantic analysis: what counts as a predicate or argument, how to represent scope, and whether presupposed or implicit content matters for the task. A task-specific parser may deliberately omit distinctions that a broader semantic analysis would retain. Building the parser makes those choices explicit.

The definition leaves the representation language open on purpose. What counts as a meaning representation depends on the downstream task. For a question-answering system over a database, the representation language might be SQL. For a theorem prover, it might be first-order logic. For a virtual assistant, it might be a JSON object that names an intent and its slots. The representation must specify which structures are well formed and what distinctions they preserve. Whether a valid structure can be executed depends on the target language and application.

The central tension is compositionality versus coverage. A compositional analysis of "Alice likes Bob" derives its meaning from the meanings of "Alice", "likes", and "Bob" and from how they combine. But natural language is also ambiguous, underspecified, context-dependent, and messy. A formal representation must preserve the distinctions its task needs. For a learned parser, representation complexity must be considered alongside the data and search procedure; execution is an additional requirement when the application needs to run the output. That tradeoff runs through every representation in this chapter.

It helps to see the tension as two failure modes. If the representation is too weak, it cannot say what the task needs, and the parser is forced to throw away distinctions that matter. If the representation introduces distinctions unsupported by the data, annotation and search can become harder and learning may require additional supervision. Good representation design balances these failure modes.

Before comparing logical forms, AMR graphs, and SQL, we need criteria. A representation is not good in the abstract. It is good relative to a task.

A representation can be adequate for one specified task and insufficient for another. Compare the target with the task requirements: which distinctions must it preserve, what supervision is available, and which errors matter?

• Expressivity: Can the representation express the distinctions the task requires? A SQL query can express aggregation and joins. A first-order formula can express quantification and negation. An AMR graph can express predicate-argument structure and reentrancy, but it does not encode quantifier scope in the way first-order logic does.
• Compositionality: Does the representation have a systematic way to combine meanings of parts? Lambda calculus gives a clean composition rule through function application. SQL has a grammar with compositional semantics, but natural-language phrases do not always map neatly onto SQL clauses.
• Executability: Can the representation be evaluated against a world, database, or interpreter? Executability gives us verification. We can run a SQL query, evaluate a logical formula in a model, or execute a program. It also gives us weak supervision: we can train a parser from denotations even when we lack gold logical forms.
• Learnability: Is the representation easy enough to annotate and search over? A representation that is too expressive may have a huge space of possible parses. A representation that is too simple may lose task-relevant meaning.
• Interpretability: Can a human inspect the representation and understand why the system produced it? Logical forms and SQL are relatively readable. Neural model hidden states are not.
• Ambiguity handling: Does the representation force a single reading, or can it represent alternatives and underspecification? "Every student reads a book" has at least two readings. A parser that outputs one fully resolved, reading-specific logical form has chosen one reading.

These criteria ask different questions. A logical form makes predicates, bindings, and scope explicit, but mapping language to that form requires choosing the intended analysis. Detailed logical-form annotation can require substantial semantic work. SQL is a natural fit when the data and computation can be expressed relationally. Base AMR concentrates on predicate-argument structure and abstraction across paraphrases while omitting some distinctions. The useful comparison is with the task requirements.

A useful exercise is to compare a candidate representation with these criteria before writing any code. For a calendar assistant, for instance, the representation might contain an intent, a single date and time, and participants. An application can validate those fields and map them to calendar operations. The listed fields do not directly encode recurrence exceptions; those require an agreed extension. A small field set constrains the output structure, but learnability also depends on the data, grounding requirements, and model. If a reasoning task needs quantification, a logical form can make the intended scope explicit while requiring choices about predicates and bindings.

Logical forms are the classical answer to the question, "What is the meaning of a sentence?" A logical form is a formula in a formal language with a model-theoretic semantics. The formula denotes a truth value in a model, or a set of satisfying assignments. Three historical contributions provide useful reference points for the discussion here. Frege distinguished the sense of an expression from its reference, Tarski gave a rigorous definition of truth in a model, and Montague showed that a fragment of English could be given a compositional model-theoretic semantics. Here we compare representation, interpretation, and composition through these contributions.

In first-order logic, we have constants, variables, predicates, quantifiers, and connectives. Constants name individuals, variables range over individuals, and predicates denote relations. The quantifiers introduced here express whether a formula holds for every domain individual or for at least one; connectives combine formulas. A simple sentence becomes a predicate application:

A quantified sentence becomes a formula with a quantifier:

This formula says: for every entity $x$, if $x$ is a student, then there exists an entity $y$ such that $y$ is a book and $x$ reads $y$.

The displayed formulas are already closed sentences: none of their variables occurs free. Their truth values are determined only after choosing a model. The predicate like could denote different binary relations in different models, and the constants alice and bob could denote different entities. Syntax specifies the formula; interpretation supplies its denotation.

The implication in the universal formula is not an accident. "Every student reads a book" does not say that everything is a student. It says that for anything, if it is a student, then it reads a book. Using conjunction instead would say that everything is both a student and a reader, which is far too strong. The existential formula uses conjunction for the opposite reason: it asserts that something exists that is both a book and read. Using implication there would be trivially satisfied by any non-book.

The meaning of a formula is defined relative to a model $\mathcal{M}=(D,I)$ and, for formulas with free variables, an assignment $g$. The domain $D$ contains the entities; $I$ interprets constants as entities and predicates as relations. The assignment maps each free variable to an entity in $D$. Write $\mathcal{M},g\models\phi$ for satisfaction, and let $g[x\mapsto d]$ change only the value assigned to $x$, keeping every other variable fixed. The recursive rules are:

• $\mathcal{M},g\models P(c)$ if $I(c)\in I(P)$. For a variable argument, use its value under $g$.
• $\mathcal{M},g\models\neg\phi$ if $\mathcal{M},g\not\models\phi$.
• $\mathcal{M},g\models\phi\land\psi$ if both conjuncts are satisfied under the same assignment $g$.
• $\mathcal{M},g\models\forall x\,\phi$ if $\mathcal{M},g[x\mapsto d]\models\phi$ for every $d\in D$.
• $\mathcal{M},g\models\exists x\,\phi$ if $\mathcal{M},g[x\mapsto d]\models\phi$ for at least one $d\in D$.

For a closed sentence, satisfaction does not depend on $g$, so we can write $\mathcal{M}\models\phi$ without it. The recursive definition states how the truth of a complex formula depends on its parts. In a finite model with explicitly available relations, you can evaluate quantifiers by enumerating the domain, as our code will do. The definition alone does not provide a terminating algorithm for arbitrary infinite models or a general decision procedure for first-order validity.

This semantics is precise, but it is also demanding. To parse natural language into first-order logic, a system must decide which predicates to use, how to handle quantifier scope, how to represent events, and how to ground names and pronouns. Those decisions are not dictated by English. They are modeling choices.

A parser that uses read(x, y) and a parser that uses reading_event(e) ∧ agent(e, x) ∧ patient(e, y) can both be correct, but they are not interchangeable. The first is simpler; the second supports adverbial modification and temporal annotation. The choice depends on what the downstream system needs to do.

First-order logic gives us a target language, but it does not tell us how to build the formula from a sentence. Lambda calculus gives us a compositional glue. The principle of compositionality says that the meaning of a complex expression is determined by the meanings of its parts and by the way those parts are combined. Lambda calculus is the standard formal tool for making this principle precise. It provides a uniform operation, function application, that mirrors the way syntactic constituents combine.

The simply typed lambda calculus has base types $e$ for entities and $t$ for truth values. Function types are written $\langle \sigma, \tau \rangle$ or $\sigma \to \tau$. Types matter because they rule out nonsensical combinations. You cannot apply an entity to an entity, or a truth value to a predicate, without a type error. A typed grammar therefore constrains the space of possible parses and gives the parser a way to reject ill-formed combinations early.

A verb like "likes" can be treated as a function from objects to functions from subjects to truth values:

The type is $\langle e, \langle e, t \rangle \rangle$. The object "Bob" has type $e$. Applying "likes" to "Bob" gives a predicate:

Applying that predicate to "Alice" gives a truth value:

The reduction rule is beta reduction:

where $M[x := N]$ means capture-avoiding substitution of $N$ for free occurrences of $x$ in $M$. Rename a bound variable first when it would otherwise capture a free variable in $N$. Function application combines compatible typed meanings in the examples below.

In a full Montague-style grammar, every syntactic rule is paired with a semantic rule. The grammar says how words and phrases combine; the semantic rule says how their meanings combine. The pairing is what makes the composition systematic rather than ad hoc.

A generalized quantifier is a function from predicates to truth values. Its type is $\langle \langle e,t \rangle, t \rangle$. Noun phrases like "every student" and "a book" have this type. The determiners "every" and "a" are one level up: they take a predicate and return a generalized quantifier, so their type is $\langle \langle e,t \rangle, \langle \langle e,t \rangle, t \rangle \rangle$.

Treating a determiner as a relation between two predicates makes its restriction and scope explicit. The universal does not carry existential import: "every student reads" entails "some student reads" only if the class of students is nonempty. The existential determiner supplies its own witness.

For each potential subject $x$, apply "a book" to the predicate $\lambda y.\,\text{read}(x,y)$. Abstracting over $x$ gives the verb-phrase predicate consumed by "every student":

which beta-reduces to:

This is the surface-scope reading. It says each student may read a different book. The universal quantifier is outermost, so its scope includes the existential. This describes logical scope rather than an evaluation-order rule. The alternative reading, in which the existential takes wide scope, is discussed next.

The string "Every student reads a book" is compatible with another reading:

This is the inverse-scope reading. It says there is one particular book that every student reads. English does not disambiguate the two readings with word order alone. Context and world knowledge can favor one reading. Prosody can also influence scope interpretation, although its effects depend on the construction and discourse; stress does not reliably select a reading in every double-quantifier sentence.

Scope choices can matter in sentences such as "A student talked to every professor": one student may have talked to everyone, or each professor may have talked to a different student. Distinct scope orders do not always yield distinct meanings; for example, two universal quantifiers commute in ordinary first-order logic. Adding quantifiers can increase the number of potential scope orders, while linguistic constraints may rule out orders. Underspecification can postpone the choice.

The truth of a scoped formula depends on the world, not only on the string. A small model makes the divergence between readings concrete.

Classical semantic parsers sometimes output one reading. That is a modeling decision, not a fact about the sentence. More sophisticated systems represent underspecification. Hole semantics, for example, uses metavariables for missing scope information and constraints on how those holes can be filled. The parser can leave scope unresolved until later.

Underspecification is attractive because it avoids committing to a reading before the context is known. This can complicate evaluation because the output retains unresolved alternatives rather than selecting one fully resolved reading.

This matters for evaluation. Under exact-match evaluation, if a test set contains one gold logical form per sentence, a parser that chooses the other reading is marked wrong even if its reading is linguistically valid. Exact-match evaluation of logical forms can therefore punish legitimate ambiguity. We will return to this issue in the evaluation discussion. A partial remedy is to annotate a set of acceptable readings and accept predictions that match one of them, using explicit annotation guidelines.

Many sentences describe events. In an event-based analysis, "Alice buttered the toast" asserts that a buttering event occurred, with Alice as the agent and the toast as the patient.

Davidson's insight was that making the event explicit solves several problems at once. It explains why "Alice buttered the toast with a knife" entails "Alice buttered the toast": the first formula conjoins more predicates to the same event variable. It also gives a natural place to attach temporal and locative modifiers.

Event semantics introduces an event variable. In Davidson's original form, the verb remains a relation over the event variable and its arguments:

Neo-Davidsonian formulations separate the event predicate from its semantic roles. The following formula uses a unary buttering predicate and separate role relations, then adds an instrument and a time as further conjuncts:

This style connects directly to the semantic roles and argument structure discussed earlier in this part. It also connects to AMR, which uses PropBank-style frames and role labels such as :ARG0 and :ARG1. The correspondence is not exact, but the intuition is the same: meaning is organized around events and their participants, not around a flat relation between two names.

Abstract Meaning Representation, or AMR, is a sentence-level semantic graph formalism. Banarescu et al. (2013) presented its influential sembanking framework, building on earlier AMR and PENMAN work. AMR represents the meaning of a sentence as a rooted, directed graph. Nodes are concepts. Edges are relations. The graph can share nodes, which lets it represent reentrancy and control. AMR was designed to be simple enough for rapid human annotation and abstract enough to be stable across paraphrases. It has since become a standard target for graph-based semantic parsing and a useful representation for summarization, information extraction, machine translation, and semantic similarity.

A constituency tree represents how words group into phrases. An AMR graph represents who did what to whom, and how the participants relate. The difference is easiest to see with control verbs. In "The boy wants to go", the boy is the subject of "wants" and also the understood subject of "go". A constituency analysis can mark this with a co-indexed empty category. An AMR graph simply reuses the same node, which makes the shared participant explicit and easy to query.

For example, "The boy wants to go" becomes something like:

(w / want-01
   :ARG0 (b / boy)
   :ARG1 (g / go-02
            :ARG0 b))

The variable w is an instance of the PropBank frame want-01. Its :ARG0 is the wanter, the boy b. Its :ARG1 is the thing wanted, an instance g of go-02. The goer is also b, so the graph reuses the same node. That reuse is reentrancy: the boy is both the wanter and the understood goer. The go-02 node describes what he wants; it does not assert that he actually goes.

Reentrancy is a structural property of the graph. Drawing the nodes and role edges shows that one boy node serves as both the wanter and the goer.

AMR uses several kinds of labels:

• Concepts: boy, go-02, want-01, city, person.
• Frame roles: :ARG0, :ARG1, :ARG2, and so on, with meanings defined by PropBank frames.
• General relations: :mod, :time, :location, :topic, :poss, :part-of.
• Inverse roles: :ARG0-of and :location-of reverse the direction of the corresponding role in the written graph.
• Constants: literal strings, numbers, and symbolic values such as - for polarity. Names and dates usually use structured name and date-entity subgraphs containing literal values.

The PropBank frames deserve a note. Each roleset defines a predicate sense and its associated argument roles. want-01 is the frame for the desire sense, not for the sense of "want" that means "lack". The numbered roles are not thematic roles in the abstract; they are frame-specific. This makes AMR precise but also makes it dependent on the frame lexicon. Annotators and parsers must select the intended frame.

AMR is "abstract" because it deliberately drops some surface distinctions. It does not represent word order. It usually does not represent articles. It does not encode quantifier scope in the way first-order logic does. The base annotation framework specifies target graphs without prescribing a syntax-to-semantics derivation from English. The base annotation conventions omit some truth-conditional distinctions discussed here. Formal interpretations have nevertheless been proposed: Bos (2016) gives a translation into first-order logic and discusses scope extensions.

AMR is usually written in PENMAN notation. The format is a parenthesized graph with variables, concepts, and role edges. The earlier example is valid PENMAN. For the concept-labeled AMR graphs used here, each structural opening parenthesis introduces a variable, a slash, and a concept. Each role is written as a colon followed by a label, and each role can point to a node or a constant.

PENMAN is compact and readable, but it is not a programming language. It is a linearization of a graph. The same graph can be written in multiple ways by reordering edges or using inverse roles. For example, (w / want-01 :ARG0 (b / boy)) and (b / boy :ARG0-of (w / want-01)) describe the same labeled relation. They choose different roots, so they also differ in the focus convention of AMR; matching a single edge is weaker than matching a complete rooted AMR. That flexibility is useful for annotation, but it complicates parsing and evaluation. A parser that generates PENMAN strings must produce valid parentheses, valid variable references, and consistent reentrancy.

AMR parsing maps a sentence to an AMR graph. Early systems used graph-based or transition-based methods. Sequence-to-sequence approaches encode the sentence and decode a graph serialization, including PENMAN strings; pretrained encoder-decoder models have also been used for this task. Graph-aware decoding can use the partially constructed graph to guide subsequent expansion, as in Cai and Lam (2020). A sequence-to-sequence model can produce valid graphs, but unconstrained generation does not guarantee validity. Grammar constraints and graph checks can help enforce that requirement.

Evaluation is usually done with Smatch, introduced by Cai and Knight in 2013. Smatch compares instance, attribute, and relation triples under a mapping between predicted and reference node variables. Its objective maximizes matching triples and computes precision, recall, and F1 from that overlap. Common implementations search with hill climbing and restarts, so the returned alignment need not attain the global maximum. Variable names themselves do not matter. What matters is the graph structure and the labels.

The variable-alignment step is necessary because two graphs can be structurally identical but use different variable names. Smatch computes F1 using the selected alignment, rather than comparing variable spellings directly.

Smatch is useful, but it has limitations. It can reward graphs that are structurally similar but semantically wrong. It does not directly evaluate truth conditions or executability. It is also sensitive to annotation choices. Two annotators may produce different graphs for the same sentence. Choices about implicit relations, light verbs, and named entities can change those graphs. AMR is a semantic representation language. These limitations are not fatal. They mean Smatch should be read as a measure of graph overlap, not as a measure of understanding.

AMR keeps a great deal of predicate-argument structure. It captures who did what, to whom, with what, where, and when. Reentrancy represents control and shared participants, and the graph can include named entities and quantities. Research applications include summarization, information extraction, machine translation, and semantic similarity. Annotation effort depends on the annotators, genre, tools, and agreement protocol. In the original AMR study, annotators using AMR Editor took 7-10 minutes to create a sentence annotation and 1-3 minutes to postedit one. Four experts annotated 100 newswire and 80 web sentences, then formed a consensus through discussion; average expert-versus-consensus Smatch was 0.83 for newswire and 0.79 for web text. These are study-specific measurements, not a general comparison with full logical-form annotation.

AMR drops other distinctions:

• It does not encode quantifier scope in a general way.
• It does not preserve surface word order.
• It often normalizes morphology and light verbs.
• Its base conventions omit distinctions such as general quantifier scope; additional formal interpretation and extensions are needed for those distinctions.

These are not bugs. They are design choices intended to make the representation more abstract and stable across paraphrases. Base AMR does not retain general quantifier scope. Using an AMR graph as a database query also requires an additional query interpretation or translation.

For tasks that need scope, such as reasoning about several quantifiers, AMR is a poor fit. For tasks that need predicate-argument structure, such as event extraction or summarization, it is a strong fit.

Text-to-SQL is semantic parsing where the target representation is a SQL query. It lets people query relational databases through natural-language questions. Enterprises store data in tables, and people who need answers may not know SQL. Reliability matters: a wrong query can silently return incorrect rows, and a user who cannot read SQL may not notice.

A SQL query has a precise syntax and an executable semantics. Consider:

SELECT name
FROM students
WHERE age > 20;

The query denotes a table. Its rows are the names of students whose age is greater than 20. This is a denotational view of SQL: the meaning of a query is the table it returns.

SQL semantics is not exactly first-order logic. It differs in several ways:

• It uses bag semantics by default, so duplicate rows can appear unless DISTINCT is used.
• It has three-valued logic because of NULL.
• It has aggregation, grouping, sorting, and nested queries.

These features make SQL expressive, but they also make the mapping from natural language challenging. A parser that assumes set semantics or two-valued logic can make mistakes when duplicates or NULL-sensitive predicates affect the result.

SQL queries can use constructs such as these:

• SELECT list: which columns or expressions to return.
• FROM clause: which tables to read.
• WHERE clause: row-level filters.
• GROUP BY: partitions rows into groups.
• HAVING: filters groups after aggregation.
• ORDER BY: sorts the result.
• LIMIT: restricts the number of rows.
• Set operations: UNION, INTERSECT, EXCEPT.
• Subqueries: nested queries in the FROM, WHERE, or SELECT clause.

A natural-language question need not spell out SQL clauses. Under the schema used below, one valid solution to "Which departments have more than two enrolled students?" joins the three tables, groups by department, counts distinct students, and applies a HAVING condition. Equivalent queries can express the same answer condition with other SQL structures. The parser must choose a structure that captures the intended relationships and count.

The count must refer to students rather than enrollment records. A student can have several enrollment rows, so the query needs to avoid counting that person repeatedly. The question supplies the intended unit; the schema determines how to recover it from the stored rows.

Schema linking is the process of mapping mentions in the question to tables, columns, and values in the database schema. A linking error can make a syntactically valid query answer the wrong question.

Schema names and storage conventions need not match how users phrase questions. Column names are abbreviated, tables are normalized, and values are stored in formats that the question does not mention. A question about "departments" may need to join a dept table through a dept_id column that the question never names.

Consider the question "Which departments have more than two enrolled students?" The word "departments" likely maps to the departments table or the department_id column. "Students" maps to the students table. "Enrolled" maps to the enrollments table. "More than two" maps to a comparison with the number 2. None of these mappings is guaranteed. A database might call the table dept, division, or org_unit. A column might be named student_count rather than student_id. The question might use a synonym that does not appear in the schema.

Real databases can contain hundreds of tables and thousands of columns. A parser can narrow the candidate set using signals such as string similarity, type compatibility, schema relationships, and learned representations.

Schema linking must handle:

• Synonyms and abbreviations: "employees" versus emp, "departments" versus dept.
• Ambiguous column names: name might exist in several tables.
• Values: "the Computer Science department" might require matching a string value.
• Joins: the question may require joining tables through foreign keys.
• Types: comparing a date column to a string, or an integer column to a word number.
• Dialect differences: SQLite, MySQL, PostgreSQL, and BigQuery differ in functions, quoting, and date handling.

A query can be syntactically valid and still be wrong because it linked "students" to the wrong table or joined on the wrong key.

Schema linking is therefore not a preprocessing detail. It is a core part of the semantic parsing problem, and schema-linking errors can propagate into the generated query and change its result.

Text-to-SQL systems expected to handle new combinations of familiar operations need compositional generalization. A model that has seen many simple SELECT ... WHERE ... queries may fail on nested queries, set operations, or aggregation with HAVING. The displayed solution to "Which departments have more than two enrolled students?" uses grouping and counting.

Generating the displayed plan combines joins, grouping, a distinct count, and a HAVING condition in a configuration the model may not have seen during training. Other valid SQL formulations can express the same answer condition.

A training set may cover individual SQL operations without covering all their combinations. Models can memorize patterns and still fail on new combinations of known components. Benchmarks such as Spider were designed to test cross-domain generalization with held-out databases and complex query structures.

The problem is compounded by the fact that the training set is finite and the space of schemas is open-ended. A model that learns to copy column names can do well on one database and fail on the next.

The main benchmarks tell the story of the field:

• WikiSQL (Zhong et al., 2017): single-table questions over Wikipedia tables. Its single-table query structures are narrower than the multi-table tasks in later benchmarks.
• Spider (Yu et al., 2018): cross-domain, multi-table, complex SQL. It became the standard benchmark for years.
• BIRD (Li et al., 2023): large databases, external knowledge, and more realistic value grounding.
• Spider 2.0 (Lei et al., 2024 preprint): enterprise workflows, real schemas, and agentic settings where the system may need to inspect data and run multiple queries.

The progression from WikiSQL to Spider to BIRD to Spider 2.0 tracks the field's growing ambition. WikiSQL provided a large single-table benchmark with learned sequence-to-sequence baselines. Spider added cross-domain generalization and complex queries. BIRD added large databases and external knowledge. Spider 2.0 added enterprise workflows and agentic settings.

Evaluation has two common modes:

• Exact match: compare a prediction with a gold query under the benchmark's normalization and structural-matching rules. For example, Spider compares parsed clause components as sets. Literal string comparison, illustrated below, is stricter.
• Execution accuracy: execute the generated query and the gold query on a database and compare the result tables. This is closer to the task, but it can reward a wrong query that happens to produce the right answer on a particular database.

Execution accuracy can accept different SQL strings that return the same result. But it has its own failure modes. A query can return the right answer for the wrong reason. A query can be correct on one database instance and wrong on another. Test-suite accuracy addresses this by executing queries against multiple database instances and comparing results. Agreement on a finite test suite for general SQL does not by itself establish equivalence on every relevant database instance.

In practice, a good evaluation combines execution accuracy with manual inspection and with robustness checks on paraphrases and schema variations.

Evaluation metrics can disagree even when two queries mean the same thing to the database. A small execution check separates literal text matching from denotation matching. This demonstration is not an implementation of Spider's structural metric.

The helper trims only leading and trailing whitespace; it does not parse or canonicalize SQL. It deliberately leaves case and quoted literals unchanged. Python row-list equality is appropriate for these queries because each has an explicit ORDER BY; unordered result comparison needs a separate protocol.

SQL is one example of an executable meaning representation. The broader idea is to map language to a formal object that can be run, checked, or interpreted. Execution lets a system compute a result when evaluation terminates and compare that result with an expected outcome. Non-executable representations can also support tasks such as graph matching and information extraction; a mathematical denotation does not itself require an effective executor.

Executable representations include:

• Logical formulas evaluated against a knowledge base or model.
• SQL queries executed against a relational database.
• Regular expressions matched against strings.
• Date and time expressions parsed into calendar objects.
• API calls such as set_alarm(time="07:00").
• Programs or DSL expressions that compute a value or perform an action.
• Planning operators that change the state of a robot or agent.

We can describe the semantics of an executable representation denotationally. We write $[\![m]\!]_{\mathcal{M}}$ for the denotation of representation $m$ in context $\mathcal{M}$. For a logical formula, the denotation is a truth value. For a SQL query, the denotation is a result table. For a program, the context can include its input and initial state; its denotation may describe a resulting value and state, with the chosen semantic model also accounting for failure or nontermination.

Denotational semantics is useful for learning because it lets us compare meanings without comparing strings. Two representations with the same denotation are observationally equivalent in that context for a task that observes only that result. Equivalence across changing databases requires agreement on every relevant instance and observation.

This gives us a powerful training signal. Instead of supervising the parser with gold logical forms, we can supervise it with denotations. The parser produces a representation, the representation is executed, and the result is compared to the correct answer. This is weak supervision. It is attractive because denotations can be cheaper to obtain than gold logical forms. Learning this way can be harder: the latent representation space may be large, and different representations can produce the same denotation.

A parser trained this way may learn a representation that happens to work on the training data but does not generalize. Credit assignment can be difficult because a final-answer mismatch need not identify which part of the representation caused the error.

Executable representations also enable verification and feedback. If a generated SQL query fails to execute, the error message can be used to repair it. If a generated program returns the wrong value, the difference can be used as a reward signal. This is one reason semantic parsing connects naturally to tool use and code generation, which we will explore in Part XLVIII: Tool Use and Agents and Part XLVII: Code Generation.

The feedback loop can be as simple as a retry with the error message prepended, or as complex as a search over candidate repairs. Either way, execution provides a direct signal for repair and learning.

A semantic parser can use an autoregressive language model. Such a parser generates a logical form, SQL query, or program one token at a time. The problem is that a language model can generate invalid output. It can produce unbalanced parentheses, a SQL query that references a nonexistent column, or a logical formula with a type error.

Constrained generation can prevent violations of the constraints it actually encodes and soundly enforces at each decoding step. These can include grammatical, schema, and type constraints. The decoder can preserve prefixes that have grammatical completions. A valid completed output also requires an accepted stopping state; a length-truncated prefix is not a successful parse.

Let $x$ be the input utterance and $y = y_1, y_2, \ldots, y_T$ be the output representation. For a completed variable-length output, let the final token $y_T$ be the end-of-sequence marker, EOS. An autoregressive model factorizes its probability as:

The input $x$ is the utterance, $y_t$ is the output token at step $t$, $y_{<t}$ is the preceding token sequence, and $T$ includes EOS. Without the EOS event, the product describes a prefix probability rather than the probability of stopping there.

At step $t$, the model produces a logit vector $z_t \in \mathbb{R}^{|\mathcal{V}|}$ over the vocabulary $\mathcal{V}$. A grammar-constrained decoder computes a set of allowed tokens:

and masks the logits:

Then it samples or takes the argmax from $\text{softmax}(z'_t)$. To preserve viability, $\mathcal{A}(y_{<t})$ must contain only tokens whose decoded continuation admits some grammatical completion, and the current prefix must already be viable. The allowed set must be nonempty; if all logits are masked, softmax has no normalized distribution and the decoder must report failure. EOS is allowed only after a complete accepted string. These conditions preserve completable prefixes; they do not force termination. For example, a decoder for strings of the form $a^n b$ can keep choosing $a$ indefinitely. A finite output cap must reject such an incomplete result.

The $-\infty$ entries make the probability of disallowed tokens zero after the softmax. The allowed set can depend on the prefix, because different prefixes can have different possible continuations. In a grammar requiring balanced parentheses, an opening parenthesis creates a later closing obligation, and the decoder must track that obligation.

For a context-free grammar $G = (N, \Sigma, R, S)$, $N$ is the set of nonterminals, $\Sigma$ the terminal alphabet, $R$ the production rules, and $S$ the start symbol, as in the earlier grammar chapter. Let $L(G)$ denote the language of complete terminal strings generated by $G$. A prefix $p$ is viable if there exists some suffix $s$ such that $p s \in L(G)$. An incremental parser can compute the allowed next tokens. Possible choices include Earley, LR, and GLR parsing, depending on the grammar and implementation. The parser tracks the set of grammar states consistent with the prefix. The allowed tokens must extend a consistent state toward a productive completion. Merely finding a locally expected terminal is insufficient if its grammar branch can never reach a complete string.

An Earley parser is particularly convenient because it can handle left recursion and ambiguity, and it can report the set of expected terminals at any point. Deterministic LR parsers are often efficient for LR grammars, while Earley and GLR support broader grammar classes. Practical speed depends on the grammar, preprocessing, and implementation. The choice depends on the target language and the latency budget.

This is more subtle than it sounds. A tokenizer may split a grammar terminal into multiple subword tokens, or merge several terminals into one token. The constrained decoder must align the model vocabulary with the grammar. Some systems operate over characters or bytes to avoid this problem. Others precompute a token-level grammar or use a parser that understands subword boundaries. The tokenization issues from Byte Pair Encoding do not disappear when the output is formal.

In practice, the alignment problem is a major source of engineering complexity, and it is easy to get subtly wrong. A decoder that is correct on paper can fail when a keyword is split into two tokens.

Syntax is only the first layer. A SQL query can be syntactically valid and still reference a table that does not exist. A logical formula can be well formed and still have a type error. A program can compile and still be semantically wrong.

Semantic constraints add another layer of masking or checking:

• Schema validity: tables and columns must exist, aliases must be defined, and join conditions must satisfy the application's type and schema policies. SQL joins do not universally require declared foreign keys.
• Type checking: predicates must receive arguments of the right type, and operators must follow the target language's signatures and allowed conversions. Date comparisons need compatible temporal representations.
• Scope and binding: closed sentence outputs have no free variables. Open queries may retain declared answer variables or variables supplied by the evaluation context; unintended free variables are rejected.
• Aggregation rules: HAVING filters aggregate groups, including the single implicit group of an aggregate query without GROUP BY. Aggregate expressions obey the target dialect's rules, including restrictions on their use in WHERE.
• Value grounding: map question mentions to the intended database literals, accounting for case, formatting, and synonyms when needed. A literal absent from the stored rows can still be valid SQL and can correctly produce an empty result.
• Execution checks: for tasks requiring a successful result, reject runtime failures and check the returned result against task-specific expectations.

Execution can supply feedback during text-to-SQL generation or repair. In execution-guided decoding, executing partial candidates can prune faulty continuations. An iterative self-debugging loop can use execution results or error messages to revise a generated candidate.

A schema checker can be thought of as a semantic grammar. It defines which identifiers are in scope and which types are compatible, and the decoder can mask tokens that would violate those constraints.

But execution feedback is not a guarantee of correctness. A query can execute successfully and return the wrong answer. A query can return the right answer for the wrong reason. A repair loop can also overfit to a particular database instance. The system needs semantic checks, not just execution checks.

A system can combine several layers:

• A decoder that enforces its specified grammar on complete accepted outputs.
• A sound schema, scope, and type checker that accepts only candidates satisfying its specified rules.
• An executor that catches runtime errors.
• A result check that applies task-specific plausibility tests.

Constrained generation is powerful, but it is not free.

• Correctness versus coverage: A sound decoder that enforces a grammar and stops in an accepted state guarantees membership in that grammar. Membership does not guarantee the intended answer. If the grammar is too restrictive, it may eliminate the correct answer. If it is too permissive, it may not help.
• Latency: Incremental parsing and masking require work during decoding. Their effect on end-to-end latency depends on implementation, overlap, caching, grammar, and output length, so measure the complete decoder.
• Engineering cost: Grammars, parsers, and schema checkers must be written and maintained. SQL dialects and schema changes can break them.
• Tokenizer mismatch: The model vocabulary and the grammar terminals may not align. This requires careful engineering.
• Over-constraining reasoning: Prompt and output-format choices can change the generated intermediate reasoning steps. Evaluate their effect on the actual task; a system may allow intermediate reasoning and constrain only the final structured artifact.

The practical lesson is to use constraints where they add value:

• Constrain the final output format.
• Validate against the schema.
• Execute when possible.
• Do not assume that syntactic validity is semantic correctness.

It is also worth measuring the cost of constraints. A grammar that reduces invalid outputs by half but doubles latency may not be worth it for an interactive application. The right tradeoff depends on the latency budget, the error tolerance, and the cost of a wrong answer.

Let us make the differences concrete with a small schema and a few sentences.

The three utterances below highlight different strengths of the representation families: quantifier scope in logic, shared participants in AMR, and aggregation in SQL. They are separate examples rather than equivalent encodings of one sentence.

Take the sentence:

Every student reads a book.

A surface-scope logical form is:

An inverse-scope logical form is:

Both are consistent with the English string. The first says each student may read a different book. The second says there is one book that every student reads. A semantic parser that outputs one fully resolved, reading-specific logical form has made a choice. A system that needs to reason about ambiguity should represent both readings or defer the choice.

The executable example below constructs the surface-scope reading explicitly. A parser must resolve or retain the ambiguity according to its application; word order alone does not determine the intended scope.

Now take:

The boy wants to go.

An AMR graph is:

(w / want-01
   :ARG0 (b / boy)
   :ARG1 (g / go-02
            :ARG0 b))

The graph contains a wanting node w, whose wanter is a boy b, and whose desired event is represented by a go-02 node g with the same boy as the understood goer. It does not assert that the boy actually goes. The reentrancy is explicit. The graph does not encode the difference between "the boy" and "a boy" in the same way first-order logic does. It abstracts over that distinction.

This is a feature for paraphrase stability: "The boy wants to go" and "A boy wants to go" receive very similar graphs, which is desirable if the task is about events and participants rather than definiteness.

Suppose we have this schema:

departments(department_id, name)
students(student_id, name, department_id)
enrollments(student_id, course_id)

And this question:

Which departments have more than two enrolled students?

A correct SQL query is:

SELECT d.name
FROM departments AS d
JOIN students AS s
  ON s.department_id = d.department_id
JOIN enrollments AS e
  ON e.student_id = s.student_id
GROUP BY d.department_id, d.name
HAVING COUNT(DISTINCT e.student_id) > 2
ORDER BY d.name;

The query joins the three tables, groups by department, counts distinct enrolled students, and filters groups with more than two students. The DISTINCT matters if a student can appear in multiple enrollment rows. Without it, the count could overcount.

The query is not a flat lookup. Under the shown schema, it uses the department and enrollment relationships to identify which students to count. The graph displays these information dependencies; equivalent SQL need not use this exact join plan.

This example shows why text-to-SQL is not just translation. The question must be grounded in the schema, with its relationships and distinct-student count expressed correctly. The displayed solution uses joins and aggregation; equivalent SQL can use other structures. A fluent English paraphrase of the query is not enough.

It must also decide whether the count refers to distinct students or enrollment rows. Inner joins discard departments without matches before aggregation. Left joins can preserve them as zero-count groups, but this example's HAVING COUNT(DISTINCT e.student_id) > 2 excludes those groups under either join choice.

We will build three small pieces:

1. A small lambda-term evaluator to show compositional semantics.
2. An AMR graph representation and a readable edge summary.
3. A toy text-to-SQL pipeline with SQLite and a grammar mask for constrained decoding.

The code is deliberately small. The goal is to make the mechanisms visible, not to build a production semantic parser.

Each piece corresponds to one of the representation families discussed above. The examples use the Python standard library, NumPy, Matplotlib, and the shared book plotting helper. They run locally on small explicit data and do not download model checkpoints.

We start with abstract syntax for variables, constants, application, and lambda abstraction. The intended types were explained above, but this evaluator does not implement a type checker; invalid combinations may therefore fail at runtime.

It returns False: Bob is a student, and after removing his reading there is no book y such that (bob, y) is in the reduced relation. This is the core of compositional semantics. The sentence meaning is a function of the lexical meanings and the way they combine. The quantifier is not a special case hard-coded into the sentence. It is a function that takes predicates as arguments.

Next, we represent a small AMR graph as a set of nodes and labeled edges. This toy treats a string target present in nodes as a node reference and any other string target as a literal display value.

The output contains the triples ('want-01', 'ARG0', 'boy'), ('want-01', 'ARG1', 'go-02'), and ('go-02', 'ARG0', 'boy'). These triples show the predicate-argument structure directly. The edge ("g", "ARG0", "b") is the reentrancy: the goer is the same boy who wants to go. In a larger graph, this structure can be much richer, but the basic representation is the same.

The amr_triples function returns a list of edge summaries using concept labels. It discards node identities, so two different nodes with the same concept label would become indistinguishable. This is a teaching display, not a lossless AMR serialization or a Smatch implementation; Smatch preserves variables until the node-alignment step.

Now we build a tiny database and a toy text-to-SQL converter. The converter recognizes one question pattern and produces a SQL query with a parameter for the threshold.

The database is small enough to inspect by eye, which makes it easy to verify the result of the query.

On this tiny database, only Computer Science has more than two enrolled students. The query is valid SQL and its denotation is a one-row table. An execution-based check judges that result against the intended answer.

The query also illustrates schema linking in a simplified form. The word "departments" maps to the departments table, "students" to the students table, "enrolled" to the enrollments table, and "more than two" to the numeric threshold. A learned parser may predict these mappings; this example supplies them explicitly.

The following tree shows one reading of "Every student reads a book". It is a simplified composition tree, not a full syntactic derivation. The point is to show how the quantifier, verb, and object phrase combine.

The root is a sentence of type t. The subject quantifier consumes the verb-phrase predicate. To construct that predicate, fix a subject $x$ and apply the object quantifier to $\lambda y.\,\text{read}(x,y)$. Then abstract over $x$. The diagram groups the lexical components; its lower edges do not stand for direct function application between the verb and the object quantifier.

The diagram shows the components of the scoped reading. The object quantifier consumes a predicate of possible books for each fixed subject; abstracting over the subject produces the verb phrase. The subject quantifier then consumes that predicate, yielding a truth value.

A full derivation would include more nodes, such as the determiner and noun inside each noun phrase, and would annotate each node with its type. The simplified version is enough to show the shape of the composition.

Finally, we build a tiny binary mask for SQL decoding. Rows are decoding steps. Columns are vocabulary tokens. A cell is 1 if the token is allowed at that step.

The mask is a simplified grammar. It does not allow joins or other query forms, but it does include one fixed filter (WHERE age). This separate syntax illustration uses a toy students/age vocabulary rather than the preceding department database schema. It demonstrates the token-masking mechanism used in a full grammar-constrained decoder.

At step 1, only SELECT is allowed. At step 2, the grammar allows name or department. The dangerous token DROP is never allowed in this simple grammar. The mask guarantees syntactic validity for this toy language. It does not guarantee that the resulting query is semantically correct for the user's question. Semantic correctness depends on matching the intended question. Schema validation, type checking, and execution feedback can help detect errors, but they do not by themselves guarantee the intended meaning.

The heatmap marks the allowed tokens in each row. In a full decoder, columns correspond to model-vocabulary items and the allowed set depends on the current prefix; its size and density depend on the grammar and prefix.

The logical-form examples map language to logic, but still require a choice of representation. A practical difficulty is choosing a representation that captures what the task needs without capturing everything the sentence could mean. A parser targeting one fully scoped first-order sentence commits to a reading; an application can instead retain alternatives or underspecification. AMR can represent predicate-argument structure and reentrancy, but it deliberately abstracts away from scope and word order. SQL offers executable relational computations whose behavior depends on dialects, NULL semantics, and schema design. The representations discussed here can abstract away from linguistic distinctions. Whether a discarded distinction matters depends on the task and domain; a representation can preserve all distinctions stipulated by a restricted task.

A useful habit is to ask, for any representation, what it cannot say. If a task requires distinguishing inputs that map to the same object, no downstream system using only that object can answer correctly on all such inputs. If correct and incorrect alternatives map to the same object, a check using only that representation cannot tell them apart.

Evaluation is another limitation. Single-reference matching can reject valid alternatives; the outcome depends on the benchmark's normalization and equivalence rules. Execution accuracy is closer to the task, but a wrong query can return the right answer on a particular database. Smatch measures graph overlap, not truth conditions. Benchmark contamination, schema drift, and dialect differences can make a model look better or worse than it is. A semantic parser that scores well on Spider may still fail on your production schema because your column names, value formats, and joins are different. The lesson is to evaluate at multiple levels: validity, denotation, robustness to paraphrase, and behavior on unseen schemas. The evaluation ideas from Part LIII: Evaluation Fundamentals apply directly here.

It is also useful to evaluate the parser as a component, not just as a standalone model. A parser that is 90 percent accurate on individual queries may be much less accurate on a workflow that requires several queries in sequence.

Semantic parsing gives language models a way to act through structured interfaces whose outputs can be checked. Applications include databases, calendars, robots, spreadsheets, and APIs. It also connects natural language with program synthesis. When a model generates a SQL query, a function call, or a small program from a request, it is doing a kind of semantic parsing. Constrained generation can enforce a chosen output language; task correctness still needs semantic checks. A deployed interface can combine those checks with execution feedback and human review where the application calls for it. In the next chapters, we will see how these ideas connect to coreference, discourse, and dialogue, where context beyond a single sentence can matter.

The broader lesson is that meaning representations are interfaces. They are where linguistic meaning meets software behavior, and their design constrains which distinctions can pass from linguistic interpretation to downstream software.

The key parameters for the code in this section are:

• domain: The finite set of entities used to evaluate quantifiers. It must include the people and books so that every and a can range over them.
• students, books, reads, likes: The lexical denotations as Python sets and relations. Changing a relation can change the truth value of the composed formula without changing its syntactic form.
• constants: The mapping from constant names to Python values, including predicates and the generalized quantifiers every and a.
• threshold: The integer extracted from the number word in the question and passed as a SQL parameter to the HAVING clause.
• vocab and allowed_sets: The decoding vocabulary and the per-step grammar constraints used to build the binary mask.
• mask: The binary allowed-token matrix, with one row per decoding step and one column per vocabulary token.

Semantic parsing maps natural language to formal meaning representations. Logical forms use predicates, quantifiers, and lambda calculus to make composition explicit. AMR uses graphs and PropBank-style roles to represent predicate-argument structure and reentrancy. Text-to-SQL maps questions to executable database queries. In the department example, schema linking and query structure determine which students are counted. Denotations are defined by semantics; execution can compute results for validation and weak supervision. Constrained generation can enforce encoded grammar and semantic policies when the integration is sound and the output reaches an accepted stopping state, but syntactic validity does not guarantee the intended meaning. The best representation depends on the task, and the best evaluation checks denotations, validity, and robustness rather than surface strings alone.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about semantic parsing and meaning representations.