9.7.1 Top-down rule selection

How to change 2d.

Let's first look at how to change 2d. When working bottom-up, we were interested in using rules right-to-left. We would start with structure that we knew we had (for example, perhaps we have a passive edge that tells us that there is a PN between positions 0 and 1) and then find a rule that we could use right-to-left to make use of this fact (for example, reading the rule right to left we could deduce that we had an NP between positions 0 and 1). Summing up: working bottom up, we read the rules right-to-left, and start with the information in passive edges.

However, when we work top-down, we do precisely the opposite: we read the rules left-to-right and start with the information in active edges. Let's see why.

Suppose we have an active edge that starts at position 0 and is trying to build an S out of an NP and a VP in that order, and suppose it has found neither the NP nor the VP. So the arc label would be . Further, suppose we can't apply the fundamental rule (that is, there is no passive edge that tells us that there is an NP starting at position 0). What should we do? Since we are hypothesizing that it is possible to build an S out of an NP and a VP in that order starting at position 0, we should try and find grammar rules that will let us do this. In particular, we should look for grammar rules that have NP on the left-hand-side, for these are the rules that tell us how to build NPs --- if we want that sentence, we need an NP! We then use these rules to add a new active edge at position 0. For example, if we have the rule , we should add an active edge at position 0 that is trying to build an NP out of a Det and an N in that order.

In short: working top-down, we read the rules left-to-right, and start with the information in active edges. So in the top-down case we should change step 2d to read: ``If the edge you added was active, try to select rules that can be used with the edge you have just added to make new active edges. Add these new edges to the agenda.'' This is the main point we need to make about rule selection, but there is another, less important issue, due to which we will make slight changes to the way we represent our grammar.