CFG from rules to parse trees

context-free grammars · parsing strategies · derivations

Words separated by spaces; matching with the lexicon is case-sensitive. Try: PP attachment · Left recursion · Italiano · Start from scratch

Build the tree by hand

Click a word and type its part of speech (Det, N, V…): this adds a lexicon entry. Click nodes that are next to each other and type their mother (NP, VP…): this adds a rewriting rule. The tree grows bottom-up as you go, and the grammar below fills in.

One rule per line, | between alternatives: NP -> Det N | PropN. Only categories on the right; words go in the lexicon. No ε-rules.

Part of speech, arrow, words: N -> dog | cat. A word may have several categories.

Algorithm
Options

CKY (Cocke–Kasami–Younger)

How it works →

40 steps · 2 parses found for “the man saw a dog with a telescope”.

Step 1 / 40

Input
span of this item

Table: cell [i,j] holds the categories spanning words i+1…j

Binarised rules (CKY needs at most two daughters) NP → Det NP|N_PPNP|N_PP → N PPVP → V VP|NP_PPVP|NP_PP → NP PP
All 40 steps

2 parse trees

Parse 1

[S [NP [Det the] [N man]] [VP [V saw] [NP [Det a] [N dog] [PP [P with] [NP [Det a] [N telescope]]]]]]

Parse 2

[S [NP [Det the] [N man]] [VP [V saw] [NP [Det a] [N dog]] [PP [P with] [NP [Det a] [N telescope]]]]]