13.1.2 Bottom-Up Parsing

Bottom-up parsing is the earliest known parsing algorithm (it was first suggested by Yngve (1955)), and is used in the shift-reduce parsers common for computer languages (Aho and Ullman, 1972). In bottom-up parsing, the parser starts with the words of the input, and tries to build trees from the words up, again by applying rules from the grammar one at a time. The parse is successful if the parser succeeds in building a tree rooted in the start symbol S that covers all of the input. Fig. 13.4 shows the bottom-up search space, beginning with the sentence Book that flight. The parser begins by looking up each input word in the lexicon and building three partial trees with the part-of-speech for each word. But the word book is ambiguous; it can be a noun or a verb. Thus the parser must consider two possible sets of trees. The first two plies in Fig. 13.4 show this initial bifurcation of the search space.

Each of the trees in the second ply is then expanded. In the parse on the left (the one in which book is incorrectly considered a noun), the Nominal $ \rightarrow $ Noun rule is applied to both of the nouns (book and flight). This same rule is also applied to the sole noun (flight) on the right, producing the trees on the third ply.

In general, the parser extends one ply to the next by looking for places in the parse-in-progress where the right-hand side of some rule might fit. This contrasts with the earlier top-down parser, which expanded trees by applying rules when their left-hand side matched an unexpanded non-terminal.

原书第 480 页

Figure 13.4 An expanding bottom-up search space for the sentence Book that flight. This figure does not show the final tier of the search with the correct parse tree (see Fig. 13.2). Make sure you understand how that final parse tree follows from the search space in this figure.

Thus in the fourth ply, in the first and third parse, the sequence Det Nominal is recognized as the right-hand side of the NP $ \rightarrow $ Det Nominal rule.

In the fifth ply, the interpretation of book as a noun has been pruned from the search space. This is because this parse cannot be continued: there is no rule in the grammar with the right-hand side Nominal NP. The final ply of the search space (not shown in Fig. 13.4) contains the correct parse (see Fig. 13.2).