Context-free grammars for syntax

A syntactic CFG differs from a morphological CFG in its intended terminals and variables, not in its formal definition. Words are terminals; categories such as $S$, $NP$, and $VP$ are variables. So what changes when we move from words to sentences? We begin with a small grammar and then ask what it can and cannot represent.

A small grammar

Consider the following fragment:

\[ \begin{aligned} S &\rightarrow NP\;VP \\ NP &\rightarrow D\;N \mid D\;N\;PP \\ VP &\rightarrow V\;NP \mid V\;NP\;PP \\ PP &\rightarrow P\;NP \\ D &\rightarrow \text{the}\mid\text{a} \\ N &\rightarrow \text{greyhound}\mid\text{person}\mid\text{telescope} \\ V &\rightarrow \text{saw}\mid\text{loved} \\ P &\rightarrow \text{with}. \end{aligned} \]

The Earley parser can use these rules directly. CKY first converts the ternary rules to CNF.

Treebanks

A treebank pairs sentences with syntactic analyses. The Penn Treebank, for instance, uses bracketed phrase structure with labels such as S, NP, VP, and PP (Marcus et al. 1993). These trees play the role that CELEX trees played for morphology: they supply rule occurrences for supervised PCFG estimation and reference structures for parser evaluation.

This parallel should not be taken too far. Treebank labels encode an annotation scheme, and different schemes may assign different structures to the same sentence. A parser learned from a treebank models those annotation decisions along with the language.

Ambiguity

The grammar above allows two structures for the greyhound saw a person with a telescope. The PP may attach inside the object NP, in which case the person has the telescope, or it may attach to VP, in which case the telescope is the instrument of seeing.

Both analyses have the same terminal yield. Thus, recognition alone cannot distinguish them; the parser must retain backpointers, and a probabilistic model must rank or sum the resulting trees.

Question

Would adding a rule for each attachment decision remove the ambiguity from the sentence?

Answer

Only if the added categories encode information that forces one attachment in this context. Merely adding more rules usually adds analyses. A PCFG can prefer one existing analysis, but it does not remove the other unless its probability is zero.

Two CFG limitations

Why might the small grammar still be inadequate even if it recognizes the examples we give it? We need to distinguish weak generative capacity from structural adequacy. Weak generative capacity concerns the set of terminal strings a grammar generates. Structural adequacy concerns whether the grammar states the intended dependencies and assigns the intended trees.

Filler-gap dependencies illustrate the second problem. A CFG can thread a finite inventory of slash categories—such as $S/NP$ and $VP/NP$—through a tree. But the formalism treats each slash category as an atomic variable. The relationship between $S$ and $S/NP$ is visible to the analyst, not to the CFG definition, so the grammar repeats related rules across the category inventory.

Swiss German cross-serial dependencies illustrate the first problem. In the relevant subordinate clauses, sequences of noun phrases correspond, in the same order, to sequences of verbs. Shieber showed that, after restricting the language with regular filters and applying a homomorphism, the pattern yields a known non-context-free language (Shieber 1985). We will work through the closure-transfer argument one step at a time.

Let $L_{SG}$ be the relevant Swiss German string language. The regular filter keeps a controlled clause shape with a block of dative noun phrases, a block of accusative noun phrases, and corresponding blocks of dative-selecting and accusative-selecting verbs. Fixed words and irrelevant alternatives are excluded. A homomorphism then erases the fixed material and maps the four relevant lexical classes to $a$, $b$, $c$, and $d$. The surviving abstract pattern has the form

\[ L_{cross}=\{a^mb^nc^md^n\mid m,n\geq1\}. \]

The first and third block lengths match, as do the second and fourth. This is the cross-serial requirement.

We first verify that $L_{cross}$ is not context-free. Assume it has context-free pumping length $p$, and choose

\[w=a^pb^pc^pd^p.\]

In any permitted decomposition $w=uvxyz$, the window $vxy$ has length at most $p$. It can thus touch at most two adjacent blocks. But the matched block pairs are nonadjacent: $a$ is matched with $c$, and $b$ is matched with $d$. Pumping $v$ and $y$ down changes at least one touched block while leaving its matched block unchanged. The resulting string violates either the $a$–$c$ equality or the $b$–$d$ equality. Thus, $L_{cross}$ is not context-free.

Now assume for contradiction that $L_{SG}$ is context-free. Context-free languages are closed under intersection with a regular language, so applying the filter would preserve context-freeness. They are also closed under homomorphism: replace every terminal $x$ in a CFG by the fixed string $h(x)$, introducing auxiliary variables if needed, and derivations map to their homomorphic yields in both directions. Thus, the filtered and mapped language $L_{cross}$ would have to be context-free. We have just proved that it is not. The assumption that $L_{SG}$ is context-free must thus be false.

This result depends on more than the presence of long dependencies. It depends on isolating two unbounded, independently varying counts and showing that a CFG would have to preserve both cross-serial equalities.

Question

Can a sufficiently large but finite set of slash categories make a CFG generate a non-context-free string language?

Answer

No. Adding finitely many variables and rules still leaves us with a CFG. Slash categories may improve the analysis of dependencies whose string patterns are context-free, but they cannot change the weak generative capacity of the formalism.

The next section abstracts away from the grammar formalism and asks how a parser follows from a set of inference rules. That abstraction will let us compare CFG parsing with the more expressive systems introduced afterward.

References

Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. “Building a Large Annotated Corpus of English: The Penn Treebank.” Computational Linguistics (Cambridge, MA) 19 (2): 313–30. https://aclanthology.org/J93-2004.

Shieber, Stuart M. 1985. “Evidence Against the Context-Freeness of Natural Language.” Linguistics and Philosophy 8 (3): 333–43. https://doi.org/10.1007/BF00630917.

