An Example
Abstract:
An example of active chart parsing.
Let's see an example of the top-down algorithm in action. As in the last chapter, we will parse the sentence
Mia danced and we will also use the same grammar. Here it is again:
S→NPVP |
S→NPVPPP |
NP→PN |
VP→IV |
PP→PNP |
PN→mia |
IV→danced |
So, our initial chart and agenda will look like shown at the end of the last section. We enter the repeat loop and move the edge 〈0,0,S→.NPVP〉 to the chart. There is nothing in the chart that we could use to apply the fundamental rule, so we go on to step 2d. 〈0,0,S→.NPVP〉 is an active edge, and as we saw above, step 2d is carried out for active instead of passive edges in the top-down algorithm. We therefore have to look for a grammar rule that has NP at its left hand side. We find NP→PN and add it to the agenda.
Figure 3: Example continued. |
1. | 〈0,0,NP→.PN〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈0,0,NP→.PN〉 is moved from the agenda to the chart. The fundamental rule creates 〈0,1,NP→PN.〉.
Figure 6: Example continued. |
1. | 〈0,1,NP→PN.〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈0,1,NP→PN.〉 is moved to the chart. Applying the fundamental rule creates 〈0,1,S→PN.VP〉.
Figure 9: Example continued. |
1. | 〈0,1,S→PN.VP〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈0,1,S→PN.VP〉 goes to the chart. Step 2d adds a new hypothesis: 〈1,1,VP→.IV〉.
Figure 12: Example continued. |
1. | 〈1,1,VP→.IV〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈1,1,VP→.IV〉 is moved to the chart and combined with IV→danced. by the fundamental rule to form 〈1,2,VP→IV.〉.
Figure 15: Example continued. |
1. | 〈1,2,VP→IV.〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈1,2,VP→IV.〉 is moved to the chart. The fundamental rule gives us 〈0,2,S→NPVP.〉.
Figure 18: Example continued. |
1. | 〈0,2,S→NPVP.〉 |
2. | 〈0,0,S→.NPVPPP〉 |
〈0,2,S→NPVP.〉 is moved to the chart. Neither the fundamental rule nor step 2d produce any new edges.
Figure 21: Example continued. |
〈0,0,S→.NPVPPP〉 is moved to the chart. The fundamental rule produces 〈0,1,S→NP.VPPP〉 and step 2d predicts 〈0,0,NP→.PN〉.
Figure 24: Example continued. |
1. | 〈0,1,S→NP.VPPP〉 |
2. | 〈0,0,NP→.PN〉 |
〈0,1,S→NP.VPPP〉 is moved to the chart. The fundamental rule creates 〈0,2,S→NPVP.PP〉 and step 2d predicts 〈1,1,VP→.IV〉
Figure 27: Example continued. |
1. | 〈0,2,S→NPVP.PP〉 |
2. | 〈1,1,VP→.IV〉 |
3. | 〈0,0,NP→.PN〉 |
〈0,2,S→NPVP.PP〉 is moved to the chart. There are no appropriate edges in the chart to apply the fundamental rule. Step 2d, however, produces 〈2,2,PP→.PNP〉.
Figure 30: Example continued. |
1. | 〈2,2,PP→.PNP〉 |
2. | 〈1,1,VP→.IV〉 |
3. | 〈0,0,NP→.PN〉 |
〈2,2,PP→.PNP〉 is moved to the chart, but no new edges can be created.
Figure 33: Example continued. |
1. | 〈1,1,VP→.IV〉 |
2. | 〈0,0,NP→.PN〉 |
The two edges which are left on the agenda at this point are both already recorded in the chart. So, they will be popped off the agenda without adding any new edges to it.
Figure 36: Example continued. |
You should experiment with other examples of this algorithm in action. You should also compare the top-down treatment of Mia danced with the bottom-up treatment that you saw in the last chapter.