CFGs

April 17, 2002

Some challenges for context-free grammars:

Agreement: leads to multiplication of rules to handle number, case

Subcategorization: leads to multiplication of rules to handle verb types

Relations between sentences: each "version" has the same number and subcategorization patterns, leading to redundancies

Parsing with CFGs:

"Search through the speace of all possible parse trees to find the correct parse tree for the sentence"

Top-down: start building trees starting with S (by expanding the left sides of rules) until you get a tree or trees that fit

Bottom-up: starting from words and tags, find node labels that fit (by matching the right sides of rules)

Top-down with bottom-up filtering: check the "left corner" (first item) before considering an expansion. NPs start with Det or N; S with Det, N, Aux, V; VP with V; etc.