31-10-2012, 04:58 PM
PARSING WITH CONTEXT-FREE GRAMMARS
ARSING WITH CONTEX.ppt (Size: 440.5 KB / Downloads: 131)
PARSING
Parsing is the process of recognizing and assigning STRUCTURE
Parsing a string with a CFG:
Finding a derivation of the string consistent with the grammar
The derivation gives us a PARSE TREE
PARSING AS SEARCH
Just as in the case of non-deterministic regular expressions, the main problem with parsing is the existence of CHOICE POINTS
There is a need for a SEARCH STRATEGY determining the order in which alternatives are considered
TOP-DOWN AND BOTTOM-UP SEARCH STRATEGIES
The search has to be guided by the INPUT and the GRAMMAR
TOP-DOWN search: the parse tree has to be rooted in the start symbol S
EXPECTATION-DRIVEN parsing
BOTTOM-UP search: the parse tree must be an analysis of the input
DATA-DRIVEN parsing
NON-PARALLEL SEARCH
If it’s not possible to examine all alternatives in parallel, it’s necessary to make further decisions:
Which node in the current search space to expand first (breadth-first or depth-first)
Which of the applicable grammar rules to expand first
Which leaf node in a parse tree to expand next (e.g., leftmost)
DYNAMIC PROGRAMMING
A standard T-D parser would reanalyze A FLIGHT 4 times, always in the same way
A DYNAMIC PROGRAMMING algorithm uses a table (the CHART) to avoid repeating work
The Earley algorithm also
Does not suffer from the left-recursion problem
Solves an exponential problem in O(n3)
THE CHART
The Earley algorithm uses a table (the CHART) of size N+1, where N is the length of the input
Table entries sit in the `gaps’ between words
Each entry in the chart is a list of
Completed constituents
In-progress constituents
Predicted constituents
All three types of objects are represented in the same way as STATES