$29
Assignment
Question 1: Grammar for French (60 points)
In this question, you will develop a context-free grammar for a fragment of French. Your grammar must account for various aspects of the French language, as listed below.
Basic sentence word order in the present
The basic word order in French is Subject-Verb-Object, as in English:
(1) Je regarde la television. I watch the television
(2) Le chat mange le poisson. The cat eats the sh
Subject-verb agreement
Just as in English, the subject must agree with the verb in number and person:
(3) Tu regardes la television. You(2Sg) watch the television
(4) Il regarde la television. He watches the television
(5) Nous regardons la television. We watch the television
(6) Vous regardez la television. You(2Pl) watch the television
(7) Ils regardent la television. They(Masc.) watch the television
Look up the list of subject pronouns in French, as well as the verb conjugation paradigm for several common verbs using an online website. Include these in your grammar.
Reference: http://www.wordreference.com/conj/FrVerbs.aspx
1
Negation
Basic verb negation is handled in French by surrounding the verb with the particles ne ... pas.
(8) Tu ne regardes pas la television. You(2Sg) do not watch the television
(9) Le chat ne mange pas le poisson. The cat does not eat the sh
De nite noun phrases and proper names
A de nite noun phrase in French follows a similar order as in English (article + noun). However, the article must agree with the noun in number and grammatical gender. Grammatical gender is a more-or-less arbitrary categorization of nouns into either masculine or feminine.
Examples:
(10) Le chat the(Masc.) cat
(11) La television the(Fem.) television
(12) Les chats the(Pl.) cats
(13) Les televisions the(Pl) televisions
As you can see, there is no distinction in the plural between masculine or feminine.
Some proper names in French do not take articles, just as in English:
(14) Jonathan Jonathan
(15) Montreal Montreal
Others do (e.g., le Canada), which you have to handle:
(16) le Canada Canada
You can look up examples of proper nouns which need an article. e.g. https://language-easy.org/ french/grammar/nouns/proper-nouns/
Direct object pronouns
When a pronoun is a direct object of the verb, they precede the verb:
(17) Il la regarde.
He it(Fem.) watches.
Look up the list of direct object pronouns in French, and enhance your grammar to account for the word order with direct objects. https://grammar.collinsdictionary.com/french-easy-learning/ personal-pronouns-direct-object
Attributive adjectives
Adjectives typically follow the noun that they modify in a noun phrase:
Page 2
(18) Le chat noir the(Masc.) cat black
(19) Le chat heureux the(Masc.) cat happy
However, other adjectives precede the noun:
(20) Le beau chat the(Masc.) beautiful cat
(21) Le joli chat the(Masc.) pretty cat
Yet others may precede OR follow the noun, though the meaning usually changes slightly:
(22) La derniere semaine the(Fem.) last week
the last week (e.g., of the year)
(23) La semaine derniere the(Fem.) week last
last week (i.e., the one before this week)
In addition, adjectives must agree with the noun that they modify in number and gender:
(24) Les chats noirs the(Pl.) cats black(Pl.) the black cats
(25) La television noire
the(Fem.) television black(Fem.) the black television
(26) Les televisions noires
the(Pl.) televisions black(Fem. Pl.) the black televisions
Note that adjectives do distinguish masculine from feminine in the plural.
Find several adjectives of each of the three classes above, and incorporate them into your grammar.
References
http://french.about.com/od/grammar/a/adjectives.htm
http://french.about.com/od/grammar/a/adjectives_4.htm
Examples and submission format
You already have many examples that your grammar should accept (though many of the above examples were only noun phrases, not full sentences). Here are some sentences that your grammar should reject:
(27) *Je mangent le poisson.
(28) *Les noirs chats mangent le poisson.
(29) *La poisson mangent les chats.
(30) *Je mange les.
Use the following nonterminals to indicate grammatical categories:
• sentence/clause
NP noun phrase
Page 3
VP verb phrase
• noun
PN proper noun
PR pronoun
• verb
DT determiner
• adjective
You may add further non-terminal categories or subdivide them (e.g., V-1Sing) as needed. Don’t forget the lexical rules! Include enough lexical items such that each of the syntactic categories can be expressed in at least three di erent ways.
Write your grammar in a text editor using a predictable, computer-readable format. In particular, you must use a format that is compatible with NLTK’s CFG.fromstring function. For instance, here is one possible rule:
S->NPVP
Here is another example of a set of four rules (here, they are lexical rules):
V-1Sg -> ’mange’ | ’aime’ | ’regarde’ | ’cherche’
These are just examples, and are not necessarily the rules you want in your grammar! Ignore punctuation and capitalization in your grammar (just use all lower-case, except for proper names). French has contractions in many cases where a word begins with a vowel (e.g., j’aime rather than *je aime). You may ignore such issues.
Submit your grammar as a plaintext .txt le. Show instances where your grammar correctly accepts and rejects some sentence. In addition, show at least one case of overgeneration and one case of undergenera-tion in your grammar. (Hint: if you don’t speak French, ask Google Translate or a friend for help! Also, many French grammar sites will give examples of mistakes.) In addition, answer the following questions in your response to the question:
1. What are some advantages of modelling French grammar with a CFG?
2. What are some disadvantages of modelling French grammar with a CFG?
3. What are some aspects of French grammar that your CFG does not handle?
This question is rather open-ended; your grammar will be judged on the following points:
Whether you followed the speci cations above (e.g. names of non-terminals, minimum number of lexical entries)
Coverage of the required grammatical constructions
• Clarity of the grammar
The responses to the questions above
You won’t get extra points for having many additional lexical items that exhibit the same type of behaviour!
Question 2: Implement CYK for your grammar (40 points)
Implement your own version of the CYK algorithm. Your code should de ne a class which represents a CYK parser. Your parser’s constructor must take in a CFG grammar that is an instance of NLTK’s CFG class. It must include a .parse() method that is able to take in sentences as a string with tokens separated by whitespace and run the CYK algorithm on it. The output of the method should be a list of all the possible trees of the sentence, which are instances of nltk.tree.Tree. This list may be empty if the sentence is not accepted by the CFG.
Run your parser on several sentences from your grammar from Q1, showing sentences that are accepted and sentences that are rejected by your grammar. Include these in the written portion of your submission.
Page 4
Notes:
You will also have to write code that converts your grammar to/from Chomsky Normal Form yourself.
Be sure the nal output parse is not in the CNF-version of the CFG!
You can use any other parser or method from NLTK to check your work, but you must write your
• own implementation of the CYK algorithm.
You may want to do Question 2 rst before Question 1, as having a parser will be useful for checking your work!
What To Submit
Your submission must be made through MyCourses, and must consist of the following three les:
1. The grammar le of Question 1, as a plaintext .txt le called ‘french-grammar.txt’.
2. Your code for Question 2, ‘a2-cyk.py’.
3. The written portions for both questions as a .pdf le called ‘a2-written.pdf’.
Page 5