ToolSphere

CYK Parser

Computer science

Test a word with CYK, inspect every triangular-table split, read a parse tree and automatically convert non-CNF grammars with an explicit explanation.

Type a word, then choose a table cell to see which grammar rules build that part.

Accepted: b a a b aS is in the full-span cell.

Already CNF: each rule produces one terminal or two nonterminals. See conversion steps

CYK triangle

A cell contains the nonterminals (grammar variables) that generate its token span. ∅ means none.

Explain span 1–5

Tokens: b a a b a · Result: {A, C, S}

Split afterLeft / right setsRules adding parents
1{B} / {A, C, S}S → B C A → B A
2{A, S} / {B}S → A B C → A B
3{} / {A, S}No matching binary rule
4{} / {A, C}No matching binary rule

One parse tree

Scroll inside the diagram to see all branches. Full labels are also available in the node tooltips.

S, B, b, C, A, a, B, C, A, a, B, b, C, aSSBBbbCCAAaaBBCCAAaaBBbbCCaa

One valid tree is read from matching table entries; this does not count or rule out other parses.

Copy table and grammar
Grammar — edit rules or inspect conversion

One rule per line, spaces between symbols, ε for empty. First rule selects the start. Maximum twelve input tokens.

Read the full baaba worked example

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use CYK Parser

  1. 1Start with baaba or type a word using the grammar’s terminal tokens.
  2. 2Read the accepted or rejected verdict; an empty input tests ε.
  3. 3Choose a triangular-table cell to highlight and explain its span.
  4. 4Inspect the child sets and productions at every split.
  5. 5Open Grammar to edit rules or inspect automatic CNF conversion, then copy the result.

About CYK Parser

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.

Guides and tutorials

Frequently asked questions

What does a CYK table cell contain?

It contains the nonterminals that generate that contiguous token span. Click a cell to see the terminal rules or binary split combinations that establish its entries.

Does CYK require Chomsky normal form?

This implementation uses strict CNF: one terminal or two nonterminals, with optional start-only epsilon. Non-CNF input is converted first and explicitly labelled.

How do I know whether the word is accepted?

For a nonempty word, check whether the start symbol is in the full-span cell. For an empty word, the start must have an epsilon production.

What does an empty CYK cell mean?

No nonterminal in the used grammar generates that span. It does not automatically reject the whole word because another full-span split may succeed.

How are split points numbered?

The explanation names the token position after which a span is divided. It also shows the left and right variable sets for that particular split.

Can I see a parse tree?

Accepted inputs show one tree reconstructed from matching table entries. Rejected inputs have no tree, and the visualizer does not enumerate all parses.

Why does the tree contain extra variables?

Non-CNF grammars are converted before CYK runs, introducing a fresh start and helper variables. The displayed tree belongs to those converted rules.

How do I test the empty string?

Leave the word input empty. The verdict checks a start-to-epsilon rule and the table has no nonempty spans.

Can terminals contain several characters?

Yes: separate tokens with spaces when helpful. Without spaces the tokenizer chooses the longest matching grammar terminal at each position.

How long can my CYK input be?

The visualizer accepts up to twelve tokens. This keeps the triangular cells and split explanations readable and bounds interactive computation.

Have a suggestion for CYK Parser?Share your feedback ↗