Context-Free Grammars and Constituency Parsing

Greek sýntaxis, “setting out together, arrangement”: the way words are arranged together.

Assigning a syntactic structure to a sentence. Uses: grammar checking (unparsable sentences may be ungrammatical), an intermediate representation for semantic analysis, and text analysis in data-science applications that model relations between sentence elements.

The idea that groups of words can behave as single units (constituents), e.g. noun phrases.

The whole sequence appears in the same syntactic environments as other noun phrases (e.g. before a verb: “three parties from Brooklyn arrive”), while its individual words can’t (*from arrive, *the is).

Phrase-structure grammars; the formalism is equivalent to Backus-Naur form (BNF). The idea of constituent structure goes back to Wundt (1900); it was formalized by Chomsky (1956) and independently by Backus (1959).

A set of rules (productions) saying how symbols can be grouped and ordered (e.g. NP → Det Nominal, Nominal → Noun | Nominal Noun) and a lexicon of words and symbols (Det → a, Noun → flight).

Terminals correspond to words (“the”, “flight”); the lexicon introduces them. Non-terminals are abstractions over terminals (NP, VP, Nominal). A rule has one non-terminal on the left and an ordered list of terminals and non-terminals on the right.

The sequence of rule expansions that produces a string from a non-terminal (NP → Det Nominal → Det Noun → a flight), usually shown as a parse tree with the root at the top.

A node dominates all nodes below it in the tree; it immediately dominates its direct children (NP immediately dominates Det and Nom).

The set of strings derivable from the designated start symbol, usually S (“sentence”).

S → NP VP; NP → Pronoun | Proper-Noun | Det Nominal; Nominal → Nominal Noun | Noun; VP → Verb | Verb NP | Verb NP PP | Verb PP; PP → Preposition NP.

[S [NP [Pro I]] [VP [V prefer] [NP [Det a] [Nom [Nom [N morning]] [N flight]]]]]

Grammatical sentences can be derived by the grammar (they are in its formal language); ungrammatical ones cannot. This hard in/out line only simplifies natural language, where acceptability often depends on context.

In linguistics, using formal languages to model natural languages: the language is the set of sentences “generated” by the grammar (a different sense of “generate” than LLM text generation).

A 4-tuple \((N, \Sigma, R, S)\): non-terminals \(N\), terminals \(\Sigma\) (disjoint from \(N\)), rules \(R\) of the form \(A \to \beta\) with \(A \in N\) and \(\beta \in (\Sigma \cup N)^*\), and a start symbol \(S \in N\).

If \(A \to \beta \in R\), then \(\alpha A \gamma \Rightarrow \alpha\beta\gamma\). Derivation (\(\Rightarrow^*\)) is a chain of direct derivations, and \(L_G = \{w \mid w \in \Sigma^*, S \Rightarrow^* w\}\).

A corpus in which every sentence is annotated with a parse tree. Usually a parser is run over each sentence and linguists hand-correct the output (e.g. the Penn Treebank for English, Arabic, Chinese).

The CFG rules can be read off the parsed sentences. The Penn Treebank grammar is very flat, giving thousands of rules, e.g. separate VP rules for every number and arrangement of PPs and arguments.

Strongly equivalent grammars generate the same strings and assign the same phrase structure to each (up to renaming non-terminals); weakly equivalent grammars generate the same strings but assign different structures.

An ε-free grammar in which every rule is A → B C (two non-terminals) or A → a (one terminal). CNF grammars are binary branching. Any CFG can be converted into a weakly equivalent CNF grammar.

Introduce a new non-terminal: A → B X and X → C D.

Generating a potentially infinite sequence with a rule of the form A → A B. Instead of VP → VBD NP PP, VP → VBD NP PP PP, … one can write VP → VBD NP PP and VP → VP PP.

When a grammar can assign more than one parse to a sentence.

PP-attachment: in my pajamas can attach inside the NP headed by elephant (the elephant wears the pajamas) or to the VP headed by shot (the shooter wears them).

NP attachment	shot [NP an elephant in my pajamas]
VP attachment	[VP shot an elephant] in my pajamas

A constituent can attach to the tree at more than one place. E.g. in “We saw the Eiffel Tower flying to Paris”, the gerundive VP flying to Paris can belong to a clause whose subject is the Eiffel Tower, or modify saw.

Ambiguity in what a conjunction conjoins: old men and women = [old [men and women]] or [[old men] and women].

Real sentences contain many grammatically valid but semantically unreasonable parses, combining attachment and coordination ambiguities; a parser must handle them efficiently (CKY) and choose the right one (syntactic disambiguation).

Because rules are context-free, once a constituent has been found over a span it can be recorded and reused in any larger derivation, rather than reanalyzed. Such table-based methods are also called chart parsing.

Chomsky normal form (rules A → B C or A → w).

