History of Grammar FormalismsWhat is a Grammar Formalism? From Formal Language TheorySlide 3What is a grammar formalism? Production RulesWhat is a grammar formalism? DerivationSlide 6ReferenceWhat does a grammar formalism look like?What is a Grammar Formalism for?StructureThis grammar makes wrong structuresSlide 12Slide 13History of Grammar Formalisms Late 19th to Early 20th centuriesSlide 15Slide 16ReferencesNoam Chomsky 1928 –Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Affix HoppingSlide 26Slide 27AnecdotesHistory of Grammar Formalisms Transformation Grammar in the 1960’s and 1970’sSlide 30No more about ChomskyMontague Grammar Syntax and Formal SemanticsHistory of Grammar Formalisms Some events in computational linguisticsSlide 34Slide 35Slide 36Functional Structure Martin KayUnification: Combining information in feature structuresThat leads to Grammar Formalisms as we know them todayLexical Functional Grammar (around 1978)Lexical Functional GrammarLocal co-description of partial structuresLevels of RepresentationUnification Based FormalismsThe Tomita ParserGeneralized Phrase Structure Grammar (GPSG) Precursor to HPSGSlide 47The nature of syntactic categories: GPSG and HPSGGPSG and HPSGHead Driven Phrase Structure GrammarHPSG: Things not handled well by context free grammarsHPSG Principles/Rule SchemataCategorial GrammarCategorial Grammar ExampleTree Adjoining GrammarTAGs: Elementary TreesSummaryGrammar formalisms and other topics not covered in this class (Can be used for term projects)History of Grammar FormalismsGrammar Formalisms: 11-722Spring Term, 2004Lori LevinWhat is a Grammar Formalism?From Formal Language Theory•A language–A language L is a possibly infinite set of strings.–The strings are made from a finite alphabet. •The “alphabet” might be the words of English•Henceforth, we will call it the “vocabulary”–Some strings of language L:•Bears live in the forest.•Never have I seen such ridiculous beasts.–Some strings are not in L:•*Never I have seen such ridiculous beasts.•*Live bears the in forest.•(* means that the string is not a member of the set of strings that comprise the language L.)What is a Grammar Formalism?From Formal Language Theory•A Grammar:–A set of production rules.–In addition to the vocabulary, the production rules can use other symbols•N (noun)•V (verb)•NP (noun phrase)•VP (verb phrase)–One symbol is special:•S (sentence)What is a grammar formalism?Production Rules•S → NP VP•NP → Det N•VP → V NP•DET → the•DET → a•N → boy•N → girl•V → saw•V → seesThese production rules have a non-terminal symbol (one that isn’t from the vocabuary) on the left, then an arrow, then some terminal (from the vocabulary) and non-terminal symbols on the right.This is one instance of a grammar formalism.We will see that other grammar formalisms use other types of symbols and production rules.What is a grammar formalism?Derivation•The production rules are interpreted as instructions:–Parsing: when you find the string on the right hand side, replace it with the string on the left hand side.–Generation: when you find the symbol on the left hand side, replace it with the string on the right hand side.–Different grammar formalisms will have different instructions.•Your job:–Generation: get from the special symbol S to a terminal string (only symbols from the vocabulary).–Parsing: get from a terminal string to the special symbol SWhat is a grammar formalism?Derivation•A derivation is the ordered list of production rules that you use to get from the special symbol to the terminal string or vice versa.•S•NP VP•Det N VP•Det N V NP•Det N V Det N•The N V Det N•The girl V Det N•The girl sees Det N•The girl sees a N•The girl sees a boyS → NP VPNP → Det NVP → V NPDET → theDET → aN → boyN → girlV → sawV → seesReference•Hopcroft, Motwani, and Ullman, Introduction to Automata Theory, Languages, and Computation, second edition, Addison-Wesley, 2001.–Chapter 5.2What does a grammar formalism look like?•Context Free Phrase Structure Grammar:S → NP VP•Lexical Functional Grammar:S → NP VP (↑ SUBJ)=↓ ↑=↓ •Tree Adjoining Grammar•Categorial GrammarX → X/Y Y(an X consists of an X missing a Y and a Y.) X YWhat is a Grammar Formalism for?•Distinguish strings that are in the language from those that are not in the language.–The girl sees a boy.–*Girl the the.•No derivation exists using the grammar rules.•Identify a structure for the sentence.Structure•S•NP VP•Det N VP•Det N V NP•Det N V Det N•The N V Det N•The girl V Det N•The girl sees Det N•The girl sees a N•The girl sees a boy S NP VPDET N V NP Det NA girl sees a boyThis grammar makes wrong structures•S → NP VP N•NP → Det •VP → N V Det•DET → the•DET → a•N → boy•N → girl•V → saw•V → sees S NP VP N Det N V Det the girl sees a boyHistory of Grammar Formalisms•500 B.C. –Pānini’s grammar of Sanskrit, Astadhyayi, contains production rules (!!!) for Sanskrit phonology, morphology, and grammar.–This is a lasting work of genius, still studied today, and remarkably similar to some modern linguistic theories.•7th to 8th centuries A.D. –Classical Arabic Grammarians define Classical Arabic.•19th century Europe–No production rules. They spend all their time on historical and comparative linguistics – finding genetic relationships among languages: –The Grimm brothers collect fairy tales, but are actually working on systematic sound correspondences between branches of Indo-European:•p-f: père – father; pied – foot; etc.History of Grammar FormalismsLate 19th to Early 20th centuries•Ferdinand de Saussure–Ferdinand de Saussure starts out as a historical linguist, and then comes back to the present.•Distinguishes synchronic linguistics from diachronic linguistics–Linguistics gets mental:•Signifier and signified: –The signifier is a word, like “tree”. The signified is not a tree, but a concept of a tree.•Langue (language) and Parole (speech)–http://www.press.jhu.edu/books/hopkins_guide_to_literary_theory/ferdinand_de_saussure.html“… he distinguishes between the particular occurrences of language – its particular