The edges that the initialization step provides are not sufficient for parsing to begin: we still need a way of creating new active edges if anything is to result from the application of the fundamental rule. One simple principle to ensure that such an edge gets added is the following: every time you add an inactive edge of category C to the chart, add a new empty active edge, starting from the same vertex, for every rule in the grammar that requires a constituent of category C as its leftmost daughter. An empty active edge is an active edge that has yet to find any of its components and which thus starts from, and finishes at, the same vertex. This rule invocation strategy will give us a kind of bottom-up parsing - we shall consider alternative rule invocation strategies later. The exact way in which this strategy works may become clearer from the following formulation:
Bottom-up rule
If you are adding edge <i, j, C -> W1.> to the chart, then for every rule in the grammar of the form B -> C W2, add an edge <i, i, B -> .C W2> to the chart.
The bottom-up rule will apply when most inactive edges are added to the chart, and the result is a set of active edges to be added. If we imagine that we had applied this rule while initializing the chart depicted in Figure 6.13, then we would have obtained a chart of the form shown in Figure 6.14.
Here, active edges have been added to the chart corresponding to rules whose leftmost daughters have been found. Clearly, there is plenty in this chart for the fundamental rule to work on, and, every time that the latter succeeds in adding an inactive edge to the chart, our bottom-up rule will probably also apply, providing yet more work for the fundamental rule to do. Indeed, the bottom-up rule and the fundamental rule are all we need to ensure that all possible analyzes are found.
Notice that in this parsing strategy a rule is retrieved as soon as the leftmost elements on its RHS have been found. This indexing on the leftmost daughter means that the strategy is a kind of left-corner parsing.
Another interesting feature is the use of active edges. The use of active edges in this parsing strategy means that, unlike the bottom-up parsers presented in Chapter 5, the parser is in a sense maintaining hypotheses about other phrases that might be present. The fact is, however, that nothing more will happen to these active edges until further required phrases have been found (bottom up). So, if an active edge with label S -> .NP VP is added to the chart on the discovery of an NP, there is nothing that this hypothesis can do apart from, using the fundamental rule, absorb any following NPs (including the one found) into a new active edge and then absorb all VPs that are found after them to make inactive S edges. The active edges are thus simply providing an efficient way of storing rules that might possibly apply (bottom up) at a later stage. When we consider the top-down rule, we will see that there are much more positive ways of using active edges than this.
Quite how the operation of the bottom-up rule will interact with that of the fundamental rule depends on the order in which the various edges are added to the chart. This question brings us to our third ingredient -
search strategy, discussed below. But we will leave consideration of this issue until we have looked in more detail at some actual chart parsers.
Send us a comment.