(1) Keep conforming rules; (2) replace terminals inside longer rules with dummy non-terminals (INF-VP → to VP becomes INF-VP → TO VP, TO → to); (3) eliminate unit productions (A → B) by rewriting with the non-unit rules they lead to; (4) binarize long rules with new non-terminals (S → Aux NP VP becomes S → X1 VP, X1 → Aux NP).

Rules with a single non-terminal on the right (Nominal → Noun). Eliminating them flattens the grammar and promotes terminals to high levels, e.g. verbs become both VPs and Ss (S → book | include | prefer).

The set of non-terminals for all constituents spanning positions \(i\) to \(j\). Indices point at the gaps between words (0 Book 1 the 2 flight 3 …), called fenceposts; the whole sentence is cell \([0, n]\).

Since every constituent has two daughters, for each split point \(k\) with \(i < k < j\), combine an entry B in \([i, k]\) (to the left, along row \(i\)) with an entry C in \([k, j]\) (below, along column \(j\)) whenever the grammar has A → B C, and add A.

Column by column from left to right, each column from bottom to top, so the cells to the left and below that a cell depends on are already filled. This also mirrors processing words one at a time.

	Book	the	flight	through	Houston
0	S, VP, Verb, Nominal, Noun		S, VP, X2		S, VP, X2 (3 parses)
1		Det	NP		NP
2			Nominal, Noun		Nominal
3				Prep	PP
4					NP, ProperNoun

Row = start position \(i\), column = end word; empty cells hold no constituent.

There are alternative parses: the PP through Houston modifies the flight, modifies the booking (VP → VP PP), or is the second argument of the original VP → Verb NP PP (now X2 PP).

No, a recognizer: it tells whether an S spans [0, n]. To parse, store with each non-terminal backpointers to the cells it came from and allow multiple copies of a non-terminal per cell; then the table contains all parses.

Returned trees don’t match the original grammar. Binarization can be undone by deleting dummy non-terminals and promoting their daughters; unit productions are easier to handle by modifying CKY itself.

CKY enumerates all parses but doesn’t say which is correct. A neural classifier scores each labeled span, and a modified CKY combines span scores to find the best-scoring tree (“neural CKY”).

It doesn’t use a hand-written grammar to constrain which constituents combine; it relies on learned span representations to encode likely combinations.

Run the tokens through a pretrained model like BERT, map subwords to words (e.g. use the first subword), optionally add transformer layers, giving one output per word.

Split each word output into a leftward and a rightward half, representing fencepost endpoints; the span vector concatenates the differences of the endpoint halves. An MLP gives a score per label: \(s(i, j, \cdot) = W_2\,\text{ReLU}(\text{LayerNorm}(W_1v(i, j)))\).

A tree is a set of labeled spans \(\{(i_t, j_t, l_t)\}\); its score is the sum of their span scores, and the parser picks the tree with the maximum score.

The greedy choice isn’t guaranteed to form a valid tree (though it usually does), so a CKY variant is used.

\(s_{best}(i, i+1) = \max_l s(i, i+1, l)\); for longer spans, \(s_{best}(i, j) = \max_l s(i, j, l) + \max_k[s_{best}(i, k) + s_{best}(k, j)]\), with no grammar constraints: the network learns them.

Measures of how well a hypothesis parse’s constituents match a hand-labeled reference (gold) parse: a hypothesis constituent is correct if a reference constituent has the same start, end and label. Labeled recall = correct / reference constituents; labeled precision = correct / hypothesis constituents; and F1.

The number of constituents bracketed one way in the reference, e.g. ((A B) C), but crossing it in the hypothesis, e.g. (A (B C)).

The canonical implementation of PARSEVAL, which also canonicalizes grammar-specific details (auxiliaries, pre-infinitival to…) for comparing parsers with different grammars.

The grammatically most important word of the phrase (N for an NP, V for a VP). Heads are passed up the tree, so each non-terminal is annotated with its head word; this idea dates to Bloomfield (1914).

They are central to dependency grammar and can map between constituency and dependency parses; they matter in probabilistic parsing and formalisms like HPSG.

Dynamically after parsing, by walking the tree with hand-written head rules (a head percolation table, Magerman/Collins), e.g. for NP: return a final POS; else search right-to-left for an NN, NNP, NNPS…; else left-to-right for an NP; and so on.

American structuralism (Bloomfield) developed immediate-constituent analysis; traditional European grammar defined relations between words, the root of dependency grammars.

If a simple form (e.g. man) can substitute for a more complex sequence (intense young man) in a construction, the sequence is probably a constituent, an early idea of constituents as equivalence classes.

John Cocke implemented a parser with the roots of CKY in 1960, later formalized by Kasami (1965) and Younger (1967); Kuno’s well-formed substring table and Kay’s chart were related; Earley (1968) gave the top-down version.