An Example (continued)
Abstract:
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 C as its left hand side, then look for grammar rules that have C 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:
Figure 3: An Example of Bottom-Up Chartparsing: Step 2 Example continued. |
1. | 〈0,0,NP→.PN〉 |
2. | 〈1,2,IV→danced.〉 |
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
〈0,0,NP→.PN〉, 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,
〈0,1,PN→mia〉. We can therefore build the edge
〈0,1,NP→PN.〉 (go back to
» The Fundamental Rule 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:
Figure 6: An Example of Bottom-Up Chartparsing: Step 3 Example continued. |
1. | 〈0,1,NP→PN.〉 |
2. | 〈1,2,IV→danced.〉 |
In the next round 〈0,1,NP→PN.〉 will be moved from the agenda to the chart. Step 2c doesn't produce any new edges, but in step 2d the active edges 〈S→NPVP〉 and 〈S→NPVPPP〉 will be added to the agenda. Chart and agenda then look as follows:
Figure 9: An Example of Bottom-Up Chartparsing: Step 4 Example continued. |
1. | 〈0,0,S→.NPVP〉 |
2. | 〈0,0,S→.NPVPPP〉 |
3. | 〈1,2,IV→danced.〉 |
Next, we move 〈0,0,S→.NPVP〉 from the agenda to the chart. Applying the fundamental rule in step 2c gives us the new edge 〈0,1,S→NP.VP〉.
Figure 12: An Example of Bottom-Up Chartparsing: Step 5 Example continued. |
1. | 〈0,1,S→NP.VP〉 |
2. | 〈0,0,S→.NPVPPP〉 |
3. | 〈1,2,IV→danced.〉 |
〈0,1,S→NP.VP〉 is moved to the chart. No new edge can be built.
Figure 15: An Example of Bottom-Up Chartparsing: Step 6 Example continued. |
1. | 〈0,0,S→.NPVPPP〉 |
2. | 〈1,2,IV→danced.〉 |
〈0,0,S→.NPVPPP〉 is moved to the chart. The fundamental rule creates 〈0,1,S→NP.VPPP〉.
Figure 18: An Example of Bottom-Up Chartparsing: Step 7 Example continued. |
1. | 〈0,1,S→NP.VPPP〉 |
2. | 〈1,2,IV→danced.〉 |
〈0,1,S→NP.VPPP〉 is moved to the chart. No new edge is created.
Figure 21: An Example of Bottom-Up Chartparsing: Step 8 Example continued. |
〈1,2,IV→danced.〉 is moved to the chart. Step 2d predicts VP→.IV.
Figure 24: An Example of Bottom-Up Chartparsing: Step 9 Example continued. |
〈1,2,VP→.IV〉 is moved to the chart. The fundamental rule produces 〈1,2,VP→IV.〉.
Figure 27: An Example of Bottom-Up Chartparsing: Step 10 Example continued. |
〈1,2,VP→IV.〉 is moved to the chart. The fundamental rule produces 〈0,2,S→NPVP.〉 and 〈0,2,S→NPVP.PP〉. Step 2d, although applicable as 〈1,2,VP→IV.〉 is a passive edge, produces no new rules.
Figure 30: An Example of Bottom-Up Chartparsing: Step 11 Example continued. |
1. | 〈0,2,S→NPVP.〉 |
2. | 〈0,2,S→NPVP.PP〉 |
〈0,2,S→NPVP.〉 is moved to the chart. Neither step 2c nor step 2d produce any new rules.
Figure 33: An Example of Bottom-Up Chartparsing: Step 12 Example continued. |
〈0,2,S→NPVP.PP〉 is moved to the chart. Again, no new edges can be built.
Figure 36: An Example of Bottom-Up Chartparsing: Step 13 Example continued. |
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.