Grammars and Constituency Structure › Context-Free Grammars

A context-free grammar is a finite set of rules that recursively defines which strings belong to a language and how those strings are structured. The formal definition is compact.

The phrase "regardless of context" is the key. A context-sensitive rule could say "rewrite A as a nonempty sequence $\alpha$ only when it appears between B and C." A context-free rule cannot require that surrounding context. For CFGs, we can use the span-based parsing method developed below. The bare rule $S \to NP\ VP$ does not encode subject-verb agreement because its categories contain no number features. A CFG can enforce finite agreement distinctions by refining these categories. Context-free does not mean that a grammar cannot constrain lexical environments; it means that each production applies to its left-hand-side category without inspecting surrounding symbols. The context-free restriction is therefore both a simplification and a limitation.

Here is a small grammar for a fragment of English:

The vertical bar means "or". So $NP$ can be either $Det\ N$ or $NP\ PP$. The symbols S, NP, VP, PP, Det, N, V, and P are nonterminals. The words "the", "a", "dog", "cat", "telescope", "chased", and "with" are terminals. The grammar is tiny, but it already supports recursion. An NP can contain a PP, and that PP contains another NP. A VP can contain a PP, and that PP contains another NP. This is enough to generate an unbounded family of structures from a finite set of rules.

A derivation shows how the start symbol rewrites step by step into a string of terminals. For example:

Continuing, we can derive:

At each step, we choose a nonterminal and replace it using one of its rules. The sequence of rewrites is a derivation. The final string contains only terminals. Different choices about which nonterminal to rewrite next can produce different derivations of the same string. That is why derivations and parse trees are not in one-to-one correspondence unless we fix a convention, such as always rewriting the leftmost nonterminal first. The tree, rather than the linear derivation, is usually the cleaner object for representing constituency.

The language generated by a grammar is the set of all terminal strings that can be derived from the start symbol:

The star on $\Rightarrow^*$ means "derives in zero or more steps." A string is grammatical with respect to $G$ if it belongs to $L(G)$. A string is ungrammatical if it does not. This notion of grammaticality is relative to a grammar. A sentence that is ungrammatical under one grammar may be grammatical under another, richer grammar. The formal definition does not tell us whether the grammar is linguistically correct. It only tells us what the grammar generates.

This definition is abstract, and that is deliberate. A CFG does not say how to find a derivation. It only defines which derivations exist. A parser is the algorithm that searches for those derivations. The grammar is the specification; the parser is the implementation, a distinction also illustrated in the NLTK book's syntax chapter. This separation is useful because the same grammar can be used by many parsers, and the same parser can be used with many grammars. It also clarifies what a parsing failure means. If a parser fails, either the sentence is outside the grammar's language, or the parser failed to find a derivation that exists. Those are different problems.

Derivations are linear sequences of rewrites. Parse trees are the same information in hierarchical form. The tree makes constituency visible. It also removes the irrelevant order in which independent rewrites happened. Two derivations that differ only in the order of rewriting unrelated nonterminals can correspond to the same tree.

For the sentence "the dog chased the cat", one parse tree has the following bracketed form:

(S
  (NP (Det the) (N dog))
  (VP
    (V chased)
    (NP (Det the) (N cat))))

The same tree can be written as a bracketed string:

[S [NP [Det the] [N dog]] [VP [V chased] [NP [Det the] [N cat]]]]

Both notations say the same thing. The sentence splits into a subject NP and a predicate VP. The subject NP splits into a determiner and a noun. The VP splits into a verb and an object NP. The object NP splits into a determiner and a noun. Each local split corresponds to a grammar rule. The root rule is $S \to NP\ VP$. The subject rule is $NP \to Det\ N$. The predicate rule is $VP \to V\ NP$. The object rule is another $NP \to Det\ N$.

The leaves are the tokens. The internal nodes are constituents. The root S dominates the whole sentence. The NP "the dog" dominates the tokens "the" and "dog". The VP dominates "chased the cat". This is the sense in which a CFG captures constituency: every nonterminal node corresponds to a span, and the rules determine how spans can combine. The tree is not a decoration added after parsing. It is the object that the grammar licenses, and the yield is the sentence that the tree derives.

CFGs are more powerful than regular expressions in an important way. A regular language can be recognized by a finite-state automaton, which has no memory beyond a finite set of states. A CFG can generate languages with unbounded nested structure. The difference is not about the number of rules. It is about the kind of memory the formalism can use. A finite-state automaton has a fixed amount of memory encoded in its states. A CFG can use recursion to keep track of nested structure without a fixed bound.

The classic example is:

This grammar generates strings like $ab$, $aabb$, $aaabbb$, and so on. The language is $\{a^n b^n : n \ge 0\}$. No finite-state automaton can recognize this language, because it would need to count arbitrarily many $a$'s and then check that the same number of $b$'s follow. A CFG does it with recursion. Each recursive expansion of $S$ adds one $a$ on the left and one $b$ on the right, so the two counts stay synchronized. The grammar does not count in the arithmetic sense. It encodes the matching dependency in the recursive structure itself.

Natural language has similar nested dependencies. Relative clauses can nest:

the cat that chased the rat that ate the cheese

The phrase "that chased the rat that ate the cheese" modifies "cat", and inside it another relative clause modifies "rat". Each relative clause can contain another. In principle, the nesting can continue indefinitely. A CFG expresses this recursive phrase analysis directly. The displayed right-branching chain alone does not prove that its string language is nonregular: a regular grammar can also generate unbounded right-branching sequences. The earlier $a^n b^n$ example establishes the formal separation by requiring an unbounded match between two counts. Tree depth and the class of generated strings are different questions.

This does not mean that every aspect of natural language is context-free. It means that context-free recursion is a useful and surprisingly powerful approximation. Later we will see where that approximation strains. For now, the important point is that CFGs give us a way to describe nested structure without enumerating every possible depth. A finite grammar can describe an infinite set of nested sentences.