2/14/2011 CSE842, Spring 2011, MSU 1CSE 842Natural Language ProcessingLecture 9: CFG and Parsing 2/14/2011 CSE842, Spring 2011, MSU 2Announcement• Homework 2 will be assigned after the class. – Contain both written and programming part– Due: March 22/14/2011 CSE842, Spring 2011, MSU 3What is Grammar• A vogue in the 19thcentury to describe the structures of an area of knowledge(e.g., Busby’s “ A Grammar of Music”Field’s “A Grammar of Colouring”)• The meaning of grammar:– principles or structures as a field of inquiry– The grammar of syntax• Syntax: setting out together or arrangement; the way words are arranged. 2/14/2011 CSE842, Spring 2011, MSU 4Syntax• Covered: POS categories• To be covered:– Constituency– Grammatical relations– Subcategorization and dependencies2/14/2011 CSE842, Spring 2011, MSU 5What is a constituent?• The idea: groups of words may behave as a single unit or phrase -> constituent• Example: noun phrase act like a unit– “Michigan State University”– “the campus”– “well-weathered three-story structure”• How can we model the constituency?– With context-free grammars2/14/2011 CSE842, Spring 2011, MSU 6Context-Free Grammars• Chomsky (1956) Backus (1959)• Set of rules (productions) – expressing the way symbols of the language can be grouped together– NP -> Det Nominal – NP -> Proper Noun– Nominal -> Noun | Noun Nominal• Lexicon –Det-> a–Det-> the– Noun -> flight2/14/2011 CSE842, Spring 2011, MSU 7Context Free Grammars• Capture constituents and ordering– Need something else for grammatical relations and dependency relations• Consists of– Set of terminals (words)– Set of non-terminal (the constituent of language)– Sets of rules of the form A->α, where α is a string of zero or more terminals and non-terminals• They are equivalent to Backus-Naur form grammars2/14/2011 CSE842, Spring 2011, MSU 8Formal Definition of CFG• Set of non-terminal symbols N• Set of terminals Σ• Set of productions A -> αA ∈N, α-string (Σ∪N)*• A designated start symbol2/14/2011 CSE842, Spring 2011, MSU 9Some NP Rules• Here are some rules for our noun phrases• Together, these describe two kinds of NPs.– One that consists of a determiner followed by a nominal– And another that says that proper names are NPs.– The third rule illustrates two things• An explicit disjunction– Two kinds of nominals• A recursive definition– Same non-terminal on the right and left-side of the rule2/14/2011 CSE842, Spring 2011, MSU 10L0 Grammar2/14/2011 CSE842, Spring 2011, MSU 11Generativity• As with FSAs and FSTs, you can view these rules as either analysis or synthesis machines– Generate strings in the language– Reject strings not in the language– Impose structures (trees) on strings in the language2/14/2011 CSE842, Spring 2011, MSU 12Derivations• A derivation is a sequence of rules applied to a string that accounts for that string– Covers all the elements in the string– Covers only the elements in the string2/14/2011 CSE842, Spring 2011, MSU 13Key Constituents•Sentences• Noun phrases• Verb phrases• Prepositional phrases2/14/2011 CSE842, Spring 2011, MSU 14Sentence Types• DeclarativesS –> NP VP (e.g., John left)• ImperativesS -> VP (e.g., Leave!)• Yes-No QuestionsS -> Aux NP VP (e.g., Did John leave?)• WH QuestionsS -> Wh-NP VP (e.g., Whose flights serve breakfast?)S -> Wh–NP Aux NP VP (e.g., Which flight did you take? )2/14/2011 CSE842, Spring 2011, MSU 15Noun Phrases• Let’s consider the following rule in more detail...NP →Det Nominal• Most of the complexity of English noun phrases is hidden in this rule.• Consider the derivation for the following example– All the morning flights from Denver to Tampa leaving before 102/14/2011 CSE842, Spring 2011, MSU 16Noun Phrases2/14/2011 CSE842, Spring 2011, MSU 17NP Structure• Clearly this NP is really about flights. That’s the central critical noun in this NP. Let’s call that the head.• We can dissect this kind of NP into the part that comes before the head, and the part that comes after it.2/14/2011 CSE842, Spring 2011, MSU 18Determiners• Noun phrases can start with determiners...• Determiners can be– Simple lexical items: the, this, a, an, etc.• A car – Or simple possessives• John’s car– Or complex recursive versions of that• John’s sister’s husband’s son’s car2/14/2011 CSE842, Spring 2011, MSU 19Nominals• Contains the head and any pre- and post-modifiers of the head.–Pre-• Quantifiers, cardinals, ordinals...– Three cars• Adjectives and Aps– large cars• Ordering constraints– Three large cars– ?large three cars2/14/2011 CSE842, Spring 2011, MSU 20Postmodifiers• Three kinds– Prepositional phrases• From Seattle– Non-finite clauses (-ing, -ed, and infinitive form)• Arriving before noon– Relative clauses• That serve breakfast• Same general (recursive) rule to handle these• Nominal →Nominal PP• Nominal →Nominal GerundVP• Nominal →Nominal RelClause2/14/2011 CSE842, Spring 2011, MSU 21Gerunds• any flights [arriving after ten p.m]• Nominal Æ Nominal GerundVP• GerundVP Æ GerundV NP | GerundV PP | GerundV | GerundV NP PP• GerundV Æ being | preferring | arriving …2/14/2011 CSE842, Spring 2011, MSU 22Infinitives and –ed forms• the last flight to arrive in Boston• I need to have dinner served• which is the aircraft used by this flight?2/14/2011 CSE842, Spring 2011, MSU 23Postnominal relative clauses• Restrictive relative clauses:– A flight that serves breakfast– Flights that leave in the morning– The United flight that arrives in San Jose at ten p.m.• Rules:– Nominal Æ Nominal RelClause– RelClause Æ (who | that) VP2/14/2011 CSE842, Spring 2011, MSU 24Combining post-modifiers• A flight from Phoenix to Detroit leaving Monday evening• Evening flights from Nashville to Houston that serve dinner• The earliest American Airlines flight that I can get2/14/2011 CSE842, Spring 2011, MSU 25Recursive Structure• Rules where the non-terminal on the left-hand side also appears on the right-hand side. – NP Æ NP PP (The flight to Boston)– VP Æ VP PP (departed Miami at noon)2/14/2011 CSE842, Spring 2011, MSU 26Recursive Structure• Allow us to the following:– Flights to Miami– Flights to Miami from Boston– Flights to Miami from Boston in April– Flights to Miami from Boston in April on