9.5.1 An Example

An example of bottom-up chartparsing.

Suppose we want to analyze the sentence "Mia danced" using the following grammar.

First, we have to initialize the chart and the agenda (step 1 of the general algorithm). The chart initialization works exactly as for the passive chart parser. So, the initial chart for the sentence Mia danced looks like this:

The initial agenda looks like this:

For all words of the input we have added passive edges saying of which category they are and what their position in the sentence is. The edge , for instance, is a passive edge (indicated by the dot at is end) that says that there is a between positions 0 and 1. This edge was added because we have the rule in our grammar.

Now that the initialization process is over, we get to step 2, the ``repeat'' part of our general algorithm. The first thing we do is take the first arc of the agenda (step 2a). In our example that's . We then check whether it is aready recorded in the chart (step 2b). That's not the case, so we add it:

Next, we try to apply the fundamental rule to the new arc (step 2c). The fundamental rule lets us combine an active arc with a passive arc that is immediately to the right of the active one. Since the arc we are working with is passive, we have to find an active arc to its left. Or more precisely, we have to find an active arc ending in position 0. There is no such arc, so we cannot do anything here. We go on to step 2d.

The general algorithm tells us that we have to build new hypotheses in this step. Let's see what that means for the bottom-up case. In bottom-up parsing, we always build the parse tree from the bottom upwards, i.e., we combine already completed constituents to form bigger ones. Therefore, we only apply step 2d to passive arcs when working bottom-up; we only predict new constituents based on already completed ones.

In our example we are dealing with a passive arc at the moment (namely with ). Making hypotheses then works as follows. We look for grammar rules whose left corner (i.e. the the first symbol on their right hand side, see Section 7.1.3) is the same as the left hand side of the arc under consideration (which is a in our case). is such a rule, for example. We then build active edges for all of these rules. These edges start in the same position as the arc we were looking at, end in exactly that same position, and have the dot right after the arrow. Like this: . This edge is the hypothesis that we might be able to build an starting in 0. To do so we still have to find a , also starting in 0. As we have already found a starting in 0, that's a sensible hypothesis to make. If there were more suitable rules, we would build an active edge for each of them.