9.7.2 Initializing Chart and Agenda

Initializing chart and agenda.

In the bottom-up algorithm, we form an initial agenda containing passive arcs that represent all possible categories of all the words in the input string. Now, this is clearly important information, and it's information we will continue to need when working top-down. But since in the top-down case new rules can only be predicted from active edges, we won't be able to use the passive arcs representing categories of words in the beginning. Only when we have worked our way down to the pre-terminal nodes will this information be important. We therefore write those arcs directly into the chart. What we do need though is at least one active edge on the agenda to start the parsing process.

So what active edge(s) should we start with? Recall that active edges can be thought of as hypotheses about structure --- and there is one very obvious hypothesis to make about the structure of the input string, namely, that it is a sentence.

This suggests that, right at the start of the top-down algorithm, we should look at our grammar and find all the rules that let us make sentences. We should then use these rules to make active edges. These active edges should start at position 0. After all, we want to show that we have an S that starts at position 0 and spans the entire sentence.

For example, if we have the rule in our grammar, we should add at position 0 an active edge that wants to make an S out of an NP and a VP in that order, at position 0. And if we have coordination rules, for example , where coord can be ``and'', ``or'', ``but'', and so on, then we should also add an active edge at position 0 that is trying to build an S out of an S followed by a coordination word followed by another S.

The initial state of chart and agenda for the sentence Mia danced and the grammar of the last chapter would look like this: