Lecture 9: Grammars & features;lexicalized parsing; treebanksProfessor Robert C. [email protected] Menu Bar• Administrivia: Lab 3 due Friday; Lab 4 out today• Why context-free grammars are no good: representationand computational issues• Slash & Burn grammar: mind the gap!• Featuritis!• What’s the matter with Probabilistic context-free kansas?• How to fix – a bit – with lexicalized context-freegrammars; treebank parsingThe Menu Bar• Why context-free grammars are no good: representationand computational issues• Slash & Burn grammar: mind the gap• Featuritis!• WHY do we choose certain rules and not others?• What’s the matter with Probabilistic context-free kansas?• How to fix – a bit – with lexicalized context-freegrammars; treebank parsing‘Empty’ elements or categoriesVery often, a phrase is displaced from its canonical syntacticposition & nothing shows on the surface:• Examples:The ice-cream was eaten vs.John ate the ice-creamWhat did John eat?What did Bill say that that John thought the cat ate?(= For What x, did Bill say… the cat ate x)Quadaffi is too stubborn to talk to =Quadaffi is too stubborn [x to talk to Quadaffi]Quadaffi is too stubborn to talk to the Pope =Quadaffi is too stubborn [Quadaffi to talk to the Pope]‘Missing’ or “empty” categories• Quadaffi promised Obama ___ to leave• Quadaffi promised Obama [Quadaffi to leave]• Known as ‘control’• Obama persuaded Quadaffi [___ to leave]• Obama persuaded Quadaffi [Quadaffi to leave]Representation & computation questionsagain• How do we represent this displacement? (differencebetween underlying & surface forms)• How do we compute it? (I.e., parse sentences thatexhibit it)• We want to recover the underlying structuralrelationship because this tells us what the predicate-argument relations are – Who did what to whom• Example: What did John eat → For which x, x a thing,did John eat x?• Note how the eat-x predicate-argument is establishedRepresentations with gaps• Let’s first look at a tree with gaps:whatdid SVVPNPSεgap orempty elementfillerSlightly crisper representationfillergapFillers can be arbitrarily far from gapsthey match with…• What did John say that Mary thought that the cat ate___?In short, many types of similarexamples…• Wh-questions:What did you findTell me who you talked to• Topicalization:This manual, I can’t findMorris, you should talk to• Easy adjectives:No Stata office is easy to findThis guy is hard to talk toThis problem everyone thought was too easyBut there are constraints on being ‘toofar’ away…• ?John seems it is certain [ _x_ to like ice-cream]• Which man did you ask whether I saw __at the park?Fillers and gaps• Since ‘gap’ is NP going to empty string, we couldjust add rule, NP→ε• But this will overgenerate Why?• We need a way to distinguish between:• What did John eat• Did John eatSo, what do we need?• A rule to expand NP as the empty symbol; that’seasy enough: NP→ε• A way to make sure that NP is expanded as emptysymbol iff there is a gap (in the right place)before/after it• A way to link the filler and the gap• We can do all this by futzing with the nonterminalnames: Generalized Phrase Structure Grammar (GPSG)(more recently known as: Head-driven Phrase structuregrammar, or HPSG)Example: relative clauses• What are they?• Noun phrase with a sentence embedded in it:• The pretzel that Obama ate• What about it? What’s the syntactic representation that willmake the semantics transparent?The pretzeli that Obama ate εiOK, that’s the output…what arethe context-free grammar rules?• Need to expand the object of eat as an emptystring• So, need rule NP→ε• But more, we need to link the head noun “thepretzel” to this positionParse structure for relative clauseBut how to generate this and yet block this:Not OK!In short..• We can expand out to ε iff there is a prior NP wewant to link to• So, we need some way of ‘marking’ this in thestate – i.e., the nonterminal• Further, we have to somehow co-index ε and ‘thesandwich’• Well: let’s use a mark, say, “+”The mark…But we can add + except this way:• Add as part of atomic nonterminal name• Before: NP→ NP CP CP → Comp S IP → NP VP VP → VP NP• After: NP → NP CP+ CP+ → Comp S+ IP+ → NP VP+ VP+ → V NP+ NP+ → εWhy does this work?• Has desired effect of blocking ‘the pretzel thatBush ate the sandwich’• Has desired effect of allowing ε exactly whenthere is no other object• Has desired effect of ‘linking’ pretzel to the object(how?)• Also: desired configuration between filler and gap(what is this?)Actual ‘marks’ in the literature• Called a ‘slash category’• Ordinary category: CP, VP, NP• Slash category: CP/NP, VP/NP, NP/NP• “X/Y” is ONE atomic nonterminal name• Interpret as: Subtree X is missing a Y (expandedas ε) underneath• Example: CP/NP = CP missing NP underneath(see our example)As for slash rules…• We need slash category introduction rule, e.g.,CP → Comp IP/NP• We need ‘elimination’ rule NP/NP→ ε• These are paired (why?)• We’ll need other slash categories, e.g.,Need PP/NP…Can also have ‘subject’ gapsAlso needed for questionsHow would we write this if we wereGerry Sussman?Filler-gap configurationNPεSSεNPFiller-gap configurationIs equivalent to the notion of ‘scope’ for naturallanguages (scope of variables) ≈ Environmentframe in Scheme/binding environment for‘variables’ that are empty categories• Formally: Fillers c-command gaps (constituentcommand)• Definition of c-command:C-command• A phrase α c-commands a phrase β iff the firstbranching node that dominates α also dominates β(blue = filler, green = gap)• We will see this is critical for semantics! (as inScheme)YesYesYesNoNoNatural for λ abstractionCPdid Obama eat whatwhatSCPObama eat xλxA Puzzle• Who saw Palin?McCainWhat should the structure of the first sentence be?Idea 1: WYSIG syntaxIs this right?Why might it not be correct?Idea 2: make syntax same as with‘ordinary’ questionsWhat are the benefits of this approach?TO WHICH CITY AND WHICH CONFERENCE DID BILL GO TOWHICH CITY AND TO WHICH CONFERENCE DID BILL GO TOWHICH CITY AND WHICH CONFERENCE DID BILL GO TO TOWHICH CITY AND WHICH CONFERENCE DID BILL GO TOTO WHICH CITY AND WHICH CONFERENCE DID BILL GOTO WHICH CITY AND TO
View Full Document
Unlocking...