Test a word and explain its CYK table
This CYK parser checks whether a context-free grammar generates a word. The loaded grammar and word produce a result immediately. Type another word, choose an example or open the Grammar panel to edit the rules. The verdict explains whether the start symbol occurs in the full-span table cell. An empty input tests the empty string rather than replacing it with another example.
The triangular table is interactive. Choose a cell to highlight it and see which token span it represents. A one-token cell lists matching terminal productions. A longer cell shows every split into a left and a right part, the two child sets and the binary productions that add parent variables. Empty sets remain visible because a failed combination is part of the explanation, not a reason to omit a cell.
Why CYK uses Chomsky normal form
Strict Chomsky normal form, or CNF, allows a nonempty rule to produce one terminal or two nonterminals. Terminals are the input tokens; nonterminals are grammar variables. The start may also produce the empty string, but the start cannot appear on a right side in this strict convention. The same validator checks the grammar before recognition.
When the entered rules are not in CNF, the page converts them first and says so beside the verdict. The conversion introduces a fresh start, removes empty and unit rules, splits long right sides and isolates terminals inside binary rules. Open Grammar to inspect the grammar actually used. The table and any displayed tree then belong to that converted grammar, including its helper variables. They do not reproduce the original tree shape.
Enter tokens and grammar symbols clearly
The main input is the word to test. Spaces may separate terminals, especially when a terminal name has several characters. Without spaces, tokenization chooses the longest matching grammar terminal at the current input position. A token that no terminal production recognizes yields an empty base cell and can cause rejection. The page does not silently delete unknown characters to force acceptance.
Inside Grammar, write one production per line and spaces between right-side symbols. The first rule selects the start symbol. Use a vertical bar between alternatives and ε as a complete empty alternative. A malformed rule gives an actionable error and clears stale parsing results. A syntactically valid grammar rejecting a word is a normal membership result, not an input-format error.
Fill terminal cells before longer spans
A cell records all nonterminals that generate one contiguous token span. The base row uses terminal rules: if A produces the token at that position, include A. For a longer span, try every nonempty left part and its remaining right part. If B is in the left cell, C is in the right cell and A produces B C, add A to the parent cell.
In set notation, parents are the union of those matching left/right combinations over all split positions. A symbol is stored once even if several splits or rules establish it. The cell explanation retains the individual contributing rules, so you can distinguish a set result from the evidence that produced it. Split positions shown in the explanation use positions in the whole word.
Complete worked table for the loaded word
The loaded word is b a a b a and the grammar has start S. It is already strict CNF, so no conversion is performed. Running the recognizer produces these cells:
| Token span | Tokens | Variables |
|---|---|---|
| 1–1 | b | B |
| 2–2 | a | A, C |
| 3–3 | a | A, C |
| 4–4 | b | B |
| 5–5 | a | A, C |
| 1–2 | b a | A, S |
| 2–3 | a a | B |
| 3–4 | a b | C, S |
| 4–5 | b a | A, S |
| 1–3 | b a a | ∅ |
| 2–4 | a a b | B |
| 3–5 | a b a | B |
| 1–4 | b a a b | ∅ |
| 2–5 | a a b a | A, C, S |
| 1–5 | b a a b a | A, C, S |
The final cell contains A, C, S, so the word is accepted. A table cell can contain the start along with other variables; acceptance requires membership of the start, not that the set contains nothing else. Empty middle cells do not imply the whole word is rejected if another full-span split succeeds.
Read a parse tree back from the table
For an accepted nonempty word, the tool starts with the start symbol in the full-span cell. It chooses a split and matching binary rule whose children occur in the corresponding smaller cells, then repeats that process. At a one-token span it uses a matching terminal production. This produces a tree whose leaves, read left to right, are the input tokens.
The diagram displays one valid tree, not every tree and not an ambiguity count. Several different rules or splits may support the same parent entry. A rejected word has no displayed parse tree. For an accepted empty word, the tree shows the start producing ε. The table has no nonempty spans in that case, so the verdict explains the start's empty rule directly.
Compare rejection with conversion
Choose the rejected example to test b b b in the loaded grammar. Its full-span cell does not contain the start, so its verdict is rejected. Inspect the base row and split explanations rather than changing an empty cell by hand. The table is generated entirely from the current rules.
The conversion example uses S -> a S b | ε and tests a a b b. The page explicitly reports conversion and uses fresh start S0; the resulting verdict is accepted. This separates normal-form preparation from recognition. A correct converter must preserve membership even though its helpers create a different-looking tree.
Use the result within the tool's limits
The input is limited to twelve tokens so the triangle and explanations remain useful on a small screen. This is a classroom visualizer, not a parser generator, source-language compiler or arbitrary-length grammar service. Grammar conversion also has size limits because nullable alternatives can expand substantially. Shorten a large exercise rather than assuming a resource-limit message proves nonmembership.
Use the CFG to CNF converter for a detailed conversion trace, and the complete CYK guide to work through the loaded table. The parse tree generator explores trees in an original grammar. The compiler lab groups the surrounding parsing tools. Copy table and grammar saves the verdict, span sets and actual rules used by this run.