CHAPTER 13 Constituency Parsing - Stanford University

1 speech and Language Processing. Daniel Jurafsky & James H. Martin. Copyright 2021. Allrights reserved. Draft of December 29, ParsingOne morning I shot an elephant in my he got into my pajamas I don t Marx,Animal Crackers, 1930 Syntactic Parsing is the task of assigning a syntactic structure to a sentence. Thischapter focuses on Constituency structures, those assigned by context-free grammarsof the kind described in CHAPTER 12. In the next CHAPTER we ll introduce dependencyparses, an alternative kind of parse structure,Parse trees can be used in applications such asgrammar checking: sentence thatcannot be parsed may have grammatical errors (or at least be hard to read).

2 Parsetrees can be an intermediate stage of representation forsemantic analysis(as weshow in CHAPTER 16) and thus play a role in applications likequestion example to answer the questionWhich flights to Denver depart before the Seattle flight?we ll need to know that the questioner wants a list of flights going to Denver, notflights going to Seattle, and parse structure (knowing thatto Denvermodifiesflights,andwhich flights to Denveris the subject of thedepart) can help begin by discussing ambiguity and the problems it presents, and then givethe Cocke-Kasami-Younger (CKY) algorithm (Kasami 1965, Younger 1967), thestandard dynamic programming approach to syntactic Parsing .

3 We ve already seenother dynamic programming algorithms like minimum edit distance ( CHAPTER 2) andViterbi ( CHAPTER 8).The vanilla CKY algorithm returns an efficient representation of the set of parsetrees for a sentence, but doesn t tell uswhichparse tree is the right one. For that,we need to augment CKY with scores for each possible constituent. We ll see howto do this with neural span-based parsers. And we ll introduce other methods likesupertaggingfor Parsing CCG,partial Parsing methods, for use in situations inwhich a superficial syntactic analysis of an input may be sufficient, and the standardset of metrics for evaluating parser AmbiguityAmbiguity is the most serious problem faced by syntactic parsers.

4 CHAPTER 8 intro-duced the notions ofpart-of- speech ambiguityandpart-of- speech disambigua-tion. Here, we introduce a new kind of ambiguity, calledstructural ambiguity,structuralambiguityillustrated with a new toy grammarL1, shown in Figure , which adds a fewrules to theL0grammar from the last ambiguity occurs when the grammar can assign more than one parseto a sentence. Groucho Marx s well-known line as Captain Spaulding inAnimalCrackersis ambiguous because the phrasein my pajamascan be part of theNP2 CHAPTER13 CONSTITUENCYPARSINGG rammarLexiconS NP VPDet that|this|the|aS Aux NP VPNoun book|flight|meal|moneyS VPVerb book|include|preferNP PronounPronoun I|she|meNP Proper-NounProper-Noun Houston|NWANP Det NominalAux doesNominal NounPreposition from|to|on|near|throughNominal Nominal NounNominal Nominal PPVP VerbVP Verb NPVP Verb NP PPVP Verb PPVP VP PPPP Preposition NPFigure English grammar and

5 My pajamasNominalNounelephantDetanVerbshotN PPronounISVPPPin my pajamasVPNPN ominalNounelephantDetanVerbshotNPPronoun IFigure parse trees for an ambiguous sentence. The parse on the left corresponds to the humorousreading in which the elephant is in the pajamas, the parse on the right corresponds to the reading in whichCaptain Spaulding did the shooting in his byelephantor a part of the verb phrase headed byshot. Figure illus-trates these two analyses of Marx s line using rules ambiguity, appropriately enough, comes in many forms.

6 Two commonkinds of ambiguity areattachment ambiguityandcoordination ambiguity. Asentence has anattachment ambiguityif a particular constituent can be attached toattachmentambiguitythe parse tree at more than one place. The Groucho Marx sentence is an example ofPP-attachment ambiguity. Various kinds of adverbial phrases are also subject to thiskind of ambiguity. For instance, in the following example the gerundive-VPflyingto Pariscan be part of a gerundive sentence whose subject isthe Eiffel Toweror itcan be an adjunct modifying the VP headed bysaw:( ) We saw the Eiffel Tower flying to ambiguityphrases can be conjoined by a conjunction CKY Parsing : A DYNAMICPROGRAMMINGAPPROACH3 For example, the phraseold men and womencan be bracketed as[old [men andwomen]], referring toold menandold women, or as[old men] and [women], inwhich case it is only the men who are old.

7 These ambiguities combine in complexways in real sentences, like the following news sentence from the Brown corpus:( ) President Kennedy today pushed aside other White House business todevote all his time and attention to working on the Berlin crisis address hewill deliver tomorrow night to the American people over nationwidetelevision and sentence has a number of ambiguities, although since they are semanticallyunreasonable, it requires a careful reading to see them. The last noun phrase could beparsed[nationwide [television and radio]]or[[nationwide television] and radio].

8 The direct object ofpushed asideshould beother White House businessbut couldalso be the bizarre phrase[other White House business to devote all his time andattention to working]( , a structure likeKennedy affirmed [his intention to proposea new budget to address the deficit]). Then the phraseon the Berlin crisis address hewill deliver tomorrow night to the American peoplecould be an adjunct modifyingthe verbpushed. APPlikeover nationwide television and radiocould be attachedto any of the higherVPs orNPs ( , it could modifypeopleornight).

9 The fact that there are many grammatically correct but semantically unreason-able parses for naturally occurring sentences is an irksome problem that affects allparsers. Fortunately, the CKY algorithm below is designed to efficiently handlestructural ambiguities. And as we ll see in the following section, we can augmentCKY with neural methods to choose a single correct parse bysyntactic CKY Parsing : A Dynamic Programming ApproachDynamic programmingprovides a powerful framework for addressing the prob-lems caused by ambiguity in grammars.

10 Recall that a dynamic programming ap-proach systematically fills in a table of solutions to sub-problems. The complete ta-ble has the solution to all the sub-problems needed to solve the problem as a the case of syntactic Parsing , these sub-problems represent parse trees for all theconstituents detected in the dynamic programming advantage arises from the context-free nature of ourgrammar rules once a constituent has been discovered in a segment of the input wecan record its presence and make it available for use in any subsequent derivationthat might require it.