Natural language understanding: the pipeline & CFG parsing

Why language is AI-hard

Understanding language needs essentially *all* of AI at once. Luger frames the difficulty as three issues: knowledge (a sentence describes relationships in a complex world, so understanding it needs vast background knowledge — "tenure-track" implies a faculty position), patterns (language is not random; sounds, words, and sentences follow statistical regularities and constrained structures), and agency (utterances are *purposive* — produced by agents with goals, so understanding means modeling speaker intent, not just decoding symbols). That last point is why "Do you have a watch?" expects the *time*, not "Yes."

Analysis is layered across seven levels — prosody, phonology, morphology, syntax, semantics, pragmatics, and world knowledge. Syntax is the most successfully automated level, because it is the most formally tractable; meaning and pragmatics are far harder.

The three-stage NLU pipeline

1. Parsing — analyze syntactic structure with grammar rules + morphology, producing a parse tree that exposes the major relations (subject-verb, verb-object, noun-modifier).
2. Semantic interpretation — combine the parse tree with word meanings and case roles to build an internal semantic representation (e.g. a conceptual graph), checking semantic consistency and filling defaults (the default instrument of "kissing" is "lips").
3. World-knowledge expansion — add relevant background knowledge from the knowledge base, producing the full contextual meaning that drives applications (question answering, database querying, translation).

These stages mirror the layers, and in practice they interleave — incomplete semantics can guide parsing, and world knowledge can resolve a syntactic ambiguity.

Context-free grammars and parse trees

A context-free grammar (CFG) is a set of rewrite rules with a single nonterminal on the left, e.g.

S  -> NP VP        Det -> the | a
NP -> Det N        N   -> dog | cat
VP -> V            V   -> runs | sleeps

A legal sentence is any string of terminals derivable from the start symbol $S$. The derivation forms a parse tree: interior nodes are nonterminals, each node-plus-children is one rule application, leaves are terminals, and $S$ is the root. The tree makes structure explicit — the verb-object relation, for instance, is visible as a verb and its noun-phrase sibling inside a VP.

Two parsing directions. A top-down parser starts at $S$ and tries to build a tree whose leaves match the input (natural for *predicting* the next token). A bottom-up parser starts at the words and looks for reductions up to $S$ (better for ambiguous grammars). The Earley parser is a chart parser that uses dynamic programming — dotted rules plus three procedures, Predictor / Scanner / Completer — to avoid recomputing partial parses; the Completer is the memoization step that makes it efficient.

Worked example — recursive-descent recognition

The Python exercise below is a top-down recognizer: to parse $S$, parse an $NP$ then a $VP$; to parse $NP$, parse a $Det$ then an $N$; terminals are checked against a tiny lexicon. On the dog runs it succeeds and prints the parse tree (S (NP the dog) (VP runs)); on dog the runs it fails (a noun where a determiner was required) and prints REJECT.

Why a CFG is not enough

English needs constraints a CFG cannot express — number agreement ("the dogs *bite*," not "the dogs *bites*"), semantic consistency ("Man bites dog" is grammatical but the case frame for *bite* expects a dog agent), and more. Formally, on the Chomsky hierarchy (regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable), English sits at roughly context-sensitive. Rather than pay the rule-explosion of context-sensitive grammars, practical systems use Augmented Transition Networks (ATNs): context-free rules for structure, with *procedural tests on the arcs* (e.g. "check the number feature matches") to enforce the context-sensitive constraints and build the frames a semantic interpreter consumes.