Syntax Analysis: CYK Parse-Chart Simulator

Sentence

CYK Chart

Autoplay speed 1.0×

Span length filled

0 / 0

Cells computed

0 / 0

Parses of S (root)

—

Grammatical?

—

Chart log

lexical (Det/N/V/P) NP VP PP S (root)

How it works

The grammar below is in Chomsky Normal Form (every rule rewrites to either two nonterminals or one word), the form the CYK algorithm (Cocke–Younger–Kasami) needs:

S  -> NP VP
NP -> Det N | NP PP
VP -> V NP  | VP PP
PP -> P NP
Det -> the | a      N -> dog | cat | man | telescope | park
V  -> saw | chased  P -> with | in

CYK fills a triangular chart bottom-up. Cell (i, l) covers the span of l words starting at word i. For a single word (l=1) the cell holds its lexical category. For l>1, the algorithm tries every split point k and every rule A → B C, and adds A to the cell whenever B derives the left part and C derives the right part:

count[A][i][l] = Σ_k Σ_(A→B C) count[B][i][k] · count[C][i+k][l-k]

The sentence is grammatical iff the single top cell — spanning all n words — contains S. If it contains S more than once (reachable via more than one derivation), the sentence is structurally ambiguous: "the dog saw the cat with the telescope" has 2 parses because "with the telescope" can attach either to the VP (an instrument of seeing) or to the NP "the cat" (a cat that owns a telescope) — the same words, two different tree shapes, exactly what the tower height at the root cell reports.

Height of each tower = number of derivations counted in that cell (ambiguity count).
Colour = the highest-level category the cell can produce (S > NP/VP > PP > lexical).
Runtime is O(n³·|G|) — cubic in sentence length, the classic complexity of chart parsing.

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.