--- title: Context-free grammars for syntax bibliography: ../references.bib --- A syntactic CFG differs from a morphological CFG in its intended terminals and variables, not in its formal definition. Words are terminals; categories such as $S$, $NP$, and $VP$ are variables. So what changes when we move from words to sentences? We begin with a small grammar and then ask what it can and cannot represent. ## A small grammar Consider the following fragment: $$ \begin{aligned} S &\rightarrow NP\;VP \\ NP &\rightarrow D\;N \mid D\;N\;PP \\ VP &\rightarrow V\;NP \mid V\;NP\;PP \\ PP &\rightarrow P\;NP \\ D &\rightarrow \text{the}\mid\text{a} \\ N &\rightarrow \text{greyhound}\mid\text{person}\mid\text{telescope} \\ V &\rightarrow \text{saw}\mid\text{loved} \\ P &\rightarrow \text{with}. \end{aligned} $$ The Earley parser can use these rules directly. CKY first converts the ternary rules to CNF. ## Treebanks A *treebank* pairs sentences with syntactic analyses. The Penn Treebank, for instance, uses bracketed phrase structure with labels such as `S`, `NP`, `VP`, and `PP` [@marcus_building_1993]. These trees play the role that CELEX trees played for morphology: they supply rule occurrences for supervised PCFG estimation and reference structures for parser evaluation. This parallel should not be taken too far. Treebank labels encode an annotation scheme, and different schemes may assign different structures to the same sentence. A parser learned from a treebank models those annotation decisions along with the language. ## Ambiguity The grammar above allows two structures for *the greyhound saw a person with a telescope*. The `PP` may attach inside the object `NP`, in which case the person has the telescope, or it may attach to `VP`, in which case the telescope is the instrument of seeing. Both analyses have the same terminal yield. Thus, recognition alone cannot distinguish them; the parser must retain backpointers, and a probabilistic model must rank or sum the resulting trees. ::: {.callout-caution} ## Question Would adding a rule for each attachment decision remove the ambiguity from the sentence? ::: ::: {.callout-tip collapse=true} ## Answer Only if the added categories encode information that forces one attachment in this context. Merely adding more rules usually adds analyses. A PCFG can prefer one existing analysis, but it does not remove the other unless its probability is zero. ::: ## Two CFG limitations Why might the small grammar still be inadequate even if it recognizes the examples we give it? We need to distinguish **weak generative capacity** from **structural adequacy**. Weak generative capacity concerns the set of terminal strings a grammar generates. Structural adequacy concerns whether the grammar states the intended dependencies and assigns the intended trees. Filler-gap dependencies illustrate the second problem. A CFG can thread a finite inventory of slash categories—such as $S/NP$ and $VP/NP$—through a tree. But the formalism treats each slash category as an atomic variable. The relationship between $S$ and $S/NP$ is visible to the analyst, not to the CFG definition, so the grammar repeats related rules across the category inventory. Swiss German cross-serial dependencies illustrate the first problem. In the relevant subordinate clauses, sequences of noun phrases correspond, in the same order, to sequences of verbs. Shieber showed that, after restricting the language with regular filters and applying a homomorphism, the pattern yields a known non-context-free language [@shieber1985evidence]. We will work through the **closure-transfer argument** one step at a time. Let $L_{SG}$ be the relevant Swiss German string language. The regular filter keeps a controlled clause shape with a block of dative noun phrases, a block of accusative noun phrases, and corresponding blocks of dative-selecting and accusative-selecting verbs. Fixed words and irrelevant alternatives are excluded. A homomorphism then erases the fixed material and maps the four relevant lexical classes to $a$, $b$, $c$, and $d$. The surviving abstract pattern has the form $$ L_{cross}=\{a^mb^nc^md^n\mid m,n\geq1\}. $$ The first and third block lengths match, as do the second and fourth. This is the cross-serial requirement. We first verify that $L_{cross}$ is not context-free. Assume it has context-free pumping length $p$, and choose $$w=a^pb^pc^pd^p.$$ In any permitted decomposition $w=uvxyz$, the window $vxy$ has length at most $p$. It can thus touch at most two adjacent blocks. But the matched block pairs are nonadjacent: $a$ is matched with $c$, and $b$ is matched with $d$. Pumping $v$ and $y$ down changes at least one touched block while leaving its matched block unchanged. The resulting string violates either the $a$–$c$ equality or the $b$–$d$ equality. Thus, $L_{cross}$ is not context-free. Now assume for contradiction that $L_{SG}$ is context-free. Context-free languages are closed under intersection with a regular language, so applying the filter would preserve context-freeness. They are also closed under homomorphism: replace every terminal $x$ in a CFG by the fixed string $h(x)$, introducing auxiliary variables if needed, and derivations map to their homomorphic yields in both directions. Thus, the filtered and mapped language $L_{cross}$ would have to be context-free. We have just proved that it is not. The assumption that $L_{SG}$ is context-free must thus be false. This result depends on more than the presence of long dependencies. It depends on isolating two unbounded, independently varying counts and showing that a CFG would have to preserve both cross-serial equalities. ::: {.callout-caution} ## Question Can a sufficiently large but finite set of slash categories make a CFG generate a non-context-free string language? ::: ::: {.callout-tip collapse=true} ## Answer No. Adding finitely many variables and rules still leaves us with a CFG. Slash categories may improve the analysis of dependencies whose string patterns are context-free, but they cannot change the weak generative capacity of the formalism. ::: The next section abstracts away from the grammar formalism and asks how a parser follows from a set of inference rules. That abstraction will let us compare CFG parsing with the more expressive systems introduced afterward.