9.1 Active Edges

In this lecture we move from passive chart parsing to active chart parsing. Active chart parsing is based on a very simple idea. A passive chart, like the one we worked with in the previous chapter, is used to keep a record of complete constituents that we have found. (For example, on a passive chart we can record the information that the string between nodes 2 and 4 is an NP.) In an active chart we additionally record hypotheses --- that is, we record what it is we are actually looking for, and how much of it we have found so far. Such information is recorded in active edge s (or active arc s).

In this lecture we move from passive chart parsing to active chart parsing. Active chart parsing is based on a very simple idea. A passive chart, like the one we worked with in the previous chapter, is used to keep a record of complete constituents that we have found. (For example, on a passive chart we can record the information that the string between nodes 2 and 4 is an NP.) In an active chart we additionally record hypotheses --- that is, we record what it is we are actually looking for, and how much of it we have found so far. Such information is recorded in active edge s (or active arc s).

Here's an example of an active edge:

This is an arc between nodes 0 and 2. The important thing to note is the arc label: This says: ``I am trying to build an s, consisting of an np followed by a vp. So far I have found an np arc, and I'm still looking for the vp. '' So the insignificant looking `.' in the middle of the rule is very important: it marks the boundary between what we have found so far, and what we are still looking for.

Here's another example:

This says: ``I am trying to build an s, consisting of an np followed by a vp, starting at node 0. So far I have neither found the np nor the vp that I need.''

Here's another example:

This says: ``I am trying to build a vp, consisting of a dv followed by an np followed by a pp, starting at node 4. So far I have found a dv arc and an np arc, and I'm still looking for the pp.'' The np-arc ends in node 8, so the pp-arc will have to start in node 8.

Here's another example:

This says: ``I am trying to build a vp consisting of a tv followed by an np starting at node 4 --- and I've done it!'' Note that the `.' is at the end of the arc label. This means that everything we need to find has been found. Such an arc is called a passive edge , or a passive arc . It records complete information. In effect, these are the arcs we are used to from the previous chapter, though we didn't use the `.' notation there.

One final example:

This says: ``I am trying to build an s consisting of an np and a vp starting at node 0 --- and I've done it! I've found both the np and the vp, and moreover, I've done it in a way that the arc goes all the way from the first to the last node. This means I've recognized the sentence!.''