B651: Parsing

Some decisions

Left-to-right, right-to-left, and head-first

Bottom-up parsing

Parsing driven by the lexicon
Rules indexed by right-hand sides
Problem with empty categories
Non-determinism when right-hand side of more than one rule or lexical entry matches

Top-down parsing

Parsing driven by the grammar
Rules indexed by left-hand sides
Non-determinism when left-hand side of more than one rule or lexical entry matches
Problems with left recursion (in left-to-right parsing)

Parsing as search: depth-first, breadth-first and combinations

Storage of intermediate results

Why

Saves time spent reparsing
- They saw the nurses report.
  The structure of the nurses is the same, whether or not it is the object of saw.
Efficient way of representing multiple parses
- Phyllis read the book on the volcano.
Permits representing partial parses
- The mischievous boy fleered from the front row.

Chart parsing as a way to parse while saving intermediate results

Chart parsing

Chart: set of edges (arcs), each characterizing a completed or partial constituent spanning a group of words: <start finish label found tofind>

Active edge: edge which still has words to be found

Inactive edge: completed

Creating new edges and combining edges

Bottom-up rule for creating active edges

if <i, j, C → W1 .>
   for each rule B → C W2, add <i, i, B → . C W2>

Top-down rule for creating active edges

at initialization, for each rule S → W
   add <0, 0, S → . W>
if <i, j, C → W1 . B W2>
   for each rule B → W, add <j, j, B → . W>

Rule for combining edges: Fundamental Rule of Chart Parsing

if <i, j, A → W1 . B W2> and <j, k, B → W3 .>
   add <i, k, A → W1 B . W2>

Chart-parsing algorithm

Initialize and invoke RULE to add active edges to AGENDA.
Until AGENDA is empty
   For each EDGE in AGENDA
   Add EDGE to chart and
      Apply fundamental rule to EDGE,
         adding any new edges to AGENDA and
      Invoke RULE on EDGE,
         adding any new edges to AGENDA.
Report any complete parses in AGENDA.

Example

Bottom-up, left-to-right, depth-first
In this trace, bold numbers indicate the order of steps, categories in braces are subcategorization values (arguments which phrasal heads expect) and categories in boxes are daughters (ordered from left to right).
Backtracking takes place following step 11 because of the word which remains (report).

The edges created

Partial parsing (chunking)

Sometimes we may not need a complete parse of a sentence; we may want to know what only some of the constituents are, for example, only the noun phrases.

Chunking identifies major non-overlapping, non-recursive phrases in sentence using finite state automata.

Cascades of finite state transducers can produce trees of greater depth, though looping through the cascade more than one may be required.

IU | INFO | CSCI