What Chomsky normal form costs you

Every textbook that introduces the CYK algorithm says the same thing in the same tone: the grammar must first be converted to Chomsky normal form, which can always be done, and the conversion is a formality. It can always be done. It is not a formality. On a real grammar the conversion can multiply the rule count by an order of magnitude, and because the running time of CYK carries the grammar size as a factor, the multiplication lands directly in the parser's cost. My CYK implementation takes normal-form grammars, and the complexity term in my paper is the size after conversion, so I measured what the conversion actually costs on grammars I could get hold of, step by step. The step everyone worries about, binarisation, is nearly free. The step everyone forgets, unit-rule elimination, is the bill.

The five steps

Chomsky normal form allows two kinds of rule: a nonterminal produces exactly two nonterminals, or a nonterminal produces exactly one terminal. Getting an arbitrary grammar into that shape takes five steps, conventionally named START, TERM, BIN, DEL and UNIT. START adds a fresh start symbol so that the old one can appear on the right of rules. TERM replaces every terminal that appears in a rule with other symbols by a new nonterminal that produces only that terminal. BIN splits every rule with more than two symbols on the right into a chain of two-symbol rules. DEL removes rules that produce the empty string, by adding copies of every rule that could have used them. UNIT removes rules of the form one nonterminal produces one other nonterminal, by copying the target's rules up to the source.

The textbook analysis gives each step a bound, and the bounds are not equal. START adds one rule. TERM adds at most one rule per terminal. BIN adds, for a rule with k symbols on the right, k minus two new rules, so its total is linear in the size of the grammar as written. DEL is the step with the scary exponent, two to the number of nullable symbols in a rule, but after BIN every rule has at most two symbols, so the exponent is at most two and the step is bounded. UNIT is the one whose bound is quadratic: for every pair of nonterminals connected by a chain of unit rules, the target's rules are copied to the source, and in the worst case that is every nonterminal times every rule.

Measuring the tax

I call the ratio of rules after conversion to rules before the CNF tax, and I measured it on three grammars with a script that applies the five steps and counts after each. The first is a grammar for JSON written from the productions in RFC 8259, with character classes collapsed to single terminals: 43 rules. The second is the arithmetic expression grammar every compiler course uses: 10 rules. The third is the grammar induced from the parsed sentences in the Penn Treebank sample that ships with NLTK, which is the kind of grammar a statistical parser actually runs on: 21,763 distinct rules, of which 666 are unit rules.

The pattern is the same in all three and the magnitude is not. The JSON grammar grows from 43 rules to 117, a tax of 2.72, and the unit step accounts for 49 of the 74 rules added. The expression grammar goes from 10 to 37, a tax of 3.70, with 15 of the 27 new rules from unit elimination. The treebank grammar goes from 21,763 rules to 354,170, a tax of 16.27, and of the 332,407 rules added, binarisation contributed 4,447 and unit elimination 327,959. The step the textbooks spend a page on added a fifth. The step they spend a sentence on multiplied the grammar by fifteen. And the tax is not a property of size alone: the tiny expression grammar pays more per rule than the JSON grammar does, because two of its ten rules are unit rules that each carry a whole nonterminal's alternatives.

Why unit rules explode

The reason is the shape of a treebank grammar. A parsed corpus is full of rules like a noun phrase that consists of just a noun, a sentence that consists of just a verb phrase, a phrase that consists of just a smaller phrase of the same kind. Each of those is a unit rule, and they chain: if S can be VP and VP can be VB, then S reaches VB through two unit steps, and unit elimination gives S a copy of every rule VB has. With 666 unit rules connecting a few dozen phrase categories, most categories reach most others, and each reachable pair copies a whole category's worth of rules. The treebank sample has about 12,000 distinct part-of-speech-to-word rules, and after elimination every phrase category that could once become a bare word through a chain now owns a copy of the relevant slice of the lexicon.

Two things follow for anyone who writes a CYK parser. The first is that the order of the steps, which the textbooks say matters, mattered less than expected in my measurements: running UNIT before BIN, with binarisation sharing suffixes, produced the same total on all three grammars, because unit elimination's contribution swamps everything else and does not depend on whether the rules it copies have been binarised. The order still matters for correctness, since DEL must follow BIN to stay bounded and UNIT must come last so that DEL does not recreate unit rules, but it is not where the size is decided.

The second is that the bill is optional. A recogniser does not have to eliminate unit rules at all. It can keep them and handle them in the parser: after filling a cell of the chart with the nonterminals that derive a span directly, close the cell under the unit rules, adding every nonterminal that reaches one already present through a chain. That closure is a small fixed-point computation per cell, its cost is bounded by the number of unit pairs rather than by the number of copied rules, and it leaves the grammar at 26,211 rules rather than 354,170. That is what my implementation does, and it is the reason the grammar-size term in my paper's bound is the binarised size rather than the fully normalised one.

What the tax is for

It is fair to ask what the full conversion buys, since parsers have worked around it for decades. The answer is the clean statement of the algorithm. With every rule in normal form, the CYK recurrence is two nested loops over split points and rule pairs, the proof of correctness is a page, and the complexity bound is the cube of the sentence length times the size of the grammar, with no asterisks. Keeping unit rules in the parser trades a line of the proof for a factor of fifteen in the grammar, and for a treebank grammar that trade is not close. The textbook is right that the conversion can always be done. What it does not say is which step to skip.