ParsingWhat is Parsing?Slide 3Programming languagesNatural languagesAmbiguitySlide 7The parsing problemApplications of parsing (1/2)Applications of parsing (2/2)Parsing for InterpretationParsing  Compositional SemanticsSlide 13Slide 14Slide 15“Papa ate the caviar with a spoon”First try … does it work?Second try …Third try …Slide 20Follow backpointers to get the parseTurn sideways: See the trees?Correct but still inefficient …Slide 24Slide 25Slide 26Slide 27Slide 28CKY algorithm, recognizer versionSlide 30Loose ends to tie up (no slides)Slide 32Alternative version of inner loopsExtensions to discuss (no slides)Chart Parsing in DynaUnderstanding the Key RuleSlide 37Slide 38Discovered phrases & their relationships (“parse forest”) when parsing the ambiguous sentence “Time flies like an arrow”Slide 41Procedural algorithms like CKY are just strategies for running this declarative programParsingWhat is Parsing?S  NP VPNP  Det NNP  NP PPVP  V NPVP  VP PPPP  P NPNP  PapaN  caviarN  spoonV  spoonV  ateP  withDet  theDet  aPapathecaviaraspoonate withSNPVPVPVNPDetNNPDetNPPPWhat is Parsing?S  NP VPNP  Det NNP  NP PPVP  V NPVP  VP PPPP  P NPNP  PapaN  caviarN  spoonV  spoonV  ateP  withDet  theDet  aSPapaNPVPVPVNPDetNthecaviarNPDetNaspoonatePPPwithProgramming languagesprintf ("/charset [%s", (re_opcode_t) *(p - 1) == charset_not ? "^" : "");assert (p + *p < pend);for (c = 0; c < 256; c++) if (c / 8 < *p && (p[1 + (c/8)] & (1 << (c % 8)))) { /* Are we starting a range? */ if (last + 1 == c && ! inrange) { putchar ('-'); inrange = 1; } /* Have we broken a range? */ else if (last + 1 != c && inrange) { putchar (last); inrange = 0; } if (! inrange) putchar (c); last = c; }Easy to parse.Designed that way!Natural languagesNo {} () [] to indicate scope & precedenceLots of overloading (arity varies)Grammar isn’t known in advance!Context-free grammar not best formalism printf "/charset %s", re_opcode_t *p - 1 == charset_not ? "^" : ""; assert p + *p < pend; for c = 0; c < 256; c++ if c / 8 < *p && p1 + c/8 & 1 << c % 8 Are we starting a range? if last + 1 == c && ! inrange putchar '-'; inrange = 1; Have we broken a range? else if last + 1 != c && inrange putchar last; inrange = 0; if ! inrange putchar c; last = c;AmbiguityS  NP VPNP  Det NNP  NP PPVP  V NPVP  VP PPPP  P NPNP  PapaN  caviarN  spoonV  spoonV  ateP  withDet  theDet  aSPapaNPVPVPVNPDetNthecaviarNPDetNaspoonatePPPwithAmbiguityS  NP VPNP  Det NNP  NP PPVP  V NPVP  VP PPPP  P NPNP  PapaN  caviarN  spoonV  spoonV  ateP  withDet  theDet  aSPapaNPVPNPVNPDetNthecaviarNPDetNaspoonatePPPwithThe parsing problemPARSERGrammarscorercorrect test treestestsentencesaccuracyRecent parsers quite accurate… good enough to help a range of NLP tasks!Applications of parsing (1/2)Machine translation (Alshawi 1996, Wu 1997, ...)English ChinesetreeoperationsSpeech synthesis from parses (Prevost 1996) The government plans to raise income tax. The government plans to raise income tax the imagination.Speech recognition using parsing (Chelba et al 1998) Put the file in the folder. Put the file and the folder.Warning: these slides are out of dateApplications of parsing (2/2)Grammar checking (Microsoft)Indexing for information retrieval (Woods 1997) ... washing a car with a hose ... vehicle maintenanceInformation extraction (Hobbs 1996)NY TimesarchiveDatabasequeryWarning: these slides are out of dateParsing for InterpretationMost linguistic properties are defined over trees.One needs to parse to see subtle distinctions. E.g.:Sara dislikes criticism of her. (her  Sara)Sara dislikes criticism of her by anyone. (her  Sara)Sara dislikes anyone’s criticism of her. (her = Sara or her  Sara)600.465 - Intro to NLP - J. Eisner 12Parsing  Compositional SemanticsWhat is meaning of 3+5*6?First parse it into 3+(5*6)+3*56EEFEEE3FN5N6N*+Preview of the next topic!600.465 - Intro to NLP - J. Eisner 13What is meaning of 3+5*6?First parse it into 3+(5*6)Now give a meaning toeach node in the tree(bottom-up)+3*56EEFEEE3FN5N6N*+35 6303335 63033addmultParsing  Compositional SemanticsPreview of the next topic!600.465 - Intro to NLP - J. Eisner 14NPLauraVstemloveVPstemVPinfTtoSinfNPGeorgeVPstemVstemwantVPfinT-sSfinNPNnationDetEveryROOTPunc.Ga ay x e act(e,loving), lover(e,x), lovee(e,y)Ly x e act(e,wanting), wanter(e,x), wantee(e,y)v x e present(e),v(x)(e)every nations assert(s)assert(every(nation, x e present(e), act(e,wanting), wanter(e,x), wantee(e, e’ act(e’,loving), lover(e’,G), lovee(e’,L))))Parsing  Compositional SemanticsPreview of the next topic!Now let’s develop some parsing algorithms!What substrings of this sentence are NPs?Which substrings could be NPs in the right context?Which substrings could be other types of phrases?How would you defend a substring on your list?are unpopular0 1 2 3 4 5 6 7 8 9The government plans to raise income tax“Papa ate the caviar with a spoon”S  NP VPNP  Det NNP  NP PPVP  V NPVP  VP PPPP  P NPNP  PapaN  caviarN  spoonV  spoonV  ateP  withDet  theDet  a0 1 2 3 4 5 6 7First try … does it work? for each constituent on the LIST (Y I Mid)scan the LIST for an adjacent constituent (Z Mid J)if grammar has a rule to combine them (X  Y Z)then add the result to the LIST (X I J)“Papa ate the caviar with a spoon”0 1 2 3 4 5 6 7Second try …initialize the list with parts-of-speech (T J-1 J) where T is a preterminal tag (like Noun) for the Jth wordfor each constituent on the LIST (Y I Mid)scan the LIST for an adjacent constituent (Z Mid J)if grammar has a rule to combine them (X  Y Z)then add the result to the LIST (X I J)if the above loop added anything, do it again! (so that X I J gets a chance to combine or be combined with)“Papa ate the caviar with a spoon”0 1 2 3 4 5 6 7Third try …initialize the list with parts-of-speech (T J-1 J) where T is a preterminal tag (like Noun) for the Jth wordfor each constituent on the LIST (Y I Mid)for