CFG from rules to parse trees

context-free grammars · parsing strategies · derivations

Sentence

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.

Rules

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

Lexicon

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

Algorithm

Top-down Bottom-up Left-corner Earley CKY

Options

all parses left-corner oracle

Start symbol

The grammar is left-recursive (NP → NP PP; VP → VP PP). Depth-first top-down parsing will loop on it once it tries that rule.

Top-down (recursive descent)

How it works →

11 steps · no parse for “John saw the dog in the park”.

Infinite loop: because of the left-recursive rule NP → NP PP, NP keeps being predicted at the same word without reading anything. A depth-first top-down parser never comes back from this branch.

Step 1 / 11

Goals next goal first
Input words read so far

All 11 steps

No parse tree

No complete tree was found before the parser stopped.