Chart Parsing

Charts

• 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 subcat values 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

  

[L645 Syllabus]