CMSC 723 / LING 645: Intro to Computational LinguisticsWhat Issues Arise in Creating Grammars?AgreementSlide 4Agreement Features Propagate Downard …What’s wrong with this picture?SubcategorizationSentential complementsOther VP ConstituentsWhy do we need Subcategorization?Slide 11AuxiliariesMovementGrammar Equivalence and Normal FormCNF ExampleWhy do care about grammar?What Linguistic Representations are necessary for parsing?Analyzing Language in Terms of these RepresentationsSyntactic ParsingCFG for Fragment of English: G0Parse Tree for ‘Book that flight’ using G0Parsing as a Search ProblemTwo Search StrategiesTop-Down ParserTop-Down Search Space for G0Bottom-Up ParsingExpanding Bottom-Up Search Space for ‘Book that flight’Comparing Top-Down and Bottom-UpSearch Strategy and Search ControlBasic Algorithm for Top-Down, Depth-First, Left-Right StrategyBasic Top-Down ParserTop-Down Depth-First Derivation Using G0Example: Does this flight include a meal?Example continued …Augmenting Top-Down Parsing with Bottom-Up FilteringLeft CornersPowerPoint PresentationSumming Up Parsing StrategiesThree Critical Problems in ParsingLeft RecursionSolutions to Left RecursionRule OrderingGrammar RewritingProblems with Grammar RewritingDepth BoundAmbiguityMore Ambiguity ExamplesTwo Parse Trees for Ambiguous SentenceMore Ambiguity: ‘Can you book TWA flights?’A Correct Parse for ‘Show me the meal on Flight UA 386 from San Francisco to Denver’Inefficient Re-Parsing of SubtreesInvariantsWhat’s the solution?Dynamic ProgrammingEarley AlgorithmChart EntriesProgress in parse represented by Dotted Rules0 Book 1 that 2 flight 30 Book 1 that 2 flight 3 (continued)Successful ParseParsing Procedure for the Earley AlgorithmStates and State SetsEarley Algorithm from BookEarley Algorithm (simpler!)3 Main Sub-Routines of Earley AlgorithmPredictorScannerCompleterSlide 69Example: State Set S1 for Parsing “Book that flight”Prediction of Next RuleLast Two StatesHow do we retrieve the parses at the end?Error HandlingEarley’s Keys to EfficiencyNext TimeCMSC 723 / LING 645: Intro to Computational LinguisticsNovember 10, 2004Lecture 10 (Dorr):CFG’s (Finish Chapter 9)Parsing (Chapter 10)Prof. Bonnie J. DorrDr. Christof MonzTA: Adam LeeWhat Issues Arise in Creating Grammars?AgreementSubcategorizationMovementAgreementSimple Examples:–This dog–Those dogs–*Those dog–*This dogs More complicated examples:–Do any flights stop in Chicago?–Does Delta fly from Atlanta to Boston?–Do I get dinner on this flight?–What flights leave in the morning?–* What flight leave in the morning?AgreementNouns: Nominal → Noun | Noun Noun–NominalSg → NounSg | NounSg NounSg–NominalPl → NounPl | NounPl NounPlSubj-Verb Agreement: S → Aux NP VP–S → Aux3sg NP3sg VP–S →Auxnon3sg NPnon3sg VPLexical items:–NounSg → flight–NounPl → flights–Aux3sg → does | has | can …–Auxnon3sg → do | have | can …Agreement Features Propagate Downard …NP3sg → (Det) (Card) (Ord) (Quant) (AP) NominalSgNPnon3sg → (Det) (Card) (Ord) (Quant) (AP) NominalPlWhat’s wrong with this picture?Combinatorial explosionOther feature-based expansions?Loss of GeneralizationSubcategorizationVerbs have preferences for the kinds of constituents they co-occur withFor example:–VP → Verb (disappear)–VP → Verb NP (prefer a morning flight)–VP → Verb NP PP (leave Boston in the morning)–VP → Verb PP (leaving on Thursday)But not: *I disappeared the cat.Sentential complementsExample: –You [VP [V said [S there were two flights that were the cheapest]]]–You [VP [ V said [S you had a two hundred sixty six dollar fare]]]–[VP [ V Tell][NP me ] [S how to get from the airport in Philadelphia to downtown]]Rule:–VP → Verb SOther VP ConstituentsA VP can be the constituent of another VP:VP → Verb VP–I want [VP to fly from Milwaukee to Orlando]–I’m trying [VP to find a flight that goes from Pittsburgh to Denver next Friday]Verbs can also be followed by particles to form a phrasal verb: VP → Verb Particle–take offWhy do we need Subcategorization?Important observation: while a verb phrase can have many possible kinds of constituents, not every verb is compatible with every verb phraseExample: verb want can be used –With a NP complement: I want a flight–With an infinitive VP complement: I want to fly to DallasBut verb find cannot take such a VP complement–*I find to fly to DallasSubcategorizationFrame Verb ExampleØ eat, sleep, … I want to eatNP prefer, find, leave, ... Find [NP the flight from Pittsburgh to Boston]NP NP show, give, … Show [NP me] [NP airlines with flights from Pittsburgh]PPfrom PPto fly, travel, … I would like to fly [pp from Boston] [pp to Philadelphia]NP PPwith help, load, … Can you help [NP me] [pp with a flight]VPto prefer, want, need, … I would prefer [VPto to go by United airlines]VPbrst can, would, might, … I can [VPbrst go from Boston]S mean Does this mean [S AA has a hub in Boston]?AuxiliariesExamples:–Modals: can, could, may, might–Perfect: have–Progressive: be–Passive: beWhat are their subcategories?Ordering: modal < perfect < progressive < passivee.g, might have been preventedMovementI looked up his grade.I looked his grade up.John put the book on the table.What did John put on the table?Long distance dependencies.Grammar Equivalence and Normal FormWeak equivalenceStrong equivalenceChomsky Normal Form (CNF)A → B C or A → aCNF ExampleConvert to Chomsky-Normal Form (CNF):S → a Y X X → a X | b Y → Y a | bWhy do care about grammar?We need grammars for parsing!Note: Parsing is the topic we will cover next.What Linguistic Representations are necessary for parsing?Words–Classes: groups of words which behave similarly–Function/Content–P.O.S.: Nouns, Verbs, Adjectives, PrepositionsConstituents: –Groupings of words into larger units which behavior similarly and have a particular p.o.s. as their head–Phrases: NP headed by Noun... VP, PP, ...Analyzing Language in Terms of these RepresentationsMorphological parsing: –analyze words into morphemes and affixes–rule-based, FSAs, FSTsPOS TaggingSyntactic parsing:–identify component parts and how related–to see if a sentence is grammatical–to assign a semantic structureSyntactic ParsingDeclarative formalisms