Playground

BNF Tester

Define a BNF grammar and test whether a string is in its language. Internally uses the Cocke-Younger-Kasami algorithm after CNF conversion.

Grammar & input

Grammar (one rule per line, ::= separator, | for alternatives, e for ε)

String to test

Result

\text{input} \in L(G)?

Input: 1 + 2 + 3

How it works

The grammar is converted to Chomsky Normal Form (ε-removal, unit-removal, binarization).
CYK builds a triangular table $O(n^3)$ in time, checking each substring against each nonterminal.
If the start symbol covers the whole string, the derivation is reconstructed cell by cell.