DRAFT12PARSING WITHCONTEXT-FREEGRAMMARSThere are and can exist but two ways of investigating and discoveringtruth. The one hurries on rapidly from the senses and particulars tothe most general axioms, and from them. . . derives and discovers theintermediate axioms. The other constructs its axioms from the sensesand particulars, by ascending continually and gradually, till it finallyarrives at the most general axioms.Francis Bacon, Novum Organum Book I.19 (1620)We defined parsing in Ch. 3 as a combination of recognizing an input string andassigning a structure to it. Syntactic parsing, then, is the task of recognizing asentence and assigning a syntactic structure to it. This chapter focuses on the kindof structures assigned by context-free grammars of the kind described in Ch. 11.However, since they are a purely declarative formalism, context-free grammarsdon’t specify how the parse tree for a given sentence should be computed, thereforewe’ll need to specify algorithms that employ these grammars to produce trees. Thischapter presents three of the most widely used parsing algorithms for automaticallyassigning a complete context-free (phrase structure) tree to an input sentence.These kinds of parse trees are directly useful in applications such as gram-mar checking in word-processing systems; a sentence which cannot be parsedmay have grammatical errors (or at least be hard to read). More typically, however,parse trees serve as an important intermediate stage of representation for semanticanalysis (as we will see in Ch. 17), and thus plays an important role in applicationslike machine translation, question answering, and information extraction. Forexample, to answer the questionWhat books were written by British women authors before 1800?we’ll need to know that the subject of the sentence was what books and that theby-adjunct was British women authors to help us figure out that the user wants alist of books (and not a list of authors).1DRAFT2 Chapter 12. Parsing with Context-Free GrammarsBefore presenting any detailed parsing algorithms, we begin by describingsome of the factors that motivate the standard algorithms. First, we revisit thesearch metaphor for parsing and recognition, which we introduced for finite-stateautomata in Ch. 2, and talk about the top-down and bottom-up search strategies.We then discuss how the ambiguity problem rears its head again in syntactic pro-cessing, and how it ultimately makes simplistic approaches based on backtrackinginfeasible.The sections that follow then present the Cocke-Kasami-Younger (CKY) al-gorithm (Kasami, 1965; Younger, 1967), the Earley algorithm (Earley, 1970), andthe Chart Parsing approach (Kay, 1986; Kaplan, 1973). These approaches all com-bine insights from bottom-up and top-down parsing with dynamic programming toefficiently handle complex inputs. Recall, that we’ve already seen several applica-tions of dynamic programming algorithms in earlier chapters — Minimum-Edit-Distance, Viterbi, Forward. Finally, we discuss partial parsing methods, for usein situations where a superficial syntactic analysis of an input may be sufficient.12.1 PARSING AS SEARCHChs. 2 and 3 showed that finding the right path through a finite-state automaton, orfinding the right transduction for an input, can be viewed as a search problem. Forfinite-state automata, the search is through the space of all possible paths througha machine. In syntactic parsing, the parser can be viewed as searching through thespace of possible parse trees to find the correct parse tree for a given sentence. Justas the search space of possible paths was defined by the structure of an automata,so the search space of possible parse trees is defined by a grammar. Consider thefollowing ATIS sentence:(12.1) Book that flight.Fig. 12.1 introduces the L1grammar, which consists of the L0grammarfrom the last chapter with a few additional rules. Given this grammar, the correctparse tree for this example would be the one shown in Fig. 12.2.How can we use L1to assign the parse tree in Fig. 12.2 to this example? Thegoal of a parsing search is to find all the trees whose root is the start symbol S andwhich cover exactly the words in the input. Regardless of the search algorithm wechoose, there are two kinds of constraints that should help guide the search. Oneset of constraints comes from the data, that is, the input sentence itself. Whateverelse is true of the final parse tree, we know that there must be three leaves, and theymust be the words book, that, and flight. The second kind of constraint comes fromthe grammar. We know that whatever else is true of the final parse tree, it mustDRAFTSection 12.1. Parsing as Search 3S → NP VP Det → that | this | aS → Aux NP VP Noun → book | flight | meal | moneyS → VP Verb → book | include | preferNP → Pronoun Pronoun → I | she | meNP → Proper-Noun Proper-Noun → Houston | TWANP → Det Nominal Aux → doesNominal → Noun Preposition → from | to | on | near | throughNominal → Nominal NounNominal → Nominal PPVP → VerbVP → Verb NPVP → Verb NP PPVP → Verb PPVP → VP PPPP → Preposition NPFigure 12.1 The L1miniature English grammar and lexicon.SVPVerbBookNPDetthatNominalNounflightFigure 12.2 The parse tree for the sentence Book that flight according to grammarL1.have one root, which must be the start symbol S.These two constraints, invoked by Bacon at the start of this chapter, give riseto the two search strategies underlying most parsers: top-down or goal-directedsearch, and bottom-up or data-directed search. These constraints are more thanjust search strategies. They reflect two important insights in the western philo-sophical tradition: the rationalist tradition, which emphasizes the use of priorRATIONALISTknowledge, and the empiricist tradition, which emphasizes the data in front of us.EMPIRICISTDRAFT4 Chapter 12. Parsing with Context-Free Grammars12.1.1 Top-Down ParsingA top-down parser searches for a parse tree by trying to build from the root node STOP-DOWNdown to the leaves. Let’s consider the search space that a top-down parser explores,assuming for the moment that it builds all possible trees in parallel. The algorithmstarts by assuming the input can be derived by the designated start symbol S. Thenext step is to find the tops of all trees which can start with S, by looking for allthe grammar rules with S on the left-hand side. In the grammar in Fig. 12.1, thereare three rules that expand S, so the
View Full Document
Unlocking...