9.5.2 An Example (continued)
Continuation.
Summing up, the instantiation of step 2d for a bottom-up strategy is as follows: If the new arc A is passive and has category 
as its left hand side, then look for grammar rules that have as their left corner. Add active edges starting and ending in the starting point of A for all of these rules to the agenda. Their dots must be right behind the arrow.
Back to our example. We have added all new edges to the agenda and are now at the end of the first round through the repeat loop of step 2. The chart and agenda look as follows:
1. |
|
2. |
|
The agenda is not empty, yet, so let's start the 2nd round. The first part of this should be clear: we simply place the top of the agenda, that is, the active edge 
, on the chart. To apply the fundamental rule (step 2c) we have to find a passive edge in the chart that starts in position 0 (the end point of the active edge). There is one; namely, 
. We can therefore build the edge 
(go back to Section 9.2 if you don't see how this works) and add it to the agenda. As step 2d only applies to passive edges, we skip it. The current state of chart and agenda are:
1. |
|
2. |
|
In the next round will be moved from the agenda to the chart. Step 2c doesn't produce any new edges, but in step 2d the active edges 
and 
will be added to the agenda. Chart and agenda then look as follows:
1. |
|
2. |
|
3. |
|
Next, we move 
from the agenda to the chart. Applying the fundamental rule in step 2c gives us the new edge 
.
1. |
|
2. |
|
3. |
|
is moved to the chart. No new edge can be built.
1. |
|
2. |
|
is moved to the chart. The fundamental rule creates 
.
1. |
|
2. |
|
is moved to the chart. No new edge is created.
1. |
|
is moved to the chart. Step 2d predicts 
.
1. |
|
is moved to the chart. The fundamental rule produces 
.
1. |
|
is moved to the chart. The fundamental rule produces 
and 
. Step 2d, although applicable as is a passive edge, produces no new rules.
1. |
|
2. |
|
is moved to the chart. Neither step 2c nor step 2d produce any new rules.
1. |
|
is moved to the chart. Again, no new edges can be built.
The agenda is now empty, so we exit the repeat. This takes us to step 3. And yes, we do have a passive s node from the first to the last node, so we have succeeded in recognizing the sentence.