6.863J/9.611J Natural language & computers Competitive Grammar Writing (CGW) Professor Robert C. Berwick [email protected] to the Competitive Grammar Writing Exercise! Timeline: • Mon/Tues: We will form random teams of ~2–3 people & email you the list of your team members; CGW handout • Weds, 2/9: Come to class w/ laptop (1/team), use Athena tools to write grammars, after more intro to the competition • Weds-Friday, 2/9-2/11: Read handout cgw.pdf & do the Checkpoint Exercise DUE MIDNIGHT FRI • Monday, 2/14: Come to class w/ laptop (1/team), use Athena tools to write grammars • Weds, 2/16: Grammar development frozen; generate test data set via grammaticality judgments • Tuesday, 2/22: Evaluation & prizes awarded1. Okay, team, please log in • You should use a laptop • Log into Athena (see instructions in cgw.pdf) • Your secret team directory – will be emailed to you cd …/teams/03-turbulent-kiwi • You can all edit files there • Publicly readable & writeable • No one else knows the secret directory name Minimizes permissions fuss2. Now Write a Grammar of English • You have 2 hours. J • What does that mean????3. Now write a grammar of English What’s a grammar? • 1 S1 → NP VP . • 1 VP → VerbT NP • 20 NP→ Det N' • 1 NP → Proper • 20 N' → Noun • 1 N' → N' PP • 1 PP → Prep NP Here’s one to start with. • You have 2 hours. J (actually, more) Terminology: Context-free grammar, Probabilistic Context-free Grammar (PCFG), Derivation rules, Nonterminals, Preterminals, POS tags, Generate a sentence3. Now write a grammar of English • 1 Noun → castle • 1 Noun → king … • 1 Proper → Arthur • 1 Proper → Guinevere … • 1 Det → a • 1 Det → every … • 1 VerbT → covers • 1 VerbT → rides … • 1 Misc → that • 1 Misc → bloodier • 1 Misc → does … Plus initial terminal rules. • 1 S1 → NP VP . • 1 VP → VerbT NP • 20 NP→ Det N' • 1 NP→ Proper • 20 N' → Noun • 1 N’ → N' PP • 1 PP → Prep NP Here’s one to start with. Any PCFG is okayUse ./randsent to test Any PCFG is okay But what is a “PCFG”? 3. Now write a grammar of English Here’s one to start with. S1 1 NP VP . • 1 S1 → NP VP . • 1 VP → VerbT NP • 20 NP →Det N' • 1 NP → Proper • 20 N' → Noun • 1 N' → N' PP • 1 PP → Prep NPSample a sentence on the blackboard Any PCFG is okay 3. Now write a grammar of English Here’s one to start with. S1 NP VP . Det N’ 20/21 1/21 • 1 S1 → NP VP . • 1 VP → VerbT NP • 20 NP → Det N' • 1 NP → Proper • 20 N' → Noun • 1 N’→ N' PP • 1 PP → Prep NPSample a sentence on the blackboard Arbitrary PCFG is okay 3. Now write a grammar of English Here’s one to start with. S1 NP VP . Det N’ Noun every castle drinks [[Arthur [across the [coconut in the castle]]] [above another chalice]] • 1 S1 → NP VP . • 1 VP → VerbT NP • 20 NP → Det N' • 1 NP → Proper • 20 N' → Noun • 1 N' → N' PP • 1 PP → Prep NPInitial part of speech (POS) tags given to you • Just 6 • Noun, Det, Prep, Proper, VerbT, Misc (noun, determiner, preposition, proper noun, transitive verb, miscellaneous) For instance: The file S1_Vocab.gr has some ‘suggestions’ for other POS categories…you may want to use these, or look at what other people have done, egPenn Treebank project POS tags 1. CC Coordinating conjunction 2. CD Cardinal number 3. DT Determiner 4. EX Existential there 5. FW Foreign word 6. IN Preposition or subordinating conjunction 7. JJ Adjective 8. JJR Adjective, comparative 9. JJS Adjective, superlative 10. LS List item marker 11. MD Modal 12. NN Noun, singular or mass 13. NNS Noun, plural 14. NP Proper noun, singular 15. NPS Proper noun, plural 16. PDT Predeterminer 17. POS Possessive ending 18. PP Personal pronoun 19. PP$ Possessive pronoun 20. RB Adverb 21. RBR Adverb, comparative 22. RBS Adverb, superlative 23. RP Particle 24. SYM Symbol 25. TO to 26. UH Interjection 27. VB Verb, base form 28. VBD Verb, past tense 29. VBG Verb, gerund or present participle 30. VBN Verb, past participle 31. VBP Verb, non-3rd person singular present 32. VBZ Verb, 3rd person singular present 33. WDT Wh-determiner 34. WP Wh-pronoun 35. WP$ Possessive wh-pronoun 36. WRB Wh-adverbInitial S1 grammar – very simple • Parses just 2 example sentences • Arthur is the king . • Arthur rides the horse near the castle . What about the rest???? We don’t want our parser just to fail (we will give you an infinite penalty for this, as we shall see), so…. We will use the backoff idea: if this grammar fails, we have a grammar S2 that never fails to parse a sentence (but it gives stupid parses)• S2 → _Verb • S2 → _Noun • S2 → _Misc • _Noun → Noun • _Noun → Noun _Noun • _Noun → Noun _Misc • _Misc → Misc • _Misc → Misc _Noun • _Misc → Misc _Misc (etc.) Use of a backoff grammar: fallback to parse anything Initial backoff grammar _Verb Verb _Misc Misc _Punc Punc _Noun Noun S2 i.e., something that starts with a Verb rides ‘s ! swallow i.e., something that starts with a Misc _Verb Verb _Misc Misc• S2 → _Verb • S2 → _Noun • S2 → _Misc • _Noun → Noun • _Noun → Noun _Noun • _Noun → Noun _Misc • _Misc → Misc • _Misc → Misc _Noun • _Misc → Misc _Misc (etc.) • S1 → NP VP . • VP → VerbT NP • NP → Det N’ • NP → Proper • N’ → Noun • N’ → N’ PP • PP → Prep NP Use of a backoff grammar Init. linguistic grammar Initial backoff grammar• S2 → _Verb • S2 → _Noun • S2 → _Misc • _Noun → Noun • _Noun → Noun _Noun • _Noun → Noun _Misc • _Misc → Misc • _Misc → Misc _Noun • _Misc → Misc _Misc (etc.) • S1 → NP VP . • VP → VerbT NP • NP → Det N’ • NP → Proper • N’ → Noun • N’ → N’ PP • PP → Prep NP Use of a backoff grammar Init. linguistic grammar Initial backoff grammar
View Full Document