What does converting a rule set to Chomsky normal form for a CYK-style cubic parser actually cost you?
answer
- two nonterminals or one terminal
- the table splits a span in two
- empty and unit productions must go
- binarise before deleting nullable symbols
- returned tree is not the authored one
basics
~20 sEvery production must become two nonterminals or one terminal, so empty and unit productions go, long right-hand sides are split by invented nonterminals, the rule set grows, and the trees the parser returns no longer match the rules anyone authored.
solid answer
~50 s**Chomsky normal form** allows only `A -> B C` and `A -> a`, plus `S -> empty` from a fresh start symbol if the language contains the empty string. A CYK-style parser wants this because its dynamic program fills a table over substrings and needs each nonterminal's derivation to split a span into exactly two parts — the binary shape is what makes the table cubic in the input length. Getting there costs four things: empty productions are removed, which changes which derivations exist; unit productions are removed, which collapses the readable cascade of single-child nodes such as expression to term to factor; long right-hand sides are binarised through invented nonterminals; and the rule set grows. The practical consequence is that the tree the parser returns is in the transformed grammar, so you need a mapping back to the authored rules before the output means anything to a human.
go deeper
Recall the shape the normal form demands — every production is two nonterminals or one terminal — and that some parsing algorithms require it.
Explain why a table-filling parser needs binary productions: each entry is built by splitting a span in two, which a longer or empty right-hand side would break.
Show what the conversion costs in a real pipeline: rule growth, the empty-string caveat, collapsed unit cascades, and downstream tooling that must be remapped to a binary tree.
Ask whether the normal form is needed at all — if generality was the goal, a parser that takes the rule set as authored avoids the whole conversion and its maintenance burden.
## What the normal form requires A context-free rule set is in **Chomsky normal form** when every production has one of two shapes: - `A -> B C` — exactly two nonterminals on the right; - `A -> a` — exactly one terminal on the right. The single exception is the empty string: the strict form cannot derive it at all, so if the language contains it, a fresh start symbol is added with the production `S0 -> empty`, and `S0` appears on no right-hand side. ## Why a cubic general parser wants it A CYK-style parser is a dynamic program over **spans** of the input. It fills a table whose entry for the span from `i` to `j` holds every nonterminal that can derive that substring. To fill an entry, it considers every way of splitting the span into a left part and a right part and looks for a production combining the two. With n the number of input tokens, there are about n squared spans and up to n split points each, so the work is proportional to n cubed times the size of the rule set. **That algorithm only makes sense if every derivation step splits a span in exactly two** — which is precisely what the binary shape guarantees. A production with three symbols on the right would need two split points at once and break the recurrence; a production deriving nothing would make a span split into a span and an empty piece, so the recursion would not shrink. ## The conversion pipeline The standard order matters, because doing it differently can blow up the rule set: 1. **New start symbol.** Add `S0 -> S` so the start symbol never appears on a right-hand side. 2. **Isolate terminals.** In any right-hand side longer than one symbol, replace each terminal `a` with a fresh nonterminal `Ta` plus the production `Ta -> a`. 3. **Binarise.** Split each right-hand side longer than two into a chain of two-symbol productions through invented nonterminals. 4. **Remove empty productions.** Find every nullable nonterminal and, for each production mentioning one, add the variants with that occurrence omitted; then delete the empty productions. 5. **Remove unit productions.** For each `A -> B`, give `A` copies of `B`'s non-unit productions and delete the unit rule. Binarising before removing empty productions is the step that keeps the growth polynomial: a right-hand side with k nullable symbols expands into up to 2 to the power k variants, so shortening right-hand sides first bounds k at 2. ## What it costs | cost | what actually changes | |---|---| | language | preserved, with one caveat — removing empty productions drops the empty string unless the fresh start symbol restores it | | rule count | grows; the invented nonterminals from binarisation and the copies from unit removal both add rules | | tree shape | every node now has exactly two children, so the authored structure is gone | | unit cascades | a readable chain such as expression to term to factor collapses, taking the precedence structure it displayed with it | | downstream tooling | anything consuming the tree — a formatter, an analyser, a diagnostic — must be rewritten against the transformed shape or given a mapping back | ## When the trade is worth taking - **When the rule set is ambiguous or unavoidably general**, and you need a parser that considers all derivations rather than committing to one. - **When you need a total answer**: the table says for every span which nonterminals derive it, which is useful for error reporting and for fragment recovery. - **When the input is short.** Cubic in the token count is fine for a configuration file or a query and hostile for a large source file. And against it: a general chart parser in the Earley family accepts any context-free rule set **as authored**, with no normal form required, and is also cubic in the worst case while running faster on well-behaved rule sets. If the reason for reaching for CYK was generality rather than the table itself, that is usually the better trade — the conversion cost buys nothing you could not have had. ## The framing that answers the question The cost is not the runtime, it is the **loss of correspondence**. After conversion, the rules the machine runs are not the rules a human wrote, the tree is binary rather than meaningful, and every piece of tooling that read the tree must be taught the mapping. That is the sentence to lead with; the rule-count growth and the empty-string caveat are the supporting detail.
- Why must binarisation run before empty productions are removed?Because removing empty productions adds one variant per subset of nullable symbols in a right-hand side: k nullable symbols can produce up to 2 to the power k variants. Binarising first caps every right-hand side at two symbols, so k is at most 2 and the growth stays polynomial instead of exponential.
- Does the conversion preserve the language exactly?Almost. Every non-empty string is preserved, but the strict normal form cannot derive the empty string, so removing empty productions loses it unless a fresh start symbol with an explicit empty production restores it. That single string is the one place the conversion is not transparent.
- If you need to parse an ambiguous rule set, is this normal form the only route?No. A general chart parser in the Earley family accepts any context-free rule set as authored — no normal form, no rewriting — and is cubic in the worst case while doing better on unambiguous input. The normal form is required by the specific table algorithm, not by generality itself.
saying these in an interview costs you the question
- Thinks the normal form makes parsing faster than cubic.
- Claims every general parser requires this normal form.
- Forgets the empty string needs a fresh start symbol.
- Removes nullable symbols before shortening right-hand sides.
- Expects the returned tree to match the authored rules.
- Believes the conversion resolves ambiguity in the rule set.