|
|
